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

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

अवधारणा

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

दरअसल, एक सांप अनुक्रम ग्रिड में आसन्न संख्याओं से बना होता है ताकि प्रत्येक संख्या के लिए, दाईं ओर की संख्या या उसके नीचे की संख्या या तो +1 या -1 उसका मान हो। यहां, उदाहरण के लिए, यदि हम ग्रिड में स्थान (ए, बी) रखते हैं, तो हम या तो दाईं ओर जा सकते हैं यानी (ए, बी + 1) यदि वह संख्या ± 1 है या मूवडाउन यानी (ए + 1, बी) यदि वह संख्या है ± 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[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;
};
// Shows function to find maximum length Snake sequence path
// (a, b) corresponds to tail of the snake
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;
}
// Shows function to find maximum length Snake sequence
void findSnakeSequence(int mat1[M][N]){
   // Shows table to store results of subproblems
   int lookup1[M][N];
   // Used to initialize by 0
   memset(lookup1, 0, sizeof lookup1);
   // Used to store maximum length of Snake sequence
   int max_len1 = 0;
   // Used to store cordinates to snake's tail
   int max_row1 = 0;
   int max_col1 = 0;
   // Used to fill the table in bottom-up fashion
   for (int a = 0; a < M; a++){
      for (int b = 0; b < N; b++){
         // Perform except for (0, 0) cell
         if (a || b){
            // look above
            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;
            }
         }
         // look left
         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;
// Determine maximum length Snake sequence path
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 << ")" ;}
// Driver code
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++ में बाइनरी ट्री में अधिकतम स्तर का योग खोजें

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

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

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

  1. सी ++ में लिंक्ड सूची में लूप की लंबाई पाएं

    इस समस्या में, हमें एक लिंक की गई सूची दी जाती है जिसमें लूप हो सकते हैं। हमारा कार्य लिंक्ड सूची में लूप की लंबाई ज्ञात करना है। समस्या का विवरण: हमें लूप में नोड्स की संख्या गिनने की आवश्यकता है यदि इसमें लूप है अन्यथा -1 लौटाएं। समस्या को समझने के लिए एक उदाहरण लेते हैं, इनपुट: लिंक्ड-लिस्