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