Hanoi塔问题（课堂PPT）

1、 【例例】 Hanoi（汉诺）塔问题。古代有（汉诺）塔问题。古代有一个梵塔，塔内有一个梵塔，塔内有3个座个座A、B、C，开始，开始时座上有时座上有64个盘子，盘子大小不等，大个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这的在下，小的在上。有一个老和尚想把这64个盘子从座移到座，但规定每次只个盘子从座移到座，但规定每次只允许移动一个盘，且在移动过程中在允许移动一个盘，且在移动过程中在3个个座上都始终保持大盘在下，小盘在上。在座上都始终保持大盘在下，小盘在上。在移动过程中可以利用移动过程中可以利用B座。要求编程序输座。要求编程序输出移动盘子的步骤。出移动盘子的步骤。 高级语言程序设计

2、 Hanoi塔问题ABC 高级语言程序设计 Hanoi塔问题解题思路：解题思路： 要把要把64个盘子从个盘子从A座移动到座移动到C座，需要移动大座，需要移动大约约264 次盘子。次盘子。 老和尚会这样想：假如有另外一个和尚能有办老和尚会这样想：假如有另外一个和尚能有办法将上面法将上面63个盘子从一个座移到另一座。那个盘子从一个座移到另一座。那么，问题就解决了。此时老和尚只需这样做：么，问题就解决了。此时老和尚只需这样做：(1) 命令第2个和尚将63个盘子从A座移到B(2) 自己将1个盘子（最底下的、最大的盘子）从A座移到C座(3) 再命令第2个和尚将63个盘子从B座移到C座 高级语言程序设计

3、Hanoi塔问题ABC将将63个从个从A到到B第第1个和尚的做法个和尚的做法 高级语言程序设计 Hanoi塔问题ABC将将63个从个从A到到B第第1个和尚的做法个和尚的做法 高级语言程序设计 Hanoi塔问题ABC将将1个从个从A到到C第第1个和尚的做法个和尚的做法 高级语言程序设计 Hanoi塔问题ABC将将1个从个从A到到C第第1个和尚的做法个和尚的做法 高级语言程序设计 Hanoi塔问题ABC将将63个从个从B到到C第第1个和尚的做法个和尚的做法 高级语言程序设计 Hanoi塔问题ABC将将63个从个从B到到C第第1个和尚的做法个和尚的做法 高级语言程序设计 Hanoi塔问题ABC将将6

4、2个从个从A到到C第第2个和尚的做法个和尚的做法 高级语言程序设计 Hanoi塔问题ABC将将62个从个从A到到C第第2个和尚的做法个和尚的做法 高级语言程序设计 Hanoi塔问题ABC将将1个从个从A到到B第第2个和尚的做法个和尚的做法 高级语言程序设计 Hanoi塔问题ABC将将1个从个从A到到B第第2个和尚的做法个和尚的做法 高级语言程序设计 Hanoi塔问题ABC将将62个从个从C到到B第第2个和尚的做法个和尚的做法 高级语言程序设计 Hanoi塔问题ABC将将62个从个从C到到B第第2个和尚的做法个和尚的做法 高级语言程序设计 Hanoi塔问题第第3个和尚的做法个和尚的做法第第4个和

5、尚的做法个和尚的做法第第5个和尚的做法个和尚的做法第第6个和尚的做法个和尚的做法第第7个和尚的做法个和尚的做法第第63个和尚的做法个和尚的做法第第64个和尚仅做：将个和尚仅做：将1个从个从A移到移到C 高级语言程序设计 Hanoi塔问题ABC将将3个盘子从个盘子从A移到移到C的全过程的全过程将将2个盘子从个盘子从A移到移到B 高级语言程序设计 Hanoi塔问题ABC将将3个盘子从个盘子从A移到移到C的全过程的全过程将将2个盘子从个盘子从A移到移到B 高级语言程序设计 Hanoi塔问题ABC将将3个盘子从个盘子从A移到移到C的全过程的全过程将将1个盘子从个盘子从A移到移到C 高级语言程序设计 H

6、anoi塔问题ABC将将3个盘子从个盘子从A移到移到C的全过程的全过程将将1个盘子从个盘子从A移到移到C 高级语言程序设计 Hanoi塔问题ABC将将3个盘子从个盘子从A移到移到C的全过程的全过程将将2个盘子从个盘子从B移到移到C 高级语言程序设计 Hanoi塔问题ABC将将3个盘子从个盘子从A移到移到C的全过程的全过程将将2个盘子从个盘子从B移到移到C 高级语言程序设计 Hanoi塔问题ABC将将2个盘子从个盘子从A移到移到B的过程的过程将将1个盘子从个盘子从A移到移到C 高级语言程序设计 Hanoi塔问题ABC将将2个盘子从个盘子从A移到移到B的过程的过程将将1个盘子从个盘子从A移到移到C

7、 高级语言程序设计 Hanoi塔问题ABC将将2个盘子从个盘子从A移到移到B的过程的过程将将1个盘子从个盘子从A移到移到B 高级语言程序设计 Hanoi塔问题ABC将将2个盘子从个盘子从A移到移到B的过程的过程将将1个盘子从个盘子从A移到移到B 高级语言程序设计 Hanoi塔问题ABC将将2个盘子从个盘子从A移到移到B的过程的过程将将1个盘子从个盘子从C移到移到B 高级语言程序设计 Hanoi塔问题ABC将将2个盘子从个盘子从A移到移到B的过程的过程将将1个盘子从个盘子从C移到移到B 高级语言程序设计 Hanoi塔问题ABC将将2个盘子从个盘子从B移到移到C的过程的过程 高级语言程序设计 Ha

8、noi塔问题ABC将将2个盘子从个盘子从B移到移到C的过程的过程 高级语言程序设计 Hanoi塔问题ABC将将2个盘子从个盘子从B移到移到C的过程的过程 高级语言程序设计 Hanoi塔问题ABC将将2个盘子从个盘子从B移到移到C的过程的过程 高级语言程序设计 Hanoi塔问题由上面的分析可知：将由上面的分析可知：将n个盘子从个盘子从A座移座移到到C座可以分解为以下座可以分解为以下3个步骤：个步骤：(1) 将将A上上n-1个盘借助个盘借助C座先移到座先移到B座上座上(2) 把把A座上剩下的一个盘移到座上剩下的一个盘移到C座上座上(3) 将将n-1个盘从个盘从B座借助于座移到座借助于座移到C座上座

9、上移移 动动圆圆 盘盘 数数源源 座座辅辅 助助 座座目目 的的 座座总总 任任 务务子任务子任务子任务子任务子任务子任务n (1 n)ABCn-1(1n-1)ABC1 ( n )ACn-1(1n-1)BCA 高级语言程序设计 Hanoi塔问题编写程序编写程序: 用用hanoi函数实现函数实现子任务子任务和子任务和子任务 用用printf函数实现函数实现子任务子任务 函数调用函数调用hanoi(n,one,two.three)表示表示将将n个盘子从个盘子从“one”座移到座移到“three”座的座的过程过程(借助借助“two”座座) 高级语言程序设计 Hanoi塔问题35void hanoi(

10、int n, char one, char two, char three) if ( i=1) printf(%d: %c-%cn, n, one, three); else hanoi( n-1, one, three, two ) ; printf(%d: %c-%cn, n, one, three); hanoi(n-1, two, one, three ) ; int main()int m ; scanf(“%d”, &m) ; hanoi(m, A, B, C ); return 0； hanoi( n, one , two , three ) if ( n=1 ) 将one轴上的圆盘移到three轴;else hanio( n-1, one, three, two ) ; 将第 n 号圆盘由 one 轴移动到 three 轴 ; hanio( n-1, two, one, three ) ; 执行程序, 输入n=3, 输出结果为 : 1 : A - C2 : A - B1 : C - B3 : A - C1 : B - A2 : B - C1: A - C 高级语言程序设计 Hanoi塔问题36H (3, A, B, C)H(2,A,C,B)(1,A,B,C)(0,A,C,B) 1: A-C(