Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Lucas Numbers

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

Bạn sẽ học được gì

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

Đề bài

Xem bản dịch

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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.