Числа Фибоначчи, как учат в учебниках и как их лучше искать

Одна из первых тем, которой учат в учебниках по программированию — это рекурсия. Это довольно сложная для понимания тема, ну то есть для некоторых (для меня например). И почти в 90% учебников рекурсию рассматривают на примере чисел Фибоначчи.

Числа Фибоначчи — это последовательность чисел, в которой каждое следующее число является суммой двух предыдущих чисел. Начинается последовательность с нуля и единицы (ноль иногда опускают). Выглядит это так:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34… и так до бесконечности

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

Вот так, примерно, будет выглядеть рекурсия для нахождения n-ного числа:

function fibonacci(n) {
  var num;

  if (n >= 2) {
    num = fibonacci(n - 1) + fibonacci(n - 2);
  } else {
    num = n
  }

  return num;
}

alert(fibonacci(6)); // >>> 8

Всё хорошо, функция отлично находит шестое число в последовательности. Но это только пока… Я не знаю насколько мощный у вас комп, но попробуйте найти пятидесятое число:

alert(fibonacci(50));

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

Итак как же нам найти любое число в последовательности Фибоначчи? Лезем в википедию и узнаём, что нам на помощь приходит формула Бине:

Нас интересует часть до первого знака равенства, реализуем её:

function fibonacci2(n) {
  var sq5 = Math.sqrt(5); // сохраняем значение корня из 5, чтобы сэкономить ресурсы
  var a = (1 + sq5) / 2;
  var b = (1 - sq5) / 2;
  return (Math.pow(a, n) - Math.pow(b, n)) / sq5;
}

alert(fibonacci2(500)); // >>> 1.3942322456169767e+104

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

Ссылка на пример

Ссылка на источник

P.S. Это тоже может быть интересно:

16 Комментарии

  1. Николай

    Хм, если запоминать уже посчитанные члены в какой нибудь массив, и проверять на входе в функцию — считали ли мы этот член, то будет тоже быстро. (Правда не зна в js есть массивы или нет, это же javascript?)

    1. psywalker

      Да, в javascript есть массивы. Советую вам изучить этот сайт от корки до корки http://javascript.ru/

  2. Gaspode

    Указанный способ чреват потерей точности. Так надёжнее:
    return Math.ceil((Math.pow(a, n) — Math.pow(b, n)) / sq5);
    Иначе уже на десятом числе спотыкаемся.

    1. GreatRash (Автор записи)

      Согласен, из-за неточности вычислений с плавающей точкой результат нужно округлять.

  3. Николай

    Я пока не готов приступить к javascript, а так спасибо!

  4. Артем

    Вот пример нормальной рекурсии с линейной сложностью (а не с 2 ^ n, как в примере)

    function fibonacci(first, second, n)
    {
    if (n == 0 || n == 1) return n;
    if (n == 2) return first + second;
    return fibonacci(second, first + second, n — 1);
    }

    alert(fibonacci(0, 1, 6));

    1. norches

      Не Работает ((
      Не показывет n’ное число ((

  5. Andrew

    В нормальных учебниках кроме вычисления «в лоб», имеющего сложность O(n^2), приводят еще и простейший алгоритм (хоть рекурсивный, хоть итерационный), имеющий сложность O(n). Суть его в том, что достаточно иметь буфер для двух последних чисел Фибоначчи. Вот простейший итерационный вариант:

    function fib(n){
    var buf = [0, 1];
    var i;
    for(i=2; i<=n; i++){
    buf[i%2]+=buf[(i+1)%2];
    }
    return buf[n%2];
    }

    А если не нравятся остатки от деления, то можно так:

    function fib(n){
    var buf = [0, 1];
    if(n0)buf=[buf[1], buf[0]+buf[1]];
    return buf[1];
    }

    1. Andrew

      Забавно на сайте, посвященном html/css/javascript, видеть совершенно ученический глюк в обработке символов «меньше» и «больше» (в данном случае было вырезано все, что находилось между этими знаками). Так что посылаю второй вариант еще раз:

      function fib(n){
      var buf = [0, 1];
      if( n 0 )buf=[buf[1], buf[0]+buf[1]];
      return buf[1];
      }

      1. Andrew

        И вторая попытка закончилась тем же самым. Попытка номер три:

        function fib(n){
        var buf = [0, 1];
        if(n < 0)return n;
        while(—n > 0)buf=[buf[1], buf[0]+buf[1]];
        return buf[1];
        }

        1. Andrew

          Разумеется, в третьей строке функции не n<0, а n<2

        2. Andrew

          А в четвертой строке перед n стоит декремент (два минуса).

      2. SelenIT

        Это не глюк, это фича — здесь в комментариях работает простейший HTML (strong, ссылки и т.п.).

        1. Andrew

          1. Если пользователей не предупреждают о такой особенности поведения редактора — это баг.

          2. Если знак < за которым следует пробел воспринимается редактором как начало тега — это безусловный баг.

          1. psywalker

            Можно поставить редактор из админки, в нём будет всё что можно и даже больше, но он объёмный, тяжёлый из из-за него происходят тормоза на слабых компах. По крайней мере у нас был такой опыт и люди жаловались, поэтому мы решили поменять его обратно на старый, текущий :(

            Можно попробовать ещё раз, посмотрим, что из этого выйдет. Поставил его, проверяйте.

  6. Crank

    Питонячий код:
    def fibo(one,two,n):
        if n < 2:
            return n
        if n == 2:
            return one + two
        if n > 2:
            return fibo(two,one + two,n — 1)
    print fibo(1,1,1000)

Оставить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Получать новые комментарии по электронной почте. Вы можете подписаться без комментирования.