Tìm số nghiệm của phương trình tuyến tính n ẩn trong C++

Giới thiệu

Cho phương trình tuyến tính n ẩn dạng: coeff1*x1 + coeff2*x2 + ... + coeffn*xn = value. Tìm số nghiệm nguyên không âm.

Ví dụ minh họa

Đầu vào

coeff[] = {3, 1}, value = 4

Đầu ra

1

Giải thích

Phương trình: 3x + y = 4. Nghiệm: x = 0, y = 4.

Phương pháp giải

Sử dụng đệ quy: thử từng hệ số, trừ vào value và đệ quy với value mới. Nếu value = 0 thì tìm được 1 nghiệm.

Chương trình minh họa

#include <iostream>
using namespace std;

int countSolutionsEq(int coeff[], int start, int end, int value) {
    if (value == 0)
        return 1;
    int coefCount = 0;
    for (int i = start; i <= end; i++)
        if (coeff[i] <= value)
            coefCount += countSolutionsEq(coeff, i, end, value - coeff[i]);
    return coefCount;
}

int main() {
    int coeff[] = {3, 5, 1, 2};
    int value = 6;
    int n = sizeof(coeff) / sizeof(coeff[0]);
    cout << "The number of solutions of the linear equation is " << countSolutionsEq(coeff, 0, n - 1, value);
    return 0;
}

Đầu ra

The number of solutions of the linear equation is 8