advertise laitec sharif univercity تبلیغات در سایت سورس کد تبلیغات در سایت سورس کد
دانلود سورس پروژه سی شارپ شبیه سازی صف بانک تحت شبکه

دانلود سورس پروژه سی شارپ شبیه سازی صف بانک تحت شبکه

3000 تومان
دانلود پروژه مدیریت کتابخانه با سی شارپ و SQL سرور

دانلود پروژه مدیریت کتابخانه با سی شارپ و SQL سرور

3000 تومان
دانلود پروژه پایانی طراحی وب سایت مخابرات با Asp.net

دانلود پروژه پایانی طراحی وب سایت مخابرات با Asp.net

14000 تومان
دانلود سورس پروژه پایانی وب سایت بنگاه املاک با php

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

18000 تومان
دانلود سورس پروژه فروشگاه کیف با asp.net و sql express

دانلود سورس پروژه فروشگاه کیف با asp.net و sql express

3000 تومان

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

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

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

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

باید توجه داشته باشید که الگوریتم تقسیم و غلبه برای حل هر مسئله ای مناسب و کارار نخواهد بود. تنها در مسائلی میتوان از این روش استفاده کرد که حل هر کدام از زیرمسائل روی جواب مسئله اصلی تاثیر داشته باشد.

در اینجا نمونه هایی از حل مسائل به روش تقسیم و غلبه را میبینید:

 

1- جستوجوی دودویی با الگوریتم تقسیم و غلبه

آرایه مرتب شده A بصورت سعودی و کلید x مفروض اند. هدف جستجوی عنصر x در آرایه است. اگر x در آرایه باشد، اندیس آن را برمی گردانیم (اگر x = A[j] باشد، j را برمیگردانیم) اگر x در آرایه نباشد، خروجی الگوریتم صفر است. هنگام فراخوانی آرایه را A[1.. n] فرض می کنیم و برای جستوجو ابتدا x را با عنصر وسط آرایه مقایسه می کنیم که سه حالت پیش می آید. اگر عنصر برابر مقدار وسط آرایه بود، اندیس همان مقدار برگردانده میشود، اگر کوچکتر بود جستجو در آرایه بین عنصر وسط و آخرین مقدار آرایه صورت میگیرد و اگر بزرگتر بود، جستجو بین مقدار اول آرایه تا عنصر وسطی انجام میشود.

این عمل تا زمانی انجام میشود که یا عنصر پیدا شود و یا اینکه به وضعیتی برسیم که مطمئن شویم، عنصر در آرایه نیست.

الگوریتم جست وجوی دودویی Bsearch:

 

Algorithm  Bsearch (A, Low , high, x)

if  Low = high  then

         if   x = A [Low]  then  return  Low  else  return  0

else {

         mid = [ (Low + high) / 2 ]

          if  x  = A [mid]  then  return  mid

                   else  if  x <   A [mid]  then  return  Bsearch (A , Low, mid – 1 , x)

                   else  return  Bserach (A, mid + 1, high, x)

 

اگر آرایه A[1…n] باشد، فراخوانی الگوریتم باید  Bserach(A, 1, n , x) باشد.

 

2- بزرگترین و کوچکترین عنصر آرایه با روش تقسیم و حل

برای یافتن کوچکترین و بزرگترین عناصر آرایه A ، باید آرایه را به دو قسمت تقسیم کنیم و در هر قسمت min و max را می یابیم و سپس با 2 مقایسه min و max نهایی را بدست می آوریم. الگوریتم بازگشتی یافتن min و max را بصورت بازگشتی می بینیم:

 

Algorithm  maxmin (low , high, max, min)

if  Low = high  then  min = max = A[Low]      //آرایه تک عنصری است

else  if  high = Low + 1  then     // آرایه دو عنصری است

{

        if   A[Low] < A[high]  {

                   max = A[high] ; min = A[Low]

         }

                 else {

 

 

                                max = A[Low] ; min = A[high]

                      }

           }

          Else    //آرایه بیش از دو عنصر است

            {

                          mid = [ (Low + high) / 2 ]

                          maxmin (Low , mid , Lmax , Lmin)

                          maxmin (mid + 1 , high , rmax , rmin)

                          if   Lmax > rmax  then  max = Lmax

                                       else   max  = rmax

                          if   Lmin < rmin  then  min= Lmin

                                       else   min= rmin

           }

 

الگوریتم تقسیم و غلبه یافتن کوچکترین و بزرگترین عضو یک آرایه، فراخوانی باید بصورت maxmin(1, n , Max , Min) انجام شود.

 

3- مرتب سازی سریع QuickSort

آرایه A[1…n] را در نظر بگیرید. میخواهیم آرایه را بصورت صعودی مرتب کنیم. یک عنصر بعنوان محور Pivot انتخاب می شود سپس با انجام عملیاتی Partition آرایه دو قسمت میشود . قسمت اول عناصر کمتر مساوی محور و قسمت دوم عناصر بیشتر مساوی محور را تشکیل میدهند. سپس بصورت بازگشتی برای هر قسمت (j+1 … n , 1 … j-1) عمل گفته شده انجام میشود. الگوریتم Partition را میتوان بصورت زیر ارائه داد:

 

Function Partition (A , Low , high) : integer;

var

          i , j, pivot : integer;

begin

          pivot := A[Low];  i:=Low; j:=high +1;

          repeat

                    repeat  i:=i+1;  until  A[i] >= pivot;

                    repeat  j:=j-1;  until  A[j] <=pivot;

                    if i

           until  i>=j;

            swap (A[Low] , A[j])

             return  j

end;

 

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

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

 

Procedure  quicksort  (Var A : Arraylist; Low , high: integer);

Var j: integer;

begin

           if  Low < high  then

           begin

           j :=partition (A , Low , high)

           quicksort (A , Low , j-1)

            quicksort (A , j+1, high)

                end

end;

 

4- مرتب سازی ادغامی mergesort

آرایه A[1…n] مفروض است و می خواهیم عناصر آن را به صورت صعودی مرتب کنیم. ابتدا با استفاده از فراخوانی های بازگشتی، آرایه را آنقدر نصف می کنیم تا به آرایه های تک عنصری برسیم و سپس آرایه های تک عنصری را با هم ادغام merge می کنیم تا لیست های 2 عنصری مرتب پدید آید. و عمل merge را به همین ترتیب روی لیست های 2 عنصری انجام می دهیم:

 

Void  mergesort(Low , high)

{

         if  (Low < high)

         {

                    mid = [ (Low + high) / 2];

                    mergesort ( Low , mid);

                    mergesort ( mid +1 , high);

                    merge ( Low , mid , high);

          }

}

 

این الگوریتم باید بصورت mergesort (1, n) فراخوانی شود.

الگوریتم merge زیرآرایه های مرتب A[low .. mid] و A[mid+1 .. high] را در یافت می کند و خروجی مرتب A[Low .. high] را تولید میکند:

void  merge (int Low , int mid , int high)

{

               int h = Low, i = Low, j = mid+1, B[1 .. n];

               while( h<=mid && j <=high)

                {

                             if ( A[h] <= A[j] )

                             {

                                      B[i] = A[h]; h++;

                              }

                              else {

                                        B[i] = A[j]; j++;

                                }

                                i++;

                    }

if ( h > mid)

              for ( k = j; k <= high; k++; i++)

                               B[i] = A[k];

else

              for ( k = h; k <= mid; k++; i++)

                               B[i] = A[k];

for ( k = low; k <= high; k++)

              A[k] = B[k]; 

 

                         



2
نظرات
  • user avatar محدثه:
    ۱۰:۵۳:۰۵ __ ۱۳۹۵/۱۰/۰۲

    سلام روزبخیرمن سورس کد تمامی روش هارو با خروجی به زبان c نیاز دارم ممنون میشم برام بفرستین.این برنامه ها الگوریتمش هستند من برنامه کاملش رو نیاز دارممتشکر

  • user avatar س:
    ۱۱:۰۸:۲۷ __ ۱۳۹۶/۰۹/۱۳

    سلام ممنون از سایت خیلی خوبتون.میشه سورس کد تمامی روشهای تقسیم و غلبه و برنامه نویسی پویا رو برام بفرستید.با تشکر

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



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


advertise
چه مسائلی با الگوریتم تقسیم و غلبه قابل حل شدن هستند؟بزرگترین و کوچکترین عنصر آرایه با روش تقسیم و حلحل مسئله Bsearch با تکنیک تقسیم و حلmergeSort algorithm با روش تقسیم و غلبهجستوجوی دودویی با الگوریتم تقسیم و غلبهروش حک کردن مسئله QuickSort با الگوریتم Divide and Conquerآموزش حل مسئله maxmin با تکنیک Divide and Conquerالگوریتم تقسیم و حل در مرتب سازی سریعحل مسائل با تکنیک تقسیم و غلبهمعرفی مسائلی به روش Divide and Conquer لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

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

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

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