HDU-1041大数运算+递归

题目连接

题意：电脑的内存首先是初始化为1.经过一段时间，变成0 和1。接着分别0变为 10，1又变为01。意思就是（1->0 1)(0->1 0)问经过n步。出现相邻的两个零的个数。

分析：

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

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

其递归方程为： f(n)=f(n-1)+2*f(n-2).

如果推出了递归方程，这只是完成了一半。我们看题目就会发现，数据n<=1000，而每步数字个数为2^n这个天文数字，普通的算法绝对过不了。

解决的方法就是：把大数按位存起来。开一个数组就行了，并且，边算边存。

神奇的代码：

 
#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;
}