Завораживающая последовательность Фибоначчи

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

Одним из таких принципов, который весьма интересен для изучения, является последовательность Фибоначчи. Мы можем обнаружить ее во многих проявлениях природы: в числе лепестков цветка, количестве спиралей у подсолнуха и т.д.

В процессе работы с кодом мы сталкиваемся со многими алгоритмами: рекурсивные, типа “разделяй и властвуй”, рандомизированные, методы подбора и пр. Однако одними из наиболее полезных являются именно рекурсивные алгоритмы.

Что же такое алгоритм?

В первую очередь, алгоритм является набором задач, которым необходимо следовать для решения проблемы. Время его выполнения определяется числом шагов, необходимых для завершения всех этих задач (в некоторых случаях термин runtime может обозначать нотацию О большое в CS, которая описывает качество алгоритма).

Так что же такое рекурсия и как работает рекурсивная функция?

Рекурсия — это процесс, при котором некий элемент вызывает сам себя или описывает себя в виде ссылки на самого себя до выполнения некоего условия (true), затем этот процесс останавливается.

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

Как мы вычисляем последовательность Фибоначчи и почему важно ее знать?

Для тех, кто только начал осваивать программирование будет очень полезным знать, как и когда стоит применять рекурсию или итеративные функции.

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

Математическая формула Фибоначчи

Принцип построения последовательности Фибоначчи заключается в том, что каждое последующее ее число соответствует сумме двух ему предшествующих. 

При n=0 мы получаем F0=0, а при n=1 получится F1=1. Нам всегда известны эти два начальных значения последовательности. Задача в том, чтобы выяснить, как формируются дальнейшие ее значения и каково будет значение для числа n, которое мы захотим проверить. Поэтому мы всегда начинаем с числа n>1. 

Последовательность Фибоначчи рассчитывается по формуле, приведенной ниже:

F0=0, F1=1

Fn=Fn-1+Fn-2 для n>1 

Шаги вычисления значения Фибоначчи для n=6:

n=0 => F0=0
n=1 => F1=1
n = 2 поскольку n>1 =>F2 = F2–1 + F2–2 =F1 + F0 = 1+0=1
n= 3 =>F3= F3–1 + F3–2 =F2 + F1=1+1 = 2
n=4 =>F4=F4–1 + F4–2=F3+F2=2+1=3
n=5 =>F5=F4+F3=3+2=5
n=6 => F6=F5+F4=5+3=8 и так далее для n>1

А что получится, если мы возведем эти числа в квадрат?

1, 1, 4, 9, 25, 64, 169, 441, …
1 + 1 + 4 =6 = 2 x 3
1 + 1 + 4 + 9 =15 = 3 x 5
1 + 1 +4 + 9 + 25 =40 = 5 x 8
1 + 1 +4 + 9 + 25 + 64 =104 = 8 x 13 …

В результате мы получим уже не числа Фибоначчи. Тем не менее они раскрываются внутри значений, получаемых при сложении этих чисел. Из этого можно сделать вывод, что почти каждая сумма является частью последовательности Фибоначчи. Давайте посмотрим, как работают числа Фибоначчи на примере золотого прямоугольника:

Нам всем известно, что:

Площадь прямоугольника S = b x h => b ширина, h высота.

Что же получится, если мы сложим квадраты чисел, как указано выше?

Площадь прямоугольника S = 1*1+ 1*1 + 2*2 +3*3 +5*5 + 8*8+13*13 = 273 = 13x21

И снова мы получаем числа Фибоначчи.

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

13/8=1.625, 21/13=1.615, 34/21=1.619, 55/34=1.6176, 89/55=1.61818 …

Здесь мы видим значение, приближенное к значению золотого сечения, и чем большее число мы делим, тем больше их соответствие.

Ниже приведен JavaScript код, вычисляющий последовательность Фибоначчи. Временная сложность в нем линейна, т.к. цикл осуществляется от 2 до n. Время выполнения составляет О(n).

function fibonacci(n) {
 var fibonacciNumbers = [],
  firstNumber = 0,
  secondNumber = 1;
 if (n <= 0) {
  return fibonacciNumbers;
 }
 if (n === 1) {
  return fibonacciNumbers.push(firstNumber);
 }
 fibonacciNumbers[0] = firstNumber;
 fibonacciNumbers[1] = secondNumber;
 for (var i = 2; i <= n; i++) {
  fibonacciNumbers[i] = fibonacciNumbers[(i— 1)] + fibonacciNumbers[(i— 2)];
 }
 return fibonacciNumbers;
}
var result = fibonacci(3);
if (result) {
 for (var i = 0; i < result.length; i++) {
  console.log(result[i]);
 }
}

Читайте также:

• Алгоритм поиска A*
• 8 базовых алгоритмических задач на собеседованиях
• Алгоритмы машинного обучения простым языком. Часть 1

---

Перевод статьи Amra Sezairi: The Beauty of the Fibonacci Sequence