問題
リュカ数は、各項が直前の2項の和になるという点でフィボナッチ数と同じ規則に従いますが、始まりが異なり、L(0) = 2, L(1) = 1 です。数列は 2, 1, 3, 4, 7, 11, 18, 29, … と続きます。
lucas_numbers(n) を実装してください。
入力
n:項の添字(0 から数えます)。
出力
L(n) を返してください。
制約
0 ≤ n ≤ 90
例
例 1
入力:
n = 6
期待される出力:
expected = 18
入力:
long long n = 6;
期待される出力:
long long expected = 18;
入力:
long n = 6;
期待される出力:
long expected = 18;
解説
項は 2, 1, 3, 4, 7, 11, 18 なので、L(6) = 18 です。
例 2
入力:
n = 0
期待される出力:
expected = 2
入力:
long long n = 0;
期待される出力:
long long expected = 2;
入力:
long n = 0;
期待される出力:
long expected = 2;
解説
数列は L(0) = 2 から始まります。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
現在の項と次の項を2つの変数で持ちます。
ヒント 2
フィボナッチ数との違いは、始まりが 2 と 1 であることだけです。
ヒント 3
n = 90 のとき、その次の項は64ビットに収まらないので、ループは n で止めましょう。
目安の計算量
時間 O(n)、追加メモリ O(1)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。