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

پاورپوینت رهيافت تقسيم و حل (pptx) 44 اسلاید

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

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 44 اسلاید

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

فصل دومرهيافت تقسيم و حل رهيافت بالا به پايين(Top – Down) استراتژي بكار رفته توسط ناپلئون نمونه اي از يك مساله را به صورت بازگشتي به تعدادي نمونه كوچكتر تقسيم كن تا زماني كه راه حل نمونه هاي كوچكتر به سادگي قابل تعيين باشند. رهيافت بالا به پايين كه توسط روتين هاي بازگشتي به كار مي رود. جستجوي دودويي اگر x با عنصر وسط برابر است خارج شو، در غير اين صورت: 1- تقسيم آرايه به دو زير آرايه با اندازه اي تقريبا برابر نصف اندازه آرايه اوليه. اگر x كوچكتر از عنصر وسط مي باشد، آرايه سمت چپ را انتخاب كن. اگر x بزرگتر از عنصر وسط مي باشد، آرايه سمت راست را انتخاب كن. 2- حل زير آرايه به صورت بازگشتي با تعيين اين كه آيا x در آن زير آرايه قرار دارد يا خير، مگر اين كه اندازه زير آرايه به اندازه كافي كوچك باشد. 3- راه حل آرايه را با توجه به راه حل زير آرايه تعيين كن. يك مثال فرض كنيد x = 18 و آرايه به صورت زير باشد: 10 12 13 14 18 20 25 27 30 35 40 45 47  عنصر وسط مرحله بعدي؟ ( شكل 2.1) كل فرآيند جستجو توسعه يك الگوريتم بازگشتي توسعه روشي براي بدست آوردن راه حل يك نمونه از روي راه حل يك يا چند نمونه كوچكتر تعيين شرط (شرايط) نهايي نزديك شدن به نمونه (هاي) كوچكتر تعيين راه حل در شرط (شرايط) نهايي جستجوی دودويی ◀ الگوريتم 2-1 جستجوی دودويی (بازگشتی) مساله: تعيين کنيد که آيا x در آرایه مرتب شده S به اندازه n وجود دارد يا خير. ورودی ها: عدد صحيح و مثبت n، آرايه مرتب S که از 1 تا n انديس گذاری شده است، کليد x. خروجی ها: location، موقعيت x در S ( اگر x در S نباشد برابر صفر می باشد( الگوريتم جستجوی دودويی index location ( index low, index high) { index mid; if ( low > high) return 0; else { mid = ( low + high)  / 2; if ( x == S[mid]) return mid; else if ( x < S[mid]) return location ( low, mid – 1); else return location ( mid + 1, high); } } پيچيدگي زماني: بدترين حالت عمل اصلي: مقايسه x با S[mid] اندازه ورودي: تعداد عناصر آرايه، n پيچيدگي زماني: حل: W(n) = lgn + 1 و اگر n به تواني از دو محدود نباشد: W(n) = lgn  + 1  (lgn)