Chương trình C++ phân tích thừa số duy nhất (Unique Factorization) của số cho trước

Đây là chương trình C++ lấy tất cả các phân tích thừa số 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 (partition) cho ra số nguyên đó. Cho số nguyên dương n, chương trình sinh tất cả các cách biểu diễn n dưới dạng tổng của các số nguyên dương.

Thuật toán

Bắt đầu hàm displayAllUniqueParts(int m):
  1) Đặt chỉ số phần tử cuối k trong phân hoạch = 0
  2) Khởi tạo phân hoạch đầu tiên là chính số đó, p[k] = m
  3) Tạo vòng lặp while: trước tiên 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 số 1.
  4) Hiển thị phân hoạch hiện tại bằng displayArray(p, k + 1)
  5) Sinh phân hoạch tiếp theo:
  6) Khởi tạo val = 0.
     Tìm giá trị khác 1 bên phải nhất trong p[]. Cập nhật val
     để biết dung lượng có thể chứa.
     Nếu k < 0, tất cả giá trị là 1 nên không còn phân hoạch.
     Giảm p[k] tìm được và điều chỉnh val.
  7) Nếu val lớn hơn, thứ tự sắp xếp bị vi phạm. Chia val thành các giá trị
     kích thước p[k] và sao chép vào các vị trí sau p[k].
     Sao chép val vào vị trí tiếp theo và tăng vị trí.
Kết thúc

Ví dụ mã nguồn

#include <iostream>
using namespace std;

void displayArray(int p[], int m) { // in mảng
    for (int i = 0; i < m; i++)
        cout << p[i] << " ";
    cout << endl;
}

void displayAllUniqueParts(int m) {
    int p[m];
    int k = 0;
    p[k] = m;
    while (true) {
        displayArray(p, k + 1);
        int val = 0; // khởi tạo val
        while (k >= 0 && p[k] == 1) {
            val += p[k]; // cập nhật val
            k--;
        }
        if (k < 0)
            return;
        p[k]--;
        val++;
        while (val > p[k]) { // nếu val lớn hơn
            p[k + 1] = p[k];
            val = val - p[k];
            k++;
        }
        p[k + 1] = val;
        k++;
    }
}

int main() {
    cout << "Hiển thị tất cả phân hoạch duy nhất của 3\n";
    displayAllUniqueParts(3);
    cout << "\nHiển thị tất cả phân hoạch duy nhất của 4\n";
    displayAllUniqueParts(4);
    cout << "\nHiển thị tất cả phân hoạch duy nhất của 5\n";
    displayAllUniqueParts(5);
    return 0;
}

Kết quả

Hiển thị tất cả phân hoạch duy nhất của 3
3
2 1
1 1 1
Hiển thị 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
Hiển thị 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