第6章2_程序设计基础ppt课件.ppt

《第6章2_程序设计基础ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、假设有三个分别命名为A、B和C的塔座，在塔座A上插有n个直径大小不同、依小到大分别编号为1,2,...,n的圆盘，如图所示：要求将塔座A上的n个圆盘移动到塔座C上并按相同顺序叠放，圆盘移动时必须遵循下述规则：每次只能移动一个圆盘；圆盘可以插在A、B与C中的任意塔座上；任何时刻都不能将较大的圆盘压在较小的圆盘上。如何实现移动圆盘的操作呢？6.4递归算法举例例6.4.1：汉诺(Hanoi)塔问题汉诺塔演示Hanoi塔问题的递归思想1、A柱上只有一只盘子，假定盘号为1，这时只需将该盘从A搬至C，一次完成，记为：move1fromAtoCABC118,446,744,073,709,

2、551,61518,446,744,073,709,551,6152、A柱上有两只盘子，1为小盘，2为大盘。step1：将1号盘从A移至Bmove1fromAtoBstep2：将2号盘从A移至Cmove2fromAtoCstep3：将1号盘从B移至Cmove1formBtoCABC213、A柱上有三只盘子，从小到大分别为1号，2号，3号step1：将1号盘和2号盘视为一个整体从A移至Bmove(2,A,C,B)step2：将3号盘从A移至Cmove3fromAtoCmove(1,A,B,C)step3：将处于B上作为一个整体的两只盘子移至Cmove(2,B,A,C)ABC21

3、3move(3,A,B,C)move(2,A,C,B)move(1,A,B,C)move(2,B,A,C)move(1,A,B,C)move(1,A,C,B)move(1,C,A,B)move(1,B,C,A)move(1,B,A,C)move(1,A,B,C)4、定义搬移函数move(n,A,B,C)，含义是将n只盘子从A经B搬到Cstep1：move(n-1,A,C,B)将上面的n-1只盘子作为一个整体从A经C移至Bstep2：输出n:AtoC，将n号盘从A移至C，直接可解结点step3：move(n-1,B,A,C)将上面的n-1只盘子作为一个整体从B经A移至C3阶Ha

4、noi塔问题的与或图3阶Hanoi塔问题的递归调用与返回3阶Hanoi塔问题的递归调用过程……intstep=1;voidmove(int,char,char,char);intmain(){intn;cout<<"请输入盘数n=";cin>>n;cout<<"在3根柱子上移"<

5、se{move(m-1,p,r,q);cout<<"["<>n;MoveHanoiTower(n,'A','B','C');return0;}另一种写法voidMoveHanoiTower(int

6、num,charsource,chartemp,chardest){if(num==1)move(source,dest);else{MoveHanoiTower(num-1,source,dest,temp);move(source,dest);MoveHanoiTower(num-1,temp,source,dest);}}voidmove(charsource,chardest){step++;cout<<"step"<"<

7、noi问题-2仍然是给定N只盘子，3根柱子，但是允许每次最多移动相邻的M只盘子（当然移动盘子的数目也可以小于M）,最少需要多少次？例如N=5，M=2时，可以分别将最小的2个盘子、中间的2个盘子以及最大的一个盘子分别看作一个整体，这样可以转变为N=3，M=1的情况，共需要移动7次。例6.4.2：冒泡排序的递归算法a[0]a[1]a[2]a[3]a[4]a[5]a[6]18324912a[0]a[1]a[2]a[3]a[4]a[5]a[6]83249121冒泡排序冒泡排序……voidbubble(int[]