โปรแกรม C หาพจน์ที่ n ของความสัมพันธ์เวียนเกิด (Recurrence Relation)

คำอธิบายปัญหา

สมมติว่าเรามีตัวเลข 3 ตัว a, b, c และค่า n ตามสูตรเวียนเกิด S(n):

S(1) = a
S(2) = b
S(3) = c
S(n) = S(n-1) + S(n-2) + S(n-3) สำหรับ n > 3

เราต้องหาพจน์ที่ n ตามสูตรนี้

ตัวอย่าง

หากอินพุตเป็น a = 5, b = 2, c = 3, n = 6 ผลลัพธ์จะเป็น 28 เพราะ:

S(4) = S(3) + S(2) + S(1) = 3 + 2 + 5 = 10
S(5) = S(4) + S(3) + S(2) = 10 + 3 + 2 = 15
S(6) = S(5) + S(4) + S(3) = 15 + 10 + 3 = 28

ขั้นตอนการแก้ปัญหา

นิยามฟังก์ชัน solve(a, b, c, n) แบบเรียกซ้ำ (Recursive)
Base cases: n=1 คืน a, n=2 คืน b, n=3 คืน c
Recursive case: คืน solve(a,b,c,n-1) + solve(a,b,c,n-2) + solve(a,b,c,n-3)

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

#include <stdio.h>

int solve(int a, int b, int c, int n) {
    if (n == 1) return a;
    if (n == 2) return b;
    if (n == 3) return c;
    return solve(a, b, c, n-1) + solve(a, b, c, n-2) + solve(a, b, c, n-3);
}

int main() {
    int a = 5, b = 2, c = 3, n = 6;
    int res = solve(a, b, c, n);
    printf("%d", res);
    return 0;
}

อินพุต

5, 2, 3, 6

เอาต์พุต

หมายเหตุ

วิธีการเรียกซ้ำแบบนี้มีประสิทธิภาพต่ำสำหรับ n ใหญ่ (Time Complexity: O(3^n)) ควรใช้ Dynamic Programming หรือ Matrix Exponentiation เพื่อเพิ่มประสิทธิภาพ