Задача про n-ое число Фибоначчи

Суть моего труда заключается в том, чтобы определить функцию для нахождения n-ого числа Фибоначчи с линейной сложностью поиска. Вот какие методы я попробовал:

Возможно получится по простым данным постоить полином большой степени, используя метод неопределённых коэффициентов и использовать его для подсчёта последующих значений последовательности.

# Тут я сделал через метод неопределённых коэффициентов, получилось примерно то что нужно, # но из-за необходимости использования больших степеней, на полиноме возникают ненужные неровности.  import numpy as np import matplotlib.pyplot as plt  n = 10 # Основной параметр  F1 = 0 F2 = 1 Y = [0, 1] for _ in range(n - 2):     A = F1 + F2     F1 = F2     F2 = A     Y.append(A)  X = np.array([i for i in range(1, n + 1)])  print(X) print(Y) print(len(X) == len(Y)) R = []  for i in range(n):   line = []   for j in range(n):     line.append(1*X[i] ** j)   R.append(line)  R = np.array(R) A = np.linalg.solve(R, Y) linsp  = np.linspace(X.min(), X.max()) f = np.poly1d(np.flip(A)) fun = [f(x) for x in linsp] plt.plot(linsp,fun); plt.scatter(X, Y, color='r', alpha=0.5); # Рисуем исходные точки #plt.plot(linsp,np.sin(2*linsp),'g--'); plt.grid(True)

[ 1 2 3 4 5 6 7 8 9 10]

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

True

Всё немного съезжает на больших степенях, возможно это получится починить, используя метод через производные, чтобы вышел более плавный и «гладкий» полином:

[ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30]

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229]

True

Первый замер числа под номером 30:

267394558.0

3524578

Чем плох первый метод? У полинома образуются ненужные углы и неровности в областях между точками, на основе которых он был построен.

Но логически подумав, нам ведь и не нужны эти нецелые промежуточные значения, ведь область определения нужной нам функции — целые числа.

Вывод: возможно стоит вернуться к первому методу и проверить его на больших числах:

# Метод неопределённых коэффициентов import numpy as np import matplotlib.pyplot as plt  n = 13 # Основной параметр  F1 = 0 F2 = 1 Y = [0, 1] for _ in range(n - 2):     A = F1 + F2     F1 = F2     F2 = A     Y.append(A)  X = np.array([i for i in range(1, n + 1)])  print(X) print(Y) print(len(X) == len(Y)) R = []  for i in range(n):   line = []   for j in range(n):     line.append(1*X[i] ** j)   R.append(line)  R = np.array(R) A = np.linalg.solve(R, Y) linsp  = np.linspace(X.min(), X.max()) f = np.poly1d(np.flip(A)) fun = [f(x) for x in linsp] plt.plot(linsp,fun); plt.scatter(X, Y, color='r', alpha=0.5); # Рисуем исходные точки #plt.plot(linsp,np.sin(2*linsp),'g--'); plt.grid(True)  # Проверяю:  print("Второй замер числа под номером 30:") print(f(30).round(0))  # -5228112930.0  # Почему-то значение получилось отрицательным...

[ 1 2 3 4 5 6 7 8 9 10 11 12 13]

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

True

Второй замер числа под номером 30:

-5228112930.0

Попробуем проанализировать график. Видно, что это экспонента.

Подберём такие значения a и b чтобы все точки совпали:

import numpy as np import matplotlib.pyplot as plt from scipy.optimize import curve_fit  n = 30  # Количество чисел Фибоначчи  # Генерация чисел Фибоначчи итеративным методом fibonacci = [0, 1] for i in range(2, n + 1):     fibonacci.append(fibonacci[i - 1] + fibonacci[i - 2])  x_data = np.arange(0, n + 1) y_data = np.array(fibonacci[:n+1])  # Определение экспоненциальной функции def exponential_func(x, a, b):     return a * np.exp(b * x)  # Подгонка параметров a и b с помощью curve_fit popt, pcov = curve_fit(exponential_func, x_data, y_data, p0=[1, 0.1])  # p0 - начальные значения для a и b  a_opt, b_opt = popt print("Оптимизированные параметры: a =", a_opt, "b =", b_opt)  # Генерация гладкой экспоненты для визуализации x_smooth = np.linspace(x_data.min(), x_data.max(), 500) y_smooth = exponential_func(x_smooth, a_opt, b_opt)  # Построение графика plt.plot(x_smooth, y_smooth, color='blue', label='Экспонента (аппроксимация)') plt.scatter(x_data, y_data, color='red', alpha=0.8, label='Точки Фибоначчи')  # Стилизация графика plt.grid(True) plt.xlabel('n') plt.ylabel('F(n)') plt.title('График экспоненты') plt.legend()  # Отображение графика plt.show() 

Оптимизированные параметры: a = 0.44721359546613776 b = 0.4812118250621712