添柴1031斐波那契数列

lyt0707

标题:	斐波那契数列
详情:	斐波纳契数列（Fibonacci Sequence），又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21……从第三项开始每一项是前两项的和。 现在输入一个数n，需要求斐波纳契数列第n项的值。

(http://bbs.codeaha.com/problem-1031.html)

这题我用三种方法：1.普通dfs，2.记忆化dfs，3.动态规划。

1.普通dfs，只用想我要求f[n]，需用知道f[n-1]与f[n-2]，一直推下去推到n-1=2，n-2=1时递推完毕，代码如下：

1. #include <cstdio>
   
2. int n;//这里n可以开全局也可以不开
   
3. int dfs(int num)
   
4. {
   
5.        if(num==1 || num==0)//边界值，num=1,0会推出
   
6.        {
   
7.               return num;//return返回到上一个递归
   
8.        }
   
9.        return dfs(num-1)+dfs(num-2); //num=num-1+num-2是斐波那契公式，返回上一个递归
   
10. }
    
11. int main()
    
12. {
    
13.       scanf("%d",&n);
    
14.       printf("%d",dfs(n));
    
15.       return 0;
    
16. }

复制代码

2.记忆化dfs,记忆每个f[n]，把每一个dfs(x-1)记忆到数组f[x-1]使其不被算很多次：

1. [/p][p=26, null, left]#include <cstdio>
   
2. int f[1009];
   
3. int dfs(int x)
   
4. {
   
5.        if(f[x]==0) //如果f[x]没算过，这里已经是边界值了因为算到f[1],f[2]时f[x]==0不成立
   
6.        {
   
7.              f[x]=dfs(x-1)+dfs(x-2);//算一遍
   
8.         }
   
9.         return f[x];//如果f[x]算过，直接return
   
10. }
    
11. int main()
    
12. {
    
13.        int n;
    
14.        f[1]=1;//第一个数于第二个数都设为1。
    
15.        f[2]=1;
    
16.        scanf("%d",&n);
    
17.        printf("%d",dfs(n));
    
18.        return 0;
    
19. }

复制代码

3.动态规划版

1. #include <cstdio>
   
2. #include <cstdlib>
   
3. int main()
   
4. {
   
5.        int f[1009],i,n;
   
6.        f[1]=1;
   
7.        f[2]=1;
   
8.        scanf("%d",&n);
   
9.        for(i=3;i<=n;i++)//一定要从3开始，不然会seg错误
   
10.        {
    
11.                 f[i]=f[i-1]+f[i-1];//斐波那契数列公式，别把状态转移方程想复杂了
    
12.         }
    
13.         printf("%d",f[n]);
    
14.         return 0;
    
15. }

复制代码

啊哈磊

写的非常好

创世菌

动态规划版有错误！

创世菌

1. #include <cstdio>
   
2. int main()
   
3. {
   
4.     int n;
   
5.     scanf("%d",&n);
   
6.     int *f=new int[n];
   
7.     f[0]=f[1]=1;
   
8.     for(int i=2;i<n;i++)
   
9.         f[i]=f[i-1]+f[i-2];
   
10.     printf("%d",f[n-1]);
    
11.     return 0;
    
12. }

复制代码

蓝天之子

这里还有一个方法：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. int main()
   
4. {
   
5.     int a=1,b=1,c,n,i=3;
   
6.     scanf("%d",&n);
   
7.     for(i=3;i<=n;i++)
   
8.     {
   
9.         c=a+b;
   
10.         a=b;
    
11.         b=c;
    
12.     }
    
13.     if(n==0)c=0;
    
14.     else if(n==1||n==2)c=1;
    
15.     printf("%d\n",c);
    
16.     system("pause");
    
17.     return 0;
    
18. }

复制代码