यह ट्यूटोरियल एक समस्या पर चर्चा करेगा जहां हमें अलग-अलग धनात्मक पूर्णांकों की एक सरणी दी गई है। हमें सबसे बड़ा उपसमुच्चय ढूंढना है जैसे कि प्रत्येक जोड़े के लिए बड़ा तत्व छोटे तत्व से विभाज्य हो, उदाहरण के लिए -
इनपुट: nums[] = { 1, 4, 2, 6, 7} आउटपुट: 1 2 4 व्याख्या: सभी विभाज्य उपसमुच्चय हैं: (1, 2, 4), (1, 2, 6), (1, 7), आदि हमारे पास लंबाई 3 के 2 उपसमुच्चय हैं जिनमें सभी जोड़े शर्त को संतुष्ट करते हैं। इनपुट: nums[] = { 1, 2, 3, 6 } आउटपुट: 6 2 1समाधान खोजने का दृष्टिकोण
इस ट्यूटोरियल में हम दो अलग-अलग दृष्टिकोण समझाएंगे।
सरल दृष्टिकोण
सरल दृष्टिकोण में, हम इस समस्या को हल करने के लिए रिकर्सन लागू कर सकते हैं। हम प्रत्येक तत्व को लेंगे और जांचेंगे कि क्या इसे उपसमुच्चय में शामिल करना चाहिए या नहीं। मान लें हम पहले तत्व से शुरू करते हैं। पहले तत्व के लिए हमारे पास दो विकल्प होंगे, या तो उपसमुच्चय में शामिल करना या नहीं। मान लें हम पहले तत्व को शामिल करते हैं। फिर दूसरे तत्व को उपसमुच्चय में शामिल करने के लिए, यह उपसमुच्चय में तत्वों से विभाज्य होना चाहिए या विभाजित करना चाहिए, यानी पहला तत्व। इस तरह हम पूरी सरणी में जाएंगे। तो 2^n संभावित पथ होंगे जो O(2^n) समय जटिलता बनाएंगे। आइए इस समस्या को हल करने के लिए संभव दृष्टिकोण देखें।
कुशल दृष्टिकोण
इस समस्या में डायनामिक प्रोग्रामिंग का उपयोग करके एक कुशल दृष्टिकोण लागू किया जा सकता है।
सरणी को सॉर्ट करें ताकि बायां तत्व दाएं तत्व से विभाज्य हो। हमें विभाज्यता केवल एक बार जांचनी होगी।
हम लॉन्गेस्ट इन्क्रीजिंग सबसीक्वेंस यानी हमारा dp[] सरणी लेंगे, ताकि ith इंडेक्स तक का सबसे बड़ा विभाज्य उपसमुच्चय स्टोर कर सकें। हम प्रत्येक इंडेक्स को 1 से इनिशियलाइज़ करेंगे क्योंकि प्रत्येक तत्व स्वयं को विभाजित करता है।
अब हम दूसरे इंडेक्स से पुनरावृति करेंगे और वर्तमान इंडेक्स के साथ समाप्त होने वाले अधिकतम विभाज्य उपसमुच्चय के लिए प्रत्येक तत्व की जांच करेंगे। इस तरह, हम प्रत्येक इंडेक्स के लिए अधिकतम उपसमुच्चय ढूंढेंगे।
अब सरणी को पार करें, और प्रत्येक तत्व के लिए, एक भाजक ढूंढें जिसकी विभाज्य गिनती सबसे बड़ी हो। और वर्तमान इंडेक्स के विभाज्य गिनती मान को उस तत्व के विभाज्य गिनती + 1 में बदलें।
उदाहरण
उपरोक्त दृष्टिकोण के लिए C++ कोड
#include<bits/stdc++.h> using namespace std; int main(){ int nums[] = {1, 2, 3, 6}; int n = sizeof(nums)/sizeof(int); // सरणी को सॉर्ट करके विभाजन की एक शर्त को बाहर करना। sort(nums, nums+n); vector <int> prev_res(n, -1); // सभी तत्वों के भाजक स्टोर करने के लिए वेक्टर vector <int> dp(n, 1); int max = 1; for (int i=1; i<n; i++){ // जांचें कि क्या ith तत्व का भाजक jth इंडेक्स पर मौजूद है। for (int j=0; j<i; j++){ if (nums[i]%nums[j] == 0){ // जांचें कि क्या उसे जोड़ने से सबसीक्वेंस में तत्वों की संख्या बढ़ती है। if (dp[i] < dp[j] + 1){ dp[i] = dp[j]+1; prev_res[i] = j; } } } // अधिकतम उपसमुच्चय वाले इंडेक्स को ढूंढना। if(max<dp[i]) max = dp[i]; } cout << "Largest divisible subset in the array: "; // अधिकतम उपसमुच्चय प्रिंट करना int k = max; while (k >= 0){ cout << nums[k] << " "; k = prev_res[k]; } return 0; }आउटपुट
Largest divisible subset in the array: 6 2 1
निष्कर्ष
इस ट्यूटोरियल में, हमने एक समस्या पर चर्चा की: हमें दी गई सरणी में सबसे बड़ा विभाज्य उपसमुच्चय ढूंढना है जहां प्रत्येक जोड़े में पूर्णांक विभाज्य हों। हमने रिकर्सन से एक दृष्टिकोण पर चर्चा की जो घातीय समय जटिलता बनाता है, इसलिए हमने डायनामिक प्रोग्रामिंग समाधान पर चर्चा की। हमने इस समस्या के लिए C++ प्रोग्राम भी चर्चा की जिसे हम C, Java, Python आदि प्रोग्रामिंग भाषाओं में कर सकते हैं। आशा है आपको यह ट्यूटोरियल उपयोगी लगा होगा।
