杭電 HDU 1041 Computer Transformation

Computer Transformation

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 6344    Accepted Submission(s): 2305

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

2
3
        

Sample Output

1
1
        

Source Southeastern Europe 2005  本來想找個簡單題呢，媽的，因為昨天程式設計練習賽 都是簡單題，沒想到竟然碰上了個大數求乘積并求和的問題，又浪費我寶貴時間 一開時 是兩個函數 分别計算成績 然後求和 因為傳回string 不能是引用 運作逾時 逾時代碼：

#include<iostream>
#include<string>
using namespace std;

string  cnt(string &co,string &gq)
{ int i;
 string str;
	int len_co=co.size();
	int len_gq=gq.size();
	int n=abs(len_co-len_gq);
	if(len_co<len_gq)
		for(i=0;i<n;i++)
			co='0'+co;
		else
			for(i=0;i<n;i++)
				gq='0'+gq;
	int jin=0;
	int tmp;
	for(i=len_co-1;i>=0;i--)
	{
		tmp=co[i]-'0'+gq[i]-'0'+jin;
		jin=tmp/10;
		tmp=tmp%10;
		str=char(tmp+'0')+str;
	}
	if(jin)
		str=char(jin+'0')+str;
	return str;
}
string  acm(string &co,string &gq)
{
string str;
	int len_co=co.length();

		int jin=0,tmp;
		for(int j=len_co-1;j>=0;j--)
		{
			tmp=(co[j]-'0'+jin)*2%10;
			jin=(co[j]-'0')*2/10;
	
			str=char(tmp+'0')+str;
		}
		if(jin)
			str=char(jin+'0')+str;
	return cnt(str,gq);
}
	

int main()
{
	int n;
	string ls[1001],str;
	ls[1]="0";
	ls[2]="1";

	for(int i=3;i<=1000;i++)
	
		ls[i]=acm(ls[i-2],ls[i-1]);
	while(cin>>n)
	cout<<ls[n]<<endl;

	return 0;
}
           

兩個函數 合并後 AC！ 代碼：

#include<iostream>
#include<string>
#include<cmath>
using namespace std;

string  acm(string &co,string &gq)
{
	string str,strr;
    int i,j ;
	int len_co=co.length();
	int jin=0,ji=0,tmp,temp;//标志進位 标志結果字元；
		for(j=len_co-1;j>=0;j--)//求乘積
		{
			tmp=((co[j]-'0')*2+jin)%10;
			jin=(co[j]-'0')*2/10;
	
			str=char(tmp+'0')+str;
		}
		if(jin)//跳出循環時 可能jin不是0。
		str=char(jin+'0')+str;
			
	int len_str=str.size();
	int len_gq=gq.size();
	int n=abs(len_str-len_gq);
	if(len_str<len_gq)//數位對齊；
		for( i=0;i<n;i++)
			str='0'+str;
		else
			for(i=0;i<n;i++)
				gq='0'+gq;


	for(i=len_str-1;i>=0;i--)//求和
	{
		temp=str[i]-'0'+gq[i]-'0'+ji;
		ji=temp/10;
		temp=temp%10;
		strr=char(temp+'0')+strr;
	}
	if(ji)
		strr=char(ji+'0')+strr;
	return strr;
}
	

int main()
{
	int n;
	string ls[1001];
	ls[1]="0";
	ls[2]="1";

	for(int i=3;i<=1000;i++)//打表
	
		ls[i]=acm(ls[i-2],ls[i-1]);
	while(cin>>n)
	cout<<ls[n]<<endl;

	return 0;
}