140831

Ruby


140823(3)　　Partition

　↓　手をくわえる。

140823(4)　　Prime Partition

汎用性はないが、140823(3)分よりも分割数を速く求めることができるコードを書いてみた。

（以下において、

p(i) = p(i - 1) + p(i - 2) - p(i - 5) - p(i - 7) + ...

を用いている。）

n = 10000

@part = [1, 1]
def part(i)
  sum = 0
  for j in (0..i)
    i1 = (1 - 2 * (j % 2)) * ((j + 2) / 2) # 1, -1, 2, -2, 3, -3, ...
    i1 = i1 * (3 * i1 - 1) / 2             # 1, 2, 5, 7, 12, 15, ...
    break if i1 > i
    if (j / 2).even?
      sum += @part[i - i1]
    else
      sum -= @part[i - i1]
    end
  end
  @part[i] = sum
end
for i in (1..n)
  part(i)
end

p @part[n]