صفحه محصول - دانلود فایل پاورپوینت آماده روش تقسیم و حل Divide and Conqure

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

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

Divide and Conqure 1 روش تقسیم و حل Divide and Conqure Divide and Conqure 2 روش تقسیم و حل Divide and Conqure یک نمونه از مساله را به دو یا چند قسمت کوچکتر تقسیم میکند که معمولا نمونه هایی از مساله اصلی هستند. اگر جواب مساله های کوچکتر به راحتی محاسبه شود, می توان جواب نمونه اصلی را با ترکیب این جوابها به دست آورد, در غیر این صورت میتوان آنها را به نمونه های کوچکتر تقسیم کرد . یک روش بالا به پایین است. 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; return Combine(DAndC(P1),DAndC(P2),…,DAndC(Pk); } } Divide and Conqure 3 زمان محاسبه تابع 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 Divide and Conqure 4 جستجوی دودویی مساله: تعیین این که آیا 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 not found Divide and Conqure 5 الگوریتم binary search int binsearch(int low,int high) { int mid; if (low > high) return 0; else { mid=[(low+high)/2]; عملگر مبنایی if (x==s[mid]) return mid; else if(x < mid) return binsearch(low,mid-1); else return binsearch(mid+1,high); } }