Problem J
Kaninavl
Det biodynamiske kaninavl på Langgården har plads til millioner af kaniner. Disse formerer sig i hastig takt, og Rued er bekymret for bæredygtigheden. Kommer de mon til at løbe tør for plads inden for de næste $n$ måneder?
En matematisk model for reproduktion af kaniner, som Valborg kan huske fra sin studietid, går tilbage til tolvhundredetallet og hedder fibonaccifølgen. I modellen får hvert kaninpar efter to måneder selv et nyt kaninpar per måned. Et nyfødt januarpar, kald det A, vil altså begynde at få nye par fra og med marts. I tegningen forneden kaldes de nye par B (marts), C (i april) og D (i maj). Par B begynder selv at få kaniner (par E) i maj.
![\includegraphics[width=.5\textwidth ]{img/fib.jpg}](/problems/itu.kaninavl/file/statement/da/img-0002.jpg)
Det samlede antal kaninpar per måned udvikler sig altså som $1$, $1$, $2$, $3$, $5$, osv. Mere generelt kan man lade det $n$te fibonaccital $f_ n$ være antallet af kaninpar efter $n$ måneder. Så gælder $f_1=f_2=1$ og
\[ f_ n = f_{n-1} + f_{n-2}\qquad (n>2)\, . \]Indlæsning
Indlæsningen består af heltallet $n\geq 2$.
Udskrift
Skriv de $n$ første fibonaccital $f_1,\ldots , f_ n$ på hver sin linje.
Pointsætning
Der er $3$ testgrupper.
|
Gruppe $1$ |
$n\leq 20$ |
$f_ i\leq 10^5$ |
|
Gruppe $2$ |
$n\leq 46$ |
$f_ i\leq 2\cdot 10^{9}$ |
|
Gruppe $3$ |
$n\leq 1000$ |
$f_ i\leq 10^{203}$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
10 |
1 1 2 3 5 8 13 21 34 55 |
