3344 - Fibonacci2: Diferență între versiuni
De la Universitas MediaWiki
Fără descriere a modificării |
Fără descriere a modificării |
||
Linia 4: | Linia 4: | ||
Fn={1Fn−1+Fn−2dacă n=1 sau n=2,dacă n>2. | 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. | 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 <code>n</code>. | |||
= 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 | = Restricții și precizări = | ||
if 1 <= n <= | |||
* <code>1 ≤ n ≤ 2.000.000.000</code> | |||
= Exemplu: = | |||
Intrare | |||
6 | |||
Ieșire | |||
8 | |||
=== 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 | return True | ||
else: | else: | ||
print("Datele nu corespund restrictiilor impuse") | |||
return False | return False | ||
def main(): | |||
n = int(input()) | |||
if verifica_restrictii(n): | |||
result = pwr(initMat, n) | |||
print(result.mat[0][1]) | |||
if __name__ == "__main__": | if __name__ == "__main__": | ||
main() | |||
</syntaxhighlight> | </syntaxhighlight> | ||
Versiunea curentă din 18 mai 2024 17:05
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
Exemplu:
Intrare
6
Ieșire
8
Explicație
Termenii sunt: 1 1 2 3 5 8 13 21 34 55 89 ...
Rezolvare
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()