2013
11-26

# Computer Transformation

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?

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

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

2
3

1
1

此题，很明显就是找规律，不可能去模拟。多画几个，就大致可推出方程了。

(1,0)  ,(2,1),(3,1),(4,3),(5,5),(6,11)………(说明：第一个数代表步数，第二个出现两个零的个数)

#include<cstdio>
#define INF 0x3fff

const int M=1002;
int num[M][M/2]={{0},{0},{1},{1}}; //给前面的四个直接赋值。
int b[M]={1};
void calc()    //巧妙！
{
for(int i=4;i<M-1;++i){
for(int c=0,j=0;j<400;++j){
b[j]=b[j]*2+c;
c=b[j]/10;
b[j]=b[j]%10;
}
for(int c=0,j=0;j<400;++j){
num[i][j]=b[j]+num[i-2][j]+c;
c=num[i][j]/10;
num[i][j]=num[i][j]%10;    //存取余数。（降位）
}
}
}
int main()
{
int n;
calc();
while(~scanf("%d",&n)){
bool flag=false;
if(n==1)
puts("0");
else{
for(int i=300;i>=0;--i){
if(num[n][i]||flag){
printf("%d",num[n][i]);
flag=true;
}
}
puts("");
}
}
return 0;
}