โปรแกรม C หาเลข Catalan ลำดับที่ n (nth Catalan Number)

ได้รับจำนวนเต็ม n ภารกิจคือหาเลข Catalan ลำดับที่ n

เลข Catalan (Catalan Numbers) คือลำดับของจำนวนธรรมชาติที่ปรากฏในปัญหาการนับหลายอย่าง เช่น

• จำนวน Binary Search Trees ที่เป็นไปได้กับ n คีย์
• จำนวนนิพจน์วงเล็บที่ถูกต้องกับ n คู่วงเล็บ
• จำนวนวิธีเชื่อมจุดบนวงกลมด้วยเส้นตรงที่ไม่ทับกัน

สูตร: Cₙ = (1/(n+1)) * C(2n, n) = (2n)! / ((n+1)! * n!)

ค่าเริ่มต้น: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...

เช่น n=3 ให้ค่า 5

ตัวอย่าง

Input: n = 6  Output: 132
Input: n = 8  Output: 1430

แนวทาง (Recursive)

• รับค่า n
• ถ้า n ≤ 1 คืนค่า 1 (Base case)
• ลูป i = 0 ถึง n-1
• สะสมผลรวม: res += catalan(i) * catalan(n-i-1)
• คืนค่า res

อัลกอริทึม

Start
Step 1: ฟังก์ชัน catalan(unsigned int n)
    ถ้า n <= 1 return 1
    res = 0
    ลูป i = 0 ถึง n-1
        res += catalan(i) * catalan(n-i-1)
    return res
Step 2: main() กำหนด n=6 พิมพ์ catalan(n)
Stop

โค้ดตัวอย่าง

#include <stdio.h>

unsigned long int catalan(unsigned int n) {
    if (n <= 1) return 1;
    unsigned long int res = 0;
    for (int i = 0; i < n; i++)
        res += catalan(i) * catalan(n - i - 1);
    return res;
}

int main() {
    int n = 6;
    printf("catalan is :%ld\n", catalan(n));
    return 0;
}

ผลลัพธ์

catalan is :132