C++ प्रोग्राम: किसी संख्या को स्वयं से छोटी संख्याओं के योग के रूप में लिखने के तरीकों की संख्या

इस प्रोग्राम में हम गिनेंगे कि एक संख्या को स्वयं से छोटी संख्याओं के योग के रूप में कितने तरीकों से दर्शाया जा सकता है। यह प्रोग्राम दी गई संख्या के पार्टीशन (partition) की गणना करेगा। हम एक संख्या n को इनपुट के रूप में लेते हैं, फिर एक संख्या से शुरू करके हर बार 1 घटाकर इसे तोड़ते हैं। यदि नया पार्टीशन उत्पन्न होता है, तो काउंटर बढ़ाते हैं।

एल्गोरिदम: partitionCount(n)

इनपुट: संख्या n
आउटपुट: पार्टीशन की संख्या

Begin
    आकार n का सरणी p बनाएं
    k := 0
    count := -1
    n को सरणी p के पहले एलिमेंट के रूप में रखें
    निम्नलिखित चरणों को दोहराएं:
        count को 1 से बढ़ाएं
        rem := 0
        जब k >= 0 और p[k] = 1, तब:
            rem := rem + p[k]
            k को 1 से घटाएं
        किया
        यदि k < 0, तो:
            count लौटाएं
        p[k] := p[k] - 1
        rem := rem + 1
        जब rem >= p[k], तब:
            p[k+1] := p[k]
            rem := rem - p[k]
            k को 1 से बढ़ाएं
        किया
        p[k+1] := rem
        k को 1 से बढ़ाएं
    किया
End

उदाहरण कोड

#include <iostream>
using namespace std;

int partitionCount(int n) {
    int p[n], k = 0, count = -1;
    p[k] = n; // n को सरणी के पहले एलिमेंट के रूप में जोड़ें
    
    while (true) { // तब तक दोहराएं जब तक सभी एलिमेंट्स 1 न बन जाएं
        count++;
        int rem = 0;
        
        while (k >= 0 && p[k] == 1) { // पॉइंटर को सही इंडेक्स पर ले जाएं जहां p[k] > 1
            rem += p[k];
            k--;
        }
        
        if (k < 0) // यदि k < 0 तो सभी एलिमेंट्स 1 में टूट चुके हैं
            return count;
        
        // अन्यथा मान को 1 से घटाएं, और rem बढ़ाएं
        p[k]--;
        rem++;
        
        while (rem > p[k]) { // तब तक दोहराएं जब तक 1 की संख्या k इंडेक्स पर मान से अधिक न हो
            p[k+1] = p[k];
            rem -= p[k]; // rem_val मान घटाएं
            k++;
        }
        
        p[k+1] = rem; // शेष मान को k के बगल वाले इंडेक्स पर असाइन करें
        k++;
    }
}

int main() {
    int n, c;
    cout << "पार्टीशन गिनती के लिए संख्या दर्ज करें: ";
    cin >> n;
    
    if (n <= 0) { // n 1 से बड़ा या बराबर होना चाहिए
        cout << "n का अमान्य मान";
        exit(1);
    }
    
    c = partitionCount(n);
    cout << "पार्टीशन की संख्या: " << c;
    return 0;
}

आउटपुट

पार्टीशन गिनती के लिए संख्या दर्ज करें: 7
पार्टीशन की संख्या: 14

व्याख्या

संख्या 7 के पार्टीशन (15 कुल, लेकिन 7 को स्वयं गिनने पर 14):

• 6+1, 5+2, 5+1+1, 4+3, 4+2+1, 4+1+1+1
• 3+3+1, 3+2+2, 3+2+1+1, 3+1+1+1+1
• 2+2+2+1, 2+2+1+1+1, 2+1+1+1+1+1
• 1+1+1+1+1+1+1

नोट: यह एल्गोरिदम पूर्णांक पार्टीशन फ़ंक्शन p(n) की गणना करता है। n=7 के लिए p(7)=15 है, लेकिन चूंकि एल्गोरिदम n को स्वयं (7) के रूप में गिनता है, इसलिए आउटपुट 14 दिखाता है।