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

程序设计入门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)def

hanoi(n,a,b,c):

ifn==1:

print("{}—>{}".format(a,c))

#将一个金盘由a移到c

else:

hanoi(n-1,a,c,b)

#借助c将n-1个金盘由a移到b

print("{}—>{}".format(a,c))#将一个金盘由a移到c

hanoi(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次；假设每秒移动一次，一年是31536000秒，则一刻不停地移动完64个金盘，需要584942417355年；即使借助于计算机，假设计算机每秒能够移动1亿次，也需要大概5849年才能够完成。汉诺塔(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