ज्यादातर मामलों में, गणना की समस्याओं को पुनरावर्ती गणना द्वारा हल किया जाता है। दुर्भाग्य से, कोई सामान्य दृष्टिकोण नहीं है, क्योंकि अक्सर, पुनरावृति विधियां स्वयं कार्य पर अत्यधिक निर्भर होती हैं।
हालांकि, कोई विभिन्न संयुक्त वस्तुओं की गणना के तरीकों के बीच कुछ समानता देख सकता है। इसलिए, एक उदाहरण के लिए, एक कोड पर विचार करें जो n से k तक सभी संयोजन उत्पन्न करता है।
इंट एन, के;
// एक सरणी जो संयोजन उपसर्गों का समर्थन करती है।
//
// इस मामले में उपसर्ग का अर्थ है कि हमने संयोजन में कुछ वस्तुओं का चयन किया है।
//
// इसके बाद, वे या तो सही संयोजन में पूरे होंगे,
// या रिकर्सन शाखा को काट देगा जब यह पता चलेगा कि ऐसा उपसर्ग सही ढंग से पूरा नहीं किया जा सकता है
वेक्टर गिरफ्तार;
// पुनरावर्ती पुनरावृत्ति समारोह ही
//
// स्थिति - संयोजन में वस्तु की संख्या, जिसे हम वर्तमान क्षण में निर्धारित करेंगे (0 से k - 1 तक)
//
// पिछला - उस वस्तु का मूल्य जो पिछले चरण में लिया गया था
//
// संयोजनों में, वस्तुओं का क्रम महत्वपूर्ण नहीं है ([1, 2] और [2, 1] को समान और समान माना जाता है),
// इसलिए हम केवल सेट उत्पन्न करना चाहते हैं जहां ऑब्जेक्ट मान आरोही क्रम में हों।
//
// यह आवश्यक है ताकि समान विकल्प जैसे [1, 2] और [2, 1] केवल एक बार पुनरावृत्त हों
// (हमारे मामले में, हम केवल [1, 2] पर विचार करेंगे, लेकिन [2, 1] पर नहीं क्योंकि यह एक आदेशित सेट नहीं है)।
//
// यही कारण है कि हम पुनरावृत्तियों की संख्या को कम करने के लिए पिछला चर रखते हैं
शून्य आरईसी (इंट पॉस, इंट प्रीव) {
// यदि चयनित तत्व की संख्या k के बराबर है, तो हमने पहले ही सभी तत्वों का चयन कर लिया है
// क्योंकि इनकी संख्या 0 से k-1 तक होती है
अगर (स्थिति == के) {
// यदि शर्त पूरी हो जाती है, तो सही संयोजन अब arr array में है
// और हम इसे किसी तरह संसाधित कर सकते हैं (इस मामले में, इसे कंसोल पर प्रिंट करें)
के लिए (int i = 0; i < k; i++)
cout << आगमन [i] + 1 << ' ';
cout << '\n';
वापस करना; // पुनरावर्तन शाखा को काट दें, क्योंकि पहले से ही एक संयोजन है और आगे जारी रखने की आवश्यकता नहीं है
}
// यहां हम जांचते हैं कि क्या हम शेष तत्वों से सही संयोजन प्राप्त कर सकते हैं
// यदि पर्याप्त शेष तत्व नहीं हैं, तो हम इस पुनरावर्तन शाखा को काट देते हैं
अगर (के - स्थिति > एन - पिछला - 1)
वापस करना;
// उस वस्तु पर पुनरावृति करें जिसे हम इंडेक्स पॉज़ के साथ स्थिति पर रखते हैं
// लेकिन क्योंकि हम एक आदेशित सेट चाहते हैं, तो न्यूनतम संभव मान prev + 1 है
for (int i = prev + 1; i < n; i++) {
आगमन.पुश_बैक (i); // वैश्विक सरणी में एक तत्व जोड़ें। अब लगता है हमने उसे चुन लिया है
आरईसी (स्थिति + 1, मैं); // निम्नलिखित आइटम सेट करने के लिए पुनरावर्ती रूप से चलाएँ
आगमन.पॉप_बैक (); // पुनरावर्तन से लौटने के बाद, हमारा वर्तमान में चयनित तत्व अब प्रासंगिक नहीं है,
// क्योंकि पुनरावर्तन के अंदर, हम इस तरह के एक उपसर्ग के साथ सभी विकल्पों के माध्यम से चले गए,
// इसलिए इस तत्व को हटाने की जरूरत है
}
}
मुख्य प्रवेश बिंदु()
{
सिने>> एनजीटी;&जीटी; क;
// प्रारंभ में हम तत्व को 0वें स्थान पर सेट करेंगे
// हम मानते हैं कि तत्व -1 को पहले चुना गया था, ताकि पुनरावृत्ति शुरू में एक अशक्त वस्तु से शुरू हो
आरईसी (0, -1);
वापसी 0;
}
समान कोड, लेकिन टिप्पणियों के बिना:
इंट एन, के;
वेक्टर गिरफ्तार;
शून्य आरईसी (इंट पॉस, इंट प्रीव) {
अगर (स्थिति == के) {
के लिए (int i = 0; i < k; i++)
cout << आगमन [i] + 1 << ' ';
cout << '\n';
वापस करना;
}
अगर (के - स्थिति > एन - पिछला - 1)
वापस करना;
for (int i = prev + 1; i < n; i++) {
आगमन.पुश_बैक (i);
आरईसी (स्थिति + 1, मैं);
आगमन.पॉप_बैक ();
}
}
मुख्य प्रवेश बिंदु() {
सिने>> एनजीटी;&जीटी; क;
आरईसी (0, -1);
वापसी 0;
}
पुनरावर्ती पुनरावृत्तियों में, पुनरावर्ती कटौती पर हमेशा विशेष ध्यान दिया जाना चाहिए। व्यवहार में, वे कार्यक्रम को बहुत तेज कर सकते हैं।
|