所谓递推,是指从已知的初始条件出发,依据某种递推关系,逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定,或是通过对问题的分析与化简后确定。关于递推的知识可以参阅本博客中随笔“递推(一):递推法的基本思想”。
HDU 2044~2050这7道题是针对初学者进行递推学习的专项练习,下面给出它们的AC程序供参考。
HDU 2044:一只小蜜蜂
不妨将图示的蜂箱结构看成从1--—2——-3——…的一个“W”型楼梯。蜜蜂只能爬向右侧相邻的蜂房,不能反向爬行。可以等效地看成蜜蜂每次上楼梯可以走一级,也可以走两级。
易得递推公式 : f[n]=f[n-1]+f[n-2] (n>2) f[1]=1 f[2]=2。
#include <stdio.h> int main() { int n,a,b,i; __int64 f[51]={0,1,2}; for (i=3;i<=50;i++) f[i]=f[i-1]+f[i-2]; scanf("%d",&n); while (n--) { scanf("%d%d",&a,&b); printf("%I64d\n",f[b-a]); } return 0; }
HDU 2045 不容易系列之(3)—— LELE的RPG难题
设满足要求的n个方格的涂色方法数为F(n)。
因为RPG有三种颜色,可以先枚举出当方格数为1、2、3时的涂法种数。
显然,F(1)=3 (即R、P、G三种)
F(2)=6 (即RP、RG、PR、PG、GR、GP六种)
F(3)=6 (即RPG、RGP、PRG、PGR、GRP、GPR六种)
当方格的个数大于3时,n个方格的涂色方案可以由n-1方格的涂色方案追加最后一个方格的涂色方案得出,分两种情况:
(1)对于已按要求涂好颜色的n-1个方格,在F(n-1)种合法的涂色方案后追加一个方格(第n个方格),由于合法方案的首尾颜色不同(即第n-1个方格的颜色不与第1个方格的相同),这样,第n个方格的颜色也是确定的,它必定是原n-1个方格的首尾两种颜色之外的一种,因此,在这种情况下的涂色方法数为F(n-1)。
(2)对于已按要求涂好颜色的n-2个方格,可以在第n-1个方格中涂与第1个方格相同的颜色,此时由于首尾颜色相同,这是不合法的涂色方案,但可以在第n个方格中涂上一个合法的颜色,使其成为方格长度为n的合法涂色方案(注意:当n等于3时,由于第1(3-2)个方格与第2(3-1)个方格颜色相同,第3个方格不论怎样涂都不会合法,因此递推的前提是n大于3),在第n个方格中可以涂上两种颜色(即首格外的两种颜色,因为与它相连的第n-1个方格和第1个方格的颜色是一样的),因此,在这种情况下的涂色方法数为2*F(n-2)。
由此,可得递推公式:F(n)= F(n-1) + 2*F(n-2) (n>=4)
#include <stdio.h> int main() { int i,n; __int64 f[51]; f[0]=0; f[1]=3; f[2]=6; f[3]=6; for(i=4;i<51;i++) f[i]=f[i-1]+2*f[i-2]; while (scanf("%d",&n)!=EOF) { printf("%I64d\n",f[n]); } return 0; }
HDU 2046 骨牌铺方格
设f[n]表示在2×n的一个长方形方格中用一个1× 2的骨牌铺满方格的方案数。显然
2×n的长方形方格可以看成由2×(n-1)的长方形(方案数为f[n-1])加1块竖放的骨牌构成,也可以看成由2×(n-2)的长方形(方案数为f[n-2])加2块横放的骨牌构成。
易得 递推式为: f[n]=f[n-1]+f[n-2] (n>2)。f[1]=1,f[2]=2。
#include <stdio.h> int main() { int n,i; __int64 f[51]={0,1,2}; for (i=3;i<=50;i++) f[i]=f[i-1]+f[i-2]; while (scanf("%d",&n)!=EOF) { printf("%I64d\n",f[n]); } return 0; }
HDU 2047 阿牛的EOF牛肉串
定义二维数组f[40][3],其中f[i][0]表示长度为i,最后字符为'E'的串的数目;
f[i][1]表示长度为i,最后字符为'O'的串的数目;f[i][2]表示长度为i,最后字符为'F'的串的数目。
显然,对于长度为i+1的字符串,若最后字符取'E'或'F',则其前面的一个字符任意,
即 f[i+1][0]=f[i][0]+f[i][1]+f[i][2]
f[i+1][2]=f[i][0]+f[i][1]+f[i][2]
若最后字符取'O',则其前面的字符只能为'E'或'F',所以
f[i+1][1]=f[i][0]+f[i][2]
#include <stdio.h> int main() { int n,i; __int64 f[41][3]; f[1][0]=1; f[1][1]=1; f[1][2]=1; for (i=2;i<40;i++) { f[i][0]=f[i-1][0]+f[i-1][1]+f[i-1][2];