หาเลขฟีโบนัชชี (Fibonacci) ลำดับที่ n ใน Python

Fibonacci Number: Fₙ = Fₙ₋₁ + Fₙ₋₂ โดย F₀=0, F₁=1 ลำดับ: 0,1,1,2,3,5,8,13...

คำนวณได้ 2 วิธี: Recursion และ Dynamic Programming

วิธี 1: Recursion

def Fibonacci(n):
    if n < 0:
        print("Fibonacci can't be computed")
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return Fibonacci(n-1) + Fibonacci(n-2)

print(Fibonacci(10))

ผลลัพธ์

34

วิธี 2: Dynamic Programming (Memoization)

Fib_Array = [0, 1]
def fibonacci(n):
    if n < 0:
        print("Fibonacci can't be computed")
    elif n <= len(Fib_Array):
        return Fib_Array[n-1]
    else:
        temp = fibonacci(n-1) + fibonacci(n-2)
        Fib_Array.append(temp)
        return temp

print(fibonacci(10))

ผลลัพธ์

34

สรุป

เรียนรู้ 2 วิธีหา Fibonacci ลำดับที่ n: Recursion (ช้า, exponential) และ Dynamic Programming (เร็ว, linear)