ভারসাম্যপূর্ণ অভিব্যক্তি যেমন প্রদত্ত অবস্থানের C++ এ খোলা বন্ধনী আছে?

একটি প্রদত্ত পূর্ণসংখ্যা m এবং অবস্থানের একটি বিন্যাসের ক্ষেত্রে 'position[]' (1 <=length(position[]) <=2m), সঠিক বন্ধনী এক্সপ্রেশনের উপায়গুলির সংখ্যা খুঁজে বের করুন যা 2m দৈর্ঘ্যে তৈরি করা যেতে পারে প্রদত্ত অবস্থানে খোলার বন্ধনী রয়েছে৷

দ্রষ্টব্য:অবস্থান[] অ্যারে (1-ভিত্তিক ইন্ডেক্সিং) [0, 1, 1, 0] আকারে প্রদান করা হয়েছে। এখানে 1 সেই অবস্থানগুলি নির্দেশ করে যেখানে খোলা বন্ধনী সেট করা উচিত। মান 0 এর ক্ষেত্রে অবস্থানে, হয় খোলা বা বন্ধ বন্ধনী সেট করা যেতে পারে।

উদাহরণ

ইনপুট:n =2, পজিশন[] =[1, 0, 1, 0]আউটপুট:1 একমাত্র সম্ভাবনা নীচে দেওয়া হল:[ ] [ ]এই ক্ষেত্রে, পুনরাবৃত্ত এবং পুনরাবৃত্ত প্রয়োগকারী মুখস্থ পদ্ধতি ব্যাখ্যা করা হবে৷ 
অ্যালগরিদম
 

 আমাদের প্রদত্ত অ্যারে adj1(বলুন) 1 হিসাবে খোলা বন্ধনী দিয়ে সমস্ত অবস্থান চিহ্নিত করতে হবে।
 

 আমরা একটি রিকার্সিভ লুপ চালাই, এইভাবে −
 
 
 

 যদি মোট বন্ধনীর গণনা (বন্ধনী বন্ধনী থেকে খোলার বন্ধনী বিয়োগ করা হয়) শূন্যের চেয়ে ছোট হয়, তাহলে 0 ফেরত দিন।
 
 
 

 যদি সূচকটি m পর্যন্ত পৌঁছায় এবং যদি মোট বন্ধনী 0 এর সমান হয়, তাহলে একটি সমাধান পাওয়া যাবে এবং 1 ফেরত দিন, অন্যথায় 0 ফেরত দিন।
 
 
 

 যদি সূচকের মানটিতে 1টি আগে থেকে নির্ধারিত থাকে, তাহলে আমাদেরকে সূচী +1 দিয়ে পুনরাবৃত্তভাবে ফাংশনটি ফেরত দিতে হবে এবং মোট বন্ধনী বাড়াতে হবে।
 
 
 

 অন্যথায় আমাদের সেই অবস্থানে বা সূচীতে খোলা বন্ধনী সন্নিবেশিত করে এবং সেই সূচকে বন্ধ বন্ধনীগুলি 1 দ্বারা + মোট বন্ধনীকে 1 দ্বারা বৃদ্ধি করে এবং মোট বন্ধনীগুলি 1 দ্বারা হ্রাস করে এবং m পর্যন্ত পরবর্তী সূচীতে যেতে হবে৷
 
 
 

 উপরের অ্যালগরিদমের ক্ষেত্রে রিকার্সিভ সমাধান নিচে দেওয়া হল −
 
উদাহরণ
 
// উপরোক্ত পদ্ধতির C++ প্রয়োগ Recursion#include Namespace ব্যবহার করে std;// সঠিক বন্ধনী এক্সপ্রেশনের সংখ্যা খুঁজে বের করতে বা খুঁজে বের করতে ফাংশন (int index1, int openbrk1, int m, int adj1 []){ // খোলা-বন্ধ বন্ধনী 0-এর কম হলে (openbrk1 <0) 0 প্রদান করে; // যদি ইনডেক্স এক্সপ্রেশনের শেষে পৌঁছায় if (index1 ==m) { // যদি বন্ধনী ভারসাম্যপূর্ণ হয় যদি (openbrk1 ==0) রিটার্ন 1; অন্যথায় রিটার্ন 0; } // যদি বর্তমান সূচকটি ওপেন ব্র্যাকেট বরাদ্দ করে থাকে if (adj1[index1] ==1) { // আমাদেরকে খোলা বন্ধনীর // দৈর্ঘ্য বাড়াতে হবে রিটার্ন ফাইন্ড (index1 + 1, openbrk1 + 1, m, adj1); } else { // আমাদেরকে ওপেন ঢোকানোর মাধ্যমে এগিয়ে যেতে হবে // সেই সূচকে বন্ধ বন্ধনী হিসাবে রিটার্ন খুঁজুন (index1 + 1, openbrk1 + 1, m, adj1) + find(index1 + 1, openbrk1 - 1, m , adj1); }}// ড্রাইভার কোডইন্ট মেইন(){ int m =2; // 1 int adj1 [4] ={ 1, 0, 0, 0} অবস্থানে বন্ধনী খুলুন; // উত্তর গণনা করার জন্য find ফাংশন কল করা হচ্ছে cout < 
আউটপুট
 
2
 

 মুখস্থ পদ্ধতি - উপরের অ্যালগরিদমের সময় জটিলতা মেমোরাইজেশন প্রয়োগ করে উন্নত বা অপ্টিমাইজ করা যেতে পারে।
 

 সম্পাদিত একমাত্র জিনিস হল পূর্ববর্তী পুনরাবৃত্তির ফলাফলগুলি সংরক্ষণ করার জন্য একটি অ্যারে প্রয়োগ করা যাতে মানটি ইতিমধ্যে গণনা করা থাকলে একই ফাংশনটিকে একাধিকবার বারবার কল করার প্রয়োজন না হয়৷
 
নিম্নলিখিত প্রয়োজনীয় বাস্তবায়ন
 
// উপরোক্ত পদ্ধতির C++ প্রয়োগ মেমোরাইজেশন#ইনক্লুড নেমস্পেস ব্যবহার করে std;#define M 1000// সঠিক বন্ধনী এক্সপ্রেশনের সংখ্যা খুঁজে বের করতে বা খুঁজে বের করার জন্য m,int dp1[M][M], int adj1[]){ // যদি খোলা-বন্ধ বন্ধনী 0-এর কম হয় যদি (openbrk1 <0) 0 ফেরত দেয়; // যদি ইনডেক্স এক্সপ্রেশনের শেষ পর্যন্ত পৌঁছায় বা পৌঁছায় যদি (index1 ==m) { // যদি বন্ধনী ভারসাম্যপূর্ণ হয় যদি (openbrk1 ==0) রিটার্ন 1; অন্যথায় রিটার্ন 0; } // যদি ইতিমধ্যে dp1 তে সংরক্ষিত থাকে if (dp1[index1][openbrk1] !=-1) রিটার্ন dp1[index1][openbrk1]; // যদি বর্তমান সূচকটি খোলা বন্ধনী নির্ধারণ করে থাকে if (adj1[index1] ==1) { // আমাদের খোলা বন্ধনীগুলির দৈর্ঘ্য বাড়িয়ে এগিয়ে যেতে হবে dp1[index1][openbrk1] =find(index1 + 1, openbrk1 + 1, m, dp1, adj1); } else { // সেই ইন্ডেক্সে dp1[index1][openbrk1] =find(index1 + 1, openbrk1 + 1, m, dp1, adj1) + find( index1 + 1, openbrk1 - 1, m, dp1, adj1); } // উত্তরটি dp1[index1][openbrk1];}// Driver Codeint main(){ // dp1 অ্যারে উত্তর int dp1[M][M] পূর্ব গণনা করতে আমাদের উত্তরটি ফেরত দিতে হবে; int m =2; memset(dp1, -1, sizeof(dp1)); // 1 int adj1 [4] অবস্থানে বন্ধনী খুলুন ={ 1, 0, 0, 0 }; // উত্তর গণনা করার জন্য আমাদের ফাইন্ড ফাংশনকে কল করতে হবে cout< 
আউটপুট
 
2
 

 সময়ের জটিলতা:O(N2)