ハノイの塔

Jr エンジニア向けにアルゴリズムの勉強会を主催した時のコード

Hanoi

#!/usr/bin/env ruby
## -*- coding: utf-8 -*-
class Poll
  def initialize
    @arr = Array.new
  end
  def push(v)
    raise "Could not push : " + v.to_s if @arr.size > 0 and @arr.last <= v
    @arr.push(v)
  end
  def pop
    @arr.pop
  end
  attr_accessor :arr
end
class Hanoi
  def initialize(n)
    @polls = {
      'S' => Poll.new,
      'G' => Poll.new,
      'B' => Poll.new
    }
    n.times { |i|
      @polls['S'].push(n-i)
    }
    @n = 0
  end
  def dump 
    print '== ' + @n.to_s + '==' + "\n"
    print "S|"
    @polls['S'].arr.each { |e|
      print e.to_s + ' '
    }
    print "\n"
    print "G|"
    @polls['G'].arr.each { |e|
      print e.to_s + ' '
    }
    print "\n"
    print "B|"
    @polls['B'].arr.each { |e|
      print e.to_s + ' '
    }
    print "\n"
    print "\n"
  end
  def move (from,to)
    @polls[to].push(@polls[from].pop)
    @n += 1
  end
  def hanoi (n,from,to,buffer)
    return move(from,to) if n === 1
    hanoi(n-1,from,buffer,to)
    dump
    move(from,to)
    dump
    hanoi(n-1,buffer,to,from)
  end
  attr_accessor :n
end

N=5
hanoi = Hanoi.new(N)
hanoi.dump
hanoi.hanoi(N,'S','G','B')
hanoi.dump

数学的帰納法の問題は単純な再帰で実装できる。

ハノイの数学的帰納法

ハノイ（= H）の手順

1. １つ小さいハノイを実行し、バッファーポールに動かす。
2. 一番下の大きい円盤をゴールポールに動かす
3. 最初にどけた山を（１つ小さいハノイで）ゴールポールに動かす。

H(1) = 1
H(2) = H(1)   + 1 + H(1)
H(3) = H(2)   + 1 + H(2)
H(4) = H(3)   + 1 + H(3)
　　　：
H(N) = H(N-1) + 1 + H(N-1)

これが def hanoi に表現されていれば合格！

実行結果

== 0==
S|4 3 2 1 
G|
B|
== 1==
S|4 3 2 
G|
B|1 
== 2==
S|4 3 
G|2 
B|1 
== 3==
S|4 3 
G|2 1 
B|
== 4==
S|4 
G|2 1 
B|3 
== 5==
S|4 1 
G|2 
B|3 
== 6==
S|4 1 
G|
B|3 2 
== 7==
S|4 
G|
B|3 2 1 
== 8==
S|
G|4 
B|3 2 1 
== 9==
S|
G|4 1 
B|3 2 
== 10==
S|2 
G|4 1 
B|3 
== 11==
S|2 1 
G|4 
B|3 
== 12==
S|2 1 
G|4 3 
B|
== 13==
S|2 
G|4 3 
B|1 
== 14==
S|
G|4 3 2 
B|1 
== 15==
S|
G|4 3 2 1 
B|

でも、これじゃ指数的に処理が増える16ハノイ辺りでもうキツイよね？

なのでちゃんと対数時間の処理まで落としてね！(宿題)

答え

ハノイの手数

H(N)   = H(N-1) + 1 + H(N-1)
H(N)   = H(N-1)*2 + 1
H(N-1) = H(N-2)*2 + 1
H(N-2) = H(N-3)*2 + 1

※ H(N-1)を展開
H(N)   = (H(N-2)*2+1)*2                          + 1
※ さらにH(N-2)を展開
       = ((H(N-3)*2 + 1)*2*2)              + 1*2 + 1
       = (H(N-3)*2*2*2              + 2*2  + 1*2 + 1
※ さらにH(N-3)を展開
       = (H(N-4)*2*2*2*2    + 2*2*2 + 2*2  + 1*2 + 1
※ よって
       = (H(1)* 2^(N-1)  +   2^(N-1)-1
       =   1  * 2^(N-1)    +   2^(N-1)-1
       =   2^N - 1
Q.E.D

コード

class Hanoi2
  def initialize(a)
    @ALL = a
  end
  def hanoi2(n,from,to,buffer)
    # print " #{@ALL} ( #{n} ) =>  from : #{from} to : #{to}  \n"
    (1..n).each { |i|
      if ( (2**i - 1 ) >= n )
        nx =  n - (2**(i-1) - 1 )
        if ( ((@ALL + i) % 2) === 1 ) 
          return [from,buffer,i] if ( nx === 1 )
          return Hanoi2.new(i-1).hanoi2(nx-1,to,buffer,from)
        else
          return [from,to,i] if ( nx === 1 )
          return Hanoi2.new(i-1).hanoi2(nx-1,buffer,to,from)
        end
      end
    }
  end
end
p hanoi2 = Hanoi2.new(5).hanoi2(1,'S','G','B')
p hanoi2 = Hanoi2.new(5).hanoi2(2,'S','G','B')
p hanoi2 = Hanoi2.new(5).hanoi2(3,'S','G','B')
p hanoi2 = Hanoi2.new(5).hanoi2(28,'S','G','B')
p hanoi2 = Hanoi2.new(5).hanoi2(29,'S','G','B')
p hanoi2 = Hanoi2.new(5).hanoi2(30,'S','G','B')
p hanoi2 = Hanoi2.new(5).hanoi2(31,'S','G','B')

["S", "G", 1]
["S", "B", 2]
["G", "B", 1]
["S", "G", 3]
["B", "S", 1]
["B", "G", 2]
["S", "G", 1]