شنبه 27 آبان 1396 | Saturday 18 th of November 2017 صفحه اصلی گروه الکترونیکی کامپیوتر
– روش تقسیم و حل

 فرض کنید aiبازای 1لیستی از عناصر باشد که به صورت صعودی مرتب شده اند . مسئله تعیین وجود یا عدم وجود عنصر مشخص  xدر لیست می باشد. اگر عنصر  xدر لیست موجود باشد اندیس عنصر در لیست به عنوان خروجی باشد.  به طوری که  aj = xباشد در غیر اینصورت مقدار 1- را به عنوان خروجی ارسال می کند.

روش تقسیم و حل را برای حل این مسئله به کار می گیریم ، اگر لیست  a بیشتر از یک عنصر داشته باشد در این صورت مراحل زیر در الگوریتم طی می شود.

اگر xبرابر عنصر میانی بود تمام ،  در غیر اینصورت :

1)     لیست  a  به دو زیر لیست تقسیم می شود (تقریبا با طول برابر )

اگر xکوچکتر از میانی باشد زیر لیست چپ انتخاب می شود در غیر اینصورت زیر لسیت راست

2)     عنصر xرا در لیست جدید در صورتی که لیست به اندازه کافی کوچک باشد جستجو می کند. در غیر اینصورت عمل تقسیم لیست به دو لیست کوچکتر دوباره ادامه می یابد.

با حل زیر مسئله ها ، مسئله اصلی حل می شود. الگوریتم (2- 4) الگوریتم جستجوی دودویی با روش تقسیم و حل را نمایش می دهد

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26