Latest revision as of 17:05, 18 May 2024

Cerința[edit | edit source]

Ș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[edit | edit source]

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

Date de ieșire[edit | edit source]

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

Restricții și precizări[edit | edit source]

1 ≤ n ≤ 2.000.000.000

Exemplu:[edit | edit source]

Intrare

Ieșire

Explicație[edit | edit source]

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

Rezolvare[edit | edit source]

<syntaxhighlight lang="python" line="1"> MOD = 666013

class Mat:

   def __init__(self, mat):
       self.mat = mat

nullMat = Mat([[1, 0], [0, 1]]) initMat = Mat([[1, 1], [1, 0]])

def prod(a, b):

   ret = Mat([[0, 0], [0, 0]])
   ret.mat[0][0] = (a.mat[0][0] * b.mat[0][0] + a.mat[0][1] * b.mat[1][0]) % MOD
   ret.mat[0][1] = (a.mat[0][0] * b.mat[0][1] + a.mat[0][1] * b.mat[1][1]) % MOD
   ret.mat[1][0] = (a.mat[1][0] * b.mat[0][0] + a.mat[1][1] * b.mat[1][0]) % MOD
   ret.mat[1][1] = (a.mat[1][0] * b.mat[0][1] + a.mat[1][1] * b.mat[1][1]) % MOD
   return ret

def pwr(mat, n):

   if n == 0:
       return nullMat
   if n % 2 == 1:
       return prod(mat, pwr(prod(mat, mat), n // 2))
   return pwr(prod(mat, mat), n // 2)

def verifica_restrictii(n):

   if 1 <= n <= 2000000000:
       return True
   else:
       print("Datele nu corespund restrictiilor impuse")
       return False

def main():

   n = int(input())
   if verifica_restrictii(n):
       result = pwr(initMat, n)
       print(result.mat[0][1])

if __name__ == "__main__":

   main()

</syntaxhighlight>

@@ Line 4: / Line 4: @@
 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 ==
-≤ n ≤ 2.000.000.000
-== Exemplul 1 ==
-; Intrare
-: 6
-; Ieșire
-: 8
-<br>
-== Exemplul 2 ==
-; Intrare
-: 10
-; Ieșire
-: 55
-<br>
-== Rezolvare ==
-<syntaxhighlight lang="python" line>
-#3344 - Fibonacci2
-def fibonacci_modulo_n(n):
-    fib = [0, 1]
-    for i in range(2, n + 1):
+= Date de intrare =
-        fib_i = (fib[i - 1] + fib[i - 2]) % 666013
+Programul citește de la tastatură numărul <code>n</code>.
-        fib.append(fib_i)
-    return fib[n]
+= Date de ieșire =
+Programul va afișa pe ecran numărul <code>F</code>, reprezentând al <code>n</code>-lea termen al șirului, modulo <code>666013</code>.
-def verificare_restrictii(n):
+= Restricții și precizări =
-     if 1 <= n <= 2.000.000.000:
+* <code>1 ≤ n ≤ 2.000.000.000</code>
+= Exemplu: =
+Intrare
+Ieșire
+=== Explicație ===
+Termenii sunt: <code>1 1 2 3 5 8 13 21 34 55 89 ...</code>
+:
+== Rezolvare ==
+<syntaxhighlight lang="python" line="1">
+MOD = 666013
+class Mat:
+    def __init__(self, mat):
+        self.mat = mat
+nullMat = Mat([[1, 0], [0, 1]])
+initMat = Mat([[1, 1], [1, 0]])
+def prod(a, b):
+    ret = Mat([[0, 0], [0, 0]])
+    ret.mat[0][0] = (a.mat[0][0] * b.mat[0][0] + a.mat[0][1] * b.mat[1][0]) % MOD
+    ret.mat[0][1] = (a.mat[0][0] * b.mat[0][1] + a.mat[0][1] * b.mat[1][1]) % MOD
+    ret.mat[1][0] = (a.mat[1][0] * b.mat[0][0] + a.mat[1][1] * b.mat[1][0]) % MOD
+    ret.mat[1][1] = (a.mat[1][0] * b.mat[0][1] + a.mat[1][1] * b.mat[1][1]) % MOD
+    return ret
+def pwr(mat, n):
+    if n == 0:
+        return nullMat
+    if n % 2 == 1:
+        return prod(mat, pwr(prod(mat, mat), n // 2))
+    return pwr(prod(mat, mat), n // 2)
+def verifica_restrictii(n):
+     if 1 <= n <= 2000000000:
          return True
      else:
+        print("Datele nu corespund restrictiilor impuse")
          return False
+def main():
+    n = int(input())
+    if verifica_restrictii(n):
+        result = pwr(initMat, n)
+        print(result.mat[0][1])
 if __name__ == "__main__":
-     n = int(input("Introduceți numărul n: "))
+     main()
-    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 ...