Auf Baidu gibt es viele Antworten auf „Nicht-rekursives Schreiben von Fibonacci“, aber sie sind nicht zufriedenstellend. Erstens ist es zu schwer zu verstehen, und zweitens ist die Leistung ungefähr die gleiche wie bei der Rekursion.
Wenn es um die Fibonacci-Folge geht, egal ob Sie ein unerfahrener Programmierer oder ein technischer Veteran sind, fällt Ihnen als Erstes definitiv die rekursive Schreibmethode ein. Der Unterschied zwischen technischen Veteranen und Programmierneulingen besteht darin, dass sie darüber nachdenken, die Ergebnisse der Rekursion zu speichern, um wiederholte Berechnungen zu reduzieren. Dies sind sehr häufige Operationen, aber haben Sie jemals darüber nachgedacht, dass die Fibonacci-Folge auch nicht rekursiv geschrieben werden kann?
Auf Baidu gibt es viele Antworten auf „Nicht-rekursives Schreiben von Fibonacci“, aber erstens ist es zu schwer zu verstehen, und zweitens ist die Leistung in etwa die gleiche wie bei der Rekursion. Am Anfang wollte ich auch selbst eines schreiben, solange es den Aufrufstapel rekursiver Aufrufe simuliert, aber diese Idee ist etwas selbstverständlich und das geschriebene Programm ist auch sehr kompliziert. Was zu tun? Zu diesem Zeitpunkt kann sich die Tiefendurchquerung des Baums als nützlich erweisen.
Zuerst definieren wir die Baumknoten:
public class Node
{
public Node(long value, bool visited)
{
Value = value;
Visited = visited;
}
public long Value { get; set; }//存放结点的值
public bool Visited { get; set; }
}Dann können wir gerne lernen, wie man den DFS-Stack schreibt
public static long Fblc(int n)
{
Stack<Node> s = new Stack<Node>();
s.Push(new Node(n, false));
long sum = 0;
long[] childrenResultMemo = new long[n+1];
childrenResultMemo[0] = 1;
childrenResultMemo[1] = 1;
//long children = 0;
while (s.Any())
{
var cur = s.Pop();
if (cur.Visited == false)
{
if (childrenResultMemo[cur.Value] == 0)
{
cur.Visited = true;
if (childrenResultMemo[cur.Value - 1] != 0 && childrenResultMemo[cur.Value - 2] != 0)
{
var result = childrenResultMemo[cur.Value - 1] + childrenResultMemo[cur.Value - 2];
childrenResultMemo[cur.Value] = result;
sum += result;
s.Push(cur);
}
else
{
s.Push(cur);
s.Push(new Node(cur.Value - 1, false));
s.Push(new Node(cur.Value - 2, false));
}
}
else
{
sum += childrenResultMemo[cur.Value];//保存子树结果的优化，会有个特殊情况要处理
}
}
}
return sum;
}Die Kernidee des obigen Algorithmus besteht darin, den zu durchlaufen stapeln und den Stapel herausnehmen. Wenn das oberste Element besucht wurde (besucht ist wahr), überspringen Sie es (der obige Code verwendet die Optimierung zum Speichern von Teilbaumergebnissen, es muss ein Sonderfall behandelt werden, der unten detailliert beschrieben wird); andernfalls ist die besuchte Markierung des aktuellen übergeordneten Knotens wahr, was bedeutet, dass er besucht und auf den Stapel verschoben wurde. Anschließend werden alle seine untergeordneten Knoten auf den Stapel verschoben.
Wenn Sie dieser Idee folgen, wird der Code, den Sie schreiben, nicht so aussehen wie oben. Die Codemenge wird jedoch viel kleiner und präziser sein. Die Komplexität des Algorithmus wird jedoch der von rekursiv ähneln Schreiben, da es wiederholte Berechnungen geben wird.
Was sollen wir also tun? Es gibt nur eine Lösung: Raum gegen Zeit austauschen und die Ergebnisse des Teilbaums speichern. Wenn der entsprechende Teilbaum berechnet wurde und Ergebnisse vorliegen, werden wir die Tiefe nicht mehr durchqueren die nächste Ebene verwenden. Wir speichern die Ergebnisse des Teilbaums in einem Array:
long[] childrenResultMemo = new long[n+1];
Wenn der Teilbaum normalerweise bereits Ergebnisse enthält, hätte logischerweise darauf zugegriffen werden müssen. Allerdings gibt es Sonderfälle, bei denen Teilbaum 0 und Teilbaum 1 am Anfang stehen:
childrenResultMemo[0] = 1; childrenResultMemo[1] = 1;
Sammeln Sie einfach die Ergebnisse in den Zweigen dieses Sonderfalls: Wie wäre es mit
sum += childrenResultMemo[cur.Value];
, ist das so? Methode, oder? Selten? Tatsächlich ähnelt der Bewertungsprozess der Fibonacci-Folge einer Tiefendurchquerung des Baums. Solange es sich also um die Implementierung der Tiefendurchquerung handelt, ist dies durchaus machbar.
Verwandte Artikel:
Beispiel für Python-Druck einer Fibonacci-Sequenz
PHP implementiert Fibonacci-Sequenz
Verwandte Videos :
Datenstruktur-Abenteuer – Warteschlangenkapitel
Das obige ist der detaillierte Inhalt vonEs stellt sich heraus, dass die Fibonacci-Folge auch so geschrieben ist, wussten Sie das?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
