首页 > 代码库 > 算法设计 之 递推法
算法设计 之 递推法
递推法就是根据已知条件,分析推导出问题中的联系,然后一步一步进行推倒直至得到结果。
根据具体问题我们需要选择是正推还是逆推来解决问题。
下面先举一个递推中的经典例子,就是求兔子数量的问题:
现有一只一个月大的兔子,已知当兔子在第三个月大时每月就可以生下一只小兔子(好吧,就按兔子是无性繁殖的),求一年后兔子的总数量。
我们根据问题分析,发现可以把兔子分三类:一个月大、二个月大、三个或三个以上月大,列表分析:
月份 | 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月份开始到本年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)); } }
运行结果:
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。