3

以下のコードは、事前定義された関数 moveLOD、swapLOI、および swapLID を使用して手のリストを返す hanoi を解決します。

MoveLOD: 1 つのディスクを 1 番目の位置から 3 番目のピンの 3 番目の位置に移動します。さらに、動きに関する情報を含む文字列が文字列のリストに積み上げられています。

type Pin = (Char, Int)        -- Represents a rod, named for a character and the number of disks in it.
type Plate = (Pin, Pin, Pin)  -- Represents the configuration of the three rods.(Origin,Intermediate,Destination
type Log = (Plate, [String])  -- Represents a state formed by the configuration of rods and a list of strings that will record the movements made by the algorithm.


moveLOD :: Log -> Log
moveLOD (((o,n), i ,(d,k)),s) = (((o,n-1), i ,(d,k+1)), (o:" -> " ++ [d]):s)

-- swapLOI: Change the positions of the origin rods and intermediate rods.
swapLOI:: Log->Log
swapLOI ((o,i,d),s) = ((i,o,d),s) 

-- swapoLID : Change the positions of the intermediate rods and destination rods.
swapLID:: Log->Log
swapLID ((o,i,d),s) = ((o,d,i),s)

hanoi :: Log -> Log
hanoi:: Int->Log->[String]
hanoi 1 log = transformaLista(moveLOD log)
hanoi n log = hanoi (n-1) (swapLID log) ++ hanoi 1 log ++ hanoi (n-1) (swapLOI(log))

changeToList::Log->[String]
changeToList(p,s) = s

callHanoi:: Int->[String]
callHanoi n = hanoi n ((('O',n),('I',0),('D',0)),[])
4

2 に答える 2

4 
hanoi :: Log -> Log
hanoi ((('o',0),i,d),s) = ((('o',0),('i',0),('d',0)), [])
hanoi ((('o',1),i,d),s) = moveLOD((('o',1),i,d),s)
hanoi ((('o',n),i,d),s)= hanoi(swapLOI(hanoi(swapLOI(swapLID(moveLOD(swapLID((('o',n),i,d),s)))))))

Charの最初Pinの がPlateである引数の関数のみを定義し'o'ます。文字が他のものである場合の方程式も提供する必要があります。

定義式があるパターンのいずれにも一致しない引数を受け取ると、「非網羅的なパターン」エラーが発生します。それを修正する唯一の方法は、残りのパターンの方程式を提供することです。

修正されたコードでは、まず、元のピンが空の場合の扱いが正しくありません。

hanoi (((o,0),i,d),s) = ((('o',0),('i',0),('d',0)),[])

これは、このケースが適用されるときはいつでも、何が何であろうdと結果が同じであることを意味しiます。fromが2 より大きい引数hanoiで呼び出されると、ある時点で元の極が空になり、呼び出しチェーンのそれより上は と のみであるため、その定数の結果が泡立ちます。(は 2 番目の方程式によって直接解かれます)の正しい結果が得られます。これは、両方の再帰呼び出しが元の極に 1 つのディスクしかないためです。chamahanoihanoiswapLOIn == 2n == 1hanoi

そのケースは

hanoi (((o,0),i,d),s) = (((o,0),i,d),s)

一般的な場合の再帰が間違っているため、それでも正しい結果は得られません (間違った一連の動き)。

君は

  • 上部ディスクを中間ピン ( swapLID . moveLOD . swapLID) に移動します。
  • 次に、残りのディスクを移動先 ( hanoi) に移動しますが、最小のディスクが中間のピンにあり、他のディスクをそこに配置できないため、これは許可されません。
  • 最後に、(現在空になっている) 起点ピンを中間として使用して、ディスクを中間ピンから宛先に移動します。

あなたがすべき

  • n-1ディスクを原点から中間ピンに移動し、
  • 次に、一番下（最大）のディスクを移動先に移動します。
  • 最後に、n-1ディスクを中間から宛先に移動します。

移動するディスクの数を追跡する追加の引数がなければ、これを行う簡単な方法がわかりません。4 ディスクのゲームを考えてみましょう。最初に、上の 3 つのディスクが中間のピンに移動され、次に下のディスクが目的のピンに移動されます。ここでのタスクは、元のピンをヘルパーとして使用して、3 つのディスクを中間のピンから目的のピンに移動することです。

正しい方法はシーケンスです

  1. i -> d ( ([],[1,2,3],[4]) -> ([],[2,3],[1,4]))
  2. i -> o ( ([],[2,3],[1,4]) -> ([2],[3],[1,4]))
  3. d -> o ( ([2],[3],[1,4]) -> ([1,2],[3],[4]))
  4. i -> d ( ([1,2],[3],[4]) -> ([1,2],[],[3,4]))
  5. o -> i ( ([1,2],[],[3,4]) -> ([2],[1],[3,4]))
  6. o -> d ( ([2],[1],[3,4]) -> ([],[1],[2,3,4]))
  7. i -> d ( ([],[1],[2,3,4]) -> ([],[],[1,2,3,4]))

手順 2 の後、元の宛先ピンは、ディスク (まあ、1 つ) の移動元のピンになりますがo、この状況では最下位のディスクは移動されません。唯一の情報が各ピンにあるディスクの数と、ディスクをどこからどこに移動するかである場合、どのようにそれを達成できますか?

のタイプをhanoiに変更すると

hanoi :: Int -> Log -> Log

そしてそれを呼び出します

chamahanoi n = hanoi n ((('o',n),('i',0),('d',0)),[])

実装は簡単です。

それをしたくない場合、または許可されていない場合は、各ピンのサイズを追跡し、ディスクをより大きなピンにのみ移動するか、適切なピンでディスクをこっそり削除して追加してエミュレートすることができますその制限ですが、適切な説明がなければ不正行為と区別するのは難しいでしょう.

于 2012-10-06T14:17:35.487 に答える
3

それが誰かを助けるなら、ここにハノイのアルゴリズムの別の塔があります：

hanoi 0 _ _ _ = []
hanoi n a b c = hanoi (n-1) a c b ++ [(a,b)] ++ hanoi (n-1) c b a

たとえば、hanoi 2 "a" "b" "c" == [("a","c"), ("a","b"), ("c","b")]

于 2014-12-25T05:31:08.427 に答える