目前，我已經學習了 3 種不同的方法來計算解決河內塔的最小移動量。
第一種方法是：“圓盤”的 2 次方減去 1。總而言之，非常直接且易于理解。
const towerHanoi = (discs) => 2**discs - 1;
console.log(towerHanoi(0)); // 0
console.log(towerHanoi(2)); // 3
console.log(towerHanoi(3)); // 7
console.log(towerHanoi(4)); // 15
console.log(towerHanoi(5)); // 31
console.log(towerHanoi(6)); // 63
第二種方法是使用“for 回圈”。在每次迭代中，將“count”添加到 2 的“i”次方，再一次，非常直接且易于理解。
function towerHanoi(discs,count=0) {
for (let i = 0; i < discs; i ) count = 2**i;
return count;
}
然而，在遞回的第三種方法中，我只是不能完全掌握遞回程序的概念。
const towerHanoi = (discs) => discs === 0 ? 0 : 2 * towerHanoi(discs-1) 1;
讓我們以 5 張棋子為例來說明遞回程序，該程序至少需要 31 步才能完成游戲。我將盡我所能分解遞回程序，如下所示：
2 * (5-1) 1 === 9
2 * (4-1) 1 === 7
2 * (3-1) 1 === 5
2 * (2-1) 1 === 3
2 * (1-1) 1 === 1
9 7 5 3 1 --> 25 =/= 31
如您所見，我得到的是 25 而不是 31。我錯過了什么。有人可以幫我理解代碼的遞回程序嗎？感謝您閱讀并提前百萬感謝:)
uj5u.com熱心網友回復：
這個遞回公式背后的推理：
const towerHanoi = (discs) => discs === 0 ? 0 : 2 * towerHanoi(discs-1) 1;
...如下：
假設我們知道如何將discs-1圓盤從一堆移到另一堆。然后我們可以按如下方式使用該知識：
將所有圓盤（除了底部的圓盤）移動到中間位置（使用該知識）。然后將最大的圓盤移動到最后一個位置。最后將中間的堆疊移到最大的圓盤上，再次應用該知識。
所以確實，我們需要移動一疊discs - 1棋子兩次，然后再移動一次。這給了我們公式的遞回部分。
至于你對 5 張光碟的分析。您沒有正確應用遞回。(5-1) 不能像那樣評估——它仍然需要擴展到更深的遞回級別。這是應該如何完成的：
2 * (
2 * (
2 * (
2 * (
2 * (
0 = 0 (base case)
) 1 = 1
) 1 = 3
) 1 = 7
) 1 = 15
) 1 = 31
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/452507.html
標籤：javascript 算法 递归 ecmascript-6
上一篇：接受字串并識別連續字母數的代碼
下一篇：如何優化brainf*ck指令