Суть моего труда заключается в том, чтобы определить функцию для нахождения 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
Автор: YanKhus
