WildTree Wiki

ユーザ用ツール

サイト用ツール

トレース:
いろんな言語でハノイの塔

差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン		前のリビジョン
いろんな言語でハノイの塔 [2019/06/27 10:58] – [Common Lisp] arakiいろんな言語でハノイの塔 [2021/04/30 12:38] (現在) – [Rust] araki
行 24: 行 24:
 ^Objective C (gcc) |4.9.3 |Celeron N3150 (1.60GHz) |Vine Linux 6.5 |- | ^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 | ^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 | 
 +^RVTL (Tiny BASIC) |4.01 |Celeron N3150 (1.60GHz) |Vine Linux 6.5 |7 | 
 +^Perl |5.12.3 |Celeron N3150 (1.60GHz) |Vine Linux 6.5 |14 | 
 +^Ruby |1.8.7 |Celeron N3150 (1.60GHz) |Vine Linux 6.5 |32 | 
 +^Python |2.6.6 |Celeron N3150 (1.60GHz) |Vine Linux 6.5 |52 | 
 +^bash |4.3.42 |Celeron N3150 (1.60GHz) |Vine Linux 6.5 |122 | 
 +^awk (gawk) |3.1.8 |Celeron N3150 (1.60GHz) |Vine Linux 6.5 |8 | 
 +^go|1.16.0|Core i3 5010U (2.1GHz) |Ubuntu 20.4 LTS|0.004 | 
 +^Rust|1.47.0|Core i3 5010U (2.1GHz) |Ubuntu 20.4 LTS|0.004 |
 ===== プログラム ===== ===== プログラム =====
 ==== PowerShell ==== ==== PowerShell ====
行 40: 行 48:
 なお、デジタル署名するのが面倒くさかったので、実行にあたっては、実行ポリシーを''AllSigned''から''RemoteSigned''に変更した。 なお、デジタル署名するのが面倒くさかったので、実行にあたっては、実行ポリシーを''AllSigned''から''RemoteSigned''に変更した。
 ((管理者権限でPowerShellを起動して''PS C:\Windows\System32> Set-ExectionPolicy RemoteSigned''とする。)) ((管理者権限でPowerShellを起動して''PS C:\Windows\System32> Set-ExectionPolicy RemoteSigned''とする。))
 +管理者権限を使ってシステム全体のポリシーを変更するのがコワイ場合は、
 +<code>
 +PS C:\Users\araki> Set-ExecutionPolicy RemoteSignedd -Scope Process
 +</code>
 +のようにして、実行中のプロセス内でのみ許可することも出来る。
 +この方法には管理者権限は不要なので、気軽にスクリプトを試すことが出来る。
 +
 一般的な関数型言語が採用している、関数呼び出しと違い、引数を括弧でくくってカンマで区切ってはいけない。 一般的な関数型言語が採用している、関数呼び出しと違い、引数を括弧でくくってカンマで区切ってはいけない。
 括弧でくくってカンマで区切るとそれは配列として、関数の第一引数に全て渡されてしまう。 括弧でくくってカンマで区切るとそれは配列として、関数の第一引数に全て渡されてしまう。
行 528: 行 543:
 </code> </code>
  
 +==== Prolog ====
 +=== 能書き ===
 +Prologとの最初の出会いは、月刊ASCIIに掲載されていたPC-8801向けの処理系をせっせと打ち込んで手に入れた時だと思う。
 +当時高校生だったと思うが、さっぱりPrologの考え方が分からないで、サンプルをちょいちょい打ち込んで動かして、あとはすっかり忘却してしまっていた。
 +Prologはパターンマッチングで動作し、そのパターンをプログラム自身が生成することが出来るので、人工知能向きの言語といわれていたが、Prologを実装するのに使っているCなどでもその動作を実現できるので、結果からいうとより高速な処理系にその役割を譲ることになり、今日に至る。
 +=== コード ===
 +Prolog本体のコードは非常に短い。
 +Prologは、マッチするパターンを探して、それを実行する。
 +ハノイの塔のような再帰プログラムの場合は、再帰の打ち切り条件に相当するものを最初に定義して、それ以外の部分をそのあとに定義する。
 +こうすることで、打ち切り条件になるまでは再帰のコードを実行し、打ち切り条件になったら先頭の何もしないコードが呼び出され、再帰を逆にたどって元に返る。
 +きっとカットオペレータとか使う方法もあるんだろうけれど、カットオペレータが入ると途端に読みにくくなるので、よくわからないのです。
  
 +GNU Prologの場合ブートストラップコードをCで書くことが出来るので、コマンドライン引数の処理なんかはそっちでやっているから、本体だけしかないのでこのようになっている。
 +参考までにブートストラップのコードも載せておく。
 +<code>
  
 +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) .
 +</code>
  
 +<code>
 +/*
 + * 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);
 +}
 +</code>
 +
 +=== 実行結果 ===
 +
 +<code>
 +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]% 
 +</code>
 +==== Tiny BASIC ====
 +=== 能書き ===
 +Tiny BASICは、非常にコンパクトなBASIC系の言語です。
 +基本的にBASICなので、再帰など普通に扱うことはできませんが、その辺はローカル変数に相当するものを配列を使って、自分で再帰レベルを管理しながら処理することで、擬似的に再帰処理を実現しています。
 +=== コード ===
 +コードにはコメントをつけてあります。
 +引数はなんとなくそんな感じになるように処理していますが、適当なので、あまり追求しないでください。
 +<code>
 +#!/usr/bin/env rvtlw
 +1000 !=^GETARG       : Set Number of Discs
 +1010 N=0             : Nesting Level
 +1020 T=*             : Pseudo Stack pointer
 +1030 A=1             : Pole #1
 +1040 B=2             : Pole #2
 +1050 C=3             : Pole #3
 +1060 *=*+(32*16)     : Stack size == 32 nest levels * 16bytes
 +1070 !=^HANOI        : Call HANOI(S, A, B, C)
 +1080 #=-1            : STOP
 +1090 ^HANOI          : Function HANOI(S, A, B, C)
 +1100 ;=S=0 N=N-1 ]   : if (s == 0) return;   // Nesting level should be --N
 +1110 W=X             : Save stack pointer to W
 +1120 X=T+(N*16)      : Setup stack pointer
 +1130 X(0)=S          : Push S
 +1140 X(1)=A          : Push A
 +1150 X(2)=B          : Push B
 +1160 X(3)=C          : Push C
 +1170 X(4)=N          : Push N
 +1180 X;1]=W          : Save stack pointer (64bit) / X[2]=W in case 32bit
 +1190 A=X(1)          : Setup arguments for recursive call
 +1200 B=X(3)
 +1210 C=X(2)
 +1220 S=X(0)-1
 +1230 N=X(4)+1        : Increase Nesting level
 +1240 !=^HANOI        : Call HANOI(N - 1, A, C, B)
 +1250 "Disc " ?=X(0) " moved from " ?=X(1) " to " ?=X(2) "." /
 +1260 A=X(3)          : Setup arguments for recursive call
 +1270 B=X(2)
 +1280 C=X(1)
 +1290 S=X(0)-1
 +1300 N=X(4)+1        : Increase Nesting level
 +1310 !=^HANOI        : Call HANOI(N - 1, C, B, A)
 +1320 X=X;1]          : Restore stack pointer
 +1330 ]               : return
 +5000 ^GETARG
 +5010 *=*+1024
 +5020 [=0
 +5030 s=&
 +5040 s*=\0
 +5050 ;=%=0 S=3 #=^NOARG
 +5060 i=0 S=0
 +5070 @
 +5080   S=S*10+(s(i)-$30)
 +5090   i=i+1
 +5100 @=(s(i)=0)
 +5110 ^NOARG
 +5120 [=1
 +5130 ]
 +#=1
 +</code>
 +=== 実行結果 ===
 +処理系が優秀だからか、あるいは、そもそも、関数呼び出しなどの処理が軽いからなのか、かなり高速だと思います。
 +<code>
 +araki@chive[109]% time ./hanoi.vtl -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.000u 0.007s 0:00.00 0.0%      0+0k 0+0io 0pf+0w
 +araki@chive[110]% 
 +</code>
 +
 +==== Perl ====
 +=== 能書き ===
 +スクリプト言語の雄。
 +何はなくともPerl。
 +とにかく一頃は何でもPerlで書かれていました。
 +今も多く使われていると思います。
 +Perlは徐々に仕様を拡張してきた結果、同じ事をするのに様々なやり方があって、気をつけないとコードに一貫性がなくなってしまったり、人によって同じ結果を得るための書き方が違っていて、他人のコードが理解しずらかったりと、あまり保守性に優れているとは言いがたいので個人的には好きではありません。
 +また、型を $やら @やら %やらで表現するのも、個人的には好みではありません。
 +とはいえ、場合によっては Perlなら使ってよしだったりするので、好む好まないに関わらず、使わざるを得ない言語でもあります。
 +=== コード ===
 +Perl 5を使うのだから、クラスを使おう。
 +と、いうことでクラスを使っています。
 +Hanoiはクラス(''package'')として定義されています。
 +''Hanoi''のインスタンスを作る際に円盤の枚数を宣言します。
 +あとは、''$hanoi->do;''とするだけで、処理を行います。
 +<code>
 +#!/usr/bin/perl -w
 +
 +use strict;
 +
 +package Hanoi;
 +
 +sub new {
 +    my $class = shift;
 +    my %args = @_;
 +    my $self = \%args || {};
 +    $self->{size} = 3 unless defined($self->{size});
 +    bless $self, $class;
 +}
 +
 +sub size
 +{
 +    my $self = shift;
 +    $self->{size}
 +}
 +
 +sub do
 +{
 +    my $self = shift;
 +    my $n = shift;
 +    my $a = shift || 1;
 +    my $b = shift || 2;
 +    my $c = shift || 3;
 +
 +    $n = $self->{size} unless defined($n);
 +    die "Same Placement: $a, $b, and $c ." if ($a == $b || $b == $c || $c == $a);
 +    return if $n == 0;
 +    $self->do($n - 1, $a, $c, $b);
 +    print "Disc $n moved from $a to $b\n";
 +    $self->do($n - 1, $c, $b, $a);
 +}
 +
 +package main;
 +
 +use Getopt::Std;
 +
 +my %opts = (n => 3);
 +getopts("n:h", \%opts);
 +
 +if(defined($opts{h}))
 +{
 +    print <<EOS;
 +Usage: $0
 +    -n <NUM>: number of discs.
 +    -h: show this message.
 +EOS
 +    exit(1);
 +}
 +
 +my $hanoi = new Hanoi(size => $opts{n});
 +$hanoi->do;
 +1;
 +</code>
 +=== 実行結果 ===
 +<code>
 +araki@chive[125]% time ./hanoi.pl -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.004s 0:00.11 9.0%      0+0k 32+0io 0pf+0w
 +araki@chive[126]%
 +</code>
 +
 +==== Ruby ====
 +=== 能書き ===
 +Perlが来たらRubyを出さないわけにはいかないでしょう。
 +日本発のスクリプト言語であるRubyはオブジェクト指向言語でもあります。
 +Perlのように、Object指向的に書けるというのではなく、そもそも、全てのデータがオブジェクトになっています。
 +
 +豊富なライブラリやRailsのようなフレームワークもあり、多くのアプリケーション開発に利用されています。
 +[[mastodon|Mastodon]]もRailsを利用しています。
 +
 +すっきりと書ける反面、やや速度が遅いという面があります。
 +=== コード ===
 +特にひねりもなく、普通に実装してあります。
 +特筆するべきこともないかと思います。
 +<code>
 +#!/usr/bin/env ruby
 +# -*- coding: utf-8 -*-
 +#
 +require 'optparse'
 +
 +opts = {
 +  :size => 3
 +}
 +OptionParser.new do |opt|
 +  opt.on('-n', '--size=NUM', 'Number of discs.') do |v| opts[:size] = v.to_i end
 +  opt.parse!(ARGV)
 +end
 +
 +class Hanoi
 +
 +    attr_reader :size
 +
 +    def initialize(n = 3)
 +        @size = n
 +    end
 +
 +    def do(n = @size, a = 1, b = 2, c = 3)
 +        return if n == 0
 +        self.do(n - 1, a, c, b)
 +        print "Disc #{n} moved from #{a} to #{b}\n"
 +        self.do(n - 1, c, b, a)
 +    end
 +
 +end
 +
 +hanoi = Hanoi.new(opts[:size])
 +hanoi.do
 +</code>
 +=== 実行結果 ===
 +<code>
 +araki@chive[131]% time ./hanoi.rb -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.017u 0.015s 0:00.07 28.5%     0+0k 672+0io 0pf+0w
 +araki@chive[132]%
 +</code>
 +
 +==== Python ====
 +=== 能書き ===
 +Perl、Rubyと来たら、Pythonを出さないわけにはいかないでしょう。
 +今日では恐らくPythonが最も広く使われているのではないかと思います。
 +
 +Pythonもオブジェクト指向言語であり、Perlよりずっとすっきりと記述できます。
 +
 +ただ、個人的には、インデントでブロックを構成する仕様が好きになれなくて、PythonでもRubyでもいいならRubyを使いたい派です。
 +インデントによるブロックが嫌いなのは、エディタによっては、勝手にいくつかのスペースをタブに置きかえる場合があり、これが発動すると、見た目にはOKなブロックが実は破綻しているなど、コーディングに集中できないケースがあるからです。
 +
 +こちらも、Perlに比べて、実行速度の面では劣る傾向があります。
 +=== コード ===
 +こちらも、特にひねりもない実装かと思います。
 +''if __name__ == '__main__':''で、''hanoi.py''をスクリプトとして起動した場合にのみ有効となるコードが記述されています。
 +つまり、クラスライブラリとそれに付随するサンプル、あるいはテストコードをひとまとめにしておくことも出来るのはなかなかに便利だと思います。
 +<code>
 +#!/usr/bin/env python
 +
 +import optparse, sys
 +
 +class Hanoi:
 +    """ Hanoi's tower """
 +    def __init__(self, size = 3):
 +        self.size = size
 +
 +    def size(self):
 +        return self.size
 +
 +    def do(self, n = None, a = 1, b = 2, c = 3):
 +        if n is None:
 +            n = self.size
 +        if a == b or b == c or c == a:
 +            print "Same placement: ", a, ", ", b, ", and ", c
 +            raise
 +        if n == 0:
 +            return
 +        self.do(n - 1, a, c, b)
 +        print "Disc", n, "moved from", a, "to", b
 +        self.do(n - 1, c, b, a)
 +
 +if __name__ == '__main__':
 +    parser = optparse.OptionParser()
 +    parser.add_option('-n', '--size', help='Number of discs.', nargs=1, type='int', default=3, dest='size', action = 'store')
 +    args,r = parser.parse_args()
 +
 +    hanoi = Hanoi(args.size)
 +    hanoi.do()
 +</code>
 +=== 実行結果 ===
 +<code>
 +araki@chive[146]% time ./hanoi.py -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.043u 0.009s 0:00.06 66.6%     0+0k 112+0io 0pf+0w
 +araki@chive[147]% 
 +</code>
 +==== bash ====
 +=== 能書き ===
 +bashは、Bone Shell (sh)に変わって、現在のUNIX系システムの標準シェルの地位を確保しているシェルです。
 +シェルスクリプトはそれなりに強力であり、簡単な処理であれば、これだけでこなすことができます。
 +シェルがないUNIX環境は事実上ないので、どんな環境でも実行できるポータビリティは魅力です。
 +
 +もちろん、本格的なプログラム言語に比べて見劣りする部分も少なくないですが、DOSのバッチに比べればはるかに強力です。
 +PowerShellとであれば、いい勝負でしょうか。
 +PowerShellはパイプでオブジェクトも渡せるので、システムの機能をフルに引き出すという点ではbashに勝りますが、他は似たようなものでしょう。
 +=== コード ===
 +特に凝ったことはしていません。基本的には shでも動くんじゃないかと思います。
 +関数の引数は関数ローカルになっているので、ローカル変数を使わない限り普通に再帰もおこなえます。
 +このため再帰呼び出しの際に ''n = discs - 1''のようにして、減算を1回にしている他の言語と違って、呼び出しの度に''`expr ${1} - 1`''して、ローカル変数を避けています。
 +
 +<code>
 +#!/usr/bin/env bash
 +
 +function hanoi()
 +{
 +    if [ ${1} -gt 0 ]; then
 +        hanoi `expr ${1} - 1` ${2} ${4} ${3}
 +        echo "Disc ${1} moved from ${2} to ${3}"
 +        hanoi `expr ${1} - 1` ${4} ${3} ${2}
 +    fi
 +}
 +
 +size=3
 +while [ $# -gt 0 ]; do
 +    case $1 in
 +    "-h" | "--help")
 +        echo " -n <NUM>: Number of discs."
 +        echo " -h: show this message."
 +        exit 1
 +        ;;
 +    "-n" | "--size")
 +        size=$2
 +        shift; shift;
 +        ;;
 +    *)
 +        shift
 +    esac
 +done
 +hanoi ${size} 1 2 3
 +</code>
 +=== 実行結果 ===
 +<code>
 +araki@chive[152]% time ./hanoi.bash -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.051u 0.071s 0:00.13 92.3%     0+0k 0+0io 0pf+0w
 +araki@chive[153]%
 +</code>
 +==== awk ====
 +=== 能書き ===
 +awkは、AT&Tのベル研で、エイホ、ワインバーガ、カーニハンの三人により開発された、CSV形式のデータなどの処理に特化したスクリプト言語である。
 +一行野郎などと言われるように、本来は、単機能を実装したコマンドを、パイプでつないで、複雑な処理を実現するのが主な使い方であり、コードそのものをコマンドラインにタイプしてしまい、わざわざスクリプトファイルにしたりしないことも多い。
 +<code>
 +$ cat resul.txt | awk '{print $2;}' | sed -e "s/^(.*)$/'\1'/"
 +</code>
 +などのように、することで、ファイルの特定カラムの値を'でくくるなどの処理を簡単に行える。
 +
 +言語仕様が単純なこともあって、処理はそれなりに早い。
 +
 +また、パターンマッチングに正規表現が使えることも利点の一つである。
 +=== コード ===
 +普通の関数型言語の側面もあるので、そのまま、ストレートに実装してある。
 +<code>
 +#!/usr/bin/awk -f
 +function hanoi(n, a, b, c)
 +{
 +    if (n > 0) {
 +        hanoi(n-1, a, c, b);
 +        printf("Disc %d moved from %d to %d\n", n, a, b);
 +        hanoi(n-1, c, b, a);
 +    }
 +}
 +
 +BEGIN {
 +    size = 3;
 +    for (i = 0 ; i < ARGC ; i++)
 +    {
 +        if (ARGV[i] == "-h" || ARGV[i] == "--help")
 +        {
 +            printf(" -n <NUM>: Number of discs.\n -h: show this message.\n");
 +            exit(1);
 +        }
 +        if (ARGV[i] == "-n" || ARGV[i] == "--size")
 +        {
 +            size = ARGV[++i];
 +        }
 +    }
 +    hanoi(size, 1, 2, 3);
 +}
 +</code>
 +=== 実行結果 ===
 +<code>
 +araki@chive[157]% time ./hanoi.awk -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.003u 0.005s 0:00.00 0.0%      0+0k 0+0io 0pf+0w
 +araki@chive[158]% 
 +</code>
 +==== Go ====
 +=== 能書き ===
 +Goは比較的新しいコンパイラ言語である。
 +静的型付けを基本とする言語であるが、メモリ管理は言語側が行い、ガベージコレクションなどの機能も内包している。
 +
 +関数型言語であり、構造体を使った、オブジェクト指向っぽい記述もできる。
 +
 +=== コード ===
 +
 +コマンドラインの引数をとるために flagを、表示の加工用に fmtモジュールを利用している以外は、コード内で完結している。
 +
 +<code>
 +package main
 +
 +import (
 +  "fmt"
 +  "flag"
 +)
 +
 +type Discs int
 +
 +type Hanoi struct {
 +    N Discs
 +    a int
 +    b int
 +    c int
 +}
 +
 +func NewTower(n int) *Hanoi {
 +    h := new(Hanoi)
 +    h.N = Discs(n)
 +    h.a = 1
 +    h.b = 2
 +    h.c = 3
 +    return h
 +}
 +
 +func (n Discs) doit(a int, b int, c int) {
 +    if n > 0 {
 +        (n - 1).doit(a, c, b)
 +        fmt.Printf("Disc %d moved from %d to %d.\n", n, a, b)
 +        (n - 1).doit(c, b, a)
 +    }
 +}
 +
 +func (h Hanoi) run() {
 +    h.N.doit(h.a, h.b, h.c)
 +}
 +
 +func main() {
 +    n := flag.Int("n", 3, "n <NUM>: Number of Discs.")
 +    flag.Parse()
 +    hanoi := NewTower(*n)
 +    hanoi.run()
 +}
 +</code>
 +=== 実行結果 ===
 +
 +<code>
 +araki@cherry:~/work/Hanoi$ time ./hanoigo -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.
 +
 +real    0m0.004s
 +user    0m0.005s
 +sys     0m0.001s
 +araki@cherry:~/work/Hanoi$
 +</code>
 +
 +==== Rust ====
 +=== 能書き ===
 +システム記述言語として注目を集めているRust。
 +メモリの管理が静的に行われており、予期せぬメモリリークなどによるセキュリティホールなどを言語レベルで防止できる。
 +
 +cargoを使用してひな型を作り、getoptsによるオプション処理を加えた。
 +ハノイの塔本体部分より、オプションの処理部分のほうが大きい。
 +なお、ハノイの塔部分に関しては特にオブジェクト指向的なつくりにはしていない。
 +=== コード ===
 +コードは、RubyやPythonなどのスクリプト型言語と似た感じになっているが、静的な片付けが行われているところが、これらの言語とは違っている。
 +また、ガベージコレクションによる動的なメモリ管理ではなく、静的な管理が中心となる。
 +
 +<code>
 +use getopts::Options;
 +use std::process;
 +use std::env;
 +
 +fn print_usage(prog_name: &str, opts: Options)
 +{
 +    let brief = format!("Usage: {} [Options]", prog_name);
 +    print!("{}", opts.usage(&brief));
 +    process::exit(1);
 +}
 +
 +fn hanoi(n: i32, a: i32, b: i32, c: i32)
 +{
 +    if n > 0
 +    {
 +        hanoi(n - 1, a, c, b);
 +        println!("Disc {} moved from {} to {}", n, a, b);
 +        hanoi(n - 1, c, b, a);
 +    }
 +}
 +
 +fn main()
 +{
 +    let args: Vec<String> = env::args().collect();
 +    let program = args[0].clone();
 +
 +    let mut opts = Options::new();
 +    opts.optopt("n","discs","Set number of discs.", "NUM");
 +    opts.optflag("h","help","show this message.");
 +    let matches = match opts.parse(&args[1..])
 +    {
 +        Ok(m) => { m }
 +        Err(f) => { panic!(f.to_string()) }
 +    };
 +    if matches.opt_present("h")
 +    {
 +        print_usage(&program, opts);
 +        return;
 +    }
 +    let n = match matches.opt_get_default::<i32>("n", 3)
 +    {
 +        Ok(t) => { t }
 +        Err(f) => { panic!(f.to_string()) }
 +    };
 +    hanoi(n, 1, 2, 3);
 +}
 +</code>
 +=== 実行結果 ===
 +<code>
 +araki@cherry:~/work/Hanoi/hanoi$ time target/debug/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
 +
 +real    0m0.004s
 +user    0m0.003s
 +sys     0m0.001s
 +araki@cherry:~/work/Hanoi/hanoi$ 
 +</code>
  
  
  
  
いろんな言語でハノイの塔.1561633098.txt.gz · 最終更新: 2019/06/27 10:58 by araki