Divide And Conquer Algorithm
প্রথম অংশটুকু হল "Divide", যা মানে ভাগ করা, বুঝাই যাচ্ছে কোন সমস্যা কে প্রথমে ছোট ছোট সাব প্রোগ্রামে ভাগ করতে হবে যতক্ষণ পর্যন্ত সেগুলো সহজে সমাধান করা যায় । এবার ইন্ডিভিজুয়ালি সবগুলো সাবপ্রব্লেমকে সমাধান করতে হবে।
সব শেষে কাজ হল "Conquer" . মানে সবগুলো পারসিয়াল সমাধান থেকে অরিজিনাল প্রবলেম এর সমাধান বের করা ! ( কত বাংলিশ কয় রে !! )
- এবার আসি কেন আমরা এই প্রসেস ফলো করবো ? উত্তরটা খুবই সহজ, এই প্রসেস ফলো করতেই হবে এম্ন কোন কথা নেই, কিন্তু এই প্রসেস এর প্রধান সুবিধা হচ্ছে বড় বড় সমস্যা গুলোকে ছোট ছোট সাবপ্রব্লেম এ ভাগ করে সহজে রিকারসিভ্লি সমাধান করা যায় । তাহলে মাথায় আসছে রিকারসন কি ? আজ রিকারসন নিয়ে লিখতে ভালো লাগছে না, যাদের কোন ধারণাই নেই, তারা এই পেজে ঘুরে দেখতে পারেন, রিকারসন ।
- মুল সমস্যাটাকে ছোট ছোট সাব প্রবলেম এ ভাগ করে ফেলে ।
- রিকারসিভ্লি সাবপ্রব্লেম গুলোকে সমাধান করে ।
- এই সমাধানগুলোকে কম্বাইন করে মূল সমস্যার ১টি সমাধান বের করে ।
বাইনারী সার্চ
প্রথমে দেখব বাইনারী সার্চ এর সাধারণ সমাধান ।
এই এল্গরিদমটি শুধু সর্টেট ডাটা এর উপর ই এপ্লাই করা যায় ।
ধরি ১টি সর্টেড অ্যারে a[] = {12, 23, 25, 37, 45, 57, 61, 77, 89, 117, 125, 131};
এই এল্গরিদমটি শুধু সর্টেট ডাটা এর উপর ই এপ্লাই করা যায় ।
ধরি ১টি সর্টেড অ্যারে a[] = {12, 23, 25, 37, 45, 57, 61, 77, 89, 117, 125, 131};
12 23 25 37 45 57 61 77 89 117 125 131
এখন আমরা এর সর্বনিম্ন সর্বচ্চ এবং মধ্যম সংখ্যাটিকে নিবো, এ ক্ষেত্রে L ,M, H যথাক্রমে সর্বনিম্ন, মধ্যম এবং সর্বচ্চ সংখ্যার ইনডেক্স ধারণ করবে , এক্ষেত্রে
L =1 A[ L] = 12,
M = (1+12)/2 = 6 A[ M] = 57,
H = 12 A[H] = 131
ধরলাম ইউজার ১২৫ কে খুঁজে বের করতে চায়, সে এখন ১২৫ কে M এর সাথে তুলনা করবে,
১২৫ কি ৫৭ এর চেয়ে বড় না ছোট ,ঊঃ ছোট ।
তাহলে যেহেতু এটি ১টি সর্টেড ডাটা, কাজেই ৫৭ এর আগে কখনই ১২৫ কে পাওয়া যাবে না, তাইলে এখন সর্বনিম্ন ইন্বেডেক্স ৫৭ এর পরের ইনডেক্স , অর্থাৎ L = M+1;
H আগের পজিশন এ থাকবে , আর M এর নতুন অবস্থান হবে (L + H) / 2;
12 23 25 37 45 57 61 77 89 117 125 131
এক্ষেত্রে L = 7, A[L] = 61
H =12, A[H] = 131
M = (7+12) /2 = 9; A[M]=89
এখন আবার ও ১২৫ কে A[M] এর সাথে তুলনা করবো। যেহেতু ১২৫ হচ্ছে ৮৯ এর চেয়ে বড় , এবং এটি ১টি সর্টেড ডাটা, কাজেই ৮৯ এর আগে আর ১২৫ কে পাওয়া যাবে না, তাই এর আগে আর খোজার দরকার নাই, তাই এখন
12 23 25 37 45 57 61 77 89 117 125 131
L = M+1 = 9+1 = 10 A[L] = 117
H = 12 A[H] = 131
M = (L+H)/2 = (10+12)/2 = 11 A[11] = 125
এখন ১২৫ ঠিক A[M] এ পাওয়া গিয়েছে ,
সুতরাং ১২৫ আমাদের এই ডাটা এর মধ্যে পাওয়া গেছে, এবং তা M নাম্বার ইনডেক্স এ আছে ।
এখন যদি এম্ন হত যে আমরা যে ডাটা খুজছি তা মাঝের সংখ্যা এর চেয়ে ছোট, তখন কি করা যেত?
১২ ২৭ ৩৫ ৪২ ৬২ ৬৭ ৭৩
এখন যদি আমরা ২৭ কে খুজি তখন?
আমাদের M এখন ৪২ এর উপরযা ২৭ এর চেয়ে বড়, কাজেই এক্ষেত্রে ৪২ এর পরে কখনই ২৭ কে পাওয়া যাবে না,
তাই H = M-1 = 4-1 = 3 নিতে হবে এবং M বের করতে হবে, এভাবেই পুরো প্রক্রিয়া চলতে থাকবে :)
কোড
#include<iostream>
using namespace std;
int main(){
int val, l=1, h=12, m;
int a[] = {12, 23, 25, 37, 45, 57, 61, 77, 89, 117, 125, 131};
bool ans = false;
m = (l+h)/2;
cout<<"\nEnter the Number u wanna search :";
cin>>val;
while(l<=h){
m = (l+h)/2;
if(a[m] == val){
ans = true;
break;
}
else if(val>a[m])
l = m+1;
else if(val<a[m])
h = m-1;
}
if(ans == true)
cout<<val<<" found in "<<m+1<<" position";
else
cout<<"Not Found ";
return 0;
return 0;
}
0 comments:
Post a Comment