Đếm số cách phân tích số nguyên thành tổng các số nhỏ hơn nó (Integer Partition)

Chương trình đếm số phân hoạch (partition) của số nguyên n: số cách viết n thành tổng các số nguyên dương nhỏ hơn n (thứ tự không quan trọng).

Thuật toán

Sử dụng mảng p lưu trữ phân hoạch hiện tại. Bắt đầu từ p[0] = n. Lặp: tìm phần tử > 1, giảm nó đi 1, phân phối phần dư vào các phần tử tiếp theo bằng giá trị vừa giảm. Đếm mỗi lần tạo ra phân hoạch mới.

Ví dụ code

#include <iostream>
using namespace std;

int partitionCount(int n) {
    int p[n], k = 0, count = -1;
    p[k] = n;
    while (true) {
        count++;
        int rem = 0;
        while (k >= 0 && p[k] == 1) { rem += p[k]; k--; }
        if (k < 0) return count;
        p[k]--; rem++;
        while (rem > p[k]) { p[k+1] = p[k]; rem -= p[k]; k++; }
        p[k+1] = rem; k++;
    }
}

int main() {
    int n; cout << "Nhập n: "; cin >> n;
    if (n <= 0) return 1;
    cout << "Số phân hoạch: " << partitionCount(n);
}

Kết quả

Nhập n: 7
Số phân hoạch: 14