漢諾塔 - 簡單算法

Question

解決漢諾塔一個簡單的遞歸代碼：

public static void hanoi(char A, char B, char C, int n) { 
    if(n>0) { 
    hanoi(A,C,B,n-1); 
    System.ouit.println("moving from " + A + " to " + B); 
    hanoi(C,B,A,n-1); 
} 
} 

我和我的同學都檢查這些代碼今天，雖然我們知道它是如何工作的，我們無法理解的算法，這意味着我們永遠不會想到這樣的解決方案。

我確實記得一位老師曾經說過，我們不在乎它是如何解決的，我們只是假設它是如此。他指的是函數自己調用的部分。

我知道我們基本上分兩步解決河內塔。首先將所有戒指移到C（這是一個來自老師的代碼，在這種情況下，我們希望將所有戒指移到B而不是C），然後將最大的戒指移動到B，然後將所有剩餘的戒指從C移動到B。在第一個調用中，我們從A移動到C，第二個從C移動到B. 我在紙上寫了如何執行代碼並獲得正確的打印，但我仍然不明白。我明白，但我不明白，如果你明白我的意思。

PS：我查過很多影片，我找到的鏈接，沒有人給我任何值得的答案，以你怎麼會想到這樣一個算法的出藍色。這是不同的，例如fibonaccis序列，這是合乎邏輯的。但是，這...

編輯：這是我很難甚至解釋什麼我不明白，我從未有過的編程問題。我知道這段代碼是如何工作的，我可以在紙上寫下整個過程。我知道如何解決河內塔。但如果你要給我一個任務來寫一個河內大廈的算法，我永遠不會想到這一點。我正在看這個代碼，我在說，這個代碼是如何給出正確的打印輸出的？我對這個信念的飛躍有一個問題，但不知怎的，這是遞歸的工作原理。基本上對於前兩個環，我沒有理解這個算法的工作原理。但從那時起，移動的戒指是不同的，因爲你已經有2個戒指坐在一個釘子上，你必須移動它們，然後才能移動更多的戒指，然後將這些舊戒指放回去。呃，我從來沒有遇到過編程方面的問題，這真的讓我感到困擾，因爲這只是一個開始，它應該是非常簡單和合乎邏輯的，我們的老師甚至不會解釋它是如何工作的，他只是給了我們代碼並感動上。

Answer 1

將hanoi函數的調用看作是「使用主軸C作爲備用，將整個磁盤從主軸A移動到主軸B」。如果你願意認爲它可以完成，則將其概念化爲函數調用。應當清楚幾分鐘後認爲，這可通過移動樁上述底部盤，其具有n-1磁盤，主軸A到備用，主軸C，底部盤移動至其目的地主軸乙來完成，然後將備用堆上的堆從C移動到B.由於移動堆被假定爲函數調用，堆移動是通過遞歸調用在移動底部磁盤之前和之後完成的。剩下的唯一問題是要認識到什麼時候沒有更多的事情要做。這是通過您的n計數器完成的，計數器表示要移動的堆中的磁盤數量。當它爲零時，不需要採取任何行動。

河內的塔是「遞歸信仰飛躍」的一個很好的例子，在這個例子中，你假設解決方案可以通過函數調用，然後將函數應用於一個或多個子問題+一個微不足道的情況。

Answer 2

看看是否有幫助：http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/video-lectures/1b-procedures-and-processes-substitution-model/從47:15開始。這些課程令人驚歎，不僅具有歷史意義。其中，河內塔。不要擔心在lisp中給出的類，這是相同的原則。