किसी दिए गए पूर्णांक m और पदों की एक सरणी 'स्थिति []' (1 <=लंबाई (स्थिति []) <=2m) के मामले में, उचित ब्रैकेट अभिव्यक्तियों के तरीकों की संख्या पाएं जिन्हें लंबाई 2m का निर्माण किया जा सकता है जैसे कि दी गई पोजीशन में ओपनिंग ब्रैकेट होता है।
नोट:स्थिति [] सरणी (1-आधारित अनुक्रमण) [0, 1, 1, 0] के रूप में प्रदान की जाती है। यहां 1 उन स्थितियों को इंगित करता है जिन पर ओपन ब्रैकेट सेट किया जाना चाहिए। मान 0 के मामले में, या तो उद्घाटन या समापन ब्रैकेट सेट किया जा सकता है।
उदाहरण
Input: n = 2, position[] = [1, 0, 1, 0] Output: 1 The only possibility is given below: [ ] [ ] In this case, recursive and recursion implementing memorization approach will be explained.
एल्गोरिदम
हमें दिए गए सरणी adj1(मानना) में खुले कोष्ठकों के साथ सभी पदों को 1 के रूप में चिह्नित करना है।
हम इस तरह से एक पुनरावर्ती लूप चलाते हैं -
-
यदि कुल कोष्ठकों की संख्या (खोलने वाले कोष्ठकों को बंद करने वाले कोष्ठकों से घटाकर) शून्य से कम है, तो 0 लौटाएँ।
-
यदि सूचकांक m तक पहुँचता है और यदि कुल कोष्ठक 0 के बराबर है, तो एक समाधान उपलब्ध है और 1 लौटाएँ अन्यथा 0 लौटाएँ।
-
यदि अनुक्रमणिका मान में 1 पूर्व-असाइन किया गया है, तो हमें फ़ंक्शन को अनुक्रमणिका+1 के साथ पुनरावर्ती रूप से वापस करना होगा और कुल कोष्ठकों को बढ़ाना होगा।
-
अन्यथा हमें उस स्थिति या अनुक्रमणिका पर खुले कोष्ठकों को सम्मिलित करके और उस अनुक्रमणिका में कुल कोष्ठकों को 1 + बढ़ाकर कुल कोष्ठकों को बढ़ाकर और कुल कोष्ठकों को 1 से घटाकर और m तक अगले सूचकांक पर आगे बढ़ते हुए पुनरावर्ती रूप से वापस करना होगा।
उपरोक्त एल्गोरिथम के मामले में पुनरावर्ती समाधान निम्नलिखित है -
उदाहरण
// C++ application of above method implementing Recursion
#include <bits/stdc++.h>
using namespace std;
// Function to locate or find Number of proper bracket expressions
int find(int index1, int openbrk1, int m, int adj1[]){
// If open-closed brackets less than 0
if (openbrk1 < 0)
return 0;
// If index reaches the end of expression
if (index1 == m) {
// If brackets are balanced
if (openbrk1 == 0)
return 1;
else
return 0;
}
// If the current index has assigned open bracket
if (adj1[index1] == 1) {
// We have to move forward increasing the
// length of open brackets
return find(index1 + 1, openbrk1 + 1, m, adj1);
}
else {
// We have to move forward by inserting open as well
// as closed brackets on that index
return find(index1 + 1, openbrk1 + 1, m, adj1)
+ find(index1 + 1, openbrk1 - 1, m, adj1);
}
}
// Driver Code
int main(){
int m = 2;
// Open brackets at position 1
int adj1[4] = { 1, 0, 0, 0 };
// Calling the find function to calculate the answer
cout << find(0, 0, 2 * m, adj1) << endl;
return 0;
} आउटपुट
2
याद रखा दृष्टिकोण - मेमोराइजेशन को लागू करके उपरोक्त एल्गोरिदम की समय जटिलता को बेहतर या अनुकूलित किया जा सकता है।
केवल एक ही काम किया जाना है, पिछले पुनरावृत्तियों के परिणामों को संग्रहीत करने के लिए एक सरणी को लागू करना ताकि मान की गणना पहले से ही एक ही फ़ंक्शन को एक से अधिक बार कॉल करने की आवश्यकता न हो।
निम्नलिखित आवश्यक कार्यान्वयन है
// C++ application of above method implementing memorization
#include <bits/stdc++.h>
using namespace std;
#define M 1000
// Function to locate or find Number of proper bracket expressions
int find(int index1, int openbrk1, int m,
int dp1[M][M], int adj1[]){
// If open-closed brackets is less than 0
if (openbrk1 < 0)
return 0;
// If index attains or reaches the end of expression
if (index1 == m) {
// If brackets are balanced
if (openbrk1 == 0)
return 1;
else
return 0;
}
// If already stored in dp1
if (dp1[index1][openbrk1] != -1)
return dp1[index1][openbrk1];
// If the current index has assigned open bracket
if (adj1[index1] == 1) {
// We have to move forward increasing the length of open brackets
dp1[index1][openbrk1] = find(index1 + 1,
openbrk1 + 1, m, dp1, adj1);
}
else {
// We have to move forward by inserting open as
// well as closed brackets on that index
dp1[index1][openbrk1] = find(index1 + 1, openbrk1 + 1, m, dp1, adj1) + find(index1 + 1, openbrk1 - 1, m, dp1, adj1);
}
// We have to return the answer
return dp1[index1][openbrk1];
}
// Driver Code
int main(){
// dp1 array to precalculate the answer
int dp1[M][M];
int m = 2;
memset(dp1, -1, sizeof(dp1));
// Open brackets at position 1
int adj1[4] = { 1, 0, 0, 0 };
// We have to call the find function to compute the answer
cout<< find(0, 0, 2 * m, dp1, adj1) << endl;
return 0;
}
आउटपुट
2
समय जटिलता:O(N2)