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

Lucas Numbers

Return the nth Lucas number, the Fibonacci-like sequence that starts 2, 1.

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

  • Compute a Fibonacci-like sequence
  • Use the right starting values
  • Avoid computing one term past the answer

問題

翻訳を表示

The Lucas numbers follow the same rule as the Fibonacci numbers, each term being the sum of the two before it, but they start differently: L(0) = 2 and L(1) = 1. The sequence goes 2, 1, 3, 4, 7, 11, 18, 29, …

Implement lucas_numbers(n).

Input

n: The index of the term, starting at 0.

Output

Return L(n).

制約

0 ≤ n ≤ 90

例

例 1
入力:
n = 6

期待される出力:
expected = 18
入力:
long long n = 6;

期待される出力:
long long expected = 18;
入力:
long n = 6;

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

解説

The terms are 2, 1, 3, 4, 7, 11, 18, so L(6) = 18.

例 2
入力:
n = 0

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

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

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

解説

The sequence starts with L(0) = 2.

解き方のヒント

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

ヒント 1

Keep the current and next terms in two variables.

ヒント 2

The only difference from Fibonacci is the start: 2 and 1.

ヒント 3

For n = 90 the next term would not fit in 64 bits, so stop the loop at n.

目安の計算量

O(n) time, O(1) extra space

参考資料

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

ランキング

全体ランキング

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

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

他の人の解答から学ぶ

コミュニティの解答

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