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

Формула Бине

важность: 4
function fibBinet(n) {
  var phi = (1 + Math.sqrt(5)) / 2;
  // используем Math.round для округления до ближайшего целого
  return Math.round(Math.pow(phi, n) / Math.sqrt(5));
}

function fib(n) {
  var a = 1,
    b = 0,
    x;
  for (i = 0; i < n; i++) {
    x = a + b;
    a = b
    b = x;
  }
  return b;
}

alert( fibBinet(2) ); // 1, равно fib(2)
alert( fibBinet(8) ); // 21, равно fib(8)
alert( fibBinet(77) ); // 5527939700884755
alert( fib(77) ); // 5527939700884757, не совпадает!

Результат вычисления F77 получился неверным!

Причина – в ошибках округления, ведь √5 – бесконечная дробь.

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

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

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

Код для их вычисления (из задачи Числа Фибоначчи):

function fib(n) {
  var a = 1,
    b = 0,
    x;
  for (i = 0; i < n; i++) {
    x = a + b;
    a = b
    b = x;
  }
  return b;
}

Существует формула Бине, согласно которой Fn равно ближайшему целому для ϕn/√5, где ϕ=(1+√5)/2 – золотое сечение.

Напишите функцию fibBinet(n), которая будет вычислять Fn, используя эту формулу. Проверьте её для значения F77 (должно получиться fibBinet(77) = 5527939700884757).

Одинаковы ли результаты, полученные при помощи кода fib(n) выше и по формуле Бине? Если нет, то почему и какой из них верный?