Tìm số nghiệm của bất phương trình x + y + z ≤ n bằng C++

Trong bài viết này, chúng ta tìm số nghiệm nguyên không âm của bất phương trình x + y + z ≤ n với ràng buộc 0 ≤ x ≤ X, 0 ≤ y ≤ Y, 0 ≤ z ≤ Z.

Phương pháp Brute Force

Duyệt tất cả cặp (x, y), tính temp = n - x - y. Nếu temp ≥ Z thì tất cả z ∈ [0, Z] đều thỏa mãn, tăng Z+1. Nếu 0 ≤ temp < Z thì tăng temp + 1. Lặp tương tự cho các cặp (x, z) và (y, z).

Lưu ý: Mã nguồn gốc có logic đếm hơi phức tạp, có thể đơn giản hóa bằng 3 vòng lặp lồng nhau trực tiếp.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int X = 1, Y = 2, Z = 3, n = 4;
    int answer = 0;

    for (int i = 0; i <= X; i++) {
        for (int j = 0; j <= Y; j++) {
            int temp = n - i - j;
            if (temp >= 0) {
                answer += min(temp, Z) + 1;
            }
        }
    }
    cout << answer << "\n";
    return 0;
}

Kết quả

17

Giải thích

Với mỗi cặp (x, y), giá trị lớn nhất của z là min(Z, n - x - y). Số nghiệm z hợp lệ là min(Z, n - x - y) + 1 (kể cả 0). Tổng hợp qua mọi x, y cho kết quả.

Kết luận

Bài viết trình bày cách đếm nghiệm của x + y + z ≤ n với giới hạn trên cho từng biến. Độ phức tạp O(X·Y). Mã nguồn C++ và giải thuật đã được trình bày. Có thể viết bằng C, Java, Python.