3344 - Fibonacci2: Difference between revisions

Revision as of 17:44, 8 January 2024

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

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 ...

@@ Line 10: / Line 10: @@
 == Restricții și precizări ==
 ≤ n ≤ 2.000.000.000
-== Exemplu 1 ==
+== Exemplul 1 ==
 ; Intrare
 : 6
@@ Line 16: / Line 16: @@
 : 8
 <br>
-== Exemplu 2 ==
+== Exemplul 2 ==
 ; Intrare
 : 10
@@ Line 25: / Line 25: @@
 <syntaxhighlight lang="python" line>
 #3344 - Fibonacci2
-def multiply(a, b, MOD):
+def fibonacci_modulo_n(n):
-     res = [[0, 0], [0, 0]]
+     fib = [0, 1]
-    for i in range(2):
-        for j in range(2):
-            for k in range(2):
-                res[i][j] += (a[i][k] * b[k][j]) % MOD
-                res[i][j] %= MOD
-    return res
-def power(matrix, exp, MOD):
+    for i in range(2, n + 1):
-    if exp == 1:
+         fib_i = (fib[i - 1] + fib[i - 2]) % 666013
-         return matrix
+         fib.append(fib_i)
-    if exp % 2 == 0:
-        half_pow = power(matrix, exp // 2, MOD)
-         return multiply(half_pow, half_pow, MOD)
-    else:
-        return multiply(matrix, power(matrix, exp - 1, MOD), MOD)
-def fibonacci(n, MOD):
+     return fib[n]
-     base_matrix = [[1, 1], [1, 0]]
-    result_matrix = power(base_matrix, n - 1, MOD)
-    return result_matrix[0][0] % MOD
-def main():
+def verificare_restrictii(n):
-     n = int(input("Introduceți n: "))
+     if 1 <= n <= 2.000.000.000:
-    MOD = 666013
+        return True
-     result = fibonacci(n, MOD)
+     else:
-    print(f"Al {n}-lea termen al șirului Fibonacci, modulo {MOD}, este: {result}")
+        return False
 if __name__ == "__main__":
-     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 ...