자신보다 작은 숫자의 합으로 숫자를 쓰는 방법의 수를 찾는 C++ 프로그램

이 프로그램에서 우리는 하나의 숫자가 자신보다 작은 숫자의 합으로 표현될 수 있는 방법의 수를 계산할 것입니다. 이 프로그램은 주어진 숫자의 파티션을 계산합니다. 숫자 n을 입력으로 받은 다음 숫자에서 시작하여 한 번에 1을 제거하여 나눕니다. 새 파티션이 생성되면 카운터를 늘립니다.

알고리즘

파티션 개수(n)

입력 :숫자 n

출력 :파티션 수

Begin
   Create array p of size n
   k := 0
   count := -1
   put n as the first element of array p
   Repeat the following steps, do
   increase count by 1
   rem := 0
   while k >= 0 and p[k] = 1, do
      rem := rem + p[k]
      decrease k by 1
   done
   if k < 0, then
      return count
      p[k] := p[k] – 1
      rem := rem + 1
      while rem >= p[k], do
         p[k+1] := p[k]
         rem := rem - p[k]
         increase k by 1
      done
      p[k+1] := rem
      increase k by 1
   done
End

예시 코드

#include<iostream>
using namespace std;
int partitionCount(int n){ //used to count all possible partitions
   int p[n], k = 0, count = -1;
   p[k] = n; //add n as the first element of array
   while(true) { //repeat untill all elements are turned to 1
      count++;
      int rem = 0;
      while (k >= 0 && p[k] == 1){ // Move the pointer to the correct index where p[k] > 1.
         rem += p[k];
         k--;
      }
      if (k < 0) // If k < 0 then the all the element are broken down to 1.
         return count;
         //otherwise decrease the value by 1, and increase rem
         p[k]--;
         rem++;
      while (rem > p[k]) { // repeat until the number of 1's are greater than the value at k index.
         p[k+1] = p[k];
         rem -= p[k]; // Decrease the rem_val value.
         k++;
      }
      p[k+1] = rem; // Assign remaining value to the index next to k.
      k++;
   }
}
main() {
   int n, c;
   cout<<"Enter number for partition counting: ";
   cin>>n;
   if (n <= 0) { //n must be greater than or equal to 1
      cout<<"Invalid value of n";
      exit(1);
   }
   c = partitionCount(n);
   cout<<"The number of partitions: "<<c;
}

출력

Enter number for partition counting: 7
The number of partitions: 14