Python語言程序設計入門4.6 應用問題選講

程序設計入門Python語言……函數(shù)……第4章應用問題選講遞歸算法12漢諾塔(HanoiTower)問題漢諾塔(HanoiTower)問題例4-17：編寫程序，用遞歸算法求解漢諾塔（HanoiTower）問題。漢諾塔問題源于印度的一個古老傳說。在一塊銅板裝置上，有三根桿（編號A、B、C），在A桿自下而上、由大到小按順序放置64個金盤。游戲的目標是，把A桿上的金盤全部移到C桿上，并仍按原有順序放置好。操作規(guī)則是，每次只能移動一個盤子，并且在移動過程中三根桿上都始終保持大盤在下、小盤在上，且在三根桿之間一次只能移動一個金盤，操作過程中盤子可以置于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桿構建遞歸函數(shù)：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("請輸入金盤的個數(shù)n="))print("金盤的移動順序為：")hanoi(n,‘A’,‘B’,‘C’)

#調(diào)用函數(shù)完成求解

漢諾塔(HanoiTower)問題例4-17：編寫程序，用遞歸算法求解漢諾塔（HanoiTower）問題。構建遞歸函數(shù)：hanoi(n,a,b,c)表示：將A桿上的n個金盤，借助B桿，移到C桿漢諾塔(HanoiTower)問題例4-17：編寫程序，用遞歸算法求解漢諾塔（HanoiTower）問題。構建遞歸函數(shù)：hanoi(n,a,b,c)表示：將A桿上的n個金盤，借助B桿，移到C桿漢諾塔(HanoiTower)問題例4-17：編寫程序，用遞歸算法求解漢諾塔（HanoiTower）問題。構建遞歸函數(shù)：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