Fibonačio seka

Pradinių duomenų failas:

fibo.in  

Rezultatų failas:

fibo.out  

Laiko apribojimas:

1 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

Fibonačio seka \(F_{n}\) apibrėžiama taip: \(F_{1}\) = \(F_{2}\) = 1, \(F_{n}\) = \(F_{n-1}\) + \(F_{n-2}\) (n > 2) (kiekvienas narys yra ankstesnių dviejų suma). Taigi šią seką sudaro skaičiai: 1, 1, 2, 3, 5, 8 ir t. t. Fibonačio sekos nariai dažnai vadinami tiesiog Fibonačio skaičiais.

Fibonačio seka pasižymi daugybe įdomių savybių, pavyzdžiui, dviejų gretimų narių santykis artėja prie auksinio skaičiaus. Nubrėžus n kvadratų, kurių kraštinių ilgiai yra Fibonačio skaičiai, bei sujungus šių kvadratų kampus, gaunama logaritminė spiralė (parodyta paveiksle). Negana to, Fibonačio skaičiai dažnai pasirodo ir gamtoje – daugelio gėlių žiedlapių skaičius yra Fibonačio skaičius.

Parašykite programą, kuri rastų k-tąjį Fibonačio skaičių \(F_{k}\).

Pradiniai duomenys

Pradinių duomenų failą sudaro ne daugiau negu šimtas eilučių. Kiekvienoje eilutėje įrašytas skaičius \(a_{i}\) (0 < \(a_{i}\) <= 90).

Rezultatai

Rezultatų failą turi sudaryti tiek pat skaičių, kiek buvo pradinių duomenų faile. Kiekvienam skaičiui \(a_{i}\) įrašykite \(a_{i}\)-tąjį Fibonačio skaičių \(F_{a_{i}}\).

Pavyzdys

1
3
6
31

1
2
8
1346269