【POJ1953】World Cup Noise(动态规划,斐波那契数列)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 04 月 20 日
/*设f[i]表示长度为i的以0结尾的合法队列个数 
*设g[i]表示长度为i的以1结尾的合法队列个数 
*显然有 
*f[i]=f[i-1]+g[i-1];  (1) 
*g[i]=f[i-1];         (2) 
*(2)代入(1)即 
*f[i]=f[i-1]+f[i-2]; 
*最终合法队列总个数为f[n]+g[n]即f[n]+f[n-1]=f[n+1] 
*即求斐波那契数列的第n+1项 
*1,2,3,5,8,13,21.............*/  
#include<cstdio>  
using namespace std;  
long long f[47]={1,1};  
int main()  
{  
    int n,i,temp;  
    for (i=2;i<=46;i++)  
        f[i]=f[i-1]+f[i-2];  
    scanf("%d",&n);  
    for (i=1;i<=n;i++)  
    {  
        scanf("%d",&temp);  
        if(f[0]==0) printf("Scenario #%d:\n0\n\n",i);  
        else printf("Scenario #%d:\n%lld\n\n",i,f[temp+1]);  
    }  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期二, 2017 年 10 月 24 日