1、第二课时第二课时非数值非数值计算计算神奇的递归神奇的递归 学习目标学习目标 1.运用合适的算法形成解决问题的方案 2.了解算法设计中的分治思想，并运用二分查找解决实际问题 3.体验递归的方法，并结合具体问题开展编程实践 教学重点教学重点 理解二分思想、递归思想，运用二分算法解决实际问题 教学难点教学难点 理解递归算法 教学过程教学过程来源来源:学科网学科网 一、游戏引入一、游戏引入： （玩汉诺塔游戏） “汉诺塔汉诺塔”游戏源于不念旧恶古老的印度传说游戏源于不念旧恶古老的印度传说。如下图所示如下图所示，在木板上有在木板上有 A、B、 C 三根杆三根杆，A 杆上有若干木盘杆上有若干木盘，规定每次移
2、动一个木盘规定每次移动一个木盘。且小的木盘只能叠在大且小的木盘只能叠在大 的木盘上面。请设计算法，用尽可能少的次数把所有的木盘从的木盘上面。请设计算法，用尽可能少的次数把所有的木盘从 A 杆全部移到杆全部移到 C 杆上。杆上。 解析：解析： 要使移动次数减少要使移动次数减少，必须排除无效的移动必须排除无效的移动，下面大家下面大家从网从网上下载 Flash 版本汉诺 塔游戏或在线汉诺塔游戏，完成下列表格。 汉诺塔的移动过程图示汉诺塔的移动过程图示 初始状态初始状态第四步第四步 第一步第一步第五步第五步 第二步第二步第六步第六步 第三步第三步第七步第七步 总结：生活中很很多类似这种具有自相似性重复
3、的事物。如：来源:学,科,网 Z,X,X,K 像这种直接或间接地调用自身的方法称为递归。像这种直接或间接地调用自身的方法称为递归。 二、递归二、递归 递归是计算科学领域中一种重要的计算思维模式。 它既是一种抽象表 达的手段，也是一种问题求解的重要方法。 数学中经常见到递归函数，如著名的斐波那契数 列“1，1，23，5， 8，13” ，可以递归定义为： 递推关系是递归的重要组成，而边界条件是递归的另一要素，它保证递归能在 有限次的计算后得出结果，而不会产生无限循环的情况。 1、递归的思想： 递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。 对递 归而言，递推与回归，二者缺一不可
4、。其特点可概括为： 1）分：将原有问题分解成 K 个子问题。 2）治：对这 K 个子问题分别求解。如果子问题的规模仍然不够小，则将其再分 解为 K 个子问题， 如此进行下去， 直到问题足够小时， 就很容易求出子问题的解。 3）合：将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步 求出原问题的解。来源:Z_xx_k.Com 2、汉诺塔的递归： 1）汉诺塔的递归过程： 将 N 个木盘从 A 杆移动到 C 杆，需要借助中间的 B 杆，只要超过一个木盘，在 移动过程中，总会存在起始杆、过渡杆及目标杆的问题。因此，定义函数时， 用到了 4 个参数：haooi(n,s,m,t),n 表示需要
5、移动的盘子数量，S 表示盘子的起始 杆，m 表示中间过渡杆，t 表示目标杆，用图示可表示为： 编程如下： def hanno(n,s,m,t):来源:学科网 ZXXK #定义一个函数,n 层塔，将盘子从 s 借助 m 移动到 t if n=1: print(s,-,t)#将一个盘子从 s 移动到 t else: hanno(n-1,s,t,m)#将前 n-1 个盘子从 s 移动到m 上 print(s,-,t)#将最底下的最后一个盘子从 s 移动到 t 上 hanno(n-1,m,s,t)#将 m 上的 n-1 个盘子移动到 t 上 #主程序 n=int(input(请输入汉诺塔的层数：)#调用函数，将 n 个木盘从 A 借助 B 移动到 C hanno(n,A,B,C) input(运行完毕，请按回车键退出.) 三、递归与迭代的关系三、递归与迭代的关系 迭代与递妆算法都需要重复执行某些代码， 两者既有区另又有密切的 联系。迭代是重复反馈过程的活动，其目的通常是逼迫所需目标或结 果。 递归是重复调用函数自身。 递归满足终止条件的情况时逐层返回。 迭代则通常使用计数器结束循环。来源:Zxxk.Com 迭代程序可以转换成等价的递归程序。如：计算斐波那契数列第 N 项的值。 练习：练习：计算“汉诺塔”游戏移动的次数。
