それ自体よりも小さい数の合計として数を書く方法の数を見つけるためのC++プログラム

このプログラムでは、1つの数をそれ自体よりも小さい数の合計で表すことができる方法の数を数えます。このプログラムは、指定された数のパーティションをカウントします。数値nを入力として受け取り、数値から始めて、一度に1を削除して数値を分割します。新しいパーティションが生成された場合は、カウンターを増やします。

アルゴリズム

partitionCount（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