Последовательность Фибоначчи глазами фронтенда

внешний интерфейс
Последовательность Фибоначчи глазами фронтенда

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

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

Во-первых, последовательность Фибоначчи начинается с 0, т.е.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

Итак, согласно этому правилу, верните n-е число Фибоначчи

Рекурсия

Прежде всего, перед первыми рекурсивными точками, а затем реализуйте их снова.

function fibonacci(n){
    if(n === 1 || n === 0 ) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}

Идея рекурсии очень проста, то есть она продолжает вызывать собственный метод до тех пор, пока n не станет равным 1 или 0, а затем начинает возвращать данные слой за слоем.

При использовании рекурсии для вычисления больших чисел производительность будет особенно низкой по двум причинам:

① В рекурсивном процессе каждый раз, когда создается новая функция, интерпретатор создает новый фрейм стека функций и помещает его в фрейм стека текущей функции, который формирует стек вызовов. Поэтому, когда количество рекурсивных слоев слишком велико, это может привести к тому, что стек вызовов займет слишком много памяти или переполнится.

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

console.log(`fibonacci(${n-1}) + fibonacci(${n-2})`)

Когда n равно 6, полученный результат

fibonacci(5) + fibonacci(4)
fibonacci(4) + fibonacci(3)
fibonacci(3) + fibonacci(2)
fibonacci(2) + fibonacci(1)
fibonacci(1) + fibonacci(0)
fibonacci(1) + fibonacci(0)
fibonacci(2) + fibonacci(1)
fibonacci(1) + fibonacci(0)
fibonacci(3) + fibonacci(2)
fibonacci(2) + fibonacci(1)
fibonacci(1) + fibonacci(0)
fibonacci(1) + fibonacci(0)

② Анализ можно найти, рекурсивное вызвало большое количество двойного подсчета.

Эти два недостатка рекурсии мы можем использоватьОптимизация вызова хвостаа такжерешать.

Во-первых, что такое хвостовой вызов.

хвостовой вызовОтносится к ситуации, когда последнее действие в функции является функцией вызова: то есть возвращаемое значение вызова напрямую возвращается текущей функцией. Википад[1]

С кодом значения возвращаемого функции B - это функция возврата.

function B() {
    return 1;
}
function A() {
    return B();  // return 1
}

В ES6 в строгом режиме оптимизация хвостовых вызовов будет включена при соблюдении следующих условий: в это время движок не будет создавать новый фрейм стека, а будет очищать данные текущего фрейма стека и использовать его повторно:[2]

  1. Функция хвостового вызова не требует доступа к переменным в текущем кадре стека.

  2. После возврата хвостового вызова функция не имеет инструкции для продолжения выполнения.

  3. Результатом хвостового вызова является возвращаемое значение функции

Например:

Следующая функция может включить оптимизацию хвостового вызова

"use strict";
function doA() {
    return doB();
}

Следующие функции не могут включить оптимизацию хвостового вызова

"use strict";
function doC() {
    doD();  // 尾调用的结果不是函数的返回值
}

"use strict";
function doE() {
    return 1 + doF(); // 尾调用返回后，函数仍然有语句要运行
}

Мы используем оптимизацию вызова хвоста, переписывая функцию.

'use strict'
function fibonacci(n, current, next) {
    if(n === 1) return next;
    if(n === 0) return 0;
    return fibonacci(n - 1, next, current + next);
}

Мы можем вызвать эту функцию следующим образом

fibonacci(6, 0, 1);

В это время, когда функция выполняется, потому что引擎不会创建一个新的栈帧，而是清除当前栈帧的数据并复用, использование памяти не будет слишком большим.

Благодаря ES2015默认参数

'use strict'
function fibonacci(n, current = 0, next = 1) {
    if(n === 1) return next;
    if(n === 0) return 0;
    return fibonacci(n - 1, next, current + next);
}

Таким образом, при вызове вам нужно передать только один параметр.

fibonacci(6);

В это время, прежде чем мы вернем оператор, который вызывает процесс печати

console.log(`fibonacci(${n}, ${next}, ${current + next})`);

Вы обнаружите, что процесс вызова значительно сократился.

fibonacci(6, 1, 1)
fibonacci(5, 1, 2)
fibonacci(4, 2, 3)
fibonacci(3, 3, 5)
fibonacci(2, 5, 8)

Уведомление:

Идея рекурсивного метода очень согласуется с идеей расчета, то есть f(0) запускается и вычисляется по одному, пока не будет добавлено нужное нам значение.

function fibonacci(n) {
    const aFi = new Array(n+1);
    aFi[0] = 0; aFi[1] = 1;
    for(let i=2; i<= n; i++){
        aFi[i] = aFi[i-1] + aFi[i-2];
    }
    return aFi[n];
}

Здесь мы определяем массив для хранениявсеРасчеты, но на самом деле нам нужно толькоf(n-1)а такжеf(n-2)два значения, поэтому мы можем хранить эти два значения в двух переменных, чтобы уменьшить накладные расходы на память.

function fibonacci(n) {
    let current = 0;
    let next = 1;
    let temp;
    for(let i = 0; i < n; i++){
        temp = current;
        current = next;
        next += temp;
    }
    return current;
}

Основываясь на этой идее, мы перепишем это, используя другой подход.

Первый вариант метода присвоения структуры ES2015

Структурное задание[3]Позволяет нам извлекать значения непосредственно из массива в разные переменные. Таким образом, мы можем использовать структуру назначение, пропуская промежуточную перемему Temp.

function fibonacci(n) {
    let current = 0;
    let next = 1;
    for(let i = 0; i < n; i++){
        [current, next] = [next, current + next];
    }
    return current;
}

Вариант 2 --> форма while

function fibonacci(n) {
    let current = 0;
    let next = 1;
    while(n --> 0){
        [current, next] = [next, current + next];
    }
    return current;
}

здесь-->Это не предельный оператор, это просто аббревиатура двух операторов. то есть - и >.

здесь

while(n --> 0){}

можно переписать как

while(n>0) {n--}

Вот это то, почему это так.

возвращаемое значениеВозвращаемое значение n – это n.

Итак, покаn>0, то он будет выполнятьсяn--

Вариант три расширенных функции

function fibonacci(n){
	let seed = 1;
	return [...Array(n)].reduce(p => {
		const temp = p + seed; 
		seed = p;
		return temp;
	},0)
}

Здесь мы используем расширенную функцию сокращения[5]Первый параметр — это значение последнего вычисления, поэтому здесь pp сохраняет значение F(n-1), а seed сохраняет значение F(n-2).

Вариант Четыре Генератора Генератор


Генератор — это новая функция ES 2015. Благодаря этой функции мы можем использовать метод генератора для создания генератора последовательности Фибоначчи.

function* fibonacci(){
    let current = 0;
    let next = 1;
    yield current;
    yield next;
    while(true) {
        [current, next] = [next, current + next];
        yield next;
    }
}

Способ использования

const fibo = fibonacci();
for(let i=0; i< 10;i ++){
    console.log(fibo.next().value);
}

Но этот генератор не является функцией, которая может генерировать указанное n. Подробные методы реализации и возможные ямки можно найти в этой статье.7 удивительных вещей, которые я узнал, написав генераторы Фибоначчи на JavaScript.

формула общего члена

Доказательство формулы общего члена Фибоначчи см.Энциклопедия Байду. CF Формула, следующий код может быть достигнут[8]:

function fibonacci(n) {
    const SQRT_FIVE = Math.sqrt(5);
    return Math.round(1/SQRT_FIVE * (Math.pow(0.5 + SQRT_FIVE/2, n) - Math.pow(0.5 - SQRT_FIVE/2, n)));
}

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

использованная литература

[1] Крики хвоста — Википедия, свободная энциклопедия

[2] «Понимание ES6» Отделочное чтение: функция (функции) (восемь) Оптимизация вызова хвоста

[3]

[4]

[5] Array.prototype.reduce() - JavaScript | MDN

[6] Столбец Фибоначчи _ Baidu Encyclopedia

[7] 7 удивительных вещей, которые я узнал, написав генераторы Фибоначчи на JavaScript

[8] Схема JS и оптимизация суммирования рядов Фибоначчи

[9] Оптимизация хвостовых вызовов - веб-журнал Руан Ифэн

[10] Оптимизация алгоритма последовательности Фибоначчи

Категории