JavaScript에서 피보나치 수열을 구현하는 네 가지 방법 소개(코드)-JS 튜토리얼-php.cn

JavaScript에서 피보나치 수열을 구현하는 네 가지 방법 소개(코드)

不言

풀어 주다： 2019-03-12 16:11:42

앞으로

12349명이 탐색했습니다.

이 글은 자바스크립트에서 피보나치 수열을 구현하는 네 가지 방법(코드)을 소개합니다. 참고할 만한 가치가 있으니 도움이 필요한 분들에게 도움이 되길 바랍니다.

몇일 전 인터뷰에서 피보나치 수열의 구현과 최적화에 대해 질문을 받았는데요, 오랫동안 현장에서 막혀서 이제 요약하겠습니다(js를 사용하여 구현).

주제 소개

피보나치 수열은 황금분할 수열이라고도 하는데, 1,1,2,3,5,8,13,21,34..., it 과 같은 수열을 말합니다. 다음 재귀 방법 정의는 다음과 같습니다. F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) (n>=2, n은 양의 정수입니다. ) , 피보나치 함수를 구현하려면 js를 사용하세요.

방법 1: 재귀적 구현

질문의 재귀에서 영감을 받아 재귀적으로 구현할 수 있습니다. 코드는 다음과 같습니다.

function fibonacci(n){
        if(n < 0) throw new Error(&#39;输入的数字不能小于0&#39;);
        if(n==1 || n==2){
            return 1;
        }else{
            return fibonacci1(n-1) + fibonacci1(n-2);
        }
    }

로그인 후 복사

장점: 코드가 비교적 간결하고 이해하기 쉽습니다.
단점: 숫자가 그 이유는 F(9)를 계산할 때 F(8)과 F(7)을 계산해야 하지만, F(7)과 F(6)을 계산해야 하기 때문입니다. F(8)을 계산하면 F(7)을 반복해서 계산하면 불필요한 낭비가 발생하므로 이 방법은 별로 좋지 않습니다.

방법 2: 클로저를 사용하여 각 재귀 값 저장

방법 1에서 일반적인 재귀를 사용하면 불필요한 낭비가 발생하므로 매번 생성되는 재귀 값을 저장하는 것이 먼저 생각되어야 합니다. 직접 사용하세요. 다음번에는 코드는 다음과 같습니다.

function fibonacci(n){
        if(n < 0) throw new Error(&#39;输入的数字不能小于0&#39;);
        let arr = [0,1];//在外部函数中定义数组，内部函数给数组添加值
        function calc(n){
            if(n<2){
                return arr[n];
            }
            if(arr[n] != undefined){
                return arr[n];
            }
            let data = calc(n-1) + calc(n-2);//使用data将每次递归得到的值保存起来
            arr[n] = data;//将每次递归得到的值放到数组中保存
            return data;
        }
        return calc(n);
    }

로그인 후 복사

방법 3: 배열 구현을 직접 사용(동적 프로그래밍)

아이디어는 방법 2와 유사합니다. 이후의 반복 계산을 피하기 위해 계산된 값을 저장해야 합니다. . 배열을 사용하여 직접 저장할 수 있습니다.

function fibonacci(n){
        var a = [0,1,1];
        if(n < 0) throw new Error(&#39;输入的数字不能小于0&#39;);
        if(n >= 3){
            for(var i=3;i<=n;i++){
                a[i] = a[i-1]+a[i-2];
            }
        }
        return a[n];
    }

로그인 후 복사

방법 4: 변수를 직접 사용하여 구현

배열을 사용하여 저장하는 것에 비해 변수를 사용하면 총 3개의 변수만 있으므로 메모리를 크게 낭비하지 않지만 단점도 있습니다. 계산된 값과 이전 두 값이 저장되면 이전 값이 대체됩니다.

function fibonacci(n){
        var pre = 0;//表示前一个值
        var cur = 1;//表示后一个值
        var data;//表示当前值

        if(n < 0) throw new Error(&#39;请输入大于0的值！&#39;);
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(n > 2){
            for(var i=2;i<=n;i++){
                data = pre + cur;
                pre = cur;
                cur = data;
            }
        }
        return data;
    }

로그인 후 복사