Альтернативный способ расчета серии Fibonacci

(Альтернативный путь в конце!)

Серия Fibonacci – это коллекция чисел, которые предшествуют им.

Который создаст такую серию:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377

Расчет

Есть два популярных способа сделать это

Используя нормальный метод ( 1 + , 1 + , 3 + , ... )
Используя рекурсивный метод ( fn (n - 1) + f (n - 2) где f1 и F2 равен 1 )

Реализации в Python будут чем -то подобным ( Нахождение первых 100 чисел фибоначчи)

Нормальный метод

a, b = 0, 1
for _ in range(100)
  print(a, end=' ')
  a, b = b, a + b

#=> 0 1 1 2 3 5 8 13...

Рекурсивный метод

def fib(n):
  if n < 3:
    return 1
  return fib(n - 1) + fib(n - 2)

for n in range(100):
  print(fib(n), end = ' ')

#=> 0 1 1 2 3 5 8 13...

(Не рекомендуется делать это в Python Due Tail Call Optimization)

Так что до сих пор я не видел других способов. Почему бы не найти другой способ?

В номерах Фибоначчи есть интересный факт. Что это за факт?

-> Разделение F (n + 1) с Fn ( f (n + 1)/Fn ) будет приближаться к золотому соотношению! ( 1.61803399... )

Давайте протестируем это!

1, 1, 2, 3, 5, 8, 13, 21, 34…

1 / 1 = 1  
2 / 1 = 2  
3 / 2 = 1.5  
8 / 5 = 1.6  
13 / 8 = 1.62  
21 / 13 = 1.615  
34 / 21 = 1.619  
...

И так далее! Хотя цифры увеличивают числа, соотношение будет более похоже на золотое соотношение. Тогда что мы можем с этим сделать?

Если F (n + 1)/Fn ≈ φ , Fn * φ будет (приблизительно) равен F (n + 1) который основывает следующий номер Фибоначчи!

Итак, давайте реализуем это в Python!

fib = 1
for _ in range(100):
  print(fib, end=' ')
  fib = round(fib * 1.618)

#=> 1, 1, 2, 3, 5, 8, 13, 21, 34...`

Итак, я умножил fib с 1.618 которое является приблизительным золотым соотношением. Как я уже сказал, это будет найдено в следующем номере Фибоначчи. Затем я округнул его, потому что я хочу целое число, а не десятичное значение. Если нам нужно это визуализировать:

fib = 1  
fib = round(fib * 1.61) -> fib = round(1.61) -> fib = 2      
fib = round(fib * 1.61) -> fib = round(3.22) -> fib = 3      
fib = round(fib * 1.61) -> fib = round(4.83) -> fib = 5      
fib = round(fib * 1.61) -> fib = round(8.05) -> fib = 8      
...

И так далее! Это интересный метод (найденный мной: P), но это может быть неправильно для действительно больших чисел. Для больших чисел вам понадобится лучшее приближение золотого соотношения, чтобы использовать его. Потому что десятичные числа, умножение с большими числами, создаст большие числа. Например:

1.2345 * 10 = 12.345  
1.2345 * 100 = 123.45  
1.2345 * 1000 = 1234.5  
1.2345 * 10000 = 12345  
1.2345 * 100000 = 123450

Так что в основном я не рекомендую этот метод для больших чисел.

Спасибо, что прочитали этот пост!

Оригинал: “https://dev.to/lyfolos/an-alternate-way-to-calculate-fibonacci-series-35e7”

(Альтернативный путь в конце!)

Расчет

(Не рекомендуется делать это в Python Due Tail Call Optimization)

Читайте ещё по теме: