Question

Python. Миллионное число Фибоначчи
Известно, что последовательность Фибоначчи задана следующими соотношениями: f(n)=f(n-1)+f(n-2), f(0)=0, f(1)=1. Сами числа: 1,1,2,3,5,8...
Требуется написать программу, которая возвращает n-ый элемент последовательности Фибоначчи (n может достигать 2000000, при этом, время работы кода не должно быть большим). Например, при n=3 программа должна возвратить 2, при n=4: 3 и т.д. (Сам пытался по формуле, но выходят погрешности и ошибки при огромных n, может быть у вас получится)

Answer 1

Ответ:

def matrix_multiply(A, B):

return [[A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],

[A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]]

def matrix_power(matrix, power):

result = [[1, 0], [0, 1]]

while power > 0:

if power % 2 == 1:

result = matrix_multiply(result, matrix)

matrix = matrix_multiply(matrix, matrix)

power //= 2

return result

def fibonacci(n):

if n == 0:

return 0

matrix = [[1, 1], [1, 0]]

result = matrix_power(matrix, n - 1)

return result[0][0]

n = 2000000

result = fibonacci(n)

print(result)

Объяснение:

Для обчислення n-го числа Фібоначчі з великим значенням n, таким як 2000000, вам знадобиться використовувати ефективний метод, щоб уникнути зайвих обчислень. Один з підходів - це використання матричних операцій. Ось приклад програми на Python, яка реалізує цей підхід (код в рішенні). Ця програма використовує матричний підхід для швидкого обчислення n-го числа Фібоначчі. Вона спрацює відносно швидко для такого великого значення n, як 2000000.