โจทย์
จำนวนลูคัสใช้กฎเดียวกับจำนวนฟีโบนักชี คือแต่ละพจน์เท่ากับผลรวมของสองพจน์ก่อนหน้า แต่เริ่มต้นต่างกัน โดย L(0) = 2 และ L(1) = 1 ลำดับจึงเป็น 2, 1, 3, 4, 7, 11, 18, 29, …
จงเขียนฟังก์ชัน lucas_numbers(n)
อินพุต
n: ดัชนีของพจน์ เริ่มจาก 0
เอาต์พุต
คืนค่า L(n)
เงื่อนไข
0 ≤ n ≤ 90
ตัวอย่าง
อินพุต:
n = 6
ผลลัพธ์ที่คาดหวัง:
expected = 18
อินพุต:
long long n = 6;
ผลลัพธ์ที่คาดหวัง:
long long expected = 18;
อินพุต:
long n = 6;
ผลลัพธ์ที่คาดหวัง:
long expected = 18;
คำอธิบาย
พจน์ต่าง ๆ คือ 2, 1, 3, 4, 7, 11, 18 ดังนั้น L(6) = 18
อินพุต:
n = 0
ผลลัพธ์ที่คาดหวัง:
expected = 2
อินพุต:
long long n = 0;
ผลลัพธ์ที่คาดหวัง:
long long expected = 2;
อินพุต:
long n = 0;
ผลลัพธ์ที่คาดหวัง:
long expected = 2;
คำอธิบาย
ลำดับเริ่มต้นด้วย L(0) = 2
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
เก็บพจน์ปัจจุบันและพจน์ถัดไปไว้ในตัวแปรสองตัว
คำใบ้ 2
ต่างจากฟีโบนักชีแค่ค่าเริ่มต้น คือ 2 และ 1
คำใบ้ 3
เมื่อ n = 90 พจน์ถัดไปจะเก็บใน 64 บิตไม่ได้ จึงต้องหยุดลูปที่ n
ความซับซ้อนที่คาดหวัง
เวลา O(n), หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน