f1=3
f2=9
f3=21
f4=51
猜测f(n)=2*f(n-1)+f(n-2)
在纸上打草稿写出f3的情况，然后推出f4的情况（在f3后边加*2或*3就成）
f3 f4 f3 f4 f3 f4
111*3 222*3 333*3
112*2 221*2 331*2
113*2 223*2 332*2
121*2 212*2 313*2
131*2 232*2 323*2
211*3 122*3 133*3
311*3 322*3 233*3
有两种思路（实质是一样的）：
思路1：f4=2*f3+？（仔细观察：？代表的就是*3的个数，而他们的共同特点就是末两位数字相同。去掉他们的最后一位，观察）
11 12 13
21 22 23
31 32 33
这不正是f2的情况吗？好，为什么呢？考虑下，f3末尾两位数字相同的情况是怎么来的？不就是把f2的末尾数字重复一遍吗。
那么，为什么不是3*f2呢？因为前边的2*f3中已经包含了2/3的3*f2了。所以只需再加1个f2就足够了。
即f(n)=2f(n-1)+f(n-2)：
思路2：f4=3*f3 -？（仔细观察：？代表的就是*2的个数，而他们的共同特点就是末两位数字不同）
Problem : 2569 ( 彼岸 ) Judge Status : Accepted
RunId : 5936964 Language : C Author : qq1203456195
Code Render Status : Rendered By HDOJ C Code Render Version 0.01 Beta
RunId : 5936964 Language : C Author : qq1203456195
Code Render Status : Rendered By HDOJ C Code Render Version 0.01 Beta
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <stdio.h>
int
main()
{
int
cas,n,i;
int
seq[50];
seq[1]=3;
seq[2]=9;
seq[3]=21;
for
(i=4;i<41;i++)
seq[i]=(seq[i-1]<<1)+seq[i-2];
scanf
(
"%d"
,&cas);
while
(cas--)
{
scanf
(
"%d"
,&n);
printf
(
"%d\n"
,seq[n]);
}
return
0;
}
|
本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/archive/2012/05/13/2497881.html，如需转载请自行联系原作者
