โปรแกรม Python หาลำดับที่ n ของเลขฟีโบนัชชี (Fibonacci)

ในบทความนี้ เราจะคำนวณเลขฟีโบนัชชีลำดับที่ n

เลขฟีโบนัชชี ถูกกำหนดโดยความสัมพันธ์แบบเวียนเกิด (recurrence relation) ดังนี้ −

Fn = Fn-1 + Fn-2

โดยที่ F₀ = 0 และ F₁ = 1

เลขฟีโบนัชชีแรกๆ คือ

0, 1, 1, 2, 3, 5, 8, 13, ................

เราสามารถคำนวณ เลขฟีโบนัชชี ได้โดยใช้วิธีการเรียกซ้ำ (recursion) และการเขียนโปรแกรมแบบไดนามิก (dynamic programming)

ตอนนี้มาดูการนำไปใช้งานในรูปแบบสคริปต์ Python

แนวทางที่ 1: วิธีการเรียกซ้ำ (Recursion)

ตัวอย่าง

# recursive approach
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)

# main
n = 10
print(Fibonacci(n))

ผลลัพธ์

34

ขอบเขตของตัวแปรที่ประกาศทั้งหมดแสดงด้านล่าง

แนวทางที่ 2: วิธีการเขียนโปรแกรมแบบไดนามิก (Dynamic Programming)

ตัวอย่าง

# dynamic approach
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

# Driver Program
n = 10
print(fibonacci(n))

ผลลัพธ์

34

ขอบเขตของตัวแปรที่ประกาศทั้งหมดแสดงด้านล่าง

สรุป

ในบทความนี้ เราได้เรียนรู้เกี่ยวกับการคำนวณเลขฟีโบนัชชีลำดับที่ n โดยใช้แนวทางการเรียกซ้ำและการเขียนโปรแกรมแบบไดนามิก