C++ এ দুই বা ততোধিক ধনাত্মক পূর্ণসংখ্যার যোগফল হিসেবে N লেখার উপায়

এই সমস্যায়, আমরা একটি পূর্ণসংখ্যা n দেওয়া হয়. আমাদের কাজ হল দুই বা ততোধিক ধনাত্মক পূর্ণসংখ্যার যোগফল হিসাবে প্রকাশ করার উপায়গুলির মোট সংখ্যা খুঁজে বের করা।

সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,

ইনপুট

N = 4

আউটপুট

5

ব্যাখ্যা

4 can be written as the sum in these ways,
4, 3+1, 2+2, 2+1+1, 1+1+1+1

এই সমস্যা সমাধানের জন্য, আমরা অয়লারের পুনরাবৃত্তি সূত্র ব্যবহার করব। একটি সংখ্যার জন্য ,

Σ∞n=0 p(n)xn = Π∞k=1 (1/(1-xk ))

এই সূত্রটি ব্যবহার করে, আমরা p(n),p(n) =p(n-1) + p(n-2) - p(n-5) - p(n-7) + … + ( -1) ^(k-1) ((k(3k-1))/2)

আমাদের সমাধানের বাস্তবায়নকে চিত্রিত করার জন্য প্রোগ্রাম,

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
long long postiveSum(int n){
   vector<long long> p(n + 1, 0);
   p[0] = 1;
   for (int i = 1; i <= n; ++i) {
      int k = 1;
      while ((k * (3 * k - 1)) / 2 <= i) {
         p[i] += (k % 2 ? 1 : -1) * p[i - (k * (3 * k - 1)) / 2];
         if (k > 0)
            k *= -1;
         else
            k = 1 - k;
      }
   }
   return p[n];
}
int main(){
   int N = 12;
   cout<<"The number of ways "<<N<<" can be written as sum of two or more positive numbers is "      <<postiveSum(N);
   return 0;
}

আউটপুট

The number of ways 12 can be written as sum of two or more positive numbers is 77