advertise laitec sharif univercity
دانلود پروژه معمای 8 با الگوریتم ژنتیک در سی شارپ

دانلود پروژه معمای 8 با الگوریتم ژنتیک در سی شارپ

10000 تومان
دانلود برنامه رنگ آمیزی گراف با الگوریتم عقبگرد در سی شارپ

دانلود برنامه رنگ آمیزی گراف با الگوریتم عقبگرد در سی شارپ

10000 تومان
دانلود برنامه آزمون تستی در مالتی مدیا بیلدر MMb

دانلود برنامه آزمون تستی در مالتی مدیا بیلدر MMb

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

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

10000 تومان
دانلود سورس پروژه TSP با الگوریتم مورچگان Ants

دانلود سورس پروژه TSP با الگوریتم مورچگان Ants

10000 تومان

الگوریتم تقسیم و غلبه 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شبه کد الگوریتم تقسیم و حلآموزش الگوریتم تقسیم و حلDivide and Conquer Algorithmروش تقسیم وحل در طراحی الگوریتمهاآشنایی با روش تقسیم و غلبه لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

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

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