河內塔反覆n> 3掛鉤

Question

3掛鉤（或棒，或任何你稱他們）的迭代算法是重複以下兩點：
1.將最小的磁盤向右/向左移動（如果奇數/偶數）
2.讓一個可能的移動而不觸及最小的磁盤

我的問題是 - 是否有一些類似的算法n> 3釘？

我無法在互聯網上找到這個（至少迭代）。我自己也弄不清楚什麼。上面的算法不起作用 - 它會無意中移動磁盤。

我知道我以前曾發佈過2種相關的問題，但您並不歡迎他們，所以在您投降之前 - 只需在評論中寫下我自己研究更多信息的評論，而我刪除此線程。

Answer 1

對於3-PEG河內問題用正> 1盤（第n == 1情況下是微不足道的）一般的遞歸算法是：

1. 移動n-1個從源栓盤到第三掛鉤（不是來源或目標）
2. 將最大的磁盤移動到目標掛鉤。
3. 將n-1個圓盤從第三個釘子移到目標釘子。

超過3個掛鉤，算法是相同的。只需用「任何未使用的掛鉤」替換「第三掛鉤」即可。

請注意，算法不使用「向左移動」或「向右移動」等術語。

正如@nhahtdh在評論中指出的那樣，任何遞歸算法都可以通過標準方法轉化爲迭代算法。

Answer 2

Wikipedia article on Tower of Hanoi：答案沒有非蠻力算法是已知的找到一個可證明的最佳解決方案，雖然有一個算法可能是最優的。

雖然三釘版本有一個簡單的遞歸解決方案，如上所述，有四個釘（稱爲Reve的難題）的河內塔問題的最佳解決方案，更不用說更多釘，仍然是一個懸而未決的問題。這是一個很好的例子，可以通過稍微放鬆一個問題限制來簡化可解決的問題，從而使問題變得更加困難。