Đề bài
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).
Ràng buộc
0 ≤ n ≤ 90
Ví dụ
Đầu vào:
n = 6
Kết quả mong đợi:
expected = 18
Đầu vào:
long long n = 6;
Kết quả mong đợi:
long long expected = 18;
Đầu vào:
long n = 6;
Kết quả mong đợi:
long expected = 18;
Giải thích
The terms are 2, 1, 3, 4, 7, 11, 18, so L(6) = 18.
Đầu vào:
n = 0
Kết quả mong đợi:
expected = 2
Đầu vào:
long long n = 0;
Kết quả mong đợi:
long long expected = 2;
Đầu vào:
long n = 0;
Kết quả mong đợi:
long expected = 2;
Giải thích
The sequence starts with L(0) = 2.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Keep the current and next terms in two variables.
Gợi ý 2
The only difference from Fibonacci is the start: 2 and 1.
Gợi ý 3
For n = 90 the next term would not fit in 64 bits, so stop the loop at n.
Độ phức tạp mong đợi
O(n) time, O(1) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.