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

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

몇일 전 인터뷰에서 피보나치 수열의 구현과 최적화에 대해 질문을 받았는데요, 오랫동안 현장에서 막혀서 이제 요약하겠습니다(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;
    }

Summary

  사실 대부분의 사람들은 피보나치 수열을 계산할 때 재귀적 방법을 생각하지만, 이벤트 복잡도 측면에서 좋은 방법이 아니기 때문에 우리의 최적화 아이디어는 공간을 활용하는 것일 수도 있습니다. 다음에 계산을 반복하지 않도록 재귀에서 생성된 값을 저장하는 시간입니다.

위 내용은 JavaScript에서 피보나치 수열을 구현하는 네 가지 방법 소개(코드)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!