こんにちは。ささだです。

  [ [ruby-math:00851] Ramanujan Number ]
  Mon, 12 May 2003 10:19:05 +0900 への返信です。

 はじめて投稿させていただきます。

> 自然数のペアで、3乗の和が等しくなるもののリストを100個あげて
> ください。

 その3乗和を''小さい順に''100個、という条件を追加したものを解く
プログラムです。

 アルゴリズムを知ってから ruby に解きました。



 一応、100個でも1000個でも10000個でもいくんじゃないでしょうか。

----------------------------------------------------------------------
def sumcube e
  e[0]**3+e[1]**3
end

def taxi_nums n
  b = yield ; found = 0
  while found < n
    a = yield
    #puts "#{a.inspect} => #{sumcube a}"
    if a[0] == b[0]
      a,b = b,a if a[1][0] > b[1][0]
      puts "#{a[1].inspect} , #{b[1].inspect} => #{a[0]}"
      found += 1
    end
    b = a
  end
end

queue = [[9,[1,2]]]

taxi_nums(30){
  r = queue.shift
  a = r[1][0]
  b = r[1][1]
  c = [a,b+1]
  queue << [sumcube(c),c]
  if a+2 == b
    c = [a+1,b]
    queue << [sumcube(c),c]
  end
  
  queue.sort!{|a,b|
    a[0] <=> b[0]
  }
  r
}
----------------------------------------------------------------------


 速くするために、児玉さんの priority queue for Ruby.
(http://www.math.kobe-u.ac.jp/~kodama/tips-ruby-pqueue.html) を利用したバージョン。


----------------------------------------------------------------------
def sumcube e
  e[0]**3+e[1]**3
end

def taxi_nums n
  b = yield ; found = 0
  while found < n
    a = yield
    #puts "#{a.inspect} => #{sumcube a}"
    if a[0] == b[0]
      a,b = b,a if a[1][0] > b[1][0]
      puts "#{a[1].inspect} , #{b[1].inspect} => #{a[0]}"
      found += 1
    end
    b = a
  end
end

# http://www.math.kobe-u.ac.jp/~kodama/tips-ruby-pqueue.html
require 'pqueue'
queue = PQueue.new lambda{|x,y|
  x[0] < y[0]
}
queue.push [9,[1,2]]

taxi_nums(30){
  r = queue.pop
  a = r[1][0]
  b = r[1][1]
  c = [a,b+1]
  queue.push [sumcube(c),c]
  if a+2 == b
    c = [a+1,b]
    queue.push [sumcube(c),c]
  end
  r
}
----------------------------------------------------------------------



 以上。

-- 
// SASADA Koichi @ namikilab.tuat.ac.jp
//