为特定情况执行整数分区的 C++ 程序
这是一个 C++ 程序,用于针对特定情况执行整数分区。在这个程序中,给定了一个正整数 n,并且必须生成所有可能的唯一方法来表示 n 为正整数之和。
算法
Beginfunction 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<iostream>输出结果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:77
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
以上是 为特定情况执行整数分区的 C++ 程序 的全部内容, 来源链接: utcz.com/z/311387.html