4.3 非数值计算 教案（2课时）

第二课时 任务二玩转“汉诺塔”游戏 活动剖析问题，?设计游戏策略 “汉诺塔”游戏源于一个古老的印度传说。如图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)， n表示需要移动的盘子数量，s表示盘子的起始杆，m表示中间过渡杆，l表示目标杆，如图4.3.4所示。 让我们根据图示一起完善程序吧。 def hanoi(n,s,m,t): #定义一个函数,将n个木盘从s借助m移到t if n==1: #当只有一个木盘时，直接从起始杆移动到目标杆 print( ) else: #将前n-1个木盘借助t从s移到m hanoi( ,s, , ) print( )#将最下面的木盘从s移到t #将m上的n-1个木盘借助s移到t hanoi( , , ,t ) #主程序 n=int(input( '请输人木盘的个数: ')) #调用函数，将n个木盘从A借助B移动到C hanoi(n,'A','B','Cc) 运行程序，输入3个木盘，记录程序运行结果。 将一个难以直接解决的大问题，分割成一些规模较小的同类问题，以便各个击破，分而治之，此为分治。分治与递归就像一-对孪生兄弟，经常同时应用在算法设计中，并由此产生了许多高效的算法。 练习 1.结合4.2的知识，计算“汉诺塔”游戏移动的次数。 2.尝试用二分法求解x3- x2+x- 1=0。 操作提示: 令f(x)=x3-x2+x- 1,针对有解的单调区间(a,b),取xo=(a+b)/2: 若f(a) f(x0)<0,则f(x)在(a, x)内有解; 若f(xo) f(b)<0,则f(x)在(Xo, b)内有解; 若|f(x0)|< 10^ ，则x为方程的解。 拓展知识 迭代与递归的关系 迭代算法与递归算法都需要重复执行某些代码，两者既有区别又有着密切的联系。 迭代是重复反馈过程的活动，其目的通常是逼近所需目标或结果。递归是重复调用函数自身。递归中，遇到满足终止条件的情况时逐层返回。迭代则通常使用计数器结束循环。 迭代程序可以转 ... ...