ilyachalov (ilyachalov) wrote,
ilyachalov
ilyachalov

Categories:

Учебник по JavaScript: ч.1, Числа Фибоначчи

Начало в предыдущем посте: «Учебник по JavaScript: ч.1, Рекурсия и стек».

Еще одна интересная задача из учебника, которая в очередной раз показывает, почему рекурсию не следует использовать в реальных программах: «Числа Фибоначчи».

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

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 и так далее...

https://ru.wikipedia.org/wiki/Числа_Фибоначчи

По условиям задачи требуется написать функцию, вычисляющую и возвращающую число из этого ряда чисел Фибоначчи по заданному номеру этого числа в этом ряду чисел.

Так как задача находится в подразделе 6.1 «Рекурсия и стек» учебника, то понятно, что предполагается, что ученик сначала попробует решить задачу методом рекурсии. Написать это решение несложно. Для проверки работы получившейся функции предлагается найти числа из ряда чисел Фибоначчи с номерами 3, 7 и 77.

Число с номером 3 из ряда чисел Фибоначчи — это число 2, с номером 7 — число 13, с номером 77 — число 5527939700884757.

И тут выясняется, что при поиске числа Фибоначчи с номером 77 вариант решения с рекурсией завешивает браузер (у меня — «Microsoft Edge») на некоторое время, после чего браузер выдает на экран сообщение о том, что «Эта страница не отвечает» (предлагается на выбор продолжить ожидание — кнопка «Wait», либо насильно завершить работу скрипта страницы — кнопка «Exit page»). Причины этого объяснены в указанном подразделе учебника.

Как я упоминал ранее (в учебнике это тоже подчеркивается), любую рекурсию можно переделать в цикл. Вариант решения с использованием цикла вместо рекурсии от авторов учебника:

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

Такое решение спокойно (без зависаний браузера) находит число с номером 77 из ряда чисел Фибоначчи. Причины этого неплохо изложены авторами учебника в их решении, рекомендую почитать.

Однако, мне кажется, у меня получилось решить эту задачу лучше (в смысле — понятнее).

Во-первых, неинформативное название переменных авторы учебника сами ругали в следующем подразделе учебника:
https://learn.javascript.ru/variables#pridumyvayte-pravilnye-imena

Переменные a и b я назвал prev («предыдущее» число в ряде чисел Фибоначчи) и cur («текущее» число в ряде чисел Фибоначчи) соответственно. На каждой итерации цикла нам необходимо знать два числа из ряда чисел Фибоначчи, я их назвал «предыдущим» и «текущим».

В цикле мы движемся по ряду чисел Фибоначчи в сторону увеличения чисел (вправо). В каждой новой итерации цикла «предыдущее» и «текущее» числа изменяются.

Новое «текущее» число вычисляется как сумма старого (из предыдущей итерации) «текущего» числа и старого (из предыдущей итерации) «предыдущего» числа. После этого старое «текущее» число становится новым «предыдущим» числом. Математическими инструкциями это можно выразить так:

curнов = curстар + prevстар
prevнов = curстар


Переменная c, очевидно, является вспомогательной. Чтобы от нее избавиться, можно применить деструктурирующее присваивание, о котором в учебнике было рассказано ранее и я о нем писал. Преобразуя вышеприведенные математические формулы в JavaScript и применив деструктурирующее присваивание, получаем более изящный и более понятный, чем у авторов учебника, код:

[cur, prev] = [cur + prev, cur];

Решение полностью:

function fib(n) {
    let cur = 1, prev = 1;
    for (let i = 3; i <= n; i++) {
        [cur, prev] = [cur + prev, cur];
    }
    return cur;
}
Tags: Математика, Образование, Программирование
Subscribe

  • Капля: от фантастического ужаса до программирования

    Помню, в детстве посмотрел американский фильм «Капля» («The Blob») 1988 года в жанре фантастических ужасов. Он произвел на меня большое впечатление.…

  • Любимый женский кавер песни «My Way»

    Голландский «Голос» вообще один из моих самых любимых. Удивительно, но почему-то именно эта маленькая страна дала этому шоу очень много понравившихся…

  • «Oh! Darling» против «Imagine»

    Не понимаю, что люди находят в песне «Imagine» Леннона. Ну да, мелодичная. Но по мне слишком спокойная и чересчур сладенькая. Вот «Oh! Darling»…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments