advertise laitec sharif univercity تبلیغات در سایت سورس کد تبلیغات در سایت سورس کد
دانلود پروژه مهندسی نرم افزار ، نمایندگی ایران خودرو

دانلود پروژه مهندسی نرم افزار ، نمایندگی ایران خودرو

3000 تومان
دانلود PDF مجموعه 300 نکته جالب برنامه نویسی در سی شارپ #C

دانلود PDF مجموعه 300 نکته جالب برنامه نویسی در سی شارپ #C

3000 تومان
سیستم اتوماسیون دهیاری ، پروژه مهندسی نرم افزار

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

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

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

3000 تومان
دانلود پروژه وب سایت هتل با HTML و ASP.NET

دانلود پروژه وب سایت هتل با HTML و ASP.NET

4900 تومان

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

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

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

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