hdu_1041(Computer Transformation) 大数加法模板+找规律

Computer Transformation

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8367    Accepted Submission(s): 3139

Problem Description

A sequence consisting of one digit, the number 1 is initially written into a computer. At each successive time step, the computer simultaneously tranforms each digit 0 into the sequence 1 0 and each digit 1 into the sequence 0 1. So, after the first time step, the sequence 0 1 is obtained; after the second, the sequence 1 0 0 1, after the third, the sequence 0 1 1 0 1 0 0 1 and so on.

How many pairs of consequitive zeroes will appear in the sequence after n steps?

Input

Every input line contains one natural number n (0 < n ≤1000).

Output

For each input n print the number of consecutive zeroes pairs that will appear in the sequence after n steps.

Sample Input

2
3

Sample Output

1
1

Source

Southeastern Europe 2005

规律：数串的右边一般是上一个数串，数串的左半边是上两个数串+上一个数串的左半区

 #include<cstdio>
 #include<cstring>
 #include<string>
 #include<algorithm>
 #include<iostream>
 using namespace std;
 #define ll long long
 const int N = ;
 struct Node{
     string sum;
     string leftsum;
     int left,right;//zuo ban qu
 }node[N];

 string add(string s1,string s2){ //大数 s1 + s2
        if(s1.length()<s2.length()){
             string temp=s1;
             s1=s2;
             s2=temp;
        }
        for(int i=s1.length()-,j=s2.length ()-;i>=;i--,j--){
             s1[i]=char(s1[i]+( j>= ? s2[j]-'' : ));
             if(s1[i]-''>=) {
                 s1[i]=char( (s1[i]-'')%+'' );
                 if(i) s1[i-]++;
                 else  s1=""+s1;
             }
        }
        return s1;
 }

 void init()
 {
    /* for(int i = 0; i < N; i++){
         node[i].sum ="0";
         node[i].leftsum = "0";
     }*/
     node[].sum = "", node[].left = , node[].right = , node[].leftsum = "";
     node[].sum = "", node[].left = , node[].right = , node[].leftsum = "";
     for(int i = ; i < N; i++)
     {
         node[i].leftsum = add(node[i-].sum,node[i-].leftsum);
         node[i].left = node[i-].left;
         node[i].right = node[i-].right;
         node[i].sum=add(node[i-].sum,node[i].leftsum);
         if(node[i].right==node[i-].left&&node[i].right == )  node[i].sum = add(node[i].sum,"");
     }
 }
 int main()
 {
     int n;
     init();
     while(~scanf("%d",&n)){
        // printf("%s\n",node[n].sum);
        cout<<node[n].sum<<endl;
     }
     return ;
 }

大数加法模板

 string add(string s1,string s2){ //大数 s1 + s2
        if(s1.length()<s2.length()){
             string temp=s1;
             s1=s2;
             s2=temp;
        }
        for(int i=s1.length()-,j=s2.length ()-;i>=;i--,j--){
             s1[i]=char(s1[i]+( j>= ? s2[j]-'' : ));
             if(s1[i]-''>=) {
                 s1[i]=char( (s1[i]-'')%+'' );
                 if(i) s1[i-]++;
                 else  s1=""+s1;
             }
        }
        return s1;
 }