解決河內拼圖塔的遞歸方法

我試圖找出「河內塔」的問題，它通過一種方式將堆棧中從最小到最大的磁盤從起始堆棧移動到目標堆棧。沒有在較小的磁盤上放置較大的磁盤。解決河內拼圖塔的遞歸方法

我被賦予了algorithim：

If numberDisks == 1: 
    Display 「Move the top disk from S to D」. 
Else 
    Move(numberDisks -1, ‘S’, ‘A’, ‘D’); 
    Move(1, ‘S’, ‘D’, ‘A’); 
    Move(numberDisks -1, ‘A’, ‘D’, ‘S’);

然而，這似乎與大多數其他examples不同這似乎不使用移動（1，「S」，「d」，「A」）的工作;在遞歸函數中。

至於我的代碼代表，我似乎重複基本情況的一舉一動，和林不知道如何構建我的打印報表給正確的輸出應該是這樣的：

Move disk 1 from S to D 
Move disk 2 from S to A 
Move disk 1 from D to A 
Move disk 3 from S to D 
Move disk 1 from A to S 
Move disk 2 from A to D 
Move disk 1 from S to D

當試圖移動3個磁盤。

// Recursively solve Towers of Hanoi puzzle 

public static void main(String[] args) { 
    if (handleArguments(args)) { 
     System.out.println("numDisks is ok"); 
     int numDisks = Integer.parseInt(args[0]); 

     Move(numDisks,'s', 'a', 'd'); 
    } 
} 

// recursive case 
public static void Move(int disks, char start, char aux, char destination) { 

    // base case 
    if (disks == 1) { 
     System.out.println("Move disk 1 from S to D"); 

     // if number of disks is 2 or greater 
    } else if(disks > 1) { 
     Move(disks - 1, start, aux, destination); 
     System.out.println("move disk " + disks + " from " + start + " to " + destination); 
     Move(1, start, destination, aux); 
     Move(disks - 1, aux, destination, start); 
    } 
}

來源

2016-02-15 Silverfin

我讀了兩遍，但我仍然不清楚你的問題。你能否考慮改寫你的問題並清楚地表明你的問題？ – user2004685

@ user2004685當然，我的遞歸函數https://gist.github.com/Silverfin13/a7ec33e296396b8c8f90要求用戶輸入他們想放入[河內問題塔]的磁盤數量（http：//www.javawithus .com/programs/towers-of-hanoi），並且一步一步地告訴哪個磁盤要從上到下編號從1到n，以便將所有磁盤移動到目標磁盤。但是，它會爲每一步重複我的基本情況，並且不會正確打印要採取的步驟。 – Silverfin

第一件事：瞭解移動ñ光盤的算法（從S到d，與A）

如果只有一個圓盤移動，只是移動它，然後停止*。
移動N - 選自S 1張光盤爲A，與D.
移動第n個盤從S到d
移動n - 源自A 1張碟片d，與S

*同樣：如果有0張光碟，請停止。（有些人會認爲這是優越的終止條件，因爲在你的代碼中，當有一個特殊情況出現時，它會阻止打印語句，它將由你用第3步打印語句自然處理。例如，您決定更改此方法以返回步驟列表而不是打印它，此更改只能應用於一個位置）

您提到「我似乎重複了每次移動的基本情況「。如果你看看你的代碼，並比較我上面的陳述。你會看到你在我的步驟3和步驟4之間調用Move(1, start, destination, aux);。這就是爲什麼你要重複你的基本情況，因爲你明確地調用，重複你的基本情況，但它沒有任何意義。

我可以看到的另一個主要問題： System.out.println("Move disk 1 from S to D");將總是按順序打印'S'和'D'，當您經常需要指定不同的移動時，確保使用該語句的參數。

我不認爲還有其他東西，但試試看。

回覆您在帖子開始時給出的例子。它會產生比你的版本差別很大的輸出。

您的指定（或嘗試）在每個步驟應移動光盤的大小，本示例僅指定將光盤移動到哪個堆棧，而不管其大小。

以1作爲其中間參數的遞歸調用將打印用於移動堆棧中最終光盤的移動指令（我的步驟3）。

來源

2016-02-15 06:30:41 moreON

我似乎仍然得到一個奇怪的[輸出]（https://gist.github.com/Silverfin13/77430ce38895650922a2） – Silverfin

@ShahobMousavi請詳細說明。你有什麼改變，你的新輸出是什麼？你認爲是什麼導致它不正確？（如果你需要添加格式良好的信息，你可以編輯你的問題） – moreON

@ShahobMousavi你應該再看看你的遞歸調用，以及定義中參數的排序。（以及特殊情況下的打印行中的空格） – moreON

解決河內拼圖塔的遞歸方法

回答

相關問題