Chương trình C++ phân hoạch số nguyên theo tất cả các cách có thể

Đây là chương trình C++ để lấy tất cả các phân hoạch duy nhất của một số nguyên cho trước sao cho tổng của một phân hoạch cho ra số nguyên đó. Trong chương trình này, một số nguyên dương n được cho, và sinh ra tất cả các cách duy nhất để biểu diễn n dưới dạng tổng các số nguyên dương.

Thuật toán

Bắt đầu
    hàm displayAllUniqueParts(int m):
    Khai báo mảng để lưu một phân hoạch p[m].
    Đặt chỉ số của phần tử cuối k trong một phân hoạch = 0
    Khởi tạo phân hoạch đầu tiên là chính số đó, p[k] = m
    Tạo vòng lặp while trước in phân hoạch hiện tại, sau đó sinh phân hoạch tiếp theo. Vòng lặp dừng khi phân hoạch hiện tại toàn là 1.
    Hiển thị phân hoạch hiện tại như displayArray(p, k + 1);
    Sinh phân hoạch tiếp theo:
    Khởi tạo val = 0.
    Tìm giá trị khác 1 bên phải nhất trong p[]. Cũng cập nhật val để biết bao nhiêu giá trị có thể chứa đựng.
    Nếu k < 0,
        tất cả giá trị là 1 nên không còn phân hoạch nào
    Giảm p[k] tìm được ở trên và điều chỉnh val.
    Nếu val lớn hơn,
        thì thứ tự sắp xếp bị vi phạm. Chia val thành các giá trị khác nhau có kích thước p[k] và sao chép các giá trị này tại các vị trí khác nhau sau p[k].
        Sao chép val vào vị trí tiếp theo và tăng vị trí.
Kết thúc

Mã ví dụ

#include<iostream> 
using namespace std; 

void printArr(int p[], int m) { 
    for (int i = 0; i < m; i++) 
        cout << p[i] << " "; 
    cout << endl; 
} 

void printAllUniqueParts(int m) { 
    int p[m]; 
    int k = 0; 
    p[k] = m; 
    while (true) { 
        printArr(p, k + 1); 
        int rem_val = 0; 
        while (k >= 0 && p[k] == 1) { 
            rem_val += p[k]; 
            k--; 
        } 
        if (k < 0) 
            return; 
        p[k]--; 
        rem_val++; 
        while (rem_val > p[k]) { 
            p[k + 1] = p[k]; 
            rem_val = rem_val - p[k]; 
            k++; 
        } 
        p[k + 1] = rem_val; 
        k++; 
    } 
} 

int main() { 
    cout << "Tất cả phân hoạch duy nhất của 3\n"; 
    printAllUniqueParts(3); 
    cout << "\nTất cả phân hoạch duy nhất của 4\n"; 
    printAllUniqueParts(4); 
    cout << "\nTất cả phân hoạch duy nhất của 5\n"; 
    printAllUniqueParts(5); 
    return 0; 
}

Kết quả

Tất cả phân hoạch duy nhất của 3 
3 
2 1 
1 1 1 
Tất cả phân hoạch duy nhất của 4 
4 
3 1 
2 2 
2 1 1 
1 1 1 1 
Tất cả phân hoạch duy nhất của 5 
5 
4 1 
3 2 
3 1 1 
2 2 1 
2 1 1 1 
1 1 1 1 1