数据结构上面在讲到栈的时候,顺便提了一下递归。实际上递归就是用栈来实现的。在很多算法书上,对于一些用递归方式写成的算法,相应的也给出了栈的算法。这里我要把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 阅读(789)
评论(0) 编辑 收藏 引用 所属分类:
我的读书笔记