Числа Фибоначчи

вернуться к уроку

Последовательность чисел Фибоначчи определяется формулой F_n = F_n-1 + F_n-2. То есть, следующее число получается как сумма двух предыдущих.

Первые два числа равны 1, затем 2(1+1), затем 3(1+2), 5(2+3) и так далее: 1, 1, 2, 3, 5, 8, 13, 21....

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

Напишите функцию fib(n) которая возвращает n-е число Фибоначчи.

Пример работы:

          function fib(n) { /* ваш код */ }

alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757
        

P.S. Все запуски функций из примера выше должны работать быстро. Вызов fib(77) должен занимать не более доли секунды.

Сначала решим через рекурсию.

Числа Фибоначчи рекурсивны по определению:

function fib(n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // вычисляется очень долго

При больших значениях n такое решение будет работать очень долго. Например, fib(77) может повесить браузер на некоторое время, съев все ресурсы процессора.

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

Например, посмотрим на отрывок вычислений для fib(5):

          ...
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
...
        

Здесь видно, что значение fib(3) нужно одновременно и для fib(5) и для fib(4). В коде оно будет вычислено два раза, совершенно независимо.

Полное дерево рекурсии:

Можно заметить, что fib(3) вычисляется дважды, а fib(2) – трижды. Общее количество вычислений растёт намного быстрее, чем n, что делает его огромным даже для n=77.

Можно это оптимизировать, запоминая уже вычисленные значения: если значение, скажем, fib(3) вычислено однажды, затем мы просто переиспользуем это значение для последующих вычислений.

Другим вариантом было бы отказаться от рекурсии и использовать совершенно другой алгоритм на основе цикла.

Вместо того, чтобы начинать с n и вычислять необходимые предыдущие значения, можно написать цикл, который начнёт с 1 и 2, затем из них получит fib(3) как их сумму, затем fib(4)как сумму предыдущих значений, затем fib(5) и так далее, до финального результата. На каждом шаге нам нужно помнить только значения двух предыдущих чисел последовательности.

Вот детальные шаги нового алгоритма.

Начало:

          // a = fib(1), b = fib(2), эти значения по определению равны 1
let a = 1, b = 1;

// получим c = fib(3) как их сумму
let c = a + b;

/* теперь у нас есть fib(1), fib(2), fib(3)
a  b  c
1, 1, 2
*/
        

Теперь мы хотим получить fib(4) = fib(2) + fib(3).

Переставим переменные: a,b, присвоим значения fib(2),fib(3), тогда c можно получить как их сумму:

          a = b; // теперь a = fib(2)
b = c; // теперь b = fib(3)
c = a + b; // c = fib(4)

/* имеем последовательность:
   a  b  c
1, 1, 2, 3
*/
        

Следующий шаг даёт новое число последовательности:

          a = b; // now a = fib(3)
b = c; // now b = fib(4)
c = a + b; // c = fib(5)

/* последовательность теперь (на одно число больше):
      a  b  c
1, 1, 2, 3, 5
*/
        

…И так далее, пока не получим искомое значение. Это намного быстрее рекурсии и не требует повторных вычислений.

Полный код:

function fib(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return b;
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757

Цикл начинается с i=3, потому что первое и второе значения последовательности заданы a=1, b=1.

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