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

C++ संतुलित अभिव्यक्ति: दिए गए स्थानों पर प्रारंभिक कोष्ठक

कोष्ठक का एक संतुलित अभिव्यक्ति एक ऐसा अभिव्यक्ति है जिसमें सभी प्रकार के कोष्ठक सही क्रम में एक साथ होते हैं। इसका अर्थ है कि प्रत्येक प्रारंभिक कोष्ठक के लिए एक समापन कोष्ठक होता है जो कोष्ठक के उचित क्रम में होता है यानी { }।

अभिव्यक्ति - {([][]{})({}[]{})}

आउटपुट - संतुलित

अब, इस समस्या में हमें दी गई कोष्ठक की संख्या से सभी संभावित संतुलित अभिव्यक्ति बनानी हैं। और शर्त यह है कि दिए गए स्थान पर प्रारंभिक कोष्ठक होंगे।

इस समस्या में, हमें एक पूर्णांक n और लंबाई 2n के कोष्ठक की स्थिति की एक सरणी दी गई है और हमें लंबाई 2n की संतुलित अभिव्यक्ति की संख्या ज्ञात करनी है जैसे कि प्रारंभिक कोष्ठक द्वारा चिह्नित स्थानों पर प्रारंभिक कोष्ठक '{' होगा।

उदाहरण -

Input: n = 2, position [1, 0, 0, 0]
Output: 2
Explanation: सभी संभावित परिणाम हैं: {{}} , {}{}.

एल्गोरिदम

  • एक वाले सभी स्थान प्रारंभिक कोष्ठक हैं।

  • निम्नलिखित नियमों का उपयोग करके एक पुनरावर्ती लूप का उपयोग करें:

    • यदि (प्रारंभिक कोष्ठक की संख्या - समापन कोष्ठक की संख्या) > 0, तो 0 लौटाएं।

    • n तक लूप करने के बाद यदि पुश और पॉप के बाद कुल कोष्ठक 0 है, तो 1 लौटाएं यानी समाधान प्राप्त हुआ। अन्यथा 0 लौटाएं।

    • यदि 1 अभिव्यक्ति के लिए पूर्व-निर्दिष्ट है, तो इंडेक्स बढ़ाकर और कुल कोष्ठक की संख्या बढ़ाकर पुनरावर्ती कॉल करें।

    • अन्यथा इंडेक्स स्थान पर प्रारंभिक कोष्ठक डालकर और फिर उसके लिए समापन कोष्ठक डालकर फंक्शन को पुनरावर्ती रूप से कॉल करें और कुल कोष्ठक की संख्या घटाएं और अगले इंडेक्स पर जाएं।

प्रोग्राम

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

int find(int index, int openbrk, int n, int expression[]) {
    if (openbrk < 0)
        return 0;
    if (index == n) {
        if (openbrk == 0)
            return 1;
        else
            return 0;
    }
    if (expression[index] == 1) {
        return find(index + 1, openbrk + 1, n, expression);
    } else {
        return find(index + 1, openbrk + 1, n, expression) + find(index + 1, openbrk - 1, n, expression);
    }
}

int main() {
    int n = 3;
    int expression[6] = { 1, 0, 1, 0, 0, 0 };
    cout << find(0, 0, 2 * n, expression) << endl;
    return 0;
}

आउटपुट

3
  1. - C++ में सरणी में उन सभी जोड़े (a, b) को खोजें जैसे कि a % b = k

    मान लीजिए हमारे पास एक सरणी A है, उस सरणी से हमें सभी जोड़े (a, b) प्राप्त करने हैं जैसे कि a%b = k। मान लीजिए सरणी A = [2, 3, 4, 5, 7], और k = 3, तो जोड़े हैं (7, 4), (3, 4), (3, 5), (3, 7)। इसे हल करने के लिए, हम सूची को पार करेंगे और जांचेंगे कि दी गई शर्त पूरी हो रही है या नहीं। उदाहरण #include

  1. - C++ में दी गई संख्या n के लिए x ढूंढें जहां x + अंकों का योग = n

    समस्या विवरण एक संख्या n दी गई है, हमें एक मान x ढूंढना है जिससे x + x के अंकों का योग = n हो। उदाहरण के लिए, n = 21 के लिए, x = 15 होगा क्योंकि 15 + (1+5) = 21। हल दृष्टिकोण सरल दृष्टिकोण: 1 से n तक पुनरावृति करें, प्रत्येक संख्या के लिए जांचें कि क्या संख्या + उसके अंकों का योग = n है। यदि हां,

  1. - C++ में दी गई रेंज में विशिष्ट जोड़ी (x, y) ढूंढें जहां x, y को विभाजित करता है

    समस्या विवरण एक रेंज [l, r] दी गई है, हमें एक जोड़ी (x, y) ढूंढनी है जहां l ≤ x, y ≤ r और x, y को विभाजित करता है। यदि कई जोड़ियां हैं तो कोई भी एक वापस करें। हल दृष्टिकोण यह समस्या O(1) समय में हल हो सकती है। सबसे छोटा अनुपात y/x = 2 होता है। इसलिए x = l और y = 2l लेने से हमेशा एक वैध जोड़ी मिलती