这是一个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 accommodated. 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<iostream> using namespace std; void displayArray(int p[], int m) //to print the array { 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; //initialize val while (k >= 0 && p[k] == 1) { val += p[k]; //update val k--; } if (k < 0) return; p[k]--; val++; while (val > p[k]) //if val is more { p[k + 1] = p[k]; val = val - p[k]; k++; } p[k + 1] = val; k++; } } int main(){ cout << "Display All Unique Partitions of 3\n"; displayAllUniqueParts(3); cout << "\nDisplay All Unique Partitions of 4\n"; displayAllUniqueParts(4); cout << "\nDisplay All Unique Partitions of 5\n"; displayAllUniqueParts(5); return 0; }
输出结果
Display All Unique Partitions of 3 3 2 1 1 1 1 Display All Unique Partitions of 4 4 3 1 2 2 2 1 1 1 1 1 1 Display All Unique Partitions of 5 5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1