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

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

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

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

3000 تومان
دانلود سورس n وزیر با جست وجوی ممنوع در سی شارپ #C

دانلود سورس n وزیر با جست وجوی ممنوع در سی شارپ #C

3000 تومان
دانلود برنامه هشت وزیر با جستجوی عمقی در سی شارپ

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

3000 تومان
دانلود پایان نامه وب سایت مهندسی پزشکی با ASP.net

دانلود پایان نامه وب سایت مهندسی پزشکی با ASP.net

12000 تومان

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

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

تولید بیت کوین با کامپیوتر

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

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