为特定情况执行整数分区的 C++ 程序

这是一个 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 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:7

7

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

回到顶部