โจทย์
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
ตัวอย่าง
อินพุต:
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.
อินพุต:
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
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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน