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, может быть у вас получится)
Известно, что последовательность Фибоначчи задана следующими соотношениями: 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, может быть у вас получится)
More Questions From This User See All
Answers & Comments
Ответ:
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.