3344 - Fibonacci2

Cerința

Șirul lui Fibonacci este definit astfel:

Fn={1Fn−1+Fn−2dacă n=1 sau n=2,dacă n>2. Se dă un număr natural n. Determinați al n-lea termen al șirului, modulo 666013.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran numărul F, reprezentând al n-lea termen al șirului, modulo 666013.

Restricții și precizări

1 ≤ n ≤ 2.000.000.000

Exemplul 1

Intrare

6

Ieșire

8

Exemplul 2

Intrare

10

Ieșire

55

Rezolvare

<syntaxhighlight lang="python" line>

1. 3344 - Fibonacci2

def fibonacci_modulo_n(n):

   fib = [0, 1]

   for i in range(2, n + 1):
       fib_i = (fib[i - 1] + fib[i - 2]) % 666013
       fib.append(fib_i)

   return fib[n]

def verificare_restrictii(n):

   if 1 <= n <= 2.000.000.000:    
       return True
   else:
       return False

if __name__ == "__main__":

   n = int(input("Introduceți numărul n: "))
   
   result = fibonacci_modulo_n(n)
   
   print(f"Al {n}-lea termen al șirului Fibonacci modulo 666013 este: {result}")

</syntaxhighlight>

Explicatie

Termenii sunt: 1 1 2 3 5 8 13 21 34 55 89 ...