Python语言程序设计入门4.6 应用问题选讲.pptx

程序设计入门Python语言……

函数……第4章

应用问题选讲递归算法12汉诺塔(HanoiTower)问题

汉诺塔(HanoiTower)问题例4-17：编写程序，用递归算法求解汉诺塔（HanoiTower）问题。汉诺塔问题源于印度的一个古老传说。在一块铜板装置上，有三根杆（编号A、B、C），在A杆自下而上、由大到小按顺序放置64个金盘。游戏的目标是，把A杆上的金盘全部移到C杆上，并仍按原有顺序放置好。操作规则是，每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下、小盘在上，且在三根杆之间一次只能移动一个金盘，操作过程中盘子可以置于A、B、C任一杆上。应该如何操作？

汉诺塔(HanoiTower)问题例4-17：编写程序，用递归算法求解汉诺塔（HanoiTower）问题。ABC

汉诺塔(HanoiTower)问题例4-17：编写程序，用递归算法求解汉诺塔（HanoiTower）问题。假如A杆上只有1个金盘，则只需移动1次，可将金盘移到C杆上，记为：A—C；假如A杆上有2个金盘：A—B，A—C，B—C假如A杆上有3个金盘：最后，借助A杆，再将B杆上的2个金盘移到C杆借助C杆，先将A杆上最上面的2个金盘移到B杆上；再将A杆上最后一个金盘移到C杆上；

汉诺塔(HanoiTower)问题例4-17：编写程序，用递归算法求解汉诺塔（HanoiTower）问题。假如A杆上只有1个金盘，则只需移动1次，可将金盘移到C杆上，记为：A—C；假如A杆上有2个金盘：A—B，A—C，B—C假如A杆上有n个金盘最后，借助A杆，再将B杆上的n-1个金盘移到C杆借助C杆，先将最上面的n-1个金盘移到B杆上；再将A杆上的最后一个金盘移到C杆上；

汉诺塔(HanoiTower)问题例4-17：编写程序，用递归算法求解汉诺塔（HanoiTower）问题。表示：将A杆上的n个金盘，借助B杆，移到C杆构建递归函数：hanoi(n,a,b,c)defhanoi(n,a,b,c):ifn==1:print({}—{}.format(a,c))#将一个金盘由a移到celse:hanoi(n-1,a,c,b)#借助c将n-1个金盘由a移到bprint({}—{}.format(a,c))#将一个金盘由a移到chanoi(n-1,b,a,c)#借助a将n-1个金盘由b移到cn=int(input(请输入金盘的个数n=))print(金盘的移动顺序为：)hanoi(n,‘A’,‘B’,‘C’)#调用函数完成求解

汉诺塔(HanoiTower)问题例4-17：编写程序，用递归算法求解汉诺塔（HanoiTower）问题。构建递归函数：hanoi(n,a,b,c)表示：将A杆上的n个金盘，借助B杆，移到C杆

汉诺塔(HanoiTower)问题例4-17：编写程序，用递归算法求解汉诺塔（HanoiTower）问题。构建递归函数：hanoi(n,a,b,c)表示：将A杆上的n个金盘，借助B杆，移到C杆

汉诺塔(HanoiTower)问题例4-17：编写程序，用递归算法求解汉诺塔（HanoiTower）问题。构建递归函数：hanoi(n,a,b,c)表示：将A杆上的n个金盘，借助B杆，移到C杆

汉诺塔(HanoiTower)问题例4-17：编写程序，用递归算法求解汉诺塔（HanoiTower）问题。

汉诺塔(HanoiTower)问题例4-17：编写程序，用递归算法求解汉诺塔（HanoiTower）问题。1个金盘，移动1次：A—C2个金盘，移动3次：A—B，A—C，B—C3个金盘，移动7次：（A—C，A—B，C—B）A—C，（B—A，B—C，A—C）4个金盘，移动15次；n个金盘，移动2n–1次；64个金盘，移动264–1=18446744073709551615次；假设每秒移动一次，一年，则一刻不停地移动完64个金盘，需要584942417355年；即使借助于计算机，假设计算机每秒能够移动1亿次，也需要大概5849年才能够完成。

汉诺塔(HanoiTower)问题例4-17：编写程序，用递归算法求解汉诺塔（HanoiTower）问题。1个金盘，移动