सी ++ प्रोग्राम सरणी में सबसे बड़ा विभाज्य उपसमुच्चय खोजने के लिए

यह ट्यूटोरियल एक समस्या पर चर्चा करेगा जहां हमें अलग-अलग सकारात्मक पूर्णांकों की एक सरणी दी जाती है। हमें सबसे बड़े उपसमुच्चय को खोजने की आवश्यकता है जैसे कि प्रत्येक जोड़ी के लिए बड़े तत्व को एक छोटे तत्व से विभाजित किया जाता है, उदाहरण के लिए -

Input: nums[ ] = { 1, 4, 2, 6, 7}
Output: 1 2 4
Explanation:
All Divisible subsets are: (1, 2, 4), (1, 2, 6), (1, 7), etc
We have 2 subsets of length 3 in which all the pairs satisfy the condition.

Input: nums[ ] = { 1, 2, 3, 6 }
Output: 6 2 1

समाधान खोजने के लिए दृष्टिकोण

इस ट्यूटोरियल में हम दो अलग-अलग तरीकों की व्याख्या करेंगे।

सरल तरीका

एक सरल दृष्टिकोण में, हम इस समस्या को हल करने के लिए पुनरावर्तन लागू कर सकते हैं। हम प्रत्येक तत्व को लेंगे और जांचेंगे कि इसे सबसेट में शामिल करना चाहिए या नहीं। मान लीजिए कि हम पहले तत्व से शुरू करते हैं। हमारे पास दो विकल्प होंगे, या तो सबसेट में शामिल होना है या पहले तत्व के लिए नहीं। आइए पहले तत्व को शामिल करें। फिर दूसरे तत्व को सबसेट में शामिल करने के लिए, इसे सबस्ट्रिंग में तत्वों से विभाजित या विभाजित किया जाना चाहिए, यानी पहला तत्व। इस तरह हम पूरे ऐरे में जाएंगे। तो 2^n संभावित पथ होंगे जो O(2^n) की समय जटिलता पैदा करेंगे। आइए इस समस्या को हल करने के लिए व्यवहार्य दृष्टिकोण को देखें।

कुशल दृष्टिकोण

इस समस्या में गतिशील प्रोग्रामिंग का उपयोग करके एक कुशल दृष्टिकोण लागू किया जा सकता है।

• बाएं तत्व को सही तत्व से विभाजित करने के लिए सरणी को क्रमबद्ध करें। हमें एक बार विभाज्यता की जांच करनी होगी।

• हम इंडेक्स तक के सबसे बड़े विभाज्य उपसमुच्चय को स्टोर करने के लिए सबसे लंबे समय तक बढ़ते हुए अनुक्रम, यानी हमारे डीपी [] सरणी को लेंगे। हम प्रत्येक अनुक्रमणिका को एक के साथ प्रारंभ करेंगे क्योंकि प्रत्येक तत्व स्वयं को विभाजित करता है।

• अब हम दूसरे सूचकांक से पुनरावृति करेंगे और वर्तमान सूचकांक के साथ समाप्त होने वाले अधिकतम विभाज्य उपसमुच्चय के लिए प्रत्येक तत्व की जांच करेंगे। इस प्रकार, हम प्रत्येक अनुक्रमणिका के लिए अधिकतम उपसमुच्चय प्राप्त करेंगे।

• अब सरणी के माध्यम से पार करें, और प्रत्येक तत्व के लिए, एक ऐसा भाजक खोजें, जिसकी विभाज्य संख्या सबसे बड़ी हो। और वर्तमान सूचकांक के विभाज्य गणना मानों को उस तत्व की विभाज्य गणना में बदलें + 1.

उदाहरण

उपरोक्त दृष्टिकोण के लिए C++ कोड

#include<bits/stdc++.h>
using namespace std;
int main(){
    int nums[] = {1, 2, 3, 6};
    int n = sizeof(nums)/sizeof(int);
    // sorting the array to exclude one condition for division.
    sort(nums, nums+n);
    vector <int> prev_res(n, -1);
    // vector to store divisors of all the elements
    vector <int> dp(n, 1);
    int max = 1;
    for (int i=1; i<n; i++){   // Check if there's a divisor of ith element present at jth index.
        for (int j=0; j<i; j++){
            if (nums[i]%nums[j] == 0){
            // check If adding that increases the number of elements in subsequence.
                if (dp[i] < dp[j] + 1){
                    dp[i] = dp[j]+1;
                    prev_res[i] = j;
                   
                }
            }
        }
   
        // finding index having a maximum number of subsets.
        if(max<dp[i])
            max = dp[i];
    }
    cout << "Largest divisible subset in the array: ";
    // printing the maximum subset
    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, आदि के साथ कर सकते हैं। हमें उम्मीद है कि आपको यह ट्यूटोरियल मददगार लगेगा।