151025

Ruby

線対称に分割

線対称に分割すると、

0 = 0,
1 = 1,
2 = 2
2 = 1 + 1,
3 = 3
3 = 1 + 1 + 1,
4 = 4
4 = 1 + 2 + 1
4 = 1 + 1 + 1 + 1
4 = 2 + 2,
5 = 5
5 = 1 + 3 + 1
5 = 1 + 1 + 1 + 1 + 1
5 = 2 + 1 + 2,
…
のようになり、それぞれ
1, 1, 2, 2, 4, 4, …
通りの分割の仕方がある。
このコードを書いてみた。

@memo = [1, 1]
n = 30
(2..n).each{|i|
  # まずi = iの１通り
  @memo[i] = 1
  # jとjで挟んだもの
  (1..i / 2).each{|j| @memo[i] += @memo[i - 2 * j]}
}
p @memo

出力結果
[1, 1, 2, 2, 4, 4, 8, 8, 16, 16, 32, 32, 64, 64, 128, 128, 256, 256, 512, 512, 1024, 1024, 2048, 2048, 4096, 4096, 8192, 8192, 16384, 16384, 32768]