首页 > 代码库 > poj 1953 world cup noise

poj 1953 world cup noise

题目大意:给出一个数n,求n位二进制中有多少个数不包含相邻的1。

思路:推出前3项后就可以发现满足斐波那契数列。先用数组记录下1~n位的结果,再通过输入的值访问相应下标的元素的值即可。

#include<iostream>
#include<stdio.h>
#include<string.h>

using namespace std;
int bit[50];


void calc()
{
    int i;
    bit[1]=2;
    bit[2]=3;//将特殊的两个值记录
    for(i=3;i<50;i++)
        bit[i]=bit[i-1]+bit[i-2];//先产生50位的结果,由于用数组记录,所以不需要通过递归进行多余的重复计算(动态规划)
    /*if(a[m]!=0)
        cnt=a[m-1]+a[m-2];
    else{
        cnt=calc(m-1)+calc(m-2);
        a[k++]=cnt;*/



}
int main(){
    int t,flag=0;
    cin>>t;
    calc();
    while(t--)
    {
        int s;
        cin>>s;
        flag++;

        printf("Scenario #%d:\n",flag);
        printf("%d\n\n",bit[s]);//访问相应的下标即可

    }
    return 0;
}

 

poj 1953 world cup noise