《Hanoi塔问题.ppt》由会员分享，可在线阅读，更多相关《Hanoi塔问题.ppt（36页珍藏版）》请在金锄头文库上搜索。
1、【例】Hanoi（汉诺）塔问题。古代有一个梵塔，塔内有3个座A、B、C，开始时座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这64个盘子从座移到座，但规定每次只允许移动一个盘，且在移动过程中在3个座上都始终保持大盘在下，小盘在上。在移动过程中可以利用B座。要求编程序输出移动盘子的步骤。,高级语言程序设计Hanoi塔问题,高级语言程序设计Hanoi塔问题,解题思路：要把64个盘子从A座移动到C座，需要移动大约264次盘子。老和尚会这样想：假如有另外一个和尚能有办法将上面63个盘子从一个座移到另一座。那么，问题就解决了。此时老和尚只需这样做：,(1)命令第2个和尚将63个盘子
2、从A座移到B(2)自己将1个盘子（最底下的、最大的盘子）从A座移到C座(3)再命令第2个和尚将63个盘子从B座移到C座,高级语言程序设计Hanoi塔问题,A,B,C,将63个从A到B,第1个和尚的做法,高级语言程序设计Hanoi塔问题,A,B,C,将63个从A到B,第1个和尚的做法,高级语言程序设计Hanoi塔问题,A,B,C,将1个从A到C,第1个和尚的做法,高级语言程序设计Hanoi塔问题,A,B,C,将1个从A到C,第1个和尚的做法,高级语言程序设计Hanoi塔问题,A,B,C,将63个从B到C,第1个和尚的做法,高级语言程序设计Hanoi塔问题,A,B,C,将63个从B到C,第1个和尚
3、的做法,高级语言程序设计Hanoi塔问题,A,B,C,将62个从A到C,第2个和尚的做法,高级语言程序设计Hanoi塔问题,A,B,C,将62个从A到C,第2个和尚的做法,高级语言程序设计Hanoi塔问题,A,B,C,将1个从A到B,第2个和尚的做法,高级语言程序设计Hanoi塔问题,A,B,C,将1个从A到B,第2个和尚的做法,高级语言程序设计Hanoi塔问题,A,B,C,将62个从C到B,第2个和尚的做法,高级语言程序设计Hanoi塔问题,A,B,C,将62个从C到B,第2个和尚的做法,高级语言程序设计Hanoi塔问题,第3个和尚的做法第4个和尚的做法第5个和尚的做法第6个和尚的做法第7个
4、和尚的做法第63个和尚的做法,第64个和尚仅做：将1个从A移到C,高级语言程序设计Hanoi塔问题,A,B,C,将3个盘子从A移到C的全过程,将2个盘子从A移到B,高级语言程序设计Hanoi塔问题,A,B,C,将3个盘子从A移到C的全过程,将2个盘子从A移到B,高级语言程序设计Hanoi塔问题,A,B,C,将3个盘子从A移到C的全过程,将1个盘子从A移到C,高级语言程序设计Hanoi塔问题,A,B,C,将3个盘子从A移到C的全过程,将1个盘子从A移到C,高级语言程序设计Hanoi塔问题,A,B,C,将3个盘子从A移到C的全过程,将2个盘子从B移到C,高级语言程序设计Hanoi塔问题,A,B,C
5、,将3个盘子从A移到C的全过程,将2个盘子从B移到C,高级语言程序设计Hanoi塔问题,A,B,C,将2个盘子从A移到B的过程,将1个盘子从A移到C,高级语言程序设计Hanoi塔问题,A,B,C,将2个盘子从A移到B的过程,将1个盘子从A移到C,高级语言程序设计Hanoi塔问题,A,B,C,将2个盘子从A移到B的过程,将1个盘子从A移到B,高级语言程序设计Hanoi塔问题,A,B,C,将2个盘子从A移到B的过程,将1个盘子从A移到B,高级语言程序设计Hanoi塔问题,A,B,C,将2个盘子从A移到B的过程,将1个盘子从C移到B,高级语言程序设计Hanoi塔问题,A,B,C,将2个盘子从A移到B
6、的过程,将1个盘子从C移到B,高级语言程序设计Hanoi塔问题,A,B,C,将2个盘子从B移到C的过程,高级语言程序设计Hanoi塔问题,A,B,C,将2个盘子从B移到C的过程,高级语言程序设计Hanoi塔问题,A,B,C,将2个盘子从B移到C的过程,高级语言程序设计Hanoi塔问题,A,B,C,将2个盘子从B移到C的过程,高级语言程序设计Hanoi塔问题,由上面的分析可知：将n个盘子从A座移到C座可以分解为以下3个步骤：(1)将A上n-1个盘借助C座先移到B座上(2)把A座上剩下的一个盘移到C座上(3)将n-1个盘从B座借助于座移到C座上,高级语言程序设计Hanoi塔问题,编写程序:用hanoi函数实现子任务和子任务用printf函数实现子任务函数调用hanoi(n,one,two.three)表示将n个盘子从“one”座移到“three”座的过程(借助“two”座),高级语言程序设计Hanoi塔问题,高级语言程序设计Hanoi塔问题,H(3,A,B,C),执行过程分析:,高级语言程序设计Hanoi塔问题,
