Đề bài
Dãy Lucas có cùng quy tắc với dãy Fibonacci: mỗi số hạng bằng tổng hai số hạng đứng trước. Điểm khác là cách bắt đầu: L(0) = 2 và L(1) = 1. Dãy có dạng 2, 1, 3, 4, 7, 11, 18, 29, …
Hãy viết lucas_numbers(n).
Đầu vào
n: Chỉ số của số hạng, bắt đầu từ 0.
Đầu ra
Trả về 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
Các số hạng là 2, 1, 3, 4, 7, 11, 18, nên 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
Dãy bắt đầu với 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
Giữ số hạng hiện tại và số hạng kế tiếp trong hai biến.
Gợi ý 2
Điểm khác duy nhất so với Fibonacci là giá trị khởi đầu: 2 và 1.
Gợi ý 3
Với n = 90, số hạng kế tiếp sẽ không vừa trong 64 bit, nên hãy dừng vòng lặp đúng ở n.
Độ phức tạp mong đợi
thời gian O(n), bộ nhớ phụ O(1)
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.