0

n個の「ディスク」と3本のスティック（ A 、 B 、 C ）の動きの数を知るために、haskellでコードを書く方法を知りたい

基本ケース ( N=1): 動き A --> C なので 1 動き

帰納的な場合 ( N = M+1 ) : M 個のディスク "A" ---> "C" を移動し、1 つのディスク "A" ---> "B" を移動し、最後に "C" から M 個のディスクを移動します。 「B」に。deコードは次のようになると思いました：

numMoveHanoi 0 = 0 
numMoveHanoi 1 = 1 
numMoveHanoi n = m+1 + numMoveHanoi m 
                 where m = n-1

残念ながら、これは numMoveHanoi 2 の場合にしか機能しません。それ以外の場合、結果は間違っています。再帰定義のどこが間違っているのかわかりません。

みんな、ありがとう。

4

2 に答える 2

5

まあ、あなたの英語と Haskell を並べてみてください。

numMoveHanoi {- Base case ( N=1) -} 1
    = {- Movement A --> C so 1 movement -} 1
numMoveHanoi {- Inductive case -} n
    = {- I move M discs "A" ---> "C" -} m
    + {- I move 1 disc "A" ---> "B" -} 1
    + {- I move M discs from "C" to "B" -} numMoveHanoi m
    where {- ( N = M+1 ) -} m = n-1

ここで、 の 1 節目と 3 節目の英語を比較しnumMoveHanoiます。次に、 の最初の節と 3 番目の節の Haskell を比較しnumMoveHanoiます。

(そして演習として: 2 番目と 3 番目の節の英語を比較してください。次に、2 番目と 3 番目の節の Haskell を比較してください。これは同じバグのインスタンスですか? なぜですか?)

于 2013-10-27T17:22:53.163 に答える
0

ハノイの塔の再帰的な解法を考えてみましょう: n 個の円盤で塔を解くには、最上部の n-1 個の円盤を予備のプラットフォーム (numMoveHanoi (n-1)) に移動し、n 番目の円盤 (1) を移動し、 n 番目の dics (numMoveHanoi (n-1)) の上の n-1 個のディスク。次に、一般的なケース：

numMovesHanoi n = numMoveHanoi (n-1) + 1 + numMoveHanoi (n-1)
{- or numMovesHanoi n = 2 * numMoveHanoi (n-1) + 1 -}
于 2013-10-29T01:37:59.050 に答える