0

我想知道如何在haskell中编写代码来了解 n个“圆盘”和3根棍子（A、B、C）的运动次数

基本情况（N=1）：运动 A --> C 所以 1 运动

归纳案例（N = M+1）：我移动 M 个圆盘“A”--->“C”，我移动 1 个圆盘“A”--->“B”，最后我从“C”移动 M 个圆盘到“B”。我认为解码代码可能是这样的：

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

现在，比较 . 的第一分句和第三分句中的英语numMoveHanoi。然后比较第一个和第三个子句中的 Haskell numMoveHanoi。

（作为一个练习：比较第二和第三子句中的英语。然后比较第二和第三子句中的 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 回答