异想天开

What's the true meaning of light, Could you tell me why

杭电1041

日期:2013-11-08 12:25:23
  
最后更新日期:2013-11-08 12:29:35
原题见杭电1041题。

0 -> 10
1 -> 01
很明显这是个状态机,给定初始状态为1.那么经过n步后,连续0的对数?
分析:
分析两位的状态图:
00 -> 1010
01 -> 1001
10 -> 0110
11 -> 0101
得知仅仅是01才会产生连续的0。计算下个数较小的步数:
1 -> 01 -> 1001 -> 01 10 10 01 -> 10 01 01 10 01 10 10 01 -> ....
汗一个,起初开始5步都算错了,白白浪费2个小时。开始认为每个1隔两步就就产生一对连续的00,而每次变换都会产生一个1(0->10 1->01),后来,经胖子指正,顿感无语。这题的关键点:找到经过相同步骤变换后,形成一对连续的00。而1-> 01 -> 1001 , 00 -> 1010  -> 01 10 01 10 符合条件。定义函数:
f(n): 为第n步后00的对数。
g(n):为第n步1的个数。那么:
f(n) = f(n-2) + g(n-2) ;
g(n) = 2^(n-1)   n从1开始计算
这题真正考察的是大数问题,n最大可以取1000,那么2^998次方这个整数不能用32,64,128来存储了。大数乘法和大数加法。
后记:
错误1:
判断数组大小时,当我在局部作用域将数组传给函数时,大概类似这样:
char bigdigit[1000];
foo(bigdigit)
然后
foo(char src[] )
{
   memset(src,0,sizeof(src));  //这个数组已经退化为指针了
}
错误2:
写字符串串时,忘记申请的长度为字符串长度+1.