پاورپوینت روش تقسیم و حل Divide and Conqure

پاورپوینت روش تقسیم و حل Divide and Conqure

پاورپوینت روش تقسیم و حل Divide and Conqureدارای 20 اسلاید با ظاهری زیبا ، متفاوت ، مفید، مختصر و قابل ویرایش می باشد قسمتی از متن را ببینید و در صورت تمایل خرید کنید.

 یک نمونه از مسأله را به دو یا چند قسمت کوچکتر تقسیم میکند که معمولا نمونه هایی از مسأله اصلی هستند. اگر جواب مسأله های کوچکتر به راحتی محاسبه شود, می توان جواب نمونه  اصلی را با ترکیب این جوابها به دست آورد, در غیر این صورت میتوان آنها را به نمونه های کوچکتر تقسیم کرد . 

 یک روش بالا به پایین است. 

Algorithm DAndC(P)

{ if Small(P) return Solve(P);

   else

     { divide P into smaller instances P1,P2,…,Pk, k>=1;

        Apply DAndC to each of these subproblems;

زمان محاسبه تابع DAndC

T(n)= g(n)                                               کوچک باشد  n

          T(n1)+ T(n2)+…+ T(nk)+f(n)          درغیراینصورت

  g(n): زمان لازم برای محاسبه مستقیم پاسخ برای ورودی های کوچک

  : f(n) زمان لازم برای تقسیم مسأله و ترکیب راه حلها

معمولا:

T(n)= T(1)                 n=1

           aT(n/b)+f(n)   n>1

  جستجوی دودویی

 مسأله: تعیین این که آیا x در آرایه مرتب s با اندازه n وجود دارد یا خیر.

مثال:n=14                                                                                                

-15,-6,0,7,9,23,54,82,101,112,125,131,142,151

x=9

low   high   mid    s[mid]

1        14       7       54

1         6        3         0

4   6        5         9       found

x=-14

low   high   mid    s[mid]

1        14       7       54

1         6        3         0

1   2        1       -15

2         2        2       -6

2         1                    

Merge sort

مراحل مرتب سازی ادغامی برای آرایه ای با n عنصر:

       1. تقسیم آرایه به دو زیر آرایه هریک با n/2 عضو

         2. حل هر زیر آرایه با مرتب کردن آن. اگر آرایه به اندازه کافی کوچک نباشد, از بازگشت برای انجام این کار استفاده می کنیم.

         3. ادغام زیر آرایه های مرتب شده

ppt: نوع فایل

سایز: 29.8 KB

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