Chương trình C ++ để thực hiện phân tích nhân tử duy nhất của một số cho trước

Đây là một Chương trình C ++ để nhận tất cả các thừa số duy nhất của một số nguyên nhất định sao cho việc bổ sung một 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à chúng tôi sẽ tạo ra 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):
   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

Ví dụ

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

Đầu ra

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