ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | class Hanoi def initialize(disk_num) @disk_num = disk_num @poles = [ { :name => "A" , :disks => @disk_num .times.to_a}, { :name => "B" , :disks => []}, { :name => "C" , :disks => []} ] puts self printf "\e[#{@disk_num + 2}A" ; STDOUT .flush; #sleep 0 . 1 end def to_s "\n" << 3 .times.map do "#{" " * (@disk_num + 1)}\e[47m \e[0m#{" " * (@disk_num + 1)}" end .join( "" ) << "\n" << @disk_num .times.map do |n| 3 .times.map do |i| if @poles [i][ :disks ].size - @disk_num + n > - 1 d = @poles [i][ :disks ][ @poles [i][ :disks ].size - @disk_num + n] "\e[46m#{" " * (d + 1)}\e[0m" .rjust( 10 + @disk_num , " " ) << "\e[46m \e[0m" << "\e[46m#{" " * (d + 1)}\e[0m" .ljust( 10 + @disk_num , " " ) else "#{" " * (@disk_num + 1)}\e[47m \e[0m#{" " * (@disk_num + 1)}" end end .join( "" ) end .join( "\n" ) end def start hanoi( @disk_num , * @poles .map { |pole| pole[ :name ] }) puts self rescue Interrupt exit 0 end def hanoi(n, from, tmp, to) return if n == 0 hanoi(n- 1 , from, to, tmp) # puts "move #{n} from #{from} to #{to}" move(from, to) hanoi(n- 1 , tmp, from, to) end def move(from, to) from_pole = @poles .find{ |pole| pole[ :name ] == from } to_pole = @poles .find{ |pole| pole[ :name ] == to } to_pole[ :disks ].unshift from_pole[ :disks ].shift puts self printf "\e[#{@disk_num + 2}A" ; STDOUT .flush; #sleep 0 . 1 end end hanoi = Hanoi. new ( 11 ) hanoi.start |
実際に解いているのはhanoiメソッドで再帰している部分(38行目〜44行目あたり)だけで、それ以外はアルゴリズムと関係ない、途中経過を表示するためだけの処理です。
Hanoiクラスのインスタンスを生成するときに与える引数が、ハノイの塔の段数です。今回の例では11段にしてみましたが、20段とか30段とかやってみるとおもしろいですよ(なかなか終わらないですが)。
実行結果
円盤の動きはわかり辛いですが、こう、バーっと表示すると解いてる感あって楽しいですよね。
おわりに
落書きスクリプトシリーズ。
アルゴリズムの説明は詳しく解説しているサイトがたくさんあるので…。
0 件のコメント:
コメントを投稿