天下

记录修行的印记

动态规划算法(3):菲波那契数列

原创作品,允许转载,转载时请务必以超链接形式标明文章

#include "stdafx.h"
using namespace std;

/*
algorithm
在数字上递归表示的问题也可以表示成递归算法,在许多情形下对朴素的穷举搜索得到显著的性能改进。
任何数字递推公式都可以直接翻译成递归算法,但是基本现实是编译器常常不能正确地对待递归算法,结果产生低效的程序,当怀疑可能是这种情况时,
必须再给编译器提供一些帮助,将递归算法重新写成非递归算法,让后者把这些子问题的答案系统地记录在一个表(table)内,
利用这种方法的一种技巧称为动态规划(dynamic programming)。


菲波那契数列指的是这样一个数列: 
1,1,2,3,5,8,13,21…… 
这个数列从第二项开始,每一项都等于前两项之和
*/




unsigned 
int fib1(unsigned int n)
{
    
if (n<=1)
    {
        
return 1;
    }
    
else
    {
        
return fib1(n-1+ fib1(n-2);
    }
}

unsigned 
int fib2(unsigned int n)
{
    
if (n<=1)
    {
        
return 1;
    }
    unsigned 
int fib_n        = 1;
    unsigned 
int fib_n_1    = 1;
    unsigned 
int fib_n_2    = 1;

    
for (int i=2;i<=n;i++)
    {
        fib_n      
= fib_n_1 + fib_n_2;
        fib_n_2   
= fib_n_1;
        fib_n_1   
= fib_n;
    }
    
return fib_n;
}

int main()
{
    
for (int i=1;i<11;i++)
    {
        printf(
"fib1(%u)=%u \r\n",i,fib1(i));
        printf(
"fib2(%u)=%u \r\n",i,fib2(i));
    }
    system(
"pause");
    
return 0;
}   

 

posted on 2013-03-21 16:25 天下 阅读(367) 评论(0)  编辑 收藏 引用 所属分类: 算法


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


<2013年3月>
242526272812
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿(4)

随笔分类(378)

随笔档案(329)

链接

最新随笔

搜索

最新评论