Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में किसी भी शहर और स्टेशन के बीच अधिकतम दूरी खोजें


अवधारणा

0 से N-1 तक संख्या वाले शहरों की दी गई संख्या N और जिन शहरों में स्टेशन स्थित हैं, के संबंध में, हमारा कार्य किसी भी शहर और उसके निकटतम स्टेशन के बीच अधिकतम दूरी निर्धारित करना है। यह ध्यान दिया जाना चाहिए कि स्टेशनों वाले शहर किसी भी क्रम में दिए जा सकते हैं।

इनपुट

numOfCities = 6, stations = [2, 4]

आउटपुट

2

इनपुट

numOfCities = 6, stations = [4]

आउटपुट

4
  • निम्नलिखित आकृति पहले उदाहरण को दर्शाती है जिसमें 6 शहर हैं और स्टेशनों वाले शहर हरे रंग से हाइलाइट किए गए हैं। तो, इस मामले में, उसके निकटतम स्टेशनों से सबसे दूर का शहर 0 है जो 2 की दूरी पर है। इसलिए अधिकतम दूरी 1 है।

C++ में किसी भी शहर और स्टेशन के बीच अधिकतम दूरी खोजें

  • दूसरे उदाहरण में, उसके निकटतम स्टेशन से सबसे दूर का शहर 0 है जो 4 की दूरी पर है। इसलिए अधिकतम दूरी 4 है।

C++ में किसी भी शहर और स्टेशन के बीच अधिकतम दूरी खोजें

विधि

यहां, इस समस्या में तीन संभावित मामले हैं −

  • पहला मामला इंगित करता है जब सबसे दूर का शहर दो स्टेशनों के बीच होता है।

  • दूसरा मामला इंगित करता है जब सबसे दूर का शहर पहले स्टेशन के बाईं ओर होता है।

  • अंतिम मामला इंगित करता है जब सबसे दूर का शहर अंतिम स्टेशन के दाईं ओर होता है।

उपरोक्त समस्या को हल करने के लिए निम्नलिखित एल्गोरिदम लागू किया जाता है −

  • हम आकार N (शहरों की संख्या) का एक बूलियन सरणी False के साथ इनिशियलाइज़ करते हैं। उसके बाद स्टेशनों वाले शहरों के मानों को True के रूप में चिह्नित करें

  • इसके बाद हम एक वेरिएबल dist को 0 से इनिशियलाइज़ करते हैं। हमें एक और वेरिएबल maxDist को इनिशियलाइज़ करना होगा जिसका मान पहले स्टेशन वाले शहर के समान हो (दूसरे मामले के लिए उपयोग किया जाता है)।

  • एक-एक करके सभी शहरों के माध्यम से लूप शुरू करें।

  • यह देखा गया है कि यदि वर्तमान शहर में स्टेशन है, और फिर (dist+1)//2 और maxDist के अधिकतम को maxDist को असाइन करें (पहले मामले के लिए उपयोग किया जाता है)। इसके अलावा, dist को 0 असाइन करें।

  • अन्यथा, dist को बढ़ाएं।

  • अंत में, dist और maxDist के अधिकतम को लौटाएं (तीसरे मामले के लिए उपयोग किया जाता है)।

उदाहरण

// C++ program to calculate the maximum // distance between any city // and its nearest station #include<bits/stdc++.h> using namespace std; // किसी भी शहर और उसके निकटतम स्टेशन के बीच अधिकतम // दूरी की गणना करने वाला फ़ंक्शन int findMaxDistance(int numOfCities1,int station1[],int N){    // बूलियन सूची को इनिशियलाइज़ करने के लिए उपयोग किया जाता है    bool hasStation[numOfCities1 + 1] = {false};    // स्टेशन वाले शहरों को True असाइन करने के लिए उपयोग किया जाता है    for (int city1 = 0; city1 < N; city1++){       hasStation[station1[city1]] = true;    }    int dist1 = 0;    int maxDist1 = INT_MAX;    for(int i = 0; i < N; i++){       maxDist1 = min(station1[i],maxDist1);    }    for (int city1 = 0; city1 < numOfCities1; city1++){       if (hasStation[city1] == true){          maxDist1 = max((dist1 + 1) / 2, maxDist1);          dist1 = 0;       }    else       dist1 += 1;    }    return max(maxDist1, dist1); } //ड्राइवर कोड int main(){    int numOfCities1 = 6;    int station1[] = {2,4};    int N = sizeof(station1)/sizeof(station1[0]);    cout << "Max Distance:" << findMaxDistance(numOfCities1,    station1, N); }

आउटपुट

Max Distance:2

  1. C++ में दो अलग-अलग गुड नोड्स की किसी भी जोड़ी के बीच सबसे छोटी दूरी खोजें C++ में दो अलग-अलग गुड नोड्स की किसी भी जोड़ी के बीच सबसे छोटी दूरी खोजें

    मान लीजिए हमारे पास N अलग-अलग नोड्स और M एजेज के साथ एक दिया गया वेटेड अनडायरेक्टेड ग्राफ है, कुछ नोड्स गुड नोड्स हैं। हमें किन्हीं दो अलग-अलग गुड नोड्स की जोड़ी के बीच सबसे छोटी दूरी खोजनी है। दिए गए आरेख में पीले नोड्स को गुड नोड्स माना जाता है। उदाहरण के लिए, यदि इनपुट इस तरह का है: तो आउटपुट 11

  1. C++ में बाइनरी ट्री के दो नोड्स के बीच दूरी - O(log n) विधि C++ में बाइनरी ट्री के दो नोड्स के बीच दूरी - O(log n) विधि

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है और हमें Q क्वेरी दी गई हैं। हमारा कार्य C++ में बाइनरी ट्री के दो नोड्स के बीच दूरी - O(log n) विधि को हल करने के लिए एक प्रोग्राम बनाना है।समस्या विवरणप्रत्येक क्वेरी में, हमें बाइनरी ट्री के दो नोड्स दिए गए हैं और हमें दो नोड्स के बीच की दूरी ढूंढनी ह

  1. C++ में थ्रेशोल्ड दूरी पर सबसे कम पड़ोसियों वाला शहर ढूंढना C++ में थ्रेशोल्ड दूरी पर सबसे कम पड़ोसियों वाला शहर ढूंढना

    मान लीजिए n शहर हैं जो 0 से n-1 तक नंबरेड हैं। अगर हमारे पास ऐरे edges है जहां edges[i] = [fromi, toi, weighti] शहरों fromi और toi के बीच एक बाईडायरेक्शनल और वेटेड एज दर्शाता है, और दिया गया इंटीजर distanceThreshold है। हमें वह शहर ढूंढना है जिसमें उन शहरों की सबसे कम संख्या हो जो किसी पथ के माध्यम