Fişierul intrare/ieşire: | fibonacci.in, fibonacci.out | Sursă | Cerc informatică Vianu |
Autor | Din Folclor | Adăugată de | |
Timp execuţie pe test | 2.5 sec | Limită de memorie | 2048 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Fibonacci (clasa a 7-a)
Notă: acesta este un exerciţiu introductiv în recursivitate. Pentru a avea sens respectaţi cerinţa întocmai, rezolvîndu-l cu o funcţie recursivă. Dacă scrieţi corect funcţia ea nu trebuie să conţină instrucţiuni de ciclare, gen for, while sau do ... while.
Se citeşte un număr n mai mic decît 100 000 000. Să se calculeze al n-lea termen al şirului lui Fibonacci, modulo 982451653 folosind o funcţie recursivă la coadă. Funcţia va fi apelată iniţial astfel:
fib( n, 1, 1 );
sau, pentru optimizare:
fib( n, 0, 1 );
Şirul lui Fibonacci se consideră a fi:
1 1 2 3 5 8 13 21 ...
Date de intrare
Fişierul de intrare fibonacci.in conţine un singur număr n cu semnificaţia de mai sus.
Date de ieşire
În fişierul de ieşire fibonacci.out se va scrie un singur număr şi anume cel de-al n-ulea termen al şirului lui Fibonacci modulo 982451653.
Restricţii
- 1 ≤ n ≤ 100 000 000
- Implementarea trebuie să fie recursivă
Exemplu
fibonacci.in | fibonacci.out |
---|---|
5 | 5 |
20 | 6765 |