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
  
  

Southeastern Europe 2005

思路：

/*本题规律题:
00只能由01推到,即01->1001->00
01只能由1,00推到,即1->01,00->1010->01.
现设a[n]表示n秒时1的个数，
b[n]表示n秒时00的个数，
c[n]表示n秒时01的个数，
由题知0,1过一秒都会产生一个1，?
所以a[n+1]=2^n.....0秒1个数，1秒2*1个数，2秒2*1*2个数，...n秒2*1*2*2*2..*2个数=2^n.
b[n+1]=c[n];
c[n+1]=a[n]+b[n],
所以b[n]=c[n-1]=a[n-2]+b[n-2]=2^(n-3)+b[n-2].
其实本题多写几个样例就能发现另一个规律b[n]=2*b[n-2]+b[n-1].?
注意本题大数相加.
*/（摘自该题后面的讨论区）

代码如下：

#include<stdio.h>
#define max 1010
int s[max][max/2]={{0},{0},{1},{1}};//i 表示多少位，j表示计算出的数字是多少位的 
int p[max]={1};//计算2的相应的阶乘
void calculate()
{
	for(int i=4;i<max-1;i++)
	{
		for(int c=0,j=0;j<=300;j++)//a[i]=2^(i-1) 
		{
			p[j]=p[j]*2+c;
			c=p[j]/10;
			p[j]=p[j]%10;
		}
		for(int c=0,j=0;j<=300;j++)//b[i]=a[i-2]+b[i-2] 
		{
			s[i][j]=p[j]+s[i-2][j]+c;
			c=s[i][j]/10;
			s[i][j]%=10;
		}
	}
}
int main()
{
	int n;
	calculate();//调用函数
	while(~scanf("%d",&n))
	{
		int flag=0;//flag用来标记，并消除输出的前导零
		if(n==1)
		{
			printf("0n");
		}
		else
		{
			for(int i=300;i>=0;i--)//倒序输出，消除前导零 
			{
				if(s[n][i]||flag)
				{
					printf("%d",s[n][i]);
					flag=1;
				}
			}
			printf("n");
		}
	}
	return 0;
}