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
Linia 10: Linia 10:
== Restricții și precizări ==
== Restricții și precizări ==
1 ≤ n ≤ 2.000.000.000
1 ≤ n ≤ 2.000.000.000
== Exemplu 1 ==
== Exemplul 1 ==
; Intrare
; Intrare
: 6
: 6
Linia 16: Linia 16:
: 8
: 8
<br>
<br>
== Exemplu 2 ==
== Exemplul 2 ==
; Intrare
; Intrare
: 10
: 10
Linia 25: Linia 25:
<syntaxhighlight lang="python" line>
<syntaxhighlight lang="python" line>
#3344 - Fibonacci2
#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__":
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>
</syntaxhighlight>
== Explicatie ==
Termenii sunt: 1 1 2 3 5 8 13 21 34 55 89 ...

Versiunea de la data 8 ianuarie 2024 17:44

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}")

Explicatie

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

Adus de la „http://wiki.universitas.ro/index.php?title=3344_-_Fibonacci2&oldid=9223”