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

C++ प्रोग्राम: दो या अधिक सीक्वेंस को सबसीक्वेंस के रूप में समाहित करने वाला सबसे छोटा सुपरसीक्वेंस


यहां हम एक C++ प्रोग्राम पर चर्चा करेंगे जो दो या अधिक सीक्वेंस को सबसीक्वेंस के रूप में समाहित करने वाला सबसे छोटा सुपरसीक्वेंस खोजता है।

एल्गोरिदम

Begin
    function ShortestSuperSeq() A और B का सुपरसीक्वेंस लौटाता है:
        1) एक ऐरे ss[i][j] घोषित करें जिसमें A[0..i-1] और B[0..j-1] के लिए सबसे छोटे सुपरसीक्वेंस की लंबाई हो।
        2) रिकर्सन का उपयोग करके बॉटम-अप तरीके से संभावित सुपरसीक्वेंस की लंबाई खोजें।
        3) एक ऐरे ss[i][j] घोषित करें जो इंडेक्स में A[0..i-1] और B[0..j-1] के लिए सबसे छोटे सुपरसीक्वेंस की लंबाई स्टोर करता है।
        4) सबसे छोटे सबसीक्वेंस को स्टोर करने के लिए एक स्ट्रिंग s घोषित करें।
        5) i = a, j = b इनिशियलाइज़ करें।
        6) while (i > 0 और j > 0)
            A) यदि A और B में वर्तमान कैरेक्टर समान हैं, तो वर्तमान कैरेक्टर सबसे छोटे सुपरसीक्वेंस का हिस्सा है।
               वर्तमान कैरेक्टर को परिणाम में डालें।
               i, j और इंडेक्स के मान कम करें।
            B) अन्यथा यदि
               यदि A और B में वर्तमान कैरेक्टर अलग हैं,
               B के वर्तमान कैरेक्टर को परिणाम में डालें।
               j और इंडेक्स के मान कम करें।
            C) अन्यथा
               A के वर्तमान कैरेक्टर को परिणाम में डालें।
               i और इंडेक्स के मान कम करें।
        7) While (i > 0)
           A के शेष कैरेक्टर्स को परिणाम स्ट्रिंग में डालें।
        8) While(j > 0)
           B के शेष कैरेक्टर्स को परिणाम स्ट्रिंग में डालें।
        9) स्ट्रिंग को रिवर्स करें और लौटाएं।
End

उदाहरण

#include <bits/stdc++.h>
using namespace std;

string ShortestSuperSeq(string A, string B) {
    int a = A.length();
    int b = B.length();
    int ss[a + 1][b + 1];
    
    for (int i = 0; i <= a; i++) {
        for (int j = 0; j <= b; j++) {
            if(i == 0)
                ss[i][j] = j;
            else if(j == 0)
                ss[i][j] = i;
            else if(A[i - 1] == B[j - 1])
                ss[i][j] = 1 + ss[i - 1][j - 1];
            else
                ss[i][j] = 1 + min(ss[i - 1][j], ss[i][j - 1]);
        }
    }
    
    int index = ss[a][b];
    string s;
    int i = a, j = b;
    
    while (i > 0 && j > 0) {
        // यदि A और B में वर्तमान कैरेक्टर समान हैं, तो वर्तमान कैरेक्टर सबसे छोटे सुपरसीक्वेंस का हिस्सा है
        if (A[i - 1] == B[j - 1]) {
            // वर्तमान कैरेक्टर को परिणाम में डालें
            // i, j और इंडेक्स के मान कम करें
            s.push_back(A[i - 1]);
            i--, j--, index--;
        }
        // यदि A और B में वर्तमान कैरेक्टर अलग हैं
        else if (ss[i - 1][j] > ss[i][j - 1]) {
            // B के वर्तमान कैरेक्टर को परिणाम में डालें
            // j और इंडेक्स के मान कम करें
            s.push_back(B[j - 1]);
            j--, index--;
        }
        // A के वर्तमान कैरेक्टर को परिणाम में डालें
        // i और इंडेक्स के मान कम करें
        else {
            s.push_back(A[i - 1]);
            i--, index--;
        }
    }
    
    // A के शेष कैरेक्टर्स को परिणाम स्ट्रिंग में डालें
    while (i > 0) {
        s.push_back(A[i - 1]);
        i--, index--;
    }
    
    // B के शेष कैरेक्टर्स को परिणाम स्ट्रिंग में डालें
    while (j > 0) {
        s.push_back(B[j - 1]);
        j--, index--;
    }
    
    reverse(s.begin(), s.end()); // स्ट्रिंग को रिवर्स करें और लौटाएं
    return s;
}

int main() {
    string M = "ABBCDDEEFF";
    string N = "ABCDEEEFF";
    cout << "The Shortest SuperSequence is:" << ShortestSuperSeq(M, N);
    return 0;
}

आउटपुट

The Shortest SuperSequence is:ABBCDEDEEFF

शॉर्टेस्ट कॉमन सुपरसीक्वेंस (SCS) समस्या LCS (लॉन्गेस्ट कॉमन सबसीक्वेंस) से संबंधित है। SCS की लंबाई = len(A) + len(B) - len(LCS)। यह डायनामिक प्रोग्रामिंग दृष्टिकोण O(m*n) समय और स्थान में SCS का निर्माण करता है।

  1. C++ में रेखा का मध्य बिंदु खोजने का प्रोग्राम C++ में रेखा का मध्य बिंदु खोजने का प्रोग्राम

    इस समस्या में, हमें दो बिंदु A और B दिए गए हैं, एक रेखा के प्रारंभिक और अंतिम बिंदु। हमारा कार्य C++ में रेखा का मध्य बिंदु खोजने के लिए एक प्रोग्राम बनाना है। समस्या विवरण यहां, हमारे पास प्रारंभिक और अंतिम बिंदु A(x1, y1) और B(x2, y2) वाली एक रेखा है। और हमें रेखा का मध्य बिंदु ज्ञात करना है। उद

  1. C++ में त्रिभुज के केंद्रक (Centroid) ज्ञात करने का प्रोग्राम C++ में त्रिभुज के केंद्रक (Centroid) ज्ञात करने का प्रोग्राम

    इस समस्या में, हमें एक 2D ऐरे दिया गया है जो त्रिभुज के तीन शीर्षों के निर्देशांक को दर्शाता है। हमारा कार्य C++ में त्रिभुज के केंद्रक (Centroid) ज्ञात करने का प्रोग्राम बनाना है।केंद्रक (Centroid) त्रिभुज का वह बिंदु है जहां त्रिभुज की तीनों मध्यिकाएं (medians) प्रतिच्छेद करती हैं।मध्यिका (Median)

  1. C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम

    इस समस्या में, हमें दो मान दिए गए हैं जो समानांतर चतुर्भुज के आधार (base) और ऊंचाई (height) को दर्शाते हैं। हमारा कार्य C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम बनाना है।समानांतर चतुर्भुज (Parallelogram) चार भुजाओं वाली एक बंद आकृति है जिसकी विपरीत भुजाएं समान औ