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

C++ में अधिकतम मोड़ों वाला पथ लंबाई


एक समस्या को हल करने के लिए जिसमें हमें एक बाइनरी ट्री दिया गया है। अब हमें अधिकतम संख्या में मोड़ों वाला पथ खोजने की आवश्यकता है। यानी, एक मोड़ तब माना जाता है जब पथ की दिशा बाएं से दाएं या इसके विपरीत बदलती है, उदाहरण के लिए

इनपुट -

C++ में अधिकतम मोड़ों वाला पथ लंबाई

आउटपुट -

6

अब इस दृष्टिकोण में, हम ट्री को पार करेंगे और पिछली गतिविधियों पर नज़र रखेंगे। यदि दिशा बदलती है, तो हम बस अपने मोड़ों की गिनती अपडेट करते हैं, और फिर हम अधिकतम खोजते हैं।

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

इस दृष्टिकोण में, हम सभी पथों को पार करेंगे, और हम अधिकतम संख्या में मोड़ निकालकर अपना उत्तर अपडेट करेंगे।

उदाहरण

 #include <bits/stdc++.h> using namespace std; struct Node { // हमारे नोड की संरचना     int key;     struct Node* left;     struct Node* right; }; struct Node* newNode(int key){ // हमारे नोड को इनिशियलाइज़ करना     struct Node* node = new Node();     node->left = NULL;     node->right = NULL;     node->key = key;     return node; } void maximumBends(struct Node* node,char direction, int bends,                     int* maxBends, int soFar,int* len){     if (node == NULL) // यदि NULL पहुंचा        return;     if (node->left == NULL && node->right == NULL) { // यदि हम लीफ नोड पर पहुंचते हैं तो                                                    //चेक करते हैं कि हमें अपना उत्तर अपडेट करना है या नहीं         if (bends > *maxBends) {             *maxBends = bends;             *len = soFar;         }     }     else {         if (direction == 'l') { // वर्तमान दिशा बाएं है             maximumBends(node->left, direction,bends, maxBends,soFar + 1, len);             maximumBends(node->right, 'r',bends + 1, maxBends,soFar + 1, len); // यदि हम दिशा बदलते हैं तो मोड़ भी बढ़ता है         }         else {             maximumBends(node->right, direction,bends, maxBends,soFar + 1, len);             maximumBends(node->left, 'l',bends + 1, maxBends,soFar + 1, len); // वही जब दिशा बाएं थी         }     } } int main(){     struct Node* root = newNode(10);     root->left = newNode(8);     root->right = newNode(2);     root->left->left = newNode(3);     root->left->right = newNode(5);     root->right->left = newNode(2);     root->right->left->right = newNode(1);     root->right->left->right->left = newNode(9);     int len = 0, bends = 0, maxBends = -1;     if(!root) // यदि ट्री खाली है        cout << "0\n";     else{         if (root->left) // यदि बायां सबट्री मौजूद है             maximumBends(root->left, 'l',bends, &maxBends, 1, &len);         if (root->right) // यदि दायां सबट्री मौजूद है             maximumBends(root->right, 'r', bends,&maxBends, 1, &len);         cout << len << "\n";     }     return 0; }

आउटपुट

4

उपरोक्त कोड की व्याख्या

उपरोक्त दृष्टिकोण में, हम बस सभी पथों को पार कर रहे हैं और अब तक मिले मोड़ों की गिनती कर रहे हैं अब जब हम पथ के अंत तक पहुंचते हैं .i.e लीफ नोड, हम चेक करते हैं कि अब तक के मोड़ पिछले अधिकतम से अधिक हैं या नहीं अब यदि शर्त सत्य है, तो हम अपने अधिकतम मोड़ों को अपडेट करते हैं और इस नई लंबाई के लिए पथ की लंबाई भी अपडेट करते हैं, और इस तरह हमारा प्रोग्राम आगे बढ़ता है।

निष्कर्ष

इस ट्यूटोरियल में, हम अधिकतम संख्या में मोड़ों वाले पथ लंबाई की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण (सामान्य) भी सीखा जिससे हमने इस समस्या को हल किया। हम यही प्रोग्राम C, Java, Python, और अन्य भाषाओं में भी लिख सकते हैं। आशा है आपको यह ट्यूटोरियल उपयोगी लगा होगा।

  1. C++ में बाइनरी ट्री में अधिकतम लगातार बढ़ते पथ की लंबाई C++ में बाइनरी ट्री में अधिकतम लगातार बढ़ते पथ की लंबाई

    समस्या विवरण मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें सबसे लंबे पथ की लंबाई की गणना करनी है जिसमें लगातार मानों वाले नोड्स बढ़ते क्रम में हों। प्रत्येक नोड को लंबाई 1 के पथ के रूप में माना जाएगा। उदाहरण आउटपुट 3 होगा क्योंकि (11, 12, 13) अधिकतम लगातार पथ है। एल्गोरिदम चरण फ़ंक्शन solve(root,

  1. - C++ में द्विभाजित ग्राफ में अधिकतम एज की संख्या

    समस्या कथन एक पूर्णांक N दिया गया है जो शीर्षों की संख्या दर्शाता है। कार्य N शीर्षों के द्विभाजित ग्राफ में संभव अधिकतम एज की संख्या ढूंढना है। द्विभाजित ग्राफ एक द्विभाजित ग्राफ वह है जिसमें शीर्षों के 2 सेट होते हैं। सेट ऐसे होते हैं कि एक ही सेट के शीर्ष कभी भी उनके बीच एज साझा नहीं करेंगे। उ

  1. - C++ में 0 और 1 के सेगमेंट की अधिकतम लंबाई

    समस्या कथन एक स्ट्रिंग दी गई है जिसमें केवल 0 और 1 हैं। कार्य स्ट्रिंग के सेगमेंट की अधिकतम लंबाई ढूंढना है जैसे कि प्रत्येक सेगमेंट में 1 की संख्या 0 से अधिक हो। उदाहरण यदि इनपुट स्ट्रिंग 10111000001011 है तो उत्तर 12 होगा - पहला सेगमेंट लंबाई 7 का है 10111000001011 दूसरा सेगमेंट लंबाई 5 का है 10