Cách viết N dưới dạng tổng của hai hoặc nhiều số nguyên dương trong C ++

Trong bài toán này, chúng ta được cung cấp một số nguyên n. Nhiệm vụ của chúng ta là tìm tổng số cách trong đó có thể được biểu thị bằng tổng của hai hoặc nhiều số nguyên dương.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

N = 4

Đầu ra

5

Giải thích

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

Để giải quyết vấn đề này, chúng tôi sẽ sử dụng công thức lặp lại của Euler. Đối với một số n, tổng số cách nó có thể được tạo ra p (n) bằng,

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

Sử dụng công thức này, chúng ta sẽ suy ra công thức cho p (n), p (n) =p (n-1) + p (n-2) - p (n-5) - p (n-7) +… + ( -1) ^(k-1) ((k (3k-1)) / 2)

Chương trình minh họa việc triển khai giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

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