パスカルの三角形を作ってみた

こういうの

　  1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

簡単に思いつく方法(再帰）

def combination n,k
  case k
  when 1 : 1
  when n : 1
  else
    combination(n-1, k-1) + combination(n-1, k)
  end
end

def pascal depth
  1.upto(depth) do  |n|
    1.upto(n) do |k|
      print combination(n,k)
    end
    puts #改行
  end
end

でも、これだと遅い。（20段ぐらいが限界）

ほかに考えた方法。*1

def pascal2 depth
=begin
 1..depth => 0..(depth-1)
  既に最初の段が入力されているため、さらに　-1
 　 なので、(0.. depth-2)でpascalと同じ段
=end
  (0 .. depth-2).inject([[0,1,0]]) do |re, i|
    re << [0,(2..re[i].size).map {|e| re[i][e-2]+re[i][e-1]},0].flatten
  end.each do |e|
    e.delete 0
    print "#{e}\n"
  end
end
# pascal 5

比較した結果(depth=20で)

      　user     system      total        real
最初の  4.125000   0.000000   4.125000 (  4.235000)
次の 　 0.015000   0.000000   0.015000 (  0.015000)

速度違いすぎww
後で、グラフにしてみようかなー

*1:直接9段分を配列に格納するだけなら、「(0.. 9-2).inject([ [0,1,0] ]) {|re,i| re << [0,(2..re[i].size).map {|e| re[i][e-2]+re[i][e-1]},0].flatten }}.each {|e| e.delete 0}」でできる。