移動手順を文字列で出力するプログラムを考えます.
左の杭を A, 真ん中の杭を B, 右の杭を C とします. 小さい順に 1番から n番まで円盤には番号が付いているとします.
A の杭にある全ての円盤を C の杭に移します.
円盤の個数をコマンドライン引数として与えると
move disc #1 from A to C move disc #2 from A to B ...
のように, 移動するべき円盤の番号と, 移動元および移動先の杭の名称を出力するようにします. 引数が無い場合は円盤の数を 3 とすることにします.
円盤の数を 3 としたときの実行結果は以下のようになります.
move disc #1 from A to C move disc #2 from A to B move disc #1 from C to B move disc #3 from A to C move disc #1 from B to A move disc #2 from B to C move disc #1 from A to C
以下のように考えて実装してみます.
n番以下の全ての円盤を杭srcから杭dstに動かすには, もうひとつの杭を tmp として,
- n – 1 番以下の全ての円盤を杭src から, 杭tmp に動かす.
- n番の円盤を杭src から杭dst に動かす.
- n – 1 番以下の全ての円盤を杭tmp から, 杭dst に動かす.
n – 1番以下の全ての円盤を杭src’ から, 杭dst’ に動かすには, src’ を新しい src として, dst’ を新しい dst として, n – 1 を新しい n として, 上記と同じことをします.
ただし, 新しく n として設定した値が 0であれば, 目的達成です.
C 言語で記述したものです.
#include <stdio.h>
#include <stdlib.h>
static void
hanoi(char src, char tmp, char dst, int n)
{
if (n == 0)
return;
hanoi(src, dst, tmp, n - 1);
printf("move disc #%d from %c to %c\n", n, src, dst);
hanoi(tmp, src, dst, n - 1);
}
int
main(int argc, char *argv[])
{
int n = (argc < 2)?3:atoi(argv[1]);
hanoi('A', 'B', 'C', n);
return 0;
}
以下は Haskell で記述したものです.
import System
format :: (Int, Char, Char) -> String
format (n,s,d) = "move disc #" ++ (show n) ++ " from " ++ [s] ++ " to " ++ [d]
hanoi :: Char -> Char -> Char -> Int -> [(Int, Char, Char)]
hanoi _ _ _ 0 = []
hanoi s t d n = hanoi s d t (n - 1) ++
[(n, s, d)] ++
hanoi t s d (n - 1)
main = do args <- getArgs
let n | (not . null) args = read (head args)::Int
| otherwise = 3
putStr $ unlines $ map format $ hanoi 'A' 'B' 'C' n
6〜10行目が, 主要な関数の定義です. C の場合と違い, この関数の中で出力を行うわけではありません.
15行目が, 動作の本体であり, $ を挟んで, 右側から左側に処理されたデータが引き渡されていきます.
hanoi ‘A’ ‘B’ ‘C’ n は [(1, 'A', 'C'), (2, 'A', 'B'), ...] のような, 円盤を動かす手を表すタプルのリストを返します.
map format で ["move disc #1 from A to C", "move disc #2 from A to B", ...] のように, 各タプルを整形,
unlines が “move disc #1 from A to C\nmove disc #2 from A to B\n…” (\n は改行です) のように行の集合に変換,
putStr が出力します.
UNIX のパイプに似ていると思う方もいらっしゃるかもしれません.
このような小さなプログラムでは, 大きな違いとはなりませんが, 出力の方法が, パズルを解く部分に組み込まれていないところが, 分離性が良いですね.
