3344 - Fibonacci2: Diferență între versiuni

De la Universitas MediaWiki
(Pagină nouă: == 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 1 == ; Intrare : 6 ; Ieșire...)
 
Fără descriere a modificării
 
(Nu s-a afișat o versiune intermediară efectuată de același utilizator)
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 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 1 ==
; Intrare
: 6
; Ieșire
: 8
<br>
== Exemplu 2 ==
; Intrare
: 10
; Ieșire
: 55
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#3344 - Fibonacci2
def multiply(a, b, MOD):
    res = [[0, 0], [0, 0]]
    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):
= Date de intrare =
     if exp == 1:
Programul citește de la tastatură numărul <code>n</code>.
         return matrix
 
     if exp % 2 == 0:
= Date de ieșire =
         half_pow = power(matrix, exp // 2, MOD)
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>.
        return multiply(half_pow, half_pow, MOD)
 
= Restricții și precizări =
 
* <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
     else:
     else:
         return multiply(matrix, power(matrix, exp - 1, MOD), MOD)
         print("Datele nu corespund restrictiilor impuse")
 
        return False
def fibonacci(n, MOD):
    base_matrix = [[1, 1], [1, 0]]
    result_matrix = power(base_matrix, n - 1, MOD)
    return result_matrix[0][0] % MOD


def main():
def main():
     n = int(input("Introduceți n: "))
     n = int(input())
     MOD = 666013
     if verifica_restrictii(n):
    result = fibonacci(n, MOD)
        result = pwr(initMat, n)
    print(f"Al {n}-lea termen al șirului Fibonacci, modulo {MOD}, este: {result}")
        print(result.mat[0][1])


if __name__ == "__main__":
if __name__ == "__main__":
     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()
Adus de la „http://wiki.universitas.ro/index.php?title=3344_-_Fibonacci2&oldid=9817”