河內塔算法

Question

河內塔

可以說我必須找到一個河內函數遞歸塔除了4釘之外最有效的方法。

顯然應比河內正常塔作爲跟隨

我的算法快：

如果我們有5個盤它看起來像這樣

 -            
    ---            
    -----            
    -------           
---------           
___________ ___________ ___________ ___________ 

我想搬到N// 2盤到兩個備用凳子中的一個

-----            
    -------      -      
---------     ---      
___________ ___________ ___________ ___________ 

現在使用3我想用n-1方法（河內的普通塔）將剩餘部分送到目的地（我意識到我把n // 2置於spare1而不是spare2，但總體上是相同的東西）

          -----  
        -      -------  
       ---     --------- 
___________ ___________ ___________ ___________ 

現在乾脆把初代N // 2到目的地

          -  
              ---  
              -----  
             -------  
             --------- 
___________ ___________ ___________ ___________ 

這得到最高效的運行時間，如果光盤是1到8，但經過9個孤單顯然是一個更好的辦法。有什麼辦法可以將n分開以獲得更好的運行時間嗎？

運行時間：

最佳運行時間明顯（來源：http://service.scs.carleton.ca/sites/default/files/tr/TR-04-10.pdf）

8：33移動

9：41移動

礦

8：33個移動

9：49步驟

Answer 1

讓Hanoi4（N）是movesit的數量需要移動Ñ盤用4個釘，並讓Hanoi3（N）是它需要移動Ñ磁盤3的移動次數釘。我們知道，Hanoi3（N）= 2^N-1

我認爲你是正確的，對於每一個ñ，最好的策略將是一些小的磁盤移動到一個備用的PEG Hanoi4，將剩餘的大號移到目標上Hanoi3，然後將小號移動到目標號碼Hanoi4。對於每一個N，則所得到的公式將是2 * Hanoi4（a）+ Hanoi3（N-a），其中a是我們首先移出的小釘的數量。

這裏有一個簡單的程序，找出和蟒紋最好的成本：

Hanoi3=[0,1] 
Hanoi4=[0,1] 

print "  N Hanoi3 Hanoi4 a" 
a=1; 
for N in range(2,20): 
    Hanoi3.append(Hanoi3[N-1]*2+1) 
    cost=2*Hanoi4[a]+Hanoi3[N-a]; 
    while a<N-1: 
     c2 = 2*Hanoi4[a+1]+Hanoi3[N-a-1] 
     if c2>cost: 
      break 
     a+=1; 
     cost=c2; 
    Hanoi4.append(cost) 
    print '{0:6d} {1:6d} {2:6d}{3:5d}'.format(N,Hanoi3[N],Hanoi4[N],a) 

輸出：

N Hanoi3 Hanoi4 a 
2   3  3 1 
3   7  5 1 
4  15  9 2 
5  31  13 3 
6  63  17 3 
7  127  25 4 
8  255  33 5 
9  511  41 6 
10  1023  49 6 
11  2047  65 7 
12  4095  81 8 
13  8191  97 9 
14  16383  113 10 
15  32767  129 10 
16  65535  161 11 
17 131071  193 12 
18 262143  225 13 
19 524287  257 14 

正如你所看到的，N/2不計算最佳a。

你可以在這裏節目播放：https://ideone.com/tdT5R1