Computer Transformation(hdoj 1041)

8116 단어 transform
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


 
Sample Output


step 1:01 step 2:1001 step 3:0110 1001 step 4:1001 0110 0110 1001 step 5:0110 1001 1001 0110 1001 0110 0110 1001
 1 /* ,0 1 1 3 5 11 21 43 85, f(n)=2*f(n-2)+f(n-1),*/
 2 #include<stdio.h>
 3 int a[1001][305]={{0},{0},{1},{1}};
 4 int b[1001]={1};
 5 int calc()/* n 1000,2^1000 long long, , */
 6 {
 7     int i=4;
 8     for(i=4;i<1001;i++)
 9     {
10         int c,j;
11         for(c=0,j=0;j<305;j++)/* b 2*f(n-2)*/
12         {
13             b[j]=b[j]*2+c;/*c */
14             c=b[j]/10;
15             b[j]=b[j]%10;
16         }
17         for(c=0,j=0;j<305;j++)/* 2*f(n-2)+f(n-1) */
18         {
19             a[i][j]=b[j]+a[i-2][j]+c;
20             c=a[i][j]/10;
21             a[i][j]=a[i][j]%10;
22         }
23     }
24 }
25 int main()
26 {
27     int n,i,k=0;
28     calc();
29     while(~scanf("%d",&n))
30     {
31         if(n==1)
32             printf("0");
33         else
34         {
35             k=0;
36             for(i=300;i>=0;i--)
37             {
38                 if(a[n][i]||k)
39                 {    
40                     printf("%d",a[n][i]);
41                     k=1;
42                 }
43             }
44         }
45         printf("
"); 46 } 47 }

좋은 웹페이지 즐겨찾기