समस्या विवरण
एक पूर्णांक n इनपुट के रूप में दिया गया है। लक्ष्य उन तरीकों की संख्या ज्ञात करना है जिनसे हम 'n' को विषम पूर्णांकों के योग के रूप में दर्शा सकते हैं। उदाहरण के लिए, यदि n 3 है तो इसे योग (1+1+1) और (3) के रूप में दर्शाया जा सकता है इसलिए कुल 2 तरीके।
उदाहरण
इनपुट
n=6
आउटपुट
'n' को विषम पूर्णांकों के योग के रूप में व्यक्त करने के तरीकों की संख्या: 8
व्याख्या
'n' को विषम पूर्णांकों के योग के रूप में व्यक्त करने के तरीके: 1. 1+1+1+1+1+1 2. 3+1+1+1 3. 1+3+1+1 4. 1+1+3+1 5. 1+1+1+3 6. 3+3 7. 1+5 8. 5+1
इनपुट
n=9
आउटपुट
'n' को विषम पूर्णांकों के योग के रूप में व्यक्त करने के तरीकों की संख्या: 34
व्याख्या
'n' को विषम पूर्णांकों के योग के रूप में व्यक्त करने के कुछ तरीके: 1. 1+1+1+1+1+1+1+1+1 2. 3+3+3 3. 5+3+1 4. 7+1+1 5. ... और अन्य ऐसे संयोजन
दृष्टिकोण
इस दृष्टिकोण में हम पिछली संख्याओं से विषम पूर्णांकों के योग के रूप में संख्या दर्शाने के तरीकों की जांच करेंगे जो n-1वीं और n-2वीं संख्याएं हैं। तरीके होंगे ways(n-1) + ways(n-2)।
एल्गोरिदम चरण
- एक पूर्णांक
nइनपुट के रूप में लें। - फंक्शन
odd_ways(int n)एक संख्या लेता है और 'n' को विषम पूर्णांकों के योग के रूप में व्यक्त करने के तरीकों की संख्या लौटाता है। - संख्याओं को विषम पूर्णांकों के योग के रूप में दर्शाने के तरीकों की गिनती संग्रहीत करने के लिए लंबाई
n+1की सरणीarrलें। - संख्या 0 के लिए, ऐसा कोई तरीका नहीं है इसलिए
arr[0]को 0 से सेट करें। - संख्या 1 के लिए केवल एक तरीका है इसलिए
arr[1]को 1 से सेट करें। - बाकी संख्याओं के लिए हम
iके बीच 2 सेnतकarr[i] = arr[i-1] + arr[i-2]सेट कर सकते हैं। - अंत में हमारे पास
arr[n]होगा उन तरीकों की संख्या के रूप में जिनसेnको विषम पूर्णांकों के योग के रूप में दर्शाया जाता है। - परिणाम के रूप में
arr[n]लौटाएं।
C++ कोड उदाहरण
#include <iostream>
using namespace std;
int odd_ways(int n) {
int arr[n+1];
arr[0] = 0;
arr[1] = 1;
for(int i = 2; i <= n; i++) {
arr[i] = arr[i-1] + arr[i-2];
}
return arr[n];
}
int main() {
int n = 6;
cout << "'n' को विषम पूर्णांकों के योग के रूप में व्यक्त करने के तरीकों की संख्या: " << odd_ways(n);
return 0;
}
आउटपुट
'n' को विषम पूर्णांकों के योग के रूप में व्यक्त करने के तरीकों की संख्या: 8