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

C++ में अधिकतम लंबाई स्नेक अनुक्रम खोजें


अवधारणा

दिए गए संख्याओं के ग्रिड के संबंध में, अधिकतम लंबाई स्नेक अनुक्रम निर्धारित करें और प्रदर्शित करें। यह देखा गया है कि यदि अधिकतम लंबाई के साथ कई स्नेक अनुक्रम मौजूद हैं, तो उनमें से किसी एक को प्रदर्शित करें।

वास्तव में, एक स्नेक अनुक्रम ग्रिड में आसन्न संख्याओं से बना होता है ताकि प्रत्येक संख्या के लिए, दाईं ओर की संख्या या नीचे की संख्या उसके मान से +1 या -1 हो। यहां, उदाहरण के लिए, यदि हम ग्रिड में स्थान (a, b) पर हैं, तो हम या तो दाईं ओर जा सकते हैं यानी (a, b+1) यदि वह संख्या ±1 है या नीचे जा सकते हैं यानी (a+1, b) यदि वह संख्या ±1 है।

उदाहरण के लिए,

10, 7, 6, 3 9, 8, 7, 6 8, 4, 2, 7 2, 2, 2, 8

उपरोक्त ग्रिड में, अधिकतम स्नेक अनुक्रम है: (10, 9, 8, 7, 6, 7, 8)

नीचे दिए गए चित्र में सभी संभावित पथ दिखाए गए हैं −

10  7 →6 3 ↓ ↓ ↓ 9 → 8 → 7→ 6 ↓↓ 8 4 2 7 ↓ 2 2 2 8

विधि

यहां, अवधारणा डायनामिक प्रोग्रामिंग लागू करना है। मैट्रिक्स के प्रत्येक सेल के संबंध में, हम वर्तमान सेल में समाप्त होने वाले स्नेक की सबसे लंबी लंबाई रखते हैं। अब सबसे लंबी लंबाई वाला स्नेक अनुक्रम अधिकतम मान रखेगा। यहां, सबसे लंबा मान वाला सेल स्नेक की पूंछ से मेल खाएगा। स्नेक को प्रिंट करने के लिए, हमें पूंछ से वापस स्नेक के सिर तक बैकट्रैक करने की आवश्यकता है। मान लें T[a][b] सेल (a, b) पर समाप्त होने वाले स्नेक की अधिकतम लंबाई को दर्शाता है, तो दी गई मैट्रिक्स M के लिए, डायनामिक प्रोग्रामिंग संबंध इस प्रकार परिभाषित किया गया है −

T[0][0] = 0 T[a][b] = max(T[a][b], T[a][b – 1] + 1) if M[a][b] = M[a][b – 1] ± 1 T[a][b] = max(T[a][b], T[a – 1][b] + 1) if M[a][b] = M[a – 1][b] ± 1

उदाहरण

// C++ program to find maximum length // Snake sequence and print it #include <bits/stdc++.h> using namespace std; #define M 4 #define N 4 struct Point{    int X, Y; }; // अधिकतम लंबाई स्नेक अनुक्रम पथ खोजने वाला फ़ंक्शन // (a, b) स्नेक की पूंछ से मेल खाता है list<Point> findPath(int grid1[M][N], int mat1[M][N], int a, int b){    list<Point> path1;    Point pt1 = {a, b};    path1.push_front(pt1);    while (grid1[a][b] != 0){       if (a > 0 &&       grid1[a][b] - 1 == grid1[a - 1][b]){          pt1 = {a - 1, b};          path1.push_front(pt1);          a--;       }       else if (b > 0 &&       grid1[a][b] - 1 == grid1[a][b - 1]){          pt1 = {a, b - 1};          path1.push_front(pt1);          b--;       }    }    return path1; } // अधिकतम लंबाई स्नेक अनुक्रम खोजने वाला फ़ंक्शन void findSnakeSequence(int mat1[M][N]){    // उपसमस्याओं के परिणाम संग्रहीत करने के लिए टेबल दिखाता है    int lookup1[M][N];    // 0 से इनिशियलाइज़ करने के लिए उपयोग किया जाता है    memset(lookup1, 0, sizeof lookup1);    // स्नेक अनुक्रम की अधिकतम लंबाई संग्रहीत करने के लिए उपयोग किया जाता है    int max_len1 = 0;    // स्नेक की पूंछ के निर्देशांक संग्रहीत करने के लिए उपयोग किया जाता है    int max_row1 = 0;    int max_col1 = 0;    // बॉटम-अप फैशन में टेबल भरने के लिए उपयोग किया जाता है    for (int a = 0; a < M; a++){       for (int b = 0; b < N; b++){          // (0, 0) सेल को छोड़कर प्रदर्शन करें          if (a || b){             // ऊपर देखें             if (a > 0 &&             abs(mat1[a - 1][b] - mat1[a][b]) == 1){                lookup1[a][b] = max(lookup1[a][b],                lookup1[a - 1][b] + 1);             if (max_len1 < lookup1[a][b]){                max_len1 = lookup1[a][b];                max_row1 = a, max_col1 = b;             }          }          // बाएं देखें          if (b > 0 &&          abs(mat1[a][b - 1] - mat1[a][b]) == 1){             lookup1[a][b] = max(lookup1[a][b],             lookup1[a][b - 1] + 1);             if (max_len1 < lookup1[a][b]){                max_len1 = lookup1[a][b];                max_row1 = a, max_col1 = b;             }          }       }    } } cout << "Maximum length of Snake sequence is: " << max_len1 << endl; // अधिकतम लंबाई स्नेक अनुक्रम पथ निर्धारित करें list<Point> path1 = findPath(lookup1, mat1, max_row1, max_col1); cout << "Snake sequence is:"; for (auto it = path1.begin(); it != path1.end(); it++) cout << endl << mat1[it->X][it->Y] << " ("<< it->X << ", " << it->Y << ")" ;} // ड्राइवर कोड int main(){    int mat1[M][N] ={{10, 7, 6, 3},{9, 8, 7, 6},{8, 4, 2, 7},{2, 2, 2, 8},};    findSnakeSequence(mat1);    return 0; }

आउटपुट

Maximum length of Snake sequence is: 6 Snake sequence is: 10 (0, 0) 9 (1, 0) 8 (1, 1) 7 (1, 2) 6 (1, 3) 7 (2, 3) 8 (3, 3)

  1. C++ में बाइनरी ट्री में अधिकतम स्तर योग खोजें C++ में बाइनरी ट्री में अधिकतम स्तर योग खोजें

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है जिसमें सकारात्मक और नकारात्मक मान हैं। हमारा कार्य बाइनरी ट्री में अधिकतम स्तर योग खोजना है। समस्या विवरण: हमारे पास एक बाइनरी ट्री है, हम बाइनरी ट्री में सभी स्तरों का योग खोजेंगे और फिर उनमें से अधिकतम लौटाएंगे।एक उदाहरण लेकर समस्या को समझते

  1. C++ में बाइनरी ट्री में अधिकतम (या न्यूनतम) मान ढूंढें C++ में बाइनरी ट्री में अधिकतम (या न्यूनतम) मान ढूंढें

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। हमारा कार्य बाइनरी ट्री में अधिकतम (या न्यूनतम) मान ढूंढना है। समस्या विवरण: हमें बाइनरी ट्री के उन नोड्स को ढूंढना है जिनका मान बाइनरी ट्री में अधिकतम और न्यूनतम है। समस्या को समझने के लिए एक उदाहरण लेते हैं, इनपुट: आउटपुट: max = 9 , min = 1 समाधान

  1. C++ में लिंक्ड लिस्ट में लूप की लंबाई ढूंढें C++ में लिंक्ड लिस्ट में लूप की लंबाई ढूंढें

    इस समस्या में, हमें एक लिंक्ड लिस्ट दी गई है जिसमें लूप हो सकते हैं। हमारा कार्य लिंक्ड लिस्ट में लूप की लंबाई ढूंढना है। समस्या विवरण: हमें लूप में नोड्स की संख्या गिननी है यदि इसमें लूप है अन्यथा -1 वापस करें। समस्या को समझने के लिए एक उदाहरण लेते हैं, इनपुट: linked-list : आउटपुट: 8 समाधान दृष्ट