ম্যাট্রিক্স সম্প্রসারণের উপর ভিত্তি করে একটি সমস্যা আলোচনা করুন। প্রসারিত ম্যাট্রিক্স হল একটি ম্যাট্রিক্স যার আকার ক্রমাগত কিছু ফ্যাক্টর দ্বারা বৃদ্ধি পায়।
এখানে আমাদের কাছে অক্ষরের একটি ম্যাট্রিক্স রয়েছে যার আকার 2 এর একটি ফ্যাক্টর দ্বারা প্রসারিত হচ্ছে, অর্থাৎ, যদি ম্যাট্রিক্সের আসল আকার N * N হয়, তাহলে প্রসারিত ম্যাট্রিক্সের আকার 2N * 2N হয়ে যায়। আমাদের ( i, j ) তে উপস্থিত অক্ষরগুলির একটি ক্রম দেওয়া হয়েছে এবং আমাদের (i, (j - N - 1)%N এ উপস্থিত অক্ষরগুলির ক্রম ফেরত দিতে হবে৷
আসুন কিছু প্রারম্ভিক প্রসারিত ম্যাট্রিক্স কল্পনা করে বুঝতে পারি,
Given Matrix -> [ a, b ] [ c, d ], 2 X 2 matrix
Multiplying with { a, b, c, d }
A X [ a, b ]
B X [ a, b ]
C X [ a, b ]
D X [ a, b ]
[ c, d ] [ c, d ] [ c, d ] [ c, d ]
Expanded Matrix -> [ aa, ab, ba, bb ]
[ ac, ad, bc, bd ]
[ ca, cb, da, db ]
[ cc, cd, dc, dd ], 4X4 matrix
To expand again, multiply it by { a, b, c, d } and a matrix of size 8X8 will be formed.
Expanded Matrix - > [ aaa, aab, aba, abb, baa, bab, bba, bbb ]
[ aac, aad, abc, abd, bac, bad, bbc, bbd ]
[ aca, acb, ada, adb, bca, bcb, bda, bdb ]
[ acc, acd, adc, add, bcc, bcd, bdc, bdd ]
[ caa, cab, cba, cbb, daa, dab, dba, dbb ]
[ cac, cad, cbc, cbd, dac, dad, dbc, dbd ]
[ cca, ccb, cda, cdb, dca, dcb, dda, ddb ]
[ ccc, ccd, cdc, cdd, dcc, dcd, ddc, ddd ] এখানে দুটি প্রাথমিক সম্প্রসারিত ম্যাট্রিক্স রয়েছে; তাই ধরা যাক আমাদেরকে "bcc" অক্ষরগুলির একটি ক্রম দেওয়া হয়েছে, তারপরে আমাদের কেবল এটিতে বাকি ক্রমটি ফিরিয়ে দিতে হবে, যেমন, "যোগ করুন।" এছাড়াও, ম্যাট্রিক্সটিকে বৃত্তাকার হিসাবে ধরে নেওয়া হয়, যেমন, যদি প্রদত্ত ক্রমটি (i, 0) হয়, তাহলে উদাহরণস্বরূপ ক্রমটি (i, N-1) এ ফেরত দিন
Input: abb Output: aba Explanation: The sequence just left to abb is aba in the 8X8 matrix. Input: aadc Output: aacd Input: abbcd Output: abbcc
সমাধান খোঁজার পদ্ধতি
প্রথমে সমস্যাটির দিকে তাকানো এবং একমাত্র সমাধান যা মনে আসে তা হল প্রসারিত ম্যাট্রিক্স খুঁজে বের করা যা প্রদত্ত ক্রম ধারণ করে কিন্তু খুব জটিল দেখায় না। আমাদের প্রথমে ম্যাট্রিক্স গঠন করতে হবে এবং তারপর ক্রম অনুসন্ধান করতে হবে।
দক্ষ পদ্ধতি
কিছু প্রাথমিকভাবে প্রসারিত ম্যাট্রিক্স দেখার পর, আমরা একটি প্যাটার্ন পেয়েছি যার মাধ্যমে আমরা পূর্ববর্তী উপাদান দেখতে পারি। অর্থাৎ
-
শেষ সূচী থেকে অক্ষরের ক্রমটি অতিক্রম করুন।
-
যদি সূচীকৃত উপাদানটি 'b' বা 'd' হয়, তাহলে এটিকে 'a' বা 'c' এ পরিবর্তন করুন এবং অ্যারেটি অতিক্রম করা বন্ধ করুন।
-
যদি সূচীকৃত উপাদান 'a' বা 'c' হয়, তাহলে এটিকে 'b' বা 'd' এ পরিবর্তন করুন এবং পরবর্তী সূচীতে যান এবং এটি পরীক্ষা করুন।
উদাহরণ
উপরের পদ্ধতির জন্য C++ কোড
#include <bits/stdc++.h>
using namespace std;
int main (){
string seq = "abbcd";
int n = seq.length ();
// traverse through the string from last.
for (int i = n; i >= 0; i--){
// if the element is b or d, change them and stop traversing.
if (seq[i] == 'b'){
seq[i] = 'a';
break;
}
if (seq[i] == 'd'){
seq[i] = 'c';
break;
}
// if an element is b or d, change them and move to the next element.
if (seq[i] == 'a')
seq[i] = 'b';
else if (seq[i] == 'c')
seq[i] = 'd';
}
cout << "The Previous sequence is: " << seq;
return 0;
} আউটপুট
The previous sequence is: abbcc
উপসংহার
এই নিবন্ধে, আমরা বিস্তৃত অক্ষর ম্যাট্রিক্স এবং এটি কীভাবে গঠিত হয়েছিল তা নিয়ে আলোচনা করেছি। আমরা একটি প্রসারিত ম্যাট্রিক্সে পূর্ববর্তী উপাদান খুঁজে পাওয়ার সমস্যা নিয়েও আলোচনা করেছি। অক্ষরের ম্যাট্রিক্স প্রসারিত করে তৈরি প্যাটার্ন বোঝার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি।
আমরা এই সমস্যার জন্য C++ কোড নিয়েও আলোচনা করেছি যা আমরা C, Java, Python, ইত্যাদির মতো যেকোনো প্রোগ্রামিং ভাষায় লিখতে পারি। আমরা আশা করি এই টিউটোরিয়ালটি আপনার কাজে লাগবে।
