پاورپوینت درمورد روش تقسیم و حل (Divide and Conquer)
پاورپوینت درمورد روش تقسیم و حل (Divide and Conquer)
مشخصات فایل
عنوان: پاورپوینت درمورد روش تقسیم و حل (Divide and Conquer)
قالب بندی: پاورپوینت
تعداد اسلاید: ۵۸
محتویات
روش تقسیم و حل (Divide and Conquer)
الف) جستجوی دودویی
ب) مرتب‌سازی ادغامی (Merge Sort)
ج) مرتب‌سازی سریع (Quick Sort) یا Partition Exchange Sort
د) ضرب ماتریس‌های استراسن (Strassen’s Matrix Multiplication )
ه) اعمال محاسباتی روی اعداد صحیح بزرگ
و) تعیین مقادیر آستانه
کجا نمی‌توان از روش تقسیم‌وحل استفاده کرد؟
قسمتی از پاورپوینت
روش تقسیم و حل (Divide and Conquer)
شیوه حل در این روش به این صورت است که:
به صورت بازگشتی …
مساله به دو یا بیشتر زیر مساله از نوع همان مساله (یا مساله‌ای که در حل مساله اصلی مرتبط است) تقسیم (divide) می‌شود و …
اینکار (شکستن و تقسیم‌کردن) تا آنجایی ادامه می‌یابد که …
مساله به اندازه‌ای ساده شود که بتواند مستقیما حل شود (conquer). سپس …
پاسخ‌های زیرمساله‌ها با هم ترکیب می‌شوند تا پاسخی برای مساله اصلی فراهم سازند.
فهم و طراحی الگوریتم‌های D&C، مهارت پیچیده‌ای است که نیازمند فهم خوب از ماهیت مساله دارد.
توجه:
•به هنگام نوشتن الگوریتم‌های بازگشتی در سطح مسئله فکر می‌کنیم و
•می‌گذاریم تا جزئیات را زبان برنامه نویسی با استفاده از Stack بر عهده گیرد
•هنگام طراحی الگوریتم‌های تقسیم و حل معمولا همین گونه فکر می‌کنیم و آن را به صورت یک روال بازگشتی می‌نویسیم
و . . .
