160117(2)

Ruby


フィボナッチ数列、トリボナッチ数列、テトラナッチ数列、…(3)

白石と黒石をn 個並べる。
先頭が黒石でk 個以上同じ色が続かない並べ方が何通りあるか考える。

求めるものをf(k, n) とおくと、

n < k のとき

f(k, n) = 2＾(k - 1)

n ≧ k のとき、

末尾が連続しないものが、f(k, n - 1) 通り,

末尾がちょうど2 連続同じ色のものが、f(k, n - 2) 通り,

末尾がちょうど3 連続同じ色のものが、f(k, n - 3) 通り,

…

末尾がちょうどk - 1 連続同じ色のものが、f(k, n - k - 1) 通り

あるので、

f(k, n) = f(k, n - 1) + … + f(k, n - k - 1)

f(k, n) の値を出力するコードは次のようになる。

# 先頭が黒石でk個以上同じ色が続かない
def f(k, n)
  ary = (1..k - 1).map{|i| 2 ** (i - 1)}
  (k..n).each{|i| ary[i - 1] = (1..k - 1).inject(0){|s, j| s += ary[i - 1 - j]}}
  ary[0..n - 1]
end

n = 20
(2..10).each{|k| p [k, f(k, n)]}

出力結果
[2, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
[3, [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946]]
[4, [1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415]]
[5, [1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953]]
[6, [1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, 26784, 52656, 103519, 203513, 400096]]
[7, [1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968]]
[8, [1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, 31489, 62725, 124946, 248888, 495776]]
[9, [1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128, 32192, 64256, 128257, 256005, 510994]]
[10, [1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144, 16272, 32512, 64960, 129792, 259328, 518145]]