170604

Ruby


k - 1段とばしまでOKな階段ののぼりおり

k - 1段とばしまでOKな階段ののぼり方は、
フィボナッチ数列やトリボナッチ数列になることは
よく知られている。
では、k - 1段とばしまでOKな階段ののぼりおりはどうなるか
実験してみた。
ただし、のぼっておりるまでに各段は少なくとも一回はふむものとする。

def f(ary, n)
  return false if ary.size < n
  a = ary[-1]
  ary[-n..-2].all?{|i| i == a}
end

def A(k, n)
  f_ary = [[]]
  ary = [1]
  f_ary = [[]]
  ary = [1]
  (n - 1).times{
    b_ary = []
    f_ary.each{|i|
      i0, i1, i2 = i + [0], i + [1], i + [2]
      b_ary << i0 if !f(i0, k)
      b_ary << i1 if !f(i1, k)
      b_ary << i2
    }
    f_ary = b_ary
    ary << f_ary.size
  }
  ary
end

n = 15
(1..10).each{|i| p A(i, n)}

出力結果
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363, 8119, 19601, 47321, 114243, 275807]
[1, 3, 9, 25, 71, 201, 569, 1611, 4561, 12913, 36559, 103505, 293041, 829651, 2348889]
[1, 3, 9, 27, 79, 233, 687, 2025, 5969, 17595, 51865, 152883, 450655, 1328401, 3915743]
[1, 3, 9, 27, 81, 241, 719, 2145, 6399, 19089, 56945, 169875, 506761, 1511739, 4509729]
[1, 3, 9, 27, 81, 243, 727, 2177, 6519, 19521, 58455, 175041, 524153, 1569555, 4699969]
[1, 3, 9, 27, 81, 243, 729, 2185, 6551, 19641, 58887, 176553, 529335, 1587033, 4758185]
[1, 3, 9, 27, 81, 243, 729, 2187, 6559, 19673, 59007, 176985, 530847, 1592217, 4775679]
[1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19681, 59039, 177105, 531279, 1593729, 4780863]
[1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59047, 177137, 531399, 1594161, 4782375]