4.3 初识非数值计算第2课时-【新教材】教科版（2019）高中信息技术必修一教案

第二课时 任务二玩转“汉诺塔”游戏 活动剖析问题， 设计游戏策略 “汉诺塔”游戏源于一个古老的印度传说。如图4.3.1所示，木板上有A、B、C三根杆，A杆上有若干木盘，规定每次移动一个木盘，且小的木盘只能叠在大的木盘上面。请设计算法，用尽可能少的次数把所有木盘从A杆全部移到C杆上。 要使移动次数尽可能少，必须排除无效移动。现在有8个木盘，不妨先以3个木盘为例，观察一下移动的过程。请在图4.3.2中 记录木盘移动的过程。 递归 递归是计算科学领域中一种重要的计算思维模式。它既是一种抽象表达的手段，也是一种问题求解的重要方法。 直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。图4.3.3所示 就是递归的一-种形象表示。 在数学与计算机领域中，递归函数是指用函数自身来定义该函数的方法。如著名的斐波那契数列“1， 1, 2, 3, 5, 8，13，..”，以递归定义为 递推关系是递归的重要组成，而边界条件是递归的另一要素，它保证递归能在有限次的计算后得出结果，而不会产生无限循环的情况。 面对一个大规模复杂问题的求解，递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。对递归而言，递推与回归，二者缺一-不可。结合分治策略，递归也可用“分”“治” “合”三个字概括。 (1)分:将原问题分解成k个子问题。 (2)治:对这k个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为k个子问题，如此进行下去，直到问题足够小时,就很容易求出子问题的解。 (3)合:将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解。 实践操作 移动3个木盘的方法是:根据木盘叠放规则，要使A杆上最大的木盘(记为x)移动到C杆上(子问题1，如图4.3.2中的第4步) ，必须先把x上方的所有木盘移动到B杆上(子问题2，如图4.3.2中的前3步)，然后再将B杆上所有的木盘移动到C杆上(子问题3，如图4.3.2中的后3步 )。 3个木盘的移动问题成功解决了，就可以解决更多木盘的移动问题了。将n个木盘从A杆移动到C杆，需要借助中间的B杆。只要超过一个木盘，在移动过程中，总会存在起始杆、过渡杆及目标杆的问题。因此，定义函数时，用到了4个参数: hanoi(n,s,m,l)，