Partition (number theory)
以下の２つのコードのうち下の方が断然はやい。
n = 6
numbers = (1..n).to_a
cnt = 0
for i in (1..n)
numbers.repeated_combination(i){|j|
if j.inject(:+) == n
cnt += 1
end
}
end
p cnt
n = 6
nums = (1..n).to_a
ps = Array.new(n + 1){0}
ps[0] = 1
nums.each{|num|
# 末尾がnumなるものをカウント
(num..n).each{|i|
ps[i] += ps[i - num]
}
}
p ps[n]
0 件のコメント:
コメントを投稿
注: コメントを投稿できるのは、このブログのメンバーだけです。