簡単 0件解決済み 正答率0%

トリボナッチ数

各項が直前の3項の和になる、n 番目のトリボナッチ数を返します。

このチャレンジで学べること

  • 数列を反復で計算できる
  • 直近の数項だけを保持できる
  • 最初の数項を直接扱える

問題

原文(英語)を表示

トリボナッチ数は、フィボナッチ数の考え方を3項に広げたものです。T(0) = 0, T(1) = 0, T(2) = 1 とし、それ以降は T(n) = T(n − 1) + T(n − 2) + T(n − 3) で定めます。数列は 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, … と続きます。

tribonacci(n) を実装してください。

入力

n:項の添字(0 から数えます)。

出力

T(n) を返してください。常に必要なのは直近の3項だけなので、3つの変数を使ったループで十分です。

制約

0 ≤ n ≤ 74

例

例 1
入力:
n = 7

期待される出力:
expected = 13
入力:
long long n = 7;

期待される出力:
long long expected = 13;
入力:
long n = 7;

期待される出力:
long expected = 13;

解説

項は 0, 0, 1, 1, 2, 4, 7, 13 なので、T(7) = 13 です。

例 2
入力:
n = 2

期待される出力:
expected = 1
入力:
long long n = 2;

期待される出力:
long long expected = 1;
入力:
long n = 2;

期待される出力:
long expected = 1;

解説

T(2) は数列で最初に現れる 1 なので、答えは 1 です。

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

最初の3項はそのまま返します。

ヒント 2

3つの変数を用意し、1ステップごとに値をずらしていきます。

ヒント 3

メモを使わない再帰では同じ計算を繰り返すので、遅すぎます。

目安の計算量

時間 O(n)、追加メモリ O(1)

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。