山东省枣庄市第八中学东校区高中信息技术教科版（2019）必修一 4.3非数数值计算教案(第2课时)

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