《C編程技巧：117個問題解決方案示例 》 —3.7　解決經典的漢諾塔問題

3.7　解決經典的漢諾塔問題

你想用遞歸的方法解決漢諾塔的經典問題。

解決方案

編寫一個C程序，按照以下規格說明使用遞歸方法解決漢諾塔的經典問題：

程序要求用戶輸入圓盤數n（1≤n≤10）。

程序定義了函數move()，它以遞歸方式調用自身來解決問題。

程序在屏幕上顯示計算結果。

代碼

以下是使用這些規格說明編寫的C程序的代碼。在文本編輯器中鍵入以下C程序，并將其保存在文件夾C:\Code中，文件名為Hnoi.c：

編譯并執行此程序。這個程序的運行結果在這里給出：

工作原理

傳說漢諾塔位于漢諾城的一座寺廟中，該地位于亞洲。有三個如圖3-4所示的立柱，此外，還有64個金盤，所有金盤的半徑都不同。每個圓盤在中心都有一個孔，這樣圓盤可以堆疊在任何立柱上，從而形成一個塔，就像一堆堆成紡錘形的CD。首先，圓盤按照從上到下逐漸增加的半徑的順序堆疊在左立柱上（參見圖3-4，但該圖僅顯示了四個圓盤）。寺廟中的僧侶試圖將所有64個圓盤都移動到右立柱。中間的立柱可用于臨時存放。他們的行為受到以下條件的限制：

應一次移動一個圓盤。

從立柱上取下的圓盤不能放在地上。它必須放在三個立柱中的一個上面。

較大的圓盤不能放在較小的圓盤上面。你當然可以將較小的圓盤放在較大的圓盤上面。

圖3-4　在遞歸過程中可以成功解決經典的漢諾塔問題

人們相信，當完成分配給僧侶的任務時，世界將會終結。計算機科學家對這個問題表現出濃厚的興趣，因為它顯示了遞歸的效用，而不是因為他們對世界末日的可能性感到擔憂。使用遞歸，可以通過編寫一個簡單的程序來解決這個問題。雖然你也可以簡單地利用迭代而不使用遞歸來解決這個問題，但程序會變得非常復雜。

出于編程目的，你可以假設左立柱周圍堆疊了n個圓盤，其中n是整數變量。圓盤從上到下依次編號，最上面的圓盤編號為1，最下面的圓盤編號為n。讓我們開發一個程序，用于將n個圓盤從左立柱移動到右立柱，而不違反前面提到的三個條件中的任何一個。問題可以用遞歸形式表示如下：

1.使用右立柱來臨時存放，將頂部的（n-1）個圓盤從左立柱移動到中間立柱。

2.將第n個圓盤（最大的圓盤，因此也是最下面的圓盤）從左立柱移動到右立柱。

3.使用左立柱來臨時存放，將（n-1）個圓盤從中間立柱移動到右立柱。

所有這三個步驟準確無誤地出現在LOC 19～25中定義的遞歸函數move()中。對于每次遞歸調用，n的值減1，因此遞歸在有限數量的調用之后停止。此外，n＝0是此程序的停止條件。

c語言 C 語言

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。