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

ในบทความนี้ เราจะเรียนรู้เกี่ยวกับการคำนวณเลขคาทาลานลำดับที่ n

เลขคาทาลาน (Catalan numbers) เป็นลำดับของจำนวนธรรมชาติที่ถูกกำหนดโดยสูตรเวียนเกิด −

$$C_{0}= 1\:and\:C_{n+1}=\displaystyle\sum\limits_{i=0}^n C_{i}C_{n-i} for \:n\geq0;$$

เลขคาทาลานตัวแรกสำหรับ n = 0, 1, 2, 3, ... คือ 1, 1, 2, 5, 14, 42, 132, 429, ...........

เลขคาทาลานสามารถได้รับได้ทั้งจากการเรียกซ้ำและการเขียนโปรแกรมแบบไดนามิก มาดูการนำไปใช้งานของพวกมัน

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

ตัวอย่าง

# A recursive solution
def catalan(n):
    # ค่าติดลบ
    if n <= 1:
        return 1
    # Catalan(n) = catalan(i)*catalan(n-i-1)
    res = 0
    for i in range(n):
        res += catalan(i) * catalan(n - i - 1)
    return res

# main
for i in range(6):
    print(catalan(i))

ผลลัพธ์

1 1 2 5 14 42

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

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

ตัวอย่าง

# using dynamic programming
def catalan(n):
    if (n == 0 or n == 1):
        return 1
    # แบ่งตาราง
    catalan = [0 for i in range(n + 1)]
    # เริ่มต้น
    catalan[0] = 1
    catalan[1] = 1
    # เวียนเกิด
    for i in range(2, n + 1):
        catalan[i] = 0
        for j in range(i):
            catalan[i] = catalan[i] + catalan[j] * catalan[i - j - 1]
    return catalan[n]

# main
for i in range(6):
    print(catalan(i), end=" ")

ผลลัพธ์

1 1 2 5 14 42

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

สรุป

ในบทความนี้ เราได้เรียนรู้วิธีการสร้างเลขคาทาลานลำดับที่ n