數據結構上面在講到棧的時候，順便提了一下遞歸。實際上遞歸就是用棧來實現的。在很多算法書上，對于一些用遞歸方式寫成的算法，相應的也給出了棧的算法。這里我要把fibonacci數列分別用遞歸和棧的方式寫出來，由于我以前的算法教材丟失了，而數據結構中也沒有給出相應的偽碼，所以只有自己從頭寫起了。
首先是fibonacci的遞歸寫法（不是很標準，但是很親切）：
int fib(int value)
{
if(0==value)
return 0;
else
if(1==value)
return 1;
else
{
return fib(value-1)+fib(value-2);
}
}
接下來要把這個算法轉換為使用棧的寫法。
首先進行一下分析。遞歸是逆向求結果的，對于不能求出結果的函數，先將運行場景壓棧，然后遞歸調用自己，如果仍然不能出結果，就再將運行場景壓棧，一直到函數可以返回結果為止。此時依次將運行場景彈棧，完成運行場景，取得返回值，再彈棧......印象中的遞歸調用過程就是如此。如果我們要自己寫遞歸求fibonacci數列，就要自己手動用程序來模擬這個過程。我首先準備一個棧來存放結果序列。在這個結果序列里面，保證第一個結果和第二個結果總是可以直接求得的數值。因為只需要n-1和n-2便能求出fib(n)，所以我們在算法中要把多余的n-3彈出，這樣棧內的元素個數在每一次調用的過程中逐漸減少，一直到里面只剩下一個元素，在這個時候，剛才彈出的兩個元素之和就是我們要求的fibonacci(n)。
下面是算法：
int fibByStack(int value)
{
int currentValue;
currentValue=value;
while(currentValue>=0)
{
fibStack.push(currentValue);
currentValue--;
}
fibStack.pop();
fibStack.pop();
//1和0是n=1和n=0時的值，為了強調壓入的是“結果”，我將頭兩個元素彈出再壓入這兩個值
fibStack.push(1);
fibStack.push(0);
while(true)
{
int topValue1,topValue2
topValue1=fibStack.top();
fibStack.pop();
topValue2=fibStack.top();
fibStack.pop();
if(1==fibStack.size())
return topValue1+topValue2;
fibStack.pop();
fibStack.push(topValue1+topValue2);
fibStack.push(topValue2);
}
}
posted on 2007-06-17 17:19
littlegai 閱讀(802)
評論(0) 編輯 收藏 引用 所屬分類:
我的讀書筆記