數(shù)據(jù)結(jié)構(gòu)上面在講到棧的時(shí)候，順便提了一下遞歸。實(shí)際上遞歸就是用棧來實(shí)現(xiàn)的。在很多算法書上，對于一些用遞歸方式寫成的算法，相應(yīng)的也給出了棧的算法。這里我要把fibonacci數(shù)列分別用遞歸和棧的方式寫出來，由于我以前的算法教材丟失了，而數(shù)據(jù)結(jié)構(gòu)中也沒有給出相應(yīng)的偽碼，所以只有自己從頭寫起了。
首先是fibonacci的遞歸寫法（不是很標(biāo)準(zhǔn)，但是很親切）：
int fib(int value)
{
if(0==value)
return 0;
else
if(1==value)
return 1;
else
{
return fib(value-1)+fib(value-2);
}
}
接下來要把這個(gè)算法轉(zhuǎn)換為使用棧的寫法。
首先進(jìn)行一下分析。遞歸是逆向求結(jié)果的，對于不能求出結(jié)果的函數(shù)，先將運(yùn)行場景壓棧，然后遞歸調(diào)用自己，如果仍然不能出結(jié)果，就再將運(yùn)行場景壓棧，一直到函數(shù)可以返回結(jié)果為止。此時(shí)依次將運(yùn)行場景彈棧，完成運(yùn)行場景，取得返回值，再彈棧......印象中的遞歸調(diào)用過程就是如此。如果我們要自己寫遞歸求fibonacci數(shù)列，就要自己手動(dòng)用程序來模擬這個(gè)過程。我首先準(zhǔn)備一個(gè)棧來存放結(jié)果序列。在這個(gè)結(jié)果序列里面，保證第一個(gè)結(jié)果和第二個(gè)結(jié)果總是可以直接求得的數(shù)值。因?yàn)橹恍枰猲-1和n-2便能求出fib(n)，所以我們在算法中要把多余的n-3彈出，這樣棧內(nèi)的元素個(gè)數(shù)在每一次調(diào)用的過程中逐漸減少，一直到里面只剩下一個(gè)元素，在這個(gè)時(shí)候，剛才彈出的兩個(gè)元素之和就是我們要求的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時(shí)的值，為了強(qiáng)調(diào)壓入的是“結(jié)果”，我將頭兩個(gè)元素彈出再壓入這兩個(gè)值
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 閱讀(803)
評論(0) 編輯 收藏 引用 所屬分類:
我的讀書筆記