ง่าย 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

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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก