پاورپوینت تقسیم و حل

پاورپوینت تقسیم و حل (pptx) 54 اسلاید

دسته بندی : پاورپوینت

نوع فایل : 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 هدف : یافتن عدد 18 6 عنصر میانی عنصر میانی find عنصر میانی int Binsrch ) int A[ ] , int low , int high , int X ( { int mid ; if ) low > high ( return -1; else { mid = ) low + high (/ 2; if ) X = = A[mid] ( return mid; else if ) X < A[mid] ( return Binsrch ) A , low , mid -1 , X (; else return Binsrch ) A , mid+1 , high , X (; } } 7 بررسی مرتبه زمانی الگوریتم جست و جوی دودویی در این مسئله ،یک آرایه n عنصری را با انجام یک مقایسه به دو زیر مسئله دیگر تقسیم می کنیم اما فقط یکی از این زیر مسائل را حل می کنیم بنابراین داریم T) n ( = T ) n /2 ( +1 O ) logn ( 8 مسئله 1 اگر در مسئله جست وجوی کلید ، آرایه را به k قسمت تقسیم کنیم مقدار k را برای بهینه شدن مرتبه زمانی به دست آورید؟ 9