Chương trình C ++ để thực hiện phân vùng số nguyên theo tất cả các cách có thể

Đây là một Chương trình C ++ để lấy tất cả các phân vùng duy nhất của một số nguyên nhất định sao cho việc bổ sung phân vùng cho kết quả là một số nguyên. Trong chương trình này, một số nguyên dương n được đưa ra và tạo tất cả các cách duy nhất có thể để biểu diễn n dưới dạng tổng các số nguyên dương.

Thuật toán

Begin
   function displayAllUniqueParts(int m):
   Declare an array to store a partition p[m].
   Set Index of last element k in a partition to 0
   Initialize first partition as number itself, p[k]=m
   Create a while loop which first prints current partition, then generates next partition. The loop stops when the current partition has all 1s.
   Display current partition as displayArray(p, k + 1);
   Generate next partition:
   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.
   If val is more,
      then the sorted order is violeted. 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

Mã mẫu

#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;
}

Đầu ra

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