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

назад до уроку

Послідовність чисел Фібоначчі має формулу 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-th число Фібоначчі.

Приклад:

          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(3) вираховується двічі, а fib(2) – тричі. Загальна кількість обчислень росте набагато швидше, ніж n, що робить його величезним навіть для n=77.

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

Як інший варіант, ми можемо відмовитись від рекурсії та використати зовсім інший алгоритм на основі циклу.

Замість переходу від n до нижчих значень ми можемо створити цикл, який починається з 1 і 2, потім отримує fib(3) як їхню суму, а потім fib(4) як суму двох попередніх значень, потім fib(5) і йде вгору і вгору, поки не досягне потрібного значення. На кожному кроці нам потрібно лише запам’ятати два попередні значення.

Ось кроки нового алгоритму в деталях.

Початок:

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

// get 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; // тепер a = fib(3)
b = c; // тепер 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.

Підхід називається динамічне програмування знизу вгору.