Chương trình C tìm số hạng thứ n của quan hệ truy hồi

Cho ba số a, b, c và giá trị n. Quan hệ truy hồi S(n) định nghĩa như sau:

• S(1) = a
• S(2) = b
• S(3) = c
• S(n) = S(n-1) + S(n-2) + S(n-3) với n > 3

Cần tìm S(n). Ví dụ: a=5, b=2, c=3, n=6 → S(6)=28.

Giải thuật

• Hàm solve(a, b, c, n) đệ quy
• Cơ sở: n==1 trả về a, n==2 trả về b, n==3 trả về c
• Đệ quy: return solve(a,b,c,n-1) + solve(a,b,c,n-2) + solve(a,b,c,n-3)

Ví dụ minh họa

#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;
}

Đầu vào

5, 2, 3, 6

Đầu ra

28