Re: [問題] 河內塔

看板C_and_CPP (C/C++)作者gba356 (瑪利歐)時間16年前 (2009/03/06 17:35)推噓3(3推 0噓 6→)

留言9則, 4人參與討論串2/3 (看更多)

※ 引述《XDGG ( )》之銘言： : 請問一開始三根塔上都有環的如何解呢? : 我只會起始狀態只有一塔有環的 : 謝謝你的描述有點模糊.. 因此我假設你問題的意思是：「從非初始狀態的特定狀態繼續完成河內塔」這應該是最一般的狀態了:) 小的不才，以前有寫過一個教學弟的文章，就是解第 m 步河內塔狀態，和解出 m+1 步的文章，希望能對你有幫助:) 獻醜了> < Binary Solution n 對於 n 個盤子的河內塔問題，我們知道一定有一個最佳解，能在 2 - 1 步解出該河內塔問題，那麼給定數字 m，試問第 m 步時的狀態？ n 觀察移動的次數，我們發現 0 到 2 - 1 步中每個狀態恰好對應到了一個數字 m，因此從一些規則，我們可以由 m 的二進位表示觀察出河內塔的狀態。觀察最大的盤子 n，我們知道原本的遞迴大概是長這樣的： I. Hanoi( N-1,Source,Destination,Intermediate ); //將 n-1 個盤移動至中間柱 II. Move from Source to Destination; //移動最底層的盤子 III.Hanoi( N-1,Intermediate,Source,Destination ); //將 n-1 個盤移動至終點柱 n-1 其中由先前的計算知道，步驟 I. 和 III. 需要花 2 - 1 步，步驟 II. 花一步。因此 n-1 可以明確地知道，最大的盤子 n，是從 2 步開始被挪到終點柱上面的，且任何時間它都 ┌───────────────────┐ │ n-1 │ 在中間柱上，因此若│ m ≧ 2 ，最底層的盤子位於終點柱上。│ │ │ └───────────────────┘ 事實上，框中的結論可以推導出：若二進位下 m 的第 n 位是 1，那麼最大的盤子位在終點，否則它還在起點。（如果你忘了二進位：二進位下第一位是二的零次方，第二位是二的一次方，因此第 n 位是二的 n-1 次方）有了這個美妙的結論以後，我們可以拿他來做更多事情。知道了最大的盤子 n 在哪裡，那 n-1 呢？直覺性的第一個應該會先想到，看 n-1 位是 1、或是 0，但那是錯的，因為河內塔是遞迴的進行，因此起點、終點和中介柱是相對的，所以我們不能這樣判斷。 n-1 那該怎麼判斷呢？我們回過頭來複習河內塔的遞迴解。我們看到前面的 2 - 1 步 n-1 在做的事是把前 n-1 個盤子從起點挪到中介柱，而後 2 - 1 步是把中介柱上的 n-1 個盤子挪到終點柱。運用遞迴的概念，我們的問題解決了！只要像河內塔遞迴解中把「起點」、「中介」、「終點」這幾個相對的係數調整一下就行了！我們可以造出以下遞迴的程式：因為用原本的命名會讓整個程式相當冗長，因此 source 以 src 代替，intermediate 以 aux(auxiliary) 代替，destination 以 des 代替： PROCEDURE BinarySolution( m,n,src,aux,des ) { if( n = 0 ) return; if( n-th bit of m = 0 ) PRINT( Position of disk n: src ); BinarySolution( m,n-1,src,des,aux ); else PRINT( Position of disk n: des ); BinarySolution( m,n-1,aux,src,des ); } 其中這個演算法在實作時有幾個優化可做，例如以位元運算快速的求得 m 的第 n 位，和解遞迴。由於這個演算法是尾歸遞迴，因此我們可以單純地視 m 的第 n 位的零一交換 aux,des 或 src,aux，而縮成迴圈。我把一部分切掉了，留給你思考囉^^ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.137.30.128