河內塔，工作，但不應該

因此，我們有經典的河內問題，我只是進入這個遞歸的事情，它的doozie！這是完全運作，但我只是不明白它可能是如何！正如我所理解的那樣，對於任何n，它都會打印出「從+」到「+直通」，每當n接近1時就會發生這種情況。人們會認爲，在n = 1時，代碼將停止，然後我得到「thru +」的打印輸出到「+ to」（最後打印輸出）。如果n = 1是終止條件，那麼我怎樣才能得到「免費的？」的最後一部分代碼。河內塔，工作，但不應該

我還希望代碼至少在每次迭代時都執行最後一次打印輸出，但不是！此外，這樣的例子總是包括兩個遞歸調用，但這隻適用於一個！這到底是怎麼回事？這段代碼如何一步一步執行？我誤解了關於遞歸方法的一些基本事實嗎？（在Eclipse編譯器上編譯）。

public static void hanoi(char from, char to, char thru, int n) { 
if (n==1) { 
    System.out.println(from + " going to " + to); 
} else { 
    System.out.println (from + " going to " + thru); 
    hanoi(from, to, thru, n-1); 
    System.out.println (thru + " going to " + to); 
} 
    }

來源

2014-04-06 user3504578

使用斷點和單步，看看它是如何運行的分步實施。 – weston

請注意，默認情況下通常有兩個遞歸調用，因爲如果它不是一個移動掛鉤，則將所有移動到'thru'使用'to'作爲新的臨時移動，將最後一個移動''從' - >'移動到' ，然後遞歸將n-1個pegs從'thru'移動到''''使用'from'作爲暫時的。你的實現打印出'2n-1'行，而它應該是'2^n-1' – Sylwester

有我誤解了有關遞歸方法的一些基本事實？

聽起來像你有。您似乎有這樣的印象：即使您多次調用該方法，該方法也只會退出一次。事實上，每一次你打這一行：

System.out.println (from + " going to " + thru); <-- this line 
hanoi(from, to, thru, n-1); 
System.out.println (thru + " going to " + to);

...你還必須打到晚的線在某一點上遞歸調用完成後：

System.out.println (from + " going to " + thru); 
hanoi(from, to, thru, n-1); 
System.out.println (thru + " going to " + to); <-- this line

n == 1是「終止條件」在某種意義上它不會進行額外的遞歸調用。然而，你的「如果」語句仍然有代碼在裏面：

if (n==1) { 
    System.out.println(from + " going to " + to); 
}

該代碼將運行作爲您的最終條件的一部分，但它不會再次調用hanoi方法。但是，這只是遞歸調用的結束。對於其他時間，在此之前調用hanoi，堆棧上仍然存在方法調用，並且需要完成這些方法調用。

System.out.println (from + " going to " + thru); 
    hanoi(from, to, thru, n-1); <-- if `n-1` here was `1`, you'd still have to 
            complete the following line. 
    System.out.println (thru + " going to " + to);

來源

2014-04-06 21:36:57 StriplingWarrior

準確！我預計在n = 1時，它不會再次調用該方法，因此，在n = 1時，我得到了我期望的打印輸出，但在此打印輸出後，我又獲得了三次「System.out.println」打印輸出+「前往」+）;'，最後打印出來。怎麼會這樣？爲什麼在遞歸停止之後我會獲得額外的打印輸出？ – user3504578

@ user3504578：如果'n'從更高的數字開始，那麼到達'n = 1'時，該方法已經被調用了很多次，不是嗎？這些方法調用必須在滿足'n = 1'條件後完成。 – StriplingWarrior

清晰簡潔！非常豐富！十分感謝！爲什麼我的編程講師沒有告訴我這個？ ^^ – user3504578

有人會認爲，在n = 1，代碼將停止

這是一個錯誤的假設所在。守則不會停止。在執行 System.out.println(from + " going to " + to); 該方法返回到它被調用的地方。在你的情況。這就是hanoi(from, to, thru, n-1);被調用的地方。然後它繼續，直到方法結束，因此執行System.out.println (thru + " going to " + to); 然後它又返回到它被調用的地方，並且一直繼續到方法體的結束。這種情況一次又一次地發生，直到您第一次致電hanoi()。

來源

2014-04-06 21:45:11

河內的目標是把所有的東西都從「from」帶到「to」，聽起來有點愚蠢，所以讓我們稱之爲「from」，「left」而不是「right」。對於n = 1，您只需將棋子從左側移動到右側，即可通過規則成功完成遊戲。這就是爲什麼你要顯示的文字，你已經提到。

對於n = 2，您必須將頂部棋子移動到中間位置，將較大的棋子從底部移到右側，然後將較小的棋子從中間移動到右側。

在僞代碼，該讀作：

put the left piece to the middle 

put the (other) left piece to the right 
(note that the roles of middle and right 
have been switched in the call of the 
hanoi-method and n is now 1, so no more calls) 

put the middle piece to the right

來源

2014-04-06 21:45:54

河內塔，工作，但不應該

回答

相關問題