صفحه محصول - دانلود پاورپوینت با عنوان تقسیم و حل

لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (..pptx) ( قابل ویرایش و آماده پرینت )
تعداد صفحه : 54 صفحه

قسمتی از متن PowerPoint (..pptx) :

تقسیم و حل Divide and Conquer 1 یکی از روش های حل مسئله ، تقسیم و حل است . اساس این روش به صورت حل بالا به پایین ( Top down ) است .در این روش مسئله ای با سایز بزرگ را آن قدر کوچک می کنیم که حل آن مقدور یا بدیهی شود . سپس از ترکیب زیر مسائل حل شده به حل مسئله اصلی می رسیم. استفاده از این روش در طراحی الگوریتم ممکن است به یکی از دلایل زیر باشد : حل مسئله با روش دیگری امکان پذیر نباشد الگوریتم آن نسبت به روش های دیگر کارا تر باشد. اما قبل از اعمال این روش باید به چند سوال پاسخ دهیم: مسئله اصلی را به چند زیر مسئله تقسیم کنیم ؟ هر زیر مسئله چه سایزی داشته باشد؟ ( زیر مسائل هم اندازه باشند یا خیر؟ ) نوع شکستن (از بالا به پایین مسئله شکسته شود یا از پایین به بالا زیر مسائل کوچکتر ترکیب شوند.) 2 الگوریتم کلی تقسیم و حل : الگوریتم DandC در آغاز به صورت DandC (P) فراخوانی می شود . که در آن P مسئله اصلی است که می بایست حل شود . Small(P) بررسی می کند که مسئله به اندازه کافی کوچک است که بتوان آنرا مستقیماً حل کرد یا خیر . اگر نتیجه کار مثبت باشد زیر مسئله P محاسبه می شود .) مثلاً توسط تابعی به نام S(P) ) . در غیر این صورت مسئله P به زیز مسئله های کوچکتر تقسیم می شود . حاصل اینکار تولید زیر مسئله های , P2 , P1 ... , Pk می باشد که حاصل بازگشت های پی در پی می باشد . در نهایت تابع Combine برای ترکیب راه حل های زیر مسئله برای محاسبه راه حل مسئله اصلی به کار می رود . 3 Result DandC ( P ) { if ( Small ( P ) ) return S( P ) ; else{ Divide P into Smaller instances P1 , ... , Pk for K ≥ 1 ; /* Apply dandC to each of these Subproblems */ return Combine(DandC(P1) , DandC(P2),…, DandC(Pk)) ; } } 4 جست و جوی دودویی هدف این مسئله جست و جوی کلید در یک آرایه مرتب است . در حل این مسئله از روش تقسیم و حل استفاده می شود به صورتی که ابتدا یک آرایه n عنصری رابه دو قسمت مساوی تقسیم کرده و کلیدرابا عنصر وسط آرایه مقایسه می کنیم اگر مساوی بود که مسئله حل شده است در غیر این صورت با توجه به کوچک تر یا بزرگ تر بودن کلید این روند را در یکی از نیم آرایه های چپ یا راست ادامه می دهیم. الگوریتم جست و جوی دودویی به روش بازگشتی را در ادامه پس از مثال مشاهده می کنید . 5