advertise laitec sharif univercity تبلیغات در سایت سورس کد تبلیغات در سایت سورس کد
دانلود سورس هوش مصنوعی رنگ آمیزی گراف با ژنتیک در #C

دانلود سورس هوش مصنوعی رنگ آمیزی گراف با ژنتیک در #C

4800 تومان
دانلود پروژه کامل مهندسی نرم افزار ، شرکت نرم افزاری

دانلود پروژه کامل مهندسی نرم افزار ، شرکت نرم افزاری

3000 تومان
دانلود آپلود سنتر پیشرفته با PHP و Ajax

دانلود آپلود سنتر پیشرفته با PHP و Ajax

3000 تومان
پروژه پایانی PHP وب سایت فروشگاه کامپیوتری

پروژه پایانی PHP وب سایت فروشگاه کامپیوتری

23000 تومان
دانلود پروژه فروشنده دوره گرد با الگوریتم گرانشی در #C

دانلود پروژه فروشنده دوره گرد با الگوریتم گرانشی در #C

4800 تومان

الگوریتم تقسیم و غلبه Divide and Conquer

در روش تقسیم و غلبه ابتدا مساله بزرگ به زیر مسائل کوچکتر تقسیم میشود و پس از آن زیر مسائل کوچکتر نیز در صورت لزوم به زیر مسائل کوچکتری تقسیم میشوند و در نهایت با حل مسائل کوچک، مساله اصلی حل میشود.
الگوریتم تقسیم و غلبه  Divide and Conquer

الگوریتم تقسیم و غلبه  Divide & Conquer

بسیاری از مسائل کاربردی کامپیوتری با روش  تقسیم و حل (Divide & Conquer) قابل حل هستند. در این روش ابتدا مساله بزرگ به زیر مسائل کوچکتر تقسیم میشود و پس از آن زیر مسائل کوچکتر نیز در صورت لزوم به زیر مسائل کوچکتری تقسیم میشوند و در نهایت با حل مسائل کوچک، مساله اصلی حل میشود.

در واقع روش تقسیم وغلبه در طراحی الگوریتم، روشی از بالا به پایین (top-down) میباشد. الگوریتم تقسیم وغلبه بازگشتی است و معمولا یک مساله کوچک ممکن است چندین بار حل شود. یعنی این روش ها معمولا از نظر زمان و حافظه بهینه نیستند ولی مزیت آنها کدنویسی راحت آنهاست.

لازم به ذکر است که تمام مسائل با روش تقسیم وغلبه قابل حل نیستند، مثلا نمیتوان برای یافتن جوابهای یک دستگاه 100 معادله 100 مجهول آن را به دو دستگاه 50 معادله 50 مجهول تبدیل کرد. ولی مثلا میتوان برای یافتن ماکزیمم یک آرایه 100 عنصری، آرایه را به 2 آرایه 50 عنصری تقسیم کرده، ماکزیمم هر قسمت را یافته سپس با مقایسه نتایج، ماکزیمم را پیدا کنیم.

میتوان الگوریتم کلی تقسیم و حل را به صورت زیر نوشت:

► اگر مسئله به اندازه کافی کوچک است و میتوان آن را حل کرد، حل کن.

► اگر مسئله بزرگ است آن را به مسائل کوچک تقسیم کن و تقسیم را ادامه بده.

► مسائل کوچکتر را حل کن (مشابه مسائل بزرگ)

► مسائل حل شده کوچک را با هم ترکیب کن تا مسئله بزرگ حل شود.

الگوریتم کلی تقسیم و حل بصورت شبه کد در زیر نوشته شده است.

 

الگوریتم انتزاعی روش تقسیم و غلبه

Algorithm  DandC (Low , high)

       if  small (low , high)  then  return  g (Low , high)

      else  {

          mid = Divide (Low , high)

          return  combine  ( DandC (Low , mid) , DandC (mid+1 , high) )

}

 

در این الگوریتم تابع small مشخص میکند آیا مساله به اندازه کافی کوچک هست که بتوان آن را بدون شکستن حل کرد یا خیر. اگر جواب مثبت باشد، تابع g فراخوانی میشود در غیر اینصوررت عمل تقسیم انجام میشود.

در ضمن اگر فرض کنیم ورودی در آرایه A[1…n] باشد، فراخوانی باید بصورت Danc(1 , n) صورت گیرد.

اگر زمان اجرای الگوریتم Combine در الگوریتم 1، f(n) فرض شود آنگاه زمان اجرای الگوریتم، برابر است با:

T(n) = 2 T(n/2) + f(n)         های بزرگ nبرای 

T(n) = g(n)                      های کوچکnبرای 

در T(n) فرض شده است که n توانی از 2 است و همچنین در هر بار تقسیم، آرایه دقیقا نصف میشود. و همچنین g(n) زمان تابع g میباشد.

الگوریتم های معروفی که به روش الگوریتم تقسیم و غلبه حل میشوند عبارتنداز:

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

► بزرگترین و کوچکترین عنصر آرایه

► ضرب اعداد بزرگ

► ضرب چند جمله ای ها

► ضرب دو ماتریس

► مرتب سازی سریع

► مرتب سازی ادغامی

► یافتن کوچکترین (بزرگترین ) کلید دوم و یافتن کوچکترین (بزرگترین) کلید i ام.

 



3
نظرات
  • user avatar frnz:
    ۱۲:۲۷:۵۱ __ ۱۳۹۴/۰۳/۲۱

    مفید بود.ممنون

  • user avatar ارمین12:
    ۱۷:۵۲:۵۱ __ ۱۳۹۵/۰۱/۳۰

    سلام خسته نباشید میشه الگورتیم معکوس یک رشته به روش تقسیم غلبه رو قرار بدین با تشکر

  • user avatar علی:
    ۱۶:۴۳:۴۹ __ ۱۳۹۶/۰۱/۱۷

    خسته نباشید . اگه میشه چند تا مثال در سطوح مختلف با این روش بزنید . برای فهم بیشتر . چون خیلیا مثله من رشتشون کامپیوتر نیست و ممکنه بدون مثاله کد نویسی درست متوجه نشن . ممنون

نظر خود را ارسال کنید



نام:
ایمیل:
دیدگاه:
captcha
کد امنیتی :


advertise
شبه کد الگوریتم تقسیم و حلالگوریتم بازگشتی تقسیم وحلروش تقسیم وحل در طراحی الگوریتمهاالگوریتم تقسیم و حلدانلود سورس کد الگوریتم تقسیم و غلبهزمان اجرای الگوریتم تقسیم و غلبهالگوریتم انتزاعی روش تقسیم و غلبهDivide and Conquer Algorithmآشنایی با روش تقسیم و غلبهالگوریتم Divide and Conquerآموزش الگوریتم تقسیم و حل لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

سفارش پروژه در سورس کد

پیشنهادات ویژه سورس کد

پکیج ویژه پروژه پایانی رشته کامپیوتر دانلود مجموعه 70 پروژه کاربردی سی شارپ وب سایت فروشگاه با php