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 : AcceptedRunId : 5936964 Language : C Author : qq1203456195Code Render Status : Rendered By HDOJ C Code Render Version 0.01 Beta #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; }
转载于:https://www.cnblogs.com/CheeseZH/archive/2012/05/13/2497881.html
