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