इस समस्या में, हमें एक पूर्णांक 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 के लिए, इसे p(n) द्वारा उत्पन्न किए जा सकने वाले तरीकों की कुल संख्या,
Σ∞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) ((के(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