为特定情况执行整数分区的 C++ 程序
这是一个C++程序，用于针对特定情况执行整数分区。在这个程序中，给定了一个正整数n，并且必须生成所有可能的唯一方法来表示n为正整数之和。
算法
Begin
function displayAllUniqueParts(int m):
1) Set Index of last element k in a partition to 0
2) Initialize first partition as number itself, p[k]=m
3) Create a while loop which first prints current partition, then generates next partition. The loop stops when the current partition has all 1s.
4) Display current partition as displayArray(p, k + 1)
5) Generate next partition:
6) Initialize val = 0.
Find the rightmost non-one value in p[]. Also, update the val so that we know how much value can be ccommodated.
If k < 0,
All the values are 1 so there are no more partitions
Decrease the p[k] found above and adjust the val.
7) If val is more,
then the sorted order is violated. Divide val in different values of size p[k] and copy these values at different positions after p[k].
Copy val to next position and increment position.
End示例
#include输出结果using namespace std; void displayArray(int p[], int m) { //打印数组 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; //初始化值 while (k >= 0 && p[k] == 1) { val += p[k]; //更新值 k--; } if (k < 0) return; p[k]--; val++; //如果val更大 while (val > p[k]) { p[k + 1] = p[k]; val = val - p[k]; k++; } p[k + 1] = val; k++; } } int main() { cout << "Display All Unique Partitions of integer:7\n"; displayAllUniqueParts(7); return 0; }
Display All Unique Partitions of integer:7 7 6 1 5 2 5 1 1 4 3 4 2 1 4 1 1 1 3 3 1 3 2 2 3 2 1 1 3 1 1 1 1 2 2 2 1 2 2 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1