首页 > > 程序设计 > C/C++ >

致初学者（四）：HDU 2044~2050 递推专项习题解

2019-09-23 08:42:12来源：博客园阅读 ()

致初学者（四）：HDU 2044~2050 递推专项习题解

所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。关于递推的知识可以参阅本博客中随笔“递推（一）：递推法的基本思想”。

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;
}

View Code

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;
}

View Code

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;
}

View Code

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];
        f[i][2]=f[i-1][0]+f[i-1][1]+f[i-1][2];
        f[i][1]=f[i-1][0]+f[i-1][2];
    }
    while (scanf("%d",&n)!=EOF)
    {
        printf("%I64d\n",f[n][0]+f[n][1]+f[n][2]);
    }
    return 0;
}

View Code

HDU 2048 神、上帝以及老天爷

用递推的方法推导错排公式。

设n个人抽n张纸条，纸条上的名字与自己的名字全不对应的方法数用F(n)表示，那么F(n-1)就表示n-1个人抽n-1张纸条，纸条上的名字与自己的名字全不对应的方法。

n张全部不对应的纸条可以看成前n - 1张纸条再加1张纸条后，将最后1张纸条弄错，弄错的方式自然是与之前的纸条进行交换，交换的方式有两种：

（1）在前n-1个全部不对应的纸条中取任意一张进行交换。n-1张纸条全部不对应的方法数为F(n-1)，在n-1张纸条中任取一张的方法数为n-1，因此，这种情况下，方法数共有F(n-1)* (n-1)种。

（2）在前n-1张纸条中，有n-2个全不对应，有1张正确，取正确的一张进行交换。n-1张纸条中只有一张对应正确的方法数有n-1，其余n-2张纸条全不对应的方法数有F(n-2)，因此，这种情况下，方法数共有F(n-1)* (n-1)种。

由此，可得错排的递推公式： F(n)=[F(n-2)+F(n-1)]*(n-1) 。

初始情况为：F(1)=0 （只有1张纸条不可抽错）

F(2)=1 （两张纸条全不对应只有1种情况，即正确的两张交换）

#include <stdio.h>
int main()
{
   int i,c,n;
   __int64 f[21]={0,0,1}; 
   double ans;
   for (i=3;i<=20;i++)
   {
        f[i]=(f[i-1]+f[i-2])*(i-1);
    }
   scanf("%d",&c);
   while (c--)
   {
       scanf("%d",&n);
       ans=1.0*f[n];
       for (i=2;i<=n;i++)
           ans/=i;
       printf("%.2lf%%\n",100*ans);
   }
   return 0;
}

View Code

HDU 2049 不容易系列之(4)——考新郎

先求出m（1<=m<=20）个元素的错排数，用一维数组a来保存，其中a[i]保存i个元素的错排数。

再求在n个元素中挑选出m个元素的组合数c（n,m）。

这样，n对新婚夫妇中m个新郎找错了新娘的情况一共有c(n,m)*a[m]种。

#include <stdio.h>
int main()
{
    int t,n,m,p,i;
    __int64  c,sum,a[21]={0,0,1};
    for(i=3;i<21;i++)
    {
        a[i]=(a[i-1]+a[i-2])*(i-1);
    }
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d",&n,&m);
        c=1;
        if (n-m>m)  p=n-m;
        else   p=m;
        for (i=n; i>p;i--)
           c=c*i;
        for (i=1;i<=n-p;i++)
           c=c/i;
        sum=c*a[m];
        printf("%I64d\n",sum);
    }
    return 0;
}

View Code

HDU 2050 折线分割平面

设n-1条折线把空间划分的区域数为f(n-1)。

现有n条折线，为了让增加的区域更多，新增的折线要和之前的n-1条折线的2*(n-1)条边都相交，产生4*(n-1)条新的线段和2条射线，每条线段或射线产生一个新区域，但是折线相交的头部的两线段一共只能产生一个区域，所以新增区域的数量为4*(n-1) -1+2，即 4*(n-1) +1。

所以有递推公式：

f(n)=f(n-1)+4(n-1) + 1;

=f(n-2)+4(n-2)+4(n-1)+2;

.......

=f(n-(n-1)) +4(n-(n-1))+4(n-(n-2))+......+4(n-1) + n-1;

=f(1) +4(1+2+3+4+....+n-1)+n-1;

=2+4((n-1)(n-1+1)/2)+n-1;

=2n^2-n+1;

#include <stdio.h>
int main()
{
    int c;
    __int64 n;
    scanf("%d",&c);
    while (c--)
    {
        scanf("%I64d",&n);
        printf("%I64d\n",2*n*n-n+1);
    }
    return 0;
}