Rabbits and Recurrence Relations

CombinatoricsDynamic Programming

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. Il problema introduce la tecnica della programmazione dinamica: costruire la soluzione per n a partire dalle soluzioni per valori più piccoli.

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

Nota

Nella cartella è presente anche "Rabbits and Recurrence Relations - 2": è lo stesso identico problema (FIB), non un problema diverso — il dataset.txt di quella cartella coincide esattamente con il Sample Dataset qui sopra ("5 3"), quindi è con ogni probabilità un doppione/tentativo di prova con il dataset di esempio, non un secondo problema ufficiale di Rosalind.

La mia esecuzione

08/24/2026 11:24:47

Input · dataset.txt

32 4

Output · run_log.txt

2863396842201

Esegui nel browser · Pyodide

Mostra il codice sorgente (problem.py)

stringa = ""
filename = "dataset.txt"
with open(filename) as f:
    riga = f.readline()
lista = riga.split(" ")
n, k = int(lista[0]), int(lista[1])
rabbits = [1, 0, 0]
for i in range(n-1):
    x = rabbits[0];
    y = rabbits[1];
    z = rabbits[2];
    rabbits[2] = z + y
    rabbits[1] = x
    rabbits[0] = k * (y+z)
print(rabbits[0]+rabbits[1]+rabbits[2])

Soluzione JavaScript

Esegui ora, live

Mostra il codice sorgente

// Rabbits and Recurrence Relations (slug: fib) - soluzione JavaScript
// indipendente, non una trascrizione di problem.py: stessa logica a
// macchina a stati (tre "età" di coppie: appena nate, di un mese, di
// due mesi o più - le adulte generano k nuove coppie ogni mese),
// riscritta in modo idiomatico per JS.
//
// BigInt per sicurezza: n può essere abbastanza grande da far superare
// a k^(n/2) il limite di Number.MAX_SAFE_INTEGER, stesso discorso già
// fatto per fibd.mjs/rabbits-and-recurrence-relations-2.mjs.
//
// 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 = Number(parti[0]);
  const k = BigInt(parti[1]);

  let rabbits = [1n, 0n, 0n];
  for (let i = 0; i < n - 1; i++) {
    const [x, y, z] = rabbits;
    rabbits = [k * (y + z), x, z + y];
  }

  return `${rabbits[0] + rabbits[1] + rabbits[2]}\n`;
}