Rabbits and Recurrence Relations - 2

CombinatoricsDynamic Programming

Nota importante

Questa cartella risolve esattamente lo stesso problema Rosalind (FIB) della cartella "Rabbits and Recurrence Relations". Il dataset.txt qui presente ("5 3") coincide con il Sample Dataset ufficiale del problema, quindi questa è verosimilmente una seconda copia / un tentativo di test con il dataset di esempio, non un problema Rosalind distinto.

Descrizione

Basato sul classico esercizio di Fibonacci sulla riproduzione dei conigli: si parte con una coppia di conigli neonati, che raggiungono l'età riproduttiva dopo un mese; ogni mese ogni coppia in età riproduttiva genera k nuove coppie di conigli (invece di una sola come nella sequenza di Fibonacci classica), e i conigli non muoiono mai.

Given

Due interi positivi n ≤ 40 e k ≤ 5.

Return

Il numero totale di coppie di conigli presenti dopo n mesi, partendo da 1 coppia, dove ogni coppia in età riproduttiva genera una cucciolata di k coppie (anziché 1 sola).

Sample Dataset

5 3

Sample Output

La mia esecuzione

08/24/2026 11:24:47

Input · dataset.txt

5 3

Output · run_log.txt

Esegui nel browser · Pyodide

Mostra il codice sorgente (problem.py)

def fibonacci(n, k):
    if n > 2:
       return fibonacci(n-1, k) + k * fibonacci(n-2, k)
    return 1   

def main():
    filename = "dataset.txt"
    with open(filename) as f:
        riga = f.readline()

    n, k = riga.split(" ")
    print(fibonacci(int(n), int(k)))

if __name__ == "__main__":
    main()

Soluzione JavaScript

Esegui ora, live

Mostra il codice sorgente

// Rabbits and Recurrence Relations - soluzione JavaScript indipendente,
// non una trascrizione di problem.py: stessa ricorrenza (ogni coppia
// adulta genera k nuove coppie ogni mese, F(n) = F(n-1) + k*F(n-2)),
// riscritta in modo idiomatico per JS (iterativa invece che ricorsiva,
// per evitare la ricorsione non ottimizzata dell'originale su n grandi).
//
// Contratto: riceve il contenuto testuale di dataset.txt, restituisce
// l'output testuale (stessa forma dell'output Python).
export default function solve(datasetText) {
  const prima_riga = datasetText.split("\n")[0].trim();
  const parti = prima_riga.split(/\s+/);

  if (parti.length !== 2 || parti.some((p) => !/^\d+$/.test(p))) {
    throw new Error(`Input non valido: attesi due interi "n k", ricevuto "${prima_riga}"`);
  }

  const [n, k] = parti.map(Number);

  if (n <= 2) return "1\n";

  let prev2 = 1n; // fibonacci(1, k)
  let prev1 = 1n; // fibonacci(2, k)
  const kBig = BigInt(k);
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + kBig * prev2;
    prev2 = prev1;
    prev1 = curr;
  }

  return `${prev1}\n`;
}