1、遞回演算法的特點
1、呼叫本身
2、設定一個結束條件
需要先將問題簡單化，找到一個可以不斷遞推下去的規律
2、問題背景：
相傳在古印度圣廟中，有一種被稱為漢諾塔(Hanoi)的游戲，該游戲是在一塊銅板裝置上，有三根桿(編號A、B、C)，在A桿自下而上、由大到小按順序放置64個金盤(如圖1)，
游戲的目標：把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好，
操作規則：每次只能移動一個盤子，并且在移動程序中三根桿上都始終保持大盤在下，小盤在上，操作程序中盤子可以置于A、B、C任一桿上，
3、問題：如何模擬這個移動的程序
4、解題核心思路：
假設金盤有n個，那么我們可以看成兩部分：最底下的1個和上面的n-1個金盤，
問題就被簡化成：移動兩部分，
移動兩部分的步驟可以拆解為以下三步：
1、把n-1個盤子從A經過C移動到B；（多個盤子想移動到B柱，必須經過C柱才行）
2、把第n個盤子從A移動到C；
3、把n-1個盤子從B經過A移動到C；
5、推演
假設n=3，我們可以根據下圖，推演一遍，是否符合這個規律
6、代碼：
def hanoi(n, a, b, c): # 引數n代表有n個盤子，a, b, c分別代表3個柱子
if n > 0:
hanoi(n-1, a, c, b)
print('moving from %s to %s'%(a, c))
hanoi(n-1, b, a, c)
hanoi(3, 'A', 'B', 'C')
7、輸出結果：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/330443.html
標籤：其他
上一篇：【c++】b_game.h投票