طراحی الگوریتم در این روش بدین صورت حاصل میشود که:
مورد اصلی مسئلهی داده شده برای حل را به چندین مورد کوچکتر (از همان نوع مورد اصلی) تقسیم میکنیم٬ سپس موارد کوچکتر را بطور مجزا حل و نتیجه حاصل از هر زیر مورد را با هم ترکیب کرده تا نتیجه مورد اصلی مسئله را بیابیم.
اگر تاکنون از روتینهای بازگشتی (Recursive Procedures) برای حل مسائل استفاده کرده باشید با روش کار تقسیم و تسخیر از پیش آشنایی دارید.
الگوریتمهایی که با این روش طراحی میشوند از دید من بسیار زیبا٬ ساده و خوانا هستند. اما این نکته منفی را هم نباید از قلم انداخت که اگر تعداد موارد منقسم شده از مورد اصلی زیاد باشد٬ ممکن است بازده الگوریتم حاصل از روش تقسیم و تسخیر افت کند.
مثال 1: جستجوی دودویی (Binary Search)
در نظر بگیرید که فهرستی از اسامی و آدرسهای مرتبط به هر اسم داشته باشیم و این فهرست دارای N جفت اسم و آدرس باشد که به ترتیب حروف الفبا بر اساس اسم مرتب شده و در دو آرایه نگهداری شوند:
کد:
میخواهیم با دادن هر اسم٬ آدرس مربوط به اسم را بیابیم. در این مثال فرض میکنیم که هر اسم مورد پرسش حتما در آرایه وجود دارد تا الگوریتم و شرح آن را سادهتر کرده باشیم.کد:Names(1..N) Numbers(1..N)
الگوریتم تقسیم و تسخیری که این مسئله را حل میکند٬ سادهترین الگوریتم در این مدل الگوریتمی است که حاصل نگرشی بگونه زیر است:
اسم داده شده
یا
درست در وسط فهرست قرار دارد
یا
در نیمه بالایی فهرست (بالا)
یا
در نیمه پایینی فهرست (پایین)
چون فهرست مرتب شده است٬ پس شرط بالا در صورتی درست است که اسم داده شده کوچکتر از اسم قرارگرفته در قسمت میانی باشد. و شرط پایین در صورتی درست است که اسم داده شده بزرگتر از اسم قرارگرفته در قسمت میانی باشد.
این دید به مسئله٬ الگوریتم زیر را در پی خواهد داشت:
کد:
الگوریتم بالا رو چگونه باید اصلاح کرد تا جوابگوی حالتی باشد که اسم وارد شده در فهرست موجود نیست؟ یا با عبارت متداول برای الگوریتمهای تقسیم و تسخیر، در چه مرحلهای این اصلاح صورت گرفته شود؟کد:function Search(X: name; Start, Finish: integer) return address Middle: integer begin Middle <- (Start + Finish) / 2 if X = Names(Middle) then return Numbers(Middle) elseif X < Names(Middle) then return Search(X, Start, Middle - 1) else -- X > Names(Middle) return Search(X, Middle + 1, Finish) endif end





پاسخ با نقل قول
