《动态规划法经典兔子问题.ppt》由会员分享,可在线阅读,更多相关《动态规划法经典兔子问题.ppt(9页珍藏版)》请在三一办公上搜索。
1、13计科1班,组长:肖利组员:李斯、李梦蝶、杨冰,动态规划法经典兔子问题,自选题:,问题描述:,有一对兔子,从出生后第三个月起都生一对兔子,小兔子长到第三个月后每个月又生一对兔子。假如兔子都不死,问每个月的兔子对数是多少?,1,分析:,首先要明确题目的意思,是求每个月的兔子总对数。将兔子分为三种:兔子出生后第一个月为小兔子,第二个月为中兔子,第三个月和之后为老兔子。那么,第一个月的兔子对数为:1、0、0,第二个月兔子对数为:0、1、0,第三个月兔子对数为:1、0、1,第四个月兔子对数为:1、1、1,第五个月兔子对数为:2、1、2,第六个月兔子对数为:3、2、3,第七个月兔子对数为:5、3、5,
2、由上可知,每个月兔子的总对数分别是:1、1、2、3、5、8、13、.,月份,1,2,3,4,5,7,6,总对数,1,1,2,3,5,8,13,8,.,表示未成熟兔子,表示成熟兔子,中,老,小,中,老,小,小,中,老,老,老,老,老,老,老,老,老,老,小,小,小,小,小,小,小,中,小,小,中,中,小,中,中,仔细观察图解,兔子所求每月总对数用F(x)表示,x表示月份数,可得出一下结论:F(x)=注:所求月份的兔子总对数是前两个月兔子总对数之和,1,x=1,1,x=2,F(x-1)+F(x-2),x2,算法流程:,输入:所求月份数x输出:所求月份中兔子总对数F(x)1.首先判断x是否为1或者2 1.1若是,则直接返回1 1.2否则,执行循环F(x)=F(x-1)+F(x-2)2.得出结果,输出F(x),算法实现,用C语言描述如下:,效果展示如下:,