โปรแกรม C++ หาจำนวนวิธีเขียนตัวเลขเป็นผลรวมของตัวเลขที่เล็กกว่าตัวมันเอง

ในโปรแกรมนี้ เราจะนับจำนวนวิธีที่สามารถแสดงจำนวนหนึ่งด้วยผลรวมของตัวเลขที่น้อยกว่าตัวมันเอง โปรแกรมนี้จะนับพาร์ทิชั่นของตัวเลขที่กำหนด เราใช้ตัวเลข n เป็นอินพุต จากนั้นเริ่มจากตัวแบ่งตัวเลขโดยลบทีละ 1 หากพาร์ติชั่นใหม่ถูกสร้างขึ้น ให้เพิ่มตัวนับ

อัลกอริทึม

partitionCount(n)

Input :หมายเลข 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