(7)--2.2 递归算法之汉诺塔问题.ppt

递归算法之汉诺塔问题算法分析与设计

一个经典的游戏——汉诺塔问题导入

汉诺塔问题（梵塔问题,TowerofHanoi）汉诺塔来源于一个印度的传说故事：上帝在创造世界时做了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着64片黄金圆盘上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上规定：在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘有预言说，这件事完成时地球会在一瞬间毁灭，也有人相信婆罗门至今仍在一刻不停地搬动着圆盘如果移动一个圆盘需要一秒钟，请大家预测一下地球多久之后将毁灭？问题导入

汉诺塔游戏A,B,C3根柱子，n个圆盘，自下而上，由大到小将这n个圆盘从A柱移动到C柱，并且在C柱也需要按照从下往上由大到小的顺序叠放在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上规则3：在满足移动规则1和2的前提下，可将圆盘移至A，B，C中任一根柱子上问题导入

汉诺塔游戏1个盘子：直接移动，A?C，1步完成2个盘子：小圆盘，A?B；大圆盘，A?C；小圆盘，B?C，3步完成问题导入原始柱辅助柱目标柱

汉诺塔游戏3个盘子：(1)将两个圆盘由A柱移到B柱（3步完成），(2)将最下面的圆盘由A柱移到C柱（1步完成），(3)将两个圆盘由B柱移到C柱（1步完成），共7步完成问题导入

算法设计设计思路将n个圆盘从A?C，可以分解为3个步骤：(1)将n-1个圆盘从A?B(2)将1个圆盘从A?C(3)将n-1个圆盘从B?CABC

算法设计伪代码Hanoi(n,A,B,C)inputnbeginifn>0Hanoi(n-1,A,C,B)Move(A,C)Hanoi(n-1,B,A,C)end

算法分析时间复杂度分析T(1)=O(1)T(n)=2T(n-1)+O(1)T(n)=(2n–1)×O(1)=O(2n)T(n)=2×2(T(n-2)+O(1))+O(1)=2×2×2T(n-3)+2×2O(1)+2O(1)+O(1)T(n)=2(2n-1–1)+1=2n-1

算法分析时间复杂度分析T(64)=264-1=18446744073709551615，假如每秒钟一次，移动64个圆盘需要多少时间呢？一年，移完这些黄金圆盘需要5800多亿年，比地球寿命还要长

算法实现C/C++语言实现代码#include<stdio.h>intstep;voidmove(intn,chara,charb){ printf("%d:move%dfrom%cto%c.\n",++step,n,a,b);}voidhanoi(intn,chara,charb,charc){if(n>0){hanoi(n-1,a,c,b);move(n,a,c);hanoi(n-1,b,a,c);}}main(){ intn; scanf("%d",&n); hanoi(n,'A','B','C');}1:move1fromAtoC.2:move2fromAtoB.3:move1fromCtoB.4:move3fromAtoC.5:move1fromBtoA.6:move2fromBtoC.7:move1fromAtoC.

课后思考思考题如果有A、B、C、D四根柱子，将n个圆盘从第一根柱子(A柱)全部移动到最后一根柱子(D柱)上，最少需要多少步？

THANKS