نمونه هایی از الگوریتم ها به روش الگوریتم تقسیم و حل
نمونه هایی از الگوریتم ها به روش الگوریتم تقسیم و حل
قبلا الگوریتم تقسیم و غلبه 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];
سلام روزبخیرمن سورس کد تمامی روش هارو با خروجی به زبان c نیاز دارم ممنون میشم برام بفرستین.این برنامه ها الگوریتمش هستند من برنامه کاملش رو نیاز دارممتشکر
سلام ممنون از سایت خیلی خوبتون.میشه سورس کد تمامی روشهای تقسیم و غلبه و برنامه نویسی پویا رو برام بفرستید.با تشکر