文書の過去の版を表示しています。
目次
いろんな言語でハノイの塔
概要
様々なプログラミング言語に手を出す時に、とりあえず書いてみているのが「ハノイの塔」である。 仕様としては、引数として、円盤の枚数をとり、省略時には3が指定されたものとする。 円盤の移動の手順を表示し、可能であればかかった経過時間を表示する。 円盤の移動は、1番の軸から2番の軸へ行うものとして、3番の軸を作業用に使用することが出来る。
ハノイの塔
いわゆるハノイの塔は64枚の円盤と三本の柱からなる。 64枚の円盤は下のものから順に小さくなっており、同じ大きさの円盤はなく、円盤は自身より大きな円盤の上にしか置けない。 これを、1の柱に64枚全てが入った状態から始めて、2の柱にすべての円盤が移動完了した時点で完成となる。
言い伝え(?)によれば、バラモン僧たちが手でこれを行っており、完成するときが世界の終わりになるらしい。
数学的には、n枚の円盤からなる場合、n-1個の円盤を1から3へ移動し、n番目の円盤を1から2へ移し、n-1個の円盤を3から2へ移動するという、帰納的な解法で解くことができることが知られており、いわゆる再帰型プログラムの代表的な例題となっている。
性能
言語 | バージョン | CPU | OS | -n 4 の実行時間[ms] |
---|---|---|---|---|
PowerShell | 5.1.17763.592 | Core i7-2620M (2.70GHz) | Windows 10 Pro (1809) | 22.9854 |
PowerShell Core | 6.2.0 | ARMv7 | Deban 9 | 74.4272 |
Cmd.exe | 10.0.17763.592 | Core i7-2620M (2.70GHz) | Windows 10 Pro (1809) | 250 |
C (gcc) | 4.9.3 | Celeron N3150 (1.60GHz) | Vine Linux 6.5 | 3 |
C++ (g++) | 4.9.3 | Celeron N3150 (1.60GHz) | Vine Linux 6.5 | 8 |
Objective C (gcc) | 4.9.3 | Celeron N3150 (1.60GHz) | Vine Linux 6.5 | - |
Common Lisp | 2.49 | Celeron N3150 (1.60GHz) | Vine Linux 6.5 | 34 |
GNU Prolog | 1.4.4 | Celeron N3150 (1.60GHz) | Vine Linux 6.5 | 11 |
プログラム
PowerShell
能書き
PowerShellはWindowsにおいて、Cmd.EXEにかわる新しいコマンドシェルであり、また .NET Frameworkのフロントエンドでもある。 MicrosoftはWindows環境のみならず、Linuxなどへの展開も積極的に行っているようである。 ハノイの塔ごっこは、別に PowerShellから始めたわけでもないのに、これが最初に書かれているのは、このWikiのエントリーを作った時に書いたのが PowerShell版だから。
なお、PowerShell Coreでも同じコードを利用している。 PowerShell Coreは、PowerShell のオープンソース版で、GitHubにレポジトリがあるが、事実上提供されているバイナリパッケージでのみ利用する方向のようである。 1)
コード
Hanoi.ps1
として以下のコードを作成した。
なお、デジタル署名するのが面倒くさかったので、実行にあたっては、実行ポリシーをAllSigned
からRemoteSigned
に変更した。
2)
一般的な関数型言語が採用している、関数呼び出しと違い、引数を括弧でくくってカンマで区切ってはいけない。
括弧でくくってカンマで区切るとそれは配列として、関数の第一引数に全て渡されてしまう。
あくまでシェルスタイルの、関数名の後ろにスペース区切りで引数を列挙すること。
3)
基本的に、1-pass型のスクリプト言語なので、前方参照はできない。なので、関数などは、先に定義しておいて、後から呼び出すPascal的なスタイルとなる。
なお、Param()
は便利な機能だが、関数4)の先頭以外にはおけないことに留意が必要。
Param()
の前にコードがあると、Param()
がエラーとなる。
分かりにくいので、気づきにくいミス。
Param([Int]$n = 3) function Hanoi { Param([Int]$discs,[Int]$a=1,[Int]$b=2,[Int]$c=3) if ($discs -eq 0) { return } [Int]$n = $discs - 1 Hanoi $n $a $c $b Write-Output "Disc ${discs} moved from ${a} to ${b}." Hanoi $n $c $b $a return } $s = Get-Date Hanoi $n $e = Get-Date $diff = $e - $s $msec = $diff.TotalMilliseconds Write-Output "Elapsed Time: ${msec} [msec]."
実行結果
第2世代Core i7のVAIO Z2(VPCZ2)上のWindows 10/PowerShell 5.1.17763.592で実行した。
PS C:\Users\araki> .\Documents\Hanoi.ps1 -n 4 Disc 1 moved from 1 to 3. Disc 2 moved from 1 to 2. Disc 1 moved from 3 to 2. Disc 3 moved from 1 to 3. Disc 1 moved from 2 to 1. Disc 2 moved from 2 to 3. Disc 1 moved from 1 to 3. Disc 4 moved from 1 to 2. Disc 1 moved from 3 to 2. Disc 2 moved from 3 to 1. Disc 1 moved from 2 to 1. Disc 3 moved from 3 to 2. Disc 1 moved from 1 to 3. Disc 2 moved from 1 to 2. Disc 1 moved from 3 to 2. Elapsed Time: 22.9854 [msec]. PS C:\Users\araki>
Batch (Cmd.exe)
能書き
言わずと知れたDOS由来のバッチコマンドによる実装である。 本来、リカーシブなコールなど書けないのだが、Windows NT以降の拡張でそれもなんとかこなせるようになっている。 プログラム言語として見たときに非常に非力なので、本来このようなことをさせることはないのだが、場合によっては、これしか使えないこともあるので、それなりに書けるスキルがあっても損はないだろう。
なお、実行速度は頭が痛くなるレベルである。
コード
Hanoi.bat
として以下のコードを作成した。
setlocal enabledelayedexpansion
しているが、今コードを見返してみると全く必要性がないように思う。
おそらく、初期の実装でリカーシブな処理をするときに何かそのあたりの機能を使おうとした名残だと思われる。
:HANOI
の中で、setlocal
することで、変数を関数ローカルにし、リカーシブな処理を実現している。
SET /A D=%1 - 1
はD
に%1 - 1
を計算した値を設定するというコマンドで確かこれがNT由来の拡張機能だったはずなので、DOSのcommmand.comでは動作しないハズである。
経過時刻を求めるために、%TIME%
環境変数を利用しているが、単純に時、分、秒に分解したときに、08
や09
という値は、八進数として扱われエラーとなる。
これを回避するために:NORMALIZE
という関数を用意して、文字列08
および09
は、数値に置きかえるように処理している。
@echo off setlocal enabledelayedexpansion SET CMD=%~nx0 SET DISCS=3 :OPTPARSE IF "%1" == "" GOTO MAIN IF "%1" == "-h" GOTO HELP IF "%1" == "-n" ( SET DISCS=%2 shift ) shift GOTO OPTPARSE :MAIN CALL :GETTIME SET ST=%ERRORLEVEL% CALL :HANOI %DISCS% 1 2 3 CALL :GETTIME SET /A ET=%ERRORLEVEL% - %ST% ECHO Elapsed Time %ET%0 msec. >&2 GOTO END :HANOI IF %1 == 0 EXIT /b setlocal SET /A D=%1 - 1 CALL :HANOI %D% %2 %4 %3 ECHO Disc %1 moved from %2 to %3 CALL :HANOI %D% %4 %3 %2 endlocal exit /b :GETTIME CALL :NORMALIZE %TIME:~0,2% SET H=%ERRORLEVEL% CALL :NORMALIZE %TIME:~3,2% SET M=%ERRORLEVEL% CALL :NORMALIZE %TIME:~6,2% SET S=%ERRORLEVEL% CALL :NORMALIZE %TIME:~9,2% SET MS=%ERRORLEVEL% SET /A T1=%H% * 360000 + %M% * 6000 + %S% * 100 + %MS% EXIT /b %T1% :NORMALIZE SET V=%1 SET V=%V:08=8% SET V=%V:09=9% EXIT /b %V% :HELP echo %CMD% :- echo ^ -n ^<NUM^>: Number of discs. echo ^ -h : show this message. GOTO END :END endlocal echo on
実行結果
PowerShell版と同じ環境で実行したが、恐ろしく遅い。
C:\Users\araki\Documents>Hanoi -n 4 Disc 1 moved from 1 to 3 Disc 2 moved from 1 to 2 Disc 1 moved from 3 to 2 Disc 3 moved from 1 to 3 Disc 1 moved from 2 to 1 Disc 2 moved from 2 to 3 Disc 1 moved from 1 to 3 Disc 4 moved from 1 to 2 Disc 1 moved from 3 to 2 Disc 2 moved from 3 to 1 Disc 1 moved from 2 to 1 Disc 3 moved from 3 to 2 Disc 1 moved from 1 to 3 Disc 2 moved from 1 to 2 Disc 1 moved from 3 to 2 Elapsed Time 250 msec. C:\Users\araki\Documents>
C (gcc)
能書き
何はなくともC言語である。
特に何の工夫もなく、教科書に出ているようなサンプルのコードを実装した。
「実装した」といったが、どういうわけか、ソースが失われてバイナリだけが残っている。
別に、新しく書いてもいいんだけれど、面倒クサイので、コードはそのうち発掘されたら掲載する。
なので、今は何もない。
Cのコードくらいすぐ書けるわ!
ということで、帰宅中の東海道線の中で書いたので掲載しておく。
コード
多分こんなだったと思い出しながら書いた。
getopt()
を使ったはずだけれど、違ったかも知れない。
本体はHanoi()
関数であり、それ以外の部分は全て冗長である。
#include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <libgen.h> char *cmd = NULL; void usage(void) { fprintf(stderr, "%s:-\n" "\t-n <int>: set number of discs. (default: 3)\n" "\t-h: show this message.\n", cmd); exit(1); } void Hanoi(int discs, int a, int b, int c) { int n = discs - 1; if (discs == 0) { return; } Hanoi(n, a, c, b); printf("Disc %d moved from %d to %d\n", discs, a, b); Hanoi(n, c, b, a); } void main(int argc, char *argv[]) { int c; opterr = 0; /*disable error log */ int n = 3; cmd = basename(argv[0]); while ((c = getopt(argc, argv, "n:h")) != -1) { switch (c) { case 'h': usage(); break; case 'n': n = strtol(optarg, NULL, 0); break; default: usage(); break; } } Hanoi(n, 1, 2, 3); exit(0); }
実行結果
当たり前だが、非力なCeleron N3150環境下でも速い。
速すぎて計測に意味がない。
多分、-n 20
くらいでやった方がいいんだろうと今更思う。
araki@chive[117]% time ./hanoic -n 4 Disc 1 moved from 1 to 3. Disc 2 moved from 1 to 2. Disc 1 moved from 3 to 2. Disc 3 moved from 1 to 3. Disc 1 moved from 2 to 1. Disc 2 moved from 2 to 3. Disc 1 moved from 1 to 3. Disc 4 moved from 1 to 2. Disc 1 moved from 3 to 2. Disc 2 moved from 3 to 1. Disc 1 moved from 2 to 1. Disc 3 moved from 3 to 2. Disc 1 moved from 1 to 3. Disc 2 moved from 1 to 2. Disc 1 moved from 3 to 2. 0.001u 0.003s 0:00.00 0.0% 0+0k 0+0io 0pf+0w araki@chive[118]%
C++ (g++)
Cが来たらばとりあえずC++でも書くだろう。
能書き
とりあえず、C++らしく、Hanoi
をクラスにして、円盤の枚数を持ったインスタンスを作り、run
関数を呼び出して実行する。
外向き(public
)のrun
は引数を持たないが、内部で再帰的に呼び出される方は、引数を持っている。
このあたりちょっとC++っぽく書いてある。
Boostを使っているのは、コマンドライン引数の処理をしてくれる手頃なライブラリだからというだけで、別にGNU のparseoptなんかを使っても良かったのだが、まあ、そんな感じで、多分このせいでCに比べてやや遅くなっている。
コード
#include <iostream> #include <string> #include <boost/program_options.hpp> class Hanoi { protected: int _size; void run(int n, int a, int b, int c) const { if (n == 0) return; run(n - 1, a, c, b); std::cout << "Disc " << n << " moved from " << a << " to " << b << std::endl; run(n - 1, c, b, a); } public: Hanoi(int size = 3) { _size = size; } inline int size() const { return _size; } inline void run(void) const { return run(_size, 1, 2, 3); } }; int main(int argc, char *argv[]) { boost::program_options::options_description opt("Options"); opt.add_options() ("help,h", "Show this message.") ("size,n", boost::program_options::value<int>()->default_value(3), "Number of discs.") ; boost::program_options::variables_map maps; boost::program_options::store(parse_command_line(argc, argv, opt), maps); boost::program_options::notify(maps); if (maps.count("help")) { std::cerr << opt << std::endl; return 1; } int size = maps["size"].as<int>(); Hanoi *hanoi = new Hanoi(size); hanoi->run(); return 0; }
実行結果
araki@chive[131]% time ./hanoicc -n 4 Disc 1 moved from 1 to 3 Disc 2 moved from 1 to 2 Disc 1 moved from 3 to 2 Disc 3 moved from 1 to 3 Disc 1 moved from 2 to 1 Disc 2 moved from 2 to 3 Disc 1 moved from 1 to 3 Disc 4 moved from 1 to 2 Disc 1 moved from 3 to 2 Disc 2 moved from 3 to 1 Disc 1 moved from 2 to 1 Disc 3 moved from 3 to 2 Disc 1 moved from 1 to 3 Disc 2 moved from 1 to 2 Disc 1 moved from 3 to 2 0.005u 0.003s 0:00.00 0.0% 0+0k 0+0io 0pf+0w araki@chive[132]%
Objective C
能書き
C、C++と来たら、Objective Cで書かないわけにはいかないでしょう? そうでもない? Objective Cは、NeXT STEPとか、初期のMacOS XやiOSの開発言語というイメージで、C++程はメジャーになれなかった印象ですが、よく考えてみればiOSの開発言語だったんだから十分にメジャーですな。
コード
こういっては何ですが、後にも先にもObjective Cのコードはこれだけしか書いたことがありません。
@interface
とか@implementation
とかで、定義と実装とを分けているんですね。
でも、なんというか、C言語との食い合わせがいまいちなスタイルで、これが好きになれなかったんですよね。
#import <stdio.h> #import <unistd.h> #import <stdlib.h> #import <objc/Object.h> @interface Hanoi : Object { int size; } - (id)init; - (id)initWithN:(int)sz; - (void)run; - (void)run:(int)n:(int)a:(int)b:(int)c; @end @implementation Hanoi - (id)init { [super init]; return [self initWithN:3]; } - (id)initWithN:(int)sz { self->size = sz; return self; } - (void)run { [self run:self->size:1:2:3]; } - (void)run:(int)n:(int)a:(int)b:(int)c { if (n == 0) return; [self run:n-1:a:c:b]; printf("Disc %d moved from %d to %d.\n", n, a, b); [self run:n-1:c:b:a]; } @end int main(int argc, char *argv[]) { int opt; int opt_size = 3; char *e; while ((opt = getopt(argc, argv, "hn:")) >= 0) { switch(opt) { case 'h': case '?': fprintf(stderr, " -n <NUM>: Number of discs.\n"); fprintf(stderr, " -h: show this message.\n"); exit(1); break; case 'n': opt_size = strtol(optarg, &e, 10); break; } } id hanoi = [[Hanoi alloc] initWithN:opt_size]; [hanoi run]; }
実行結果
どういうわけか、SIGSEGVで落ちるようになってしまいました。
Common Lisp
能書き
Common Lispといえば、リスト操作言語であり、ハノイの塔なんか解いている場合ではないのだけれど、やろうと思えば出来るというサンプルである。
勿論、本体は hanoi 関数であり、それ以外は、コマンドラインの走査だったり、余分なのだが、余分の方が大勢を占めている。
とはいえ、これはいろんな言語とその処理系を学ぶための素材なので、こういう部分も大事だったりする。
個人的には、(progn )
はあんまりすきじゃないのだが、使わないで書く方法が思いつかなかったので、使っている。
コード
Lispの特徴はリスト操作につきるのだが、本体のhanoi
関数ではほとんど使わず、引数を走査しているparse
の方が多く使っているのがご愛敬。
そもそも、こういう題材に向いている言語ではないんだよね。
Quick Sortとか書くと Lispっぽくていいんだけれどね。
; (defun hanoi (n a b c) (if (> n 0) (progn (hanoi (1- n) a c b) (print (format t "Disc ~D moved from ~S to ~S." n a b)) (hanoi (1- n) c b a) t ) t ) ) (defun parse (args) (setq r nil) (loop (if (null args) (return r)) (setq arg0 (car args) args (cdr args)) (if (or (string= arg0 "-n") (string= arg0 "--size")) (setq r (parse-integer (car args)) args (cdr args)) ) ) ) (setq n (parse *args*)) (print n) (if (null n) (setq n 3)) (hanoi n '1 '2 '3)
実行結果
araki@chive[171]% time clisp hanoi.cl -n 4 4 Disc 1 moved from 1 to 3. NIL Disc 2 moved from 1 to 2. NIL Disc 1 moved from 3 to 2. NIL Disc 3 moved from 1 to 3. NIL Disc 1 moved from 2 to 1. NIL Disc 2 moved from 2 to 3. NIL Disc 1 moved from 1 to 3. NIL Disc 4 moved from 1 to 2. NIL Disc 1 moved from 3 to 2. NIL Disc 2 moved from 3 to 1. NIL Disc 1 moved from 2 to 1. NIL Disc 3 moved from 3 to 2. NIL Disc 1 moved from 1 to 3. NIL Disc 2 moved from 1 to 2. NIL Disc 1 moved from 3 to 2. NIL 0.013u 0.021s 0:00.03 100.0% 0+0k 0+0io 0pf+0w araki@chive[172]%
Prolog
能書き
コード
Prolog本体のコードは非常に短い。 Prologは、マッチするパターンを探して、それを実行する。 ハノイの塔のような再帰プログラムの場合は、再帰の打ち切り条件に相当するものを最初に定義して、それ以外の部分をそのあとに定義する。 こうすることで、打ち切り条件になるまでは再帰のコードを実行し、打ち切り条件になったら先頭の何もしないコードが呼び出され、再帰を逆にたどって元に返る。 きっとカットオペレータとか使う方法もあるんだろうけれど、カットオペレータが入ると途端に読みにくくなるので、よくわからないのです。
GNU Prologの場合ブートストラップコードをCで書くことが出来るので、コマンドライン引数の処理なんかはそっちでやっているから、本体だけしかないのでこのようになっている。 参考までにブートストラップのコードも載せておく。
hanoi(0,A,B,C) . hanoi(N,A,B,C) :- N1 is N -1, hanoi(N1, A, C, B), format('Disc ~d moved from ~d to ~d\n', [N, A, B]), hanoi(N1, C, B, A) .
/* * Prolog Wrapper */ #include <stdio.h> #include <stdlib.h> #include <getopt.h> #include <gprolog.h> #define SOL_SIZE_DEFAULT 10000 #define SOL_SIZE_STEP 10000 int Main_Wrapper(int argc, char *argv[]) { int size = 3; int sol_size = SOL_SIZE_DEFAULT; int i, p, opt; int hanoi; PlTerm arg[4]; char *sol = NULL; PlBool res; while ((opt = getopt(argc, argv, "n:h")) != -1) { switch (opt) { case 'n': size = strtol(optarg, NULL, 0); break; case 'h': default: fprintf(stderr, " -n <NUM>: Number of discs.\n -h: show this message.\n"); exit(1); break; } } Pl_Start_Prolog(argc, argv); hanoi = Pl_Find_Atom("hanoi"); Pl_Query_Begin(PL_TRUE); arg[0] = Pl_Mk_Integer(size); arg[1] = Pl_Mk_Integer(1); arg[2] = Pl_Mk_Integer(2); arg[3] = Pl_Mk_Integer(3); res = Pl_Query_Call(hanoi, 4, arg); Pl_Query_End(PL_RECOVER); Pl_Stop_Prolog(); return 0; } int main(int argc, char *argv[]) { return Main_Wrapper(argc, argv); }
実行結果
araki@chive[177]% time ./hanoipro -n 4 Disc 1 moved from 1 to 3 Disc 2 moved from 1 to 2 Disc 1 moved from 3 to 2 Disc 3 moved from 1 to 3 Disc 1 moved from 2 to 1 Disc 2 moved from 2 to 3 Disc 1 moved from 1 to 3 Disc 4 moved from 1 to 2 Disc 1 moved from 3 to 2 Disc 2 moved from 3 to 1 Disc 1 moved from 2 to 1 Disc 3 moved from 3 to 2 Disc 1 moved from 1 to 3 Disc 2 moved from 1 to 2 Disc 1 moved from 3 to 2 0.010u 0.001s 0:00.01 100.0% 0+0k 0+0io 0pf+0w araki@chive[178]%