首页 > ACM题库 > HDU-杭电 > HDU 1041 Computer Transformation-高精度-[解题报告] C++
2013
11-26

HDU 1041 Computer Transformation-高精度-[解题报告] C++

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 和1。接着分别0变为 10,1又变为01。意思就是(1->0 1)(0->1 0)问经过n步。出现相邻的两个零的个数。

分析:

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

 (1,0)  ,(2,1),(3,1),(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;
}