C++ में N को दो या अधिक पॉजिटिव इंटीजर्स के योग के रूप में लिखने के तरीके

इस समस्या में, हमें एक पूर्णांक n दिया गया है। हमारा कार्य उन तरीकों की कुल संख्या ज्ञात करना है जिनसे इसे दो या अधिक पॉजिटिव इंटीजर्स के योग के रूप में व्यक्त किया जा सकता है।

उदाहरण

इनपुट

N = 4

आउटपुट

5

व्याख्या

4 को इन तरीकों से योग के रूप में लिखा जा सकता है:
4, 3+1, 2+2, 2+1+1, 1+1+1+1

इस समस्या को हल करने के लिए, हम यूलर के पुनरावृत्ति सूत्र का उपयोग करेंगे। एक संख्या n के लिए, इसे उत्पन्न करने के तरीकों की कुल संख्या p(n) होगी:

Σ^∞ n=0 p(n)x^n = Π^∞ k=1 (1/(1-x^k))

इस सूत्र का उपयोग करके, हम 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 positiveSum(int n) {
    vector 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 << N << " को दो या अधिक पॉजिटिव संख्याओं के योग के रूप में लिखने के तरीकों की संख्या: "
         << positiveSum(N);
    return 0;
}

आउटपुट

12 को दो या अधिक पॉजिटिव संख्याओं के योग के रूप में लिखने के तरीकों की संख्या: 77