Einführung in vier Methoden zur Implementierung der Fibonacci-Sequenz in JavaScript (Code)

Dieser Artikel bietet Ihnen eine Einführung (Code) in die vier Methoden zur Implementierung der Fibonacci-Folge in JavaScript. Ich hoffe, dass er Ihnen als Referenz dienen wird. .

Vor ein paar Tagen wurde ich während des Interviews nach der Implementierung und Optimierung der Fibonacci-Sequenz gefragt. Jetzt fasse ich sie zusammen.

Titeleinleitung

Die Fibonacci-Folge wird auch als Goldene-Schnitt-Folge bezeichnet, die sich auf eine solche Folge bezieht: 1,1,2,3,5,8,13,21,34. ..., es hat die folgende rekursive Methodendefinition: F(1)=1,F(2)=1,F(n)=F(n-1)+F(n-2)(n> ;=2, n ist eine positive ganze Zahl. Verwenden Sie bitte js, um die Fibonacci-Funktion zu implementieren.

Methode 1: Rekursive Implementierung

Inspiriert durch die Rekursion in der Frage kann sie rekursiv implementiert werden. Der Code lautet wie folgt:

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

Vorteile: Der Code ist relativ einfach und leicht zu verstehen;
Nachteile: Wenn die Zahl zu groß ist, wird sie besonders langsam. Der Grund dafür ist, dass Sie bei der Berechnung von F(8) und F(7) berechnen müssen Wenn Sie F(8) berechnen, müssen Sie F(7) und F(6) berechnen. F(7) wird jedes Mal wiederholt berechnet, was zu unnötigem Abfall führt, daher ist diese Methode nicht sehr gut.

Methode 2: Verwenden Sie den Abschluss, um jeden Rekursionswert zu speichern

  Anhand von Methode 1 können wir erkennen, dass die Verwendung einer gewöhnlichen Rekursion unnötigen Abfall verursacht. Daher sollten wir als Erstes daran denken, jeden einzelnen Wert zu speichern Rekursionswert. Der dieses Mal generierte rekursive Wert wird gespeichert und kann beim nächsten Mal direkt verwendet werden. Der Code lautet wie folgt:

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

Methode 3: Direkte Verwendung der Array-Implementierung (dynamische Programmierung)

Die Idee ähnelt Methode 2. Um zu vermeiden, dass nachfolgende wiederholte Berechnungen erforderlich sind, müssen die berechneten Werte gespeichert werden. Wir können sie direkt mit einem Array speichern.

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

Methode 4: Verwenden Sie Variablen direkt zum Implementieren

  Im Vergleich zur Verwendung von Arrays zum Speichern verschwendet die Verwendung von Variablen nicht so viel Speicher, da insgesamt nur 3 Variablen vorhanden sind Es gibt auch Nachteile: Es können nur der zuletzt berechnete Wert und die ersten beiden Werte gespeichert werden, und die vorherigen Werte werden ersetzt.

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

Zusammenfassung

  Tatsächlich denken die meisten Leute bei der Berechnung der Fibonacci-Folge an die rekursive Methode, aber im Hinblick auf die Ereigniskomplexität ist sie keine gute Methode. Unsere Optimierungsidee könnte Es besteht darin, den Raum zum Austauschen der Zeit zu verwenden, d. h. die durch die Rekursion generierten Werte zu speichern, um beim nächsten Mal wiederholte Berechnungen zu vermeiden.

Das obige ist der detaillierte Inhalt vonEinführung in vier Methoden zur Implementierung der Fibonacci-Sequenz in JavaScript (Code). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!