题目：有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。

用Ruby来解，不知道结果对不对。

  1. #define the Ant class
  2. class Ant
  3.   attr_accessor :direction,:pos,:id
  4.  
  5.   def veer # turn back when run into other ants
  6.     @direction = 1 - @direction
  7.   end
  8.  
  9.   def arrived?
  10.      return true if @pos == 0 or @pos == 27
  11.      return false
  12.   end
  13.  
  14.   def step
  15.      if @direction == 1 then
  16.          @pos = @pos + 1
  17.      else
  18.          @pos = @pos - 1
  19.      end
  20.   end
  21.  
  22.   def run_into(a) # if run into other ant,return true if so
  23.       return false if a.direction == self.direction 
  24.       return true  if a.pos == self.pos
  25.       return false
  26.   end
  27.  
  28.   def to_s
  29.      "id:#{@id}.direction:#{@direction}.pos:#{@pos}"
  30.   end
  31.  
  32. end # end of Ant
  33.  
  34. class Hash
  35.    def keys
  36.        a = Array.new
  37.        self.each_key do |k|
  38.          a.push k
  39.        end
  40.        a
  41.    end
  42. end
  43.  
  44. #initialize the ant[5] array
  45. def create_ant(d1,d2,d3,d4,d5)
  46.     a1,a2,a3,a4,a5=nil,nil,nil,nil,nil
  47.     (1..5).each do |i|
  48.        eval " a#{i} = Ant.new;a#{i}.id = #{i};a#{i}.direction = d#{i};"
  49.     end
  50.  
  51.     a1.pos = 3
  52.     a2.pos = 7
  53.     a3.pos = 11
  54.     a4.pos = 17
  55.     a5.pos = 23
  56.     return [a1,a2,a3,a4,a5]
  57.    
  58. end
  59.  
  60. #if all ant has arrived ,return true
  61. def all_arrived a
  62.    a.each do |a1|
  63.       return false unless a1.arrived?
  64.    end
  65.    return true
  66. end
  67.  
  68. # get one plan's cost
  69. # p is for puts the ant's progress if it is set to true
  70. def travel(d1,d2,d3,d4,d5,p=false)
  71.    c = 0 #total cost
  72.    x = 0 #loop variables
  73.    onway = create_ant(d1,d2,d3,d4,d5)
  74.    while true
  75.      break if all_arrived(onway)
  76.      x = 0
  77.      while (x < onway.length-1) do
  78.          (x=x+1 ; next) if onway[x].arrived?
  79.      if onway[x].run_into onway[x+1] then
  80.         onway[x].veer
  81.         onway[x+1].veer
  82.             x = x + 2
  83.      else
  84.         x = x + 1
  85.      end
  86.      end
  87.      onway.each do |ai|
  88.          ai.step unless ai.arrived?
  89.      end
  90.      c = c + 1
  91.      print "   step#{format("%2d",c)} : #{format("%-2d",onway[0].pos)},#{format("%-2d",onway[1].pos)}," if p
  92.      print "#{format("%-2d",onway[2].pos)},#{format("%-2d",onway[3].pos)},#{format("%-2d",onway[4].pos)} \n" if p
  93.  
  94.    end
  95.    c
  96. end
  97.  
  98. #path = {path length=><Array of direction info>}
  99. path = Hash.new
  100.  
  101. [1,0].each do |d1|
  102. [1,0].each do |d2|
  103. [1,0].each do |d3|
  104. [1,0].each do |d4|
  105. [1,0].each do |d5|
  106.     cost = travel(d1,d2,d3,d4,d5)
  107.     (path[cost]||=Array.new).push binding
  108. end
  109. end
  110. end
  111. end
  112. end
  113.  
  114. puts "short path length : #{path.keys.sort.first},path count :#{path[path.keys.sort.first].length}"
  115.  
  116. path[path.keys.sort.first].each_with_index do |b,i|
  117.     puts " short path  #{format("%2d",i+1)}:"
  118.     eval " print '   direction : ',d1,' ',d2,' ',d3,' ',d4,' ',d5,\"\n\"",b
  119.     #eval "travel(d1,d2,d3,d4,d5,true)", b
  120. end
  121.  
  122. puts "long path length : #{path.keys.sort.last},path count :#{path[path.keys.sort.last].length}"
  123.  
  124. path[path.keys.sort.last].each_with_index do |b,i|
  125.     puts " long path #{format("%2d",i+1)}:"
  126.     eval " print '   direction : ',d1,' ',d2,' ',d3,' ',d4,' ',d5,\"\n\"",b
  127.     #eval "travel(d1,d2,d3,d4,d5,true)", b
  128. end
Related posts for the current post: