河內塔問題
You are challenged for a challenge to find the number of moves required to move a stack of disks from one peg to another peg. Wait for a second, it sounds easy? Let’s find are what is going on and in this article, we are introducing a chapter of "TOWER OF HANOI".
您面臨一項挑戰，即尋找將一疊磁盤從一個釘移到另一個釘所需的移動次數。 等待一秒鐘，聽起來很簡單？ 讓我們找到正在發生的事情，在本文中，我們將介紹“ TOWER OF HANOI”一章。
You are given with a stack of n disks on a peg arranges as largest is at the bottom and smallest is at the top. We are required to shift this whole stack to another peg (total three pegs, two are empty initially) with considering the following rule:
您會得到一堆n塊磁盤，它們在釘子上排列，最大的在底部，最小的在頂部。 我們需要考慮以下規則，將整個堆棧移動到另一個釘子(總共三個釘子，最初兩個是空的)：
No larger disk can be placed over a smaller one.
較大的磁盤不能放在較小的磁盤上。
One disk at a time.
一次一個磁盤。
The problem is looking easy but it's not. The way we are going to tackle it is recursion. The problem is simple when you see it from recursion perspective.
問題看起來很簡單，但事實并非如此。 我們要解決的方法是遞歸。 從遞歸角度看時，問題很簡單。
Key: The number of steps required to shift the stack is exactly equal to the twice of steps for shifting the stack of one less disk(The largest one) plus one step.
關鍵：移位堆棧所需的步驟數完全等于移位少一個磁盤(最大的磁盤)加一級的步驟的兩倍。
Consider the case of shifting one disk : T(1) = 1Consider the case of shifting two disk : T(2) = 2*T(1) + 1 = 3Consider the case of shifting three disk : T(3) = 2*T(2) + 1 = 7.... T(n) = 2*T(n-1) + 1
Implementing this formula now in our python program is our next goal of solving this.
現在在我們的python程序中實現此公式是解決此問題的下一個目標。
So here is the code:
所以這是代碼：
def hanoi(x):
if x == 1:
return 1
else:
return 2*hanoi(x-1) + 1
x = int(input("ENTER THE NUMBER OF DISKS: "))
print('NUMBER OF STEPS: ', hanoi(x))
Output:
輸出：
ENTER THE NUMBER OF DISKS: 5
NUMBER OF STEPS: 31
翻譯自: https://www.includehelp.com/python/tower-of-hanoi.aspx
河內塔問題
)
