HNUST 20120214(递推专题)-解题报告

1、2022-2-201Derson Xiang解题报告解题报告HNUST 20120214（递推专题）（递推专题）2022-2-202一只小蜜蜂一只小蜜蜂nhttp:/ (roadsi)n相当于一个fib数列： roadsi=roadsi-1+roadsi-2;2022-2-203Hdoj_2044源代码：源代码：n#includenint main()nint i,n,a,b;n_int64 roads51=1,1;nfor(i=2;i3时，求f(n)。在涂色第n个格子时，考虑2种情况：n1）若第n-1个格子和第一个格子色不同，则涂法为f(n-1)；n2）若第n-1个格子和第1个格子相同，则第

2、n-2个格子和第1个格子必然不同，此时为f(n-2)。再乘第n个格子的颜色数，很显然第n个格子可以是第1个格子（即第n-2个格子）的颜色外的另外两种，这样涂法为2*f(n-2)；n因此总的情况为f(n)=f(n-1)+2*f(n-2);2022-2-205Hdoj_2045源代码：源代码：n#include nint main()n int n,i; n _int64 a51; n a1=3; n a2=6; n a3=6; n for(i=4;i=50;i+) n ai=ai-1+2*ai-2; n while(scanf(%d,&n)!=EOF) n printf(%I64dn,a

3、n); n 2022-2-206骨牌铺方格骨牌铺方格nhttp:/ nint main()nnint i,num;n_int64 f52;nf1 = 1;nf2 = 2;nf3 = 3;nfor(i=4; i=50; +i)nfi = fi-1+fi-2;nwhile(scanf(%d, &num) != EOF)nprintf(%I64dn, fnum);nreturn 0;n2022-2-208阿牛的阿牛的EOF牛肉串牛肉串nhttp:/ nint main()n int n = 0;n while(scanf(%d,&n)!=EOF)n int j=2;n_int64 f

4、 = 0, f1 = 3, f2 = 8;nif(n=1) f = f1;nif(n=2) f = f2;nwhile(jn)nf = 2*(f2 + f1);nf1 = f2;nf2 = f;nj+;nnprintf(%I64dn, f);n n return 0;n2022-2-2010汉诺塔汉诺塔III （递推题）（递推题）nhttp:/ 把n 个盘子从A 间接(不能把盘子直接从A 移到C )移到C 需要以下五步: 1. 把n - 1 个盘子间接从A 移到C，移动次数：f(n - 1) 2. 把最大的盘子从A 移到B，移动次数： 1 3. 把n - 1 个盘子间接从C 移到A,移动次数：

5、 f(n - 1) 4. 把最大的盘子从B 移到C，移动次数： 1 5. 把n - 1 个盘子间接从A 移到C，移动次数： f(n - 1) 易得f(n) = 3 *f(n - 1) + 2, f(1) = 2;2022-2-2011ABC1n-1nABC(1)n1n-1ABC(2)n1n-1ABC1n-1n(3)ABC1n-1n(4)ABC(5)n1n-12022-2-2012Hdoj_2064源代码：源代码：#include int main()int n;_int64 num36;num1 = 2;for(int i=2; i36; +i)numi = numi-1*3+2;while(

6、scanf(%d, &n) != EOF)printf(%I64dn, numn);return 0; 2022-2-2013神、上帝以及老天爷（错排题）神、上帝以及老天爷（错排题）nhttp:/ nhttp:/ = (n - 1) * f(n - 1) + f(n - 2) n 错排公式！2022-2-2015Hdoj_2048源代码：源代码：n#include nint main()nint nCases;n_int64 fib22;n_int64 pala22;npala1 = 0;npala2 = 1;nfib1 = 1;nfib2 = 2;nfor(int i = 3; i

7、n / 2 的错排方法.错排公式 : F ( n ) = ( n - 1 ) * ( F(n-1) + F ( n - 2 ) ) 2022-2-2017Hdoj_2068源代码：源代码：#include _int64 Com(int m, int n ) / 取 Cmn 的组合数 _int64 up = 1,down = 1; if(n=0) return 1; for(int i=0; in; +i ) up *= m-i; down *= i+1; return up/down;int main() int nNum; _int64 cuopai30=0,0,1,2; for(int i=4; i=25; +i) cuopaii = (i-1)*(cuopaii-1+cuopaii-2); while(scanf(%d, &nNum) & nNum) _int64 sum = 0; for(int i=1; i=nNum/2; +i) sum += Com(nNum, i)*cuopaii;/从nNum中 /取i