ลำดับฟีโบนัชชี
ในแบบฝึกหัดนี้ คุณจะนำ ลำดับฟีโบนัชชี (Fibonacci sequence) มาใช้งาน ซึ่งเป็นลำดับที่พบได้ทั่วไปในธรรมชาติ ลำดับนี้มีรูปแบบดังนี้: "0, 1, 1, 2, 3, 5, 8…" โดยจะสร้างอัลกอริทึมแบบ recursive เพื่อสร้างลำดับดังกล่าว
ตัวเลขสองตัวแรกคือ 0 และ 1 ส่วนตัวเลขที่เหลือคือผลรวมของตัวเลขสองตัวก่อนหน้า
สามารถนิยามลำดับนี้แบบ recursive ได้ว่า: \(fib(n)=fib(n-1)+fib(n-2)\) โดยที่ \(fib(0)=0\) และ \(fib(1)=1\) ซึ่ง \(n\) คือตำแหน่งที่ \(nth\) ในลำดับ
ในขั้นตอนแรก จะเขียน Fibonacci โดยใช้ recursion และในขั้นตอนที่สอง จะปรับปรุงให้ดียิ่งขึ้นด้วย dynamic programming โดยบันทึกผลลัพธ์ของปัญหาย่อยไว้ในตัวแปร cache
แบบฝึกหัดนี้เป็นส่วนหนึ่งของหลักสูตร
โครงสร้างข้อมูลและอัลกอริทึมใน Python
แบบฝึกหัดเชิงโต้ตอบแบบลงมือทำ
ลองทำแบบฝึกหัดนี้โดยเติมโค้ดตัวอย่างนี้ให้สมบูรณ์
def fibonacci(n):
# Define the base case
if ____ <= ____:
return n
else:
# Call recursively to fibonacci
____
print(fibonacci(6))