Introduction à quatre méthodes d'implémentation de la séquence de Fibonacci en JavaScript (code)

Ce que cet article vous apporte est une introduction (code) aux quatre méthodes d'implémentation de la séquence de Fibonacci en JavaScript. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. .

Il y a quelques jours, lors de l'interview, on m'a interrogé sur l'implémentation et l'optimisation de la séquence de Fibonacci. La scène était bloquée depuis longtemps. Je vais maintenant la résumer (implémentée en utilisant js).

Introduction au titre

La séquence de Fibonacci est aussi appelée séquence du nombre d'or, qui fait référence à une telle séquence : 1,1,2,3,5,8,13,21 ,34. ..., il a la définition de méthode récursive suivante : F(1)=1,F(2)=1,F(n)=F(n-1)+F(n-2)(n> ;=2, n est un entier positif), veuillez utiliser js pour implémenter la fonction Fibonacci.

Méthode 1 : Implémentation récursive

Inspirée de la récursion dans la question, elle peut être implémentée de manière récursive Le code est le suivant :

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

Avantages : Comparaison de code. Simple et facile à comprendre ;
Inconvénients : Lorsque le nombre est trop grand, il deviendra particulièrement lent. La raison en est que F(8) et F(7) doivent être calculés lors du calcul de F(9), mais quand. calcul de F(8) Pour calculer F(7) et F(6), F(7) sera calculé à plusieurs reprises. Des calculs répétés à chaque fois entraîneront un gaspillage inutile, cette méthode n'est donc pas très bonne.

Méthode 2 : utilisez la fermeture pour enregistrer chaque valeur de récursion

  De la méthode 1, nous pouvons voir que l'utilisation de la récursivité ordinaire entraînera un gaspillage inutile, donc la première chose à laquelle nous pensons devrait être de sauvegarder chacune valeur de récursion. La valeur récursive générée cette fois est enregistrée et peut être utilisée directement la prochaine fois. Le code est le suivant :

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

Méthode 3 : Utilisation directe de l'implémentation du tableau (programmation dynamique)

<🎜. > L'idée est similaire à la méthode 2. Afin d'éviter des calculs répétés ultérieurs, les valeurs calculées doivent être enregistrées. Nous pouvons directement utiliser un tableau pour les enregistrer.

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

Méthode 4 : utiliser directement des variables pour implémenter

  Par rapport à l'utilisation de tableaux pour stocker, l'utilisation de variables ne gaspillera pas autant de mémoire, car il n'y en aura que 3 au total. Une variable, mais il présente également l'inconvénient de ne pouvoir enregistrer que la dernière valeur calculée et les deux premières valeurs, et les valeurs précédentes seront remplacées.

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

Résumé

  En fait, la plupart des gens pensent à la méthode récursive lors du calcul de la séquence de Fibonacci, mais en termes de complexité des événements, ce n'est pas une bonne méthode, alors notre optimisation. L'idée peut être d'utiliser l'espace pour échanger du temps, c'est-à-dire de sauvegarder la valeur générée par récursion pour éviter des calculs répétés la prochaine fois.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!