hdu 1041（Computer Transformation）（找規律，二維數組大數）

Computer Transformation

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6025 Accepted Submission(s): 2193

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

思路： /*本題規律題:
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
#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=0;i--)//倒序輸出，消除前導零 
			{
				if(s[n][i]||flag)
				{
					printf("%d",s[n][i]);
					flag=1;
				}
			}
			printf("\n");
		}
	}
	return 0;
}