第29课 求解兔子数列.ppt

第29课求解兔子数列 1 兔子数列 如果兔子在出生两个月后 就有繁殖能力 一对兔子每个月能生出一对小兔子来 并且如果所有兔都不死 那么一年以后可以繁殖多少对兔子 2 小猴吃桃 有一天小猴子摘若干个桃子 当即吃了一半还觉得不过瘾 又多吃了一个 第二天接着吃剩下桃子中的一半 仍觉得不过瘾又多吃了一个 以后小猴子都是吃尚存桃子一半多一个 到第10天早上小猴子再去吃桃子的时候 看到只剩下一个桃子 问小猴子第一天共摘下了多少个桃子 复习引入 递归算法的基本思想是把规模较大的 较难解决的问题变成规模较小的 容易解决的同一问题 规模较小的问题又变成规模更小的问题 当问题小到一定程度时 可以直接得出它的解 从而得到原来问题的解 即采用 大事化小 小事化了 的基本思想 采用递归算法的条件 1 每一步骤解决问题的方法要一致 2 必须有一个明确的递归结束条件 称为递归出口 问题提出 兔子数列 是意大利数学家列昂纳多 斐波那契 LeonardoFibonacci 提出的 他以兔子繁殖为例子而引入 故斐波那契数列又称为 兔子数列 一般而言 兔子在出生两个月后 就有繁殖能力 一对兔子每个月能生出一对小兔子来 并且如果所有兔都不死 那么一年以后可以繁殖多少对兔子 我们不妨拿新出生的一对小兔子分析一下 第一个月小兔子没有繁殖能力 所以还是一对 两个月后 生下一对小兔民数共有两对 三个月以后 老兔子又生下一对 因为小兔子还没有繁殖能力 所以一共是三对 依次类推可以列出下表 这样一个数列1 1 2 3 5 8 13 21 就是兔子数列 该数列有很多奇妙的属性 这个数列从第三项开始 每一项都等于前两项之和 随着数列项数的增加 前一项与后一项之比越逼近黄金分割0 6180339887 从第二项开始 每个奇数项的平方都比前后两项之积多1 每个偶数项的平方都比前后两项之积少1 分析这个数列 因为从第2个月开始 每月的兔子总数目等于前2个月的兔子总数之和 因此 兔子问题 很容易用递推式解决 假设第n个月的兔子数目是F n 有 f n f n 1 f n 2 n 3 f 1 f 2 1 n 1或n 2 在解决有些问题时 从初始条件入手 需要一步步地按递推关系式递推 直至求出最终结果 这种方法叫做递推或迭代法求解 2 算法分析Function有多少对兔子 第几月 如果是第一月或第二月 那么就有一对兔子 否则 本月 兔子数 本月 1 月的兔子数 本月 2 月的兔子数EndFunction 3 编写程序代码 Functionf nAsInteger AsLongIfn 1ORn 2Thenf 1 当n 1或n 2时 函数f的返回值为1Elsef f n 1 f n 2 递归地调用函数f来计算f n 的值EndIfEndFunction 4 运行调试程序根据算法流程图 填空完善已经设计好的界面和部分代码的求n阶乘算法 并进行调试 课堂练习 1 小猴吃桃问题 有一天小猴子摘若干个桃子 当即吃了一半还觉得不过瘾 又多吃了一个 第二天接着吃剩下桃子中的一半 仍觉得不过瘾又多吃了一个 以后小猴子都是吃尚存桃子一半多一个 到第10天早上小猴子再去吃桃子的时候 看到只剩下一个桃子 问小猴子第一天共摘下了多少个桃子 1 算法分析假设第n天的桃子数是A n A 10 1A 9 2 A 10 1 A 8 2 A 9 1 A n 2 A n 1 1 2 写出递归表达式A n 2 A n 1 1 n 10 A 10 1 n 10 2 算法描述function有多少桃子 第几天 如果是第10天 那么就有一个桃子 否则 桃子数 2 后一天的桃子数 1 endfunction 3 编写程序代码 将划线处填写完整Functiontao daysAsInteger AsIntegerIfdays 10Thentao 1Elsetao 2 tao days 1 1 EndIfEndFunction 4 运行调试程序根据算法流程图 填空完善已经设计好的界面和部分代码的求n阶乘算法 并进行调试 2 走台阶问题 从楼下到楼上共有n个台阶 每一步有2种走法 走1个台阶 走2个台阶 走上这n个台阶共有多少种走法 1 算法分析 仅有1级台阶 走法有1种 有2级台阶时 走法有2种 有3级台阶时 走法有3种 有4级台阶时 走法有5种 有5级台阶时 走法有8种 有n级台阶时 走法有f n 1 f n 2 种 其中f n 为走上n个台阶的走