010: フィボナッチの四重奏

ヒント / 解答

難易度: ☆

問題

テトラナッチ数列は、直前4項の和で次の項を作る数列です。 この演習では、OEIS A000078 と同じ添字で、次のように定義します。

• T(0) = 0
• T(1) = 0
• T(2) = 0
• T(3) = 1
• n >= 4 のとき、T(n) = T(n - 1) + T(n - 2) + T(n - 3) + T(n - 4)

整数 n を受け取り、T(n) を返す関数 tetranacci を書いてください。

制約

• n は0以上100以下の整数です。
• tetranacci(100) を現実的な時間で計算できるようにしてください。

例

>>> tetranacci(0)
0
>>> tetranacci(3)
1
>>> tetranacci(8)
15
>>> tetranacci(10)
56

目標

次の値を計算してください。

>>> tetranacci(50)
14075762303480
>>> tetranacci(100)
2505471397838180985096739296

参考

• フィボナッチ数の一般化: テトラナッチ数
• OEIS A000078