C++ में किसी संख्या को घातों के योग के रूप में व्यक्त करने के तरीकों की गिनती

समस्या विवरण

दो संख्याएं num और power इनपुट के रूप में दी गई हैं। लक्ष्य उन तरीकों को ढूंढना है जिनसे num को दी गई घात पर उठाई गई अद्वितीय प्राकृतिक संख्याओं के योग के रूप में दर्शाया जा सकता है। यदि num 10 है और power 2 है तो हम 10 को 1^2 + 3^2 के रूप में दर्शा सकते हैं। तो कुल 1 तरीका।

उदाहरण

इनपुट

num=30

आउटपुट

घातों के योग के रूप में व्यक्त करने के तरीकों की संख्या: 2

व्याख्या

30 को घातों के योग के रूप में व्यक्त करने के तरीके: 1^2 + 2^2 + 5^2 और 1^2 + 2^2 + 3^2 + 4^2

इनपुट

num=35

आउटपुट

घातों के योग के रूप में व्यक्त करने के तरीकों की संख्या: 1

व्याख्या

'num' को घातों के योग के रूप में व्यक्त करने के तरीके: 2^2 + 3^2

दृष्टिकोण

इस दृष्टिकोण में हम पहले जांचते हैं कि संख्या स्वयं किसी num^power की घात है या नहीं। यदि हां तो तरीके 1 के रूप में लौटाएं, यदि नहीं तो पुनरावर्ती रूप से num^power + (num+1)^power के योग की जांच करें।

एल्गोरिदम चरण

दो पूर्णांक num और power इनपुट के रूप में लें।
फंक्शन sum_of_powers(int num, int power, int val) एक num लेता है और दी गई घात पर उठाई गई अद्वितीय प्राकृतिक संख्याओं के योग के रूप में 'num' को व्यक्त करने के तरीकों की संख्या लौटाता है।
check = (num - pow(val, power)) लें। यदि check 0 है तो 1 लौटाएं क्योंकि संख्या स्वयं val^power है।
यदि check 0 से कम है तो 0 लौटाएं।
अन्यथा temp = val + 1 लें।
(sum_of_powers(check, power, temp) + sum_of_powers(num, power, temp)) का योग लौटाएं।
अंत में हमें लौटाने के लिए तरीके मिल जाएंगे।

C++ कोड उदाहरण

#include <bits/stdc++.h>
using namespace std;

int sum_of_powers(int num, int power, int val) {
    int check = (num - pow(val, power));
    if(check == 0) {
        return 1;
    } else if(check < 0) {
        return 0;
    } else {
        int temp = val + 1;
        return sum_of_powers(check, power, temp) + sum_of_powers(num, power, temp);
    }
}

int main() {
    int num = 25, power = 2;
    cout << "घातों के योग के रूप में व्यक्त करने के तरीकों की संख्या: " << sum_of_powers(num, power, 1);
    return 0;
}

आउटपुट

घातों के योग के रूप में व्यक्त करने के तरीकों की संख्या: 2