4.3 非数值计算（第二课时）课件-2020-2021学年高中信息技术教科版（2019）必修1

非数值计算 第二课时 第 4 单元 4.3 学习目标 ★运用合适的算法形成解决问题的方案。 ★了解算法设计中的分治思想，并运用二分查找解决实际问题。 ★体验递归算法，并结合具体问题开展编程实践。 活动 剖析问题，设计游戏策略 “汉诺塔”游戏源于 一个古老的印度传说。 如图所示，木板上有A、B、C三根杆， A杆上有若干木盘，规定每次移动一个木盘，且小的木盘只能叠在大的木盘上面。 请设计算法，用尽可能少的次数把所有木盘从A杆移动到C杆上。 要使移动次数尽可能少，必须排除无效移动。现在有8个木盘，不妨先以3个木盘为例，观察一下移动的过程。请在表中记录木盘移动的过程。 递归 直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。 在数学与计算机领域中，递归函数是指用函数自身来定义该函数的方法。 如著名的斐波那契数列 “1, 1, 2, 3, 5, 8, 13,…”，可以递归定义为： F(n) = 1 (n=1 或 n=2) F(n-1) + F(n-2) (n>2) 递归 递推关系是递归的重要组成，而边界条件是递归的另一要素，它保证递归能在有限次的计算后得出结果，而不会产生尤限循环的情况。 面对一个大规模复杂问题的求解， 递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。 对递归而言， 递推与回归，“分”、“治”、“合”二者缺一不可。 结合分治策略， 递归也可用 “分”三个字概括。 (1) 分：将原问题分解成K个子问题。 (2) 治：对这K个子问题分别求解。 如果子问题的规模仍然不够小， 则将其再分解为K个子问题， 如此进行下去， 直到问题足够小时，就很容易求出子问题的解。 (3)合：将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解。 移动3个木盘的方法是：根据木盘叠放规则，要使A杆上最大的木盘（记为x)移动到C杆上（子问题1, 如图第4步），必须先把 x上方的所有木盘移动到B杆上（子问题2, 如图4中的前3步），然后再将B杆上所有的木盘移动到C杆上（子问题3, 如图中的后3步）。 第1步：A→C 第2步：A→B 第3步：C→B 第4步：A→C 第5步：B→A 第6步：B→C 第7步：A→C 3个木盘的移动问题成功解决了，就可以解决更多木盘的移动问题了。 解决移动n个木盘的问题。