C++ 程序以所有可能的方式对整数进行分区

c++server side programmingprogramming

这是一个 C++ 程序,用于获取给定整数的所有唯一分区,以便分区相加得到一个整数。在这个程序中,给定一个正整数 n,并生成所有可能的唯一方式将 n 表示为正整数之和。

算法

开始
   function displayAllUniqueParts(int m):
   声明一个数组来存储分区 p[m]。
   将分区中最后一个元素 k 的索引设置为 0
   将第一个分区初始化为数字本身,p[k]=m
   创建一个 while 循环,首先打印当前分区,然后生成下一个分区。当当前分区全为 1 时,循环停止。
   将当前分区显示为 displayArray(p, k + 1);
   生成下一个分区:
   初始化 val=0。
   在 p[] 中找到最右边的非 1 值。同时,更新 val,以便我们知道可以容纳多少值。
   如果 k < 0,
      所有值均为 1,因此不再有分区
      减少上面找到的 p[k] 并调整 val。
   如果 val 更大,
      然后违反排序顺序。将 val 分成大小为 p[k] 的不同值,并将这些值复制到 p[k] 之后的不同位置。
      将 val 复制到下一个位置并增加 position。
结束

示例代码

#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 << "All Unique Partitions of 3\n";
   printAllUniqueParts(3);
   cout << "\nAll Unique Partitions of 4\n";
   printAllUniqueParts(4);
   cout << "\nAll Unique Partitions of 5\n";
   printAllUniqueParts(5);
   return 0;
}

输出

All Unique Partitions of 3
3
2 1
1 1 1
All Unique Partitions of 4
4
3 1
2 2
2 1 1
1 1 1 1
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

相关文章