百度下“斐波拉契的非遞歸寫法”,也有不少的答案,但是並不令人滿意,首先是太複製難懂,其次是性能和遞歸差不多。
一說到斐波拉契數列,無論是程序菜鳥,還是技術老手,首先想到的,肯定是遞歸寫法。然後,技術老手與程式菜鳥不同的地方,就是會想到將遞歸的結果存起來以減少重複計算。這些都是些很常規的操作,但是你有沒有想過,斐波拉契數列還能用非遞歸的方法來寫?
百度下“斐波拉契的非遞歸寫法”,也有不少的答案,但是並不令人滿意,首先是太複製難懂,其次是性能和遞歸差不多。一開始我也想自己寫個,只要模擬遞歸呼叫的呼叫棧不就行了嘛,不過這種想法真是有點想當然了,寫出來的程式也很複雜。怎麼辦呢?這時候,樹的深度優先遍歷就可以派上用場了。
首先,我們定義樹結點:
public class Node { public Node(long value, bool visited) { Value = value; Visited = visited; } public long Value { get; set; }//存放结点的值 public bool Visited { get; set; } }
然後,我們就可以愉快地上DFS的棧寫法啦
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; }
上述演算法的核心思想是,遍歷棧,pop出棧頂元素,如果已經訪問過(visited為true),就跳過(上面代碼由於採用了保存子樹結果的優化,會有個特殊情況要處理,下文會詳述);否則,將當前父結點的visited標記為true,代表已訪問過,並push到棧;然後將其子結點都push到棧。
如果按照這個思路,寫出來的程式碼不會是上面那個樣子的,程式碼量少很多也簡潔得多,不過演算法複雜度就會像遞歸寫法差不多,因為存在重複計算。
那怎麼辦呢,解決辦法只有一個,空間換時間,將子樹的結果存起來,如果對應子樹已經計算過有結果,就不再往下一層的深度遍歷了,直接使用結果。我們將子樹結果保存在了一個陣列裡面:
long[] childrenResultMemo = new long[n+1];
通常如果子樹已經有結果,按邏輯來說應該就會被存取過。不過存在特例,就是一開始的子樹0和子樹1:
childrenResultMemo[0] = 1; childrenResultMemo[1] = 1;
只需在這個特例的分支裡面累加結果即可:
sum += childrenResultMemo[cur.Value];
怎麼樣,這種寫法是不是很少見?其實斐波拉契數列的求值過程就像是樹的深度優先遍歷。所以只要是深度優先遍歷的實現,完全就是可行的。
相關文章:
相關影片:
以上是原來斐波拉契數列還有這種寫法,你知道嗎?的詳細內容。更多資訊請關注PHP中文網其他相關文章!