随笔 - 181  文章 - 15  trackbacks - 0
<2009年2月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
1234567

常用链接

留言簿(1)

随笔分类

随笔档案

My Tech blog

搜索

  •  

最新评论

阅读排行榜

评论排行榜

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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理