1041.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

/*将序列分成对半看
列出由1开始和由0开始的序列，设f(n),g(n)为两个序列的零对的对数
flag(n):当n为奇数＝0，n为偶数为1;此函数为左右序列合并时中间的一对数配对情况
f(n)中间一对不会出现11；g(n)中间一对不会出现00；所以可列出递推式：
f(n)=g(n-1)+flag(n)+f(n-1);
g(n)=f(n-1)+g(n-1);
g(n-1)=f(n-2)+g(n-2);
代入得：f(n)=f(n-2)+g(n-2)+flag(n)+f(n-1);
            =2f(n-2)+2g(n-2)+flag(n)+flag(n-1);
            =2f(n-1)+flag(n)-flag(n-1);*/
#include<iostream>
#include<string>
using namespace std;
char s[1001][1001];
void main()
{
    int i,j,k,n;
    strcpy(s[2],"1");
    for(i=3;i<1001;i++){
        int len=strlen(s[i-1]);
        int temp[1001];
        int re[1001];
        for(j=0;j<len;j++)
            temp[j]=s[i-1][len-j-1]-'0';
        int left=0;
        for(j=0;j<len;j++){
            re[j]=(temp[j]*2+left)%10;
            left=(temp[j]*2+left)/10;
        }
        if(left>0){
            re[len]=left;
            len++;
        }
        if(i%2){
            for(j=0;j<len;j++)
                if(re[j]>=1){
                    re[j]--;
                    break;
                }
            for(k=0;k<j;k++)
                re[k]=9;
        }
        else{
            for(j=0;j<len;j++)
                if(re[j]<9){
                    re[j]++;
                    break;
                }
            for(k=0;k<j;k++)
                re[k]=0;
        }
        for(j=0;j<len;j++)
            s[i][j]=re[len-1-j]+'0';
    }
    while(cin>>n)
        if(n<2)
            cout<<"0\n";
        else
            cout<<s[n]<<endl;
}