首页 > 代码库 > 算法设计 之 递推法

算法设计 之 递推法

递推法就是根据已知条件,分析推导出问题中的联系,然后一步一步进行推倒直至得到结果。

根据具体问题我们需要选择是正推还是逆推来解决问题。

 

下面先举一个递推中的经典例子,就是求兔子数量的问题:

现有一只一个月大的兔子,已知当兔子在第三个月大时每月就可以生下一只小兔子(好吧,就按兔子是无性繁殖的),求一年后兔子的总数量。

我们根据问题分析,发现可以把兔子分三类:一个月大、二个月大、三个或三个以上月大,列表分析:

月份 1月大 2月大 >=3月大
1 1 0 0
2 0 1 0
3 1 0 1
4 1 1 1
5 2 1 2
……      

根据上面图表分析可知:

下月“一月大”的兔子数量等于上月“>=3月大”的兔子数量;

下月“二月大”的兔子数量等于上月“一月大”的兔子数量;

下月“>=3月大”的兔子数量等于上月“二月大”+上月“>=3月大”的兔子数量;

既然分析完问题,代码就很简单了:

/// <summary>
/// 递推(正推)计算兔子的数量
/// </summary>
public static void ShowRabbitsCount() 
{
    int oneMonthCount = 1;
    int twoMonthCount = 0;
    int threeOrMoreMonthCount = 0;

    for (int month = 2; month <= 12; month++)
    {
        //临时存储上月各种兔子数量
        int preOneMonthCount = oneMonthCount;
       int preTwoMonthCount = twoMonthCount;
       int preThreeOrMoreMonthCount = threeOrMoreMonthCount;

        //更新本月各种兔子的数量
        oneMonthCount = preTwoMonthCount+preThreeOrMoreMonthCount;
       twoMonthCount = preOneMonthCount;
       threeOrMoreMonthCount += preTwoMonthCount;

       Console.WriteLine(string.Format("第 {0} 个月兔子的总数为:{1}", month, oneMonthCount + twoMonthCount + threeOrMoreMonthCount));
    }
}

运行结果:

1

 

下面再看一个逆推的例子:

假设有一个人从1月份开始到本年12月初时体重减少到150斤,他每个月增加的体重为当月初体重的2%,每月锻炼减少的体重为10斤(这里也按这10斤是月底突然减掉的吐舌笑脸),计算此人一月初时的体重。

根据问题分析:

12月初的体重为150斤,然后: 本月初体重+10=上月初体重*1.02

/// <summary>
/// 递推(逆推)计算开始时的体重
/// </summary>
public static void ShowWeight()
{
    double endWeight = 150;
    double perMonthReduce = 10;
    for (int month = 11; month > 0; month--)
    {
        double preStartWeight = (endWeight + perMonthReduce) / 1.02;
        endWeight = preStartWeight;

        Console.WriteLine(string.Format("第 {0} 个月的开始体重为:{1}", month, preStartWeight));
    }
}

运行结果:

2