CSS-live.ru

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

Одна из первых тем, которой учат в учебниках по программированию — это рекурсия. Это довольно сложная для понимания тема, ну то есть для некоторых (для меня например). И почти в 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. Это тоже может быть интересно:

    None Found

19 комментариев

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

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

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

    2. return Math.round(((Math.pow(a, n) — Math.pow(b, n)) / Math.sqrt(5)));
      так луче потомучто з ceil не точно округляет

  3. Вот пример нормальной рекурсии с линейной сложностью (а не с 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));

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

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

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

        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];
        }

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

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

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

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

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

  5. Питонячий код:
    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)

  6. function count() {
    var i = 1;
    var a = 2;
    var b = 0;
    for (i = 1; i < 55;) {
    i = i + a;
    alert( i );
    b = i;
    a = a + b;
    alert( a );
    }
    }
    count();

    Можно ли таким способом?

    1. В смысле, простым циклом, а не рекурсией? Можно, конечно (только условие выхода из цикла лучше бы передавать параметром, а не хардкодить:). Но по формуле даже при не очень большом n получается эффективнее, даже без «экономии ресурсов».

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

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

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