پیدا کردن بزرگ ترین زیر آرایه ، شرح الگوریتم و کد سی پلاس پلاس
پیدا کردن بزرگ ترین زیرآرایه در یک آرایه یکی از بهترین سوال ها برای پی بردن به ارزش روش تقسیم و حل است (لینک ویکیپدیا مسئله). در این سوال شما یک آرایه (مجموعه) دارید و می خواهید بزرگ ترین زیرآرایه را در آن پیدا کنید.
بزرگ ترین زیر آرایه – maximum sub array
ابتدا بگذارید مفهوم زیر آرایه را بیان کنیم : زیر آرایه بخشی از آرایه است که تمام اجزای آن پشت سر هم آمده اند. برای مثال آرایه زیر را در نظر بگیرید :
-۱۰ , ۲ , ۳ , -۲ , ۶ , -۴ , ۶ , ۸ , -۴ , ۴ , -۵۰ , -۹
تعدادی از زیر آرایه ها آرایه بالا این ها می شوند:
-۱۰ , ۲ , ۳
-۴ , ۴ , ۴ , -۵۰
-۹
۶ , ۸ , -۴ , ۴
الگوریتم شما چیست ؟ اولین الگوریتمی که به ذهن بیشتر افراد می رسد پیدا کردن تمام زیر آرایه ها است این الگوریتم هزینه اش از مرتبه n^2 است .ولی ما در این پست الگوریتمی را بر مبنای روش تقسیم و حل ( divide and conquer ) ارایه می دهیم که از مرتبه n*log n است.
الگوریتم پیدا کردن بزرگ ترین زیر آرایه با استفاده از روش تقسیم و حل (Divide and conquer) :
هر آرایه ای با هر تعداد عضوی دارای این سه مشخصه است یکی خانه آغاز آرایه (Low) و یکی هم خانه ی آخر آرایه (High) و دیگر هم خانه ی وسط (Mid) آرایه که در عکس زیر آن ها را مشخص کرده ام :
همین طور که در شکل بالا می بینید هر زیر آرایه حتما در یکی از این سه مکان قرار می گیرد :
۱- زیر آرایه ای که کلا در قسمت چپ Mid است که با رنگ سبز مشخص شده است.
۲- زیر آرایه ای که کلا در سمت راست Mid است که با زنگ قهوه ای مشخص شده است.
۳ – زیر آرایه ای که از Mid می گذرد و بخشی از آن در سمت راست Mid قرار دارد و بخشی از آن در سمت چپ Mid قرار دارد که با رنگ آبی مشخص شده است.
پیدا کردن بزرگ ترین زیر آرایه ای که جز قسمت سوم است بسیار آسان است و می توان آن را با تابع ای با هزینه ی n به دست آورد.
از آنجایی که توابع ما سه مقدار : خانه آغاز زیر آرایه ، خانه پایان زیر آرایه و مجموع اعضای زیر آرایه را باید بر گرداند من کلاس زیر را تعریف کرده ام:
1 2 3 4 5 6 7 | class arrayInformation { public: int sum;//sum of sub array element int low;//sub array start location int high;//sub array end location }; |
ابتدا کد این تابع را در ببینید تا آن را را تو ضیح دهیم :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | //find max crossing subarray arrayInformation find_max_crossing_subarray(int *arr, int n, int low, int mid, int high) { arrayInformation myarry; int leftSum = -2000000000; int rightSum = -2000000000; int sum = 0; for (int i = mid; i >= low; i--) { sum += arr[i]; if (sum > leftSum) { leftSum = sum; myarry.low = i; } } sum = 0; for (int i = mid+1; i <= high; i++) { sum += arr[i]; if (sum > rightSum) { rightSum = sum; myarry.high = i; } } myarry.sum = rightSum + leftSum; return myarry; } |
کد بالا تابع find_max_crossing_subarray است که قرار است بزرگترین زیر آرایه ای را که از Mid می گذرد پیدا کند.
آرگومان ها :
int *arr : آرایه است که قرار است پردازش روی آن انجام شود و به صورت pointer به تابع فرستاده شده است.
int n: تعداد اعضای آرایه arr است.
int low: نقطه آغاز آرایه ای است که می خواهیم بزرگ ترین زیر دامنه ی آن را که از مرکز آن می گذرد پیدا کنیم.
int mid : نقطه وسط آرایه ای است که می خواهیم بزرگ ترین زیر دامنه ی آن را که از مرکز آن می گذرد پیدا کنیم.
int high:نقطه آخر آرایه ای است که می خواهیم بزرگ ترین زیر دامنه ی آن را که از مرکز آن می گذرد پیدا کنیم.
حلقه ی for اول قسمت چپ زیر آرایه که از مرکز می گذرد را پیدا می کند و مجموع اعضای آن و نقطه ی شروع آن را پیدا می کند.
حلقه ی for دوم قسمت راست زیر آرایه که از مرکز می گذرد را پیدا می کند و مجموع اعضای آن و نقطه ی آخر آن را پیدا می کند.
و بعد مشخص شدن انتها و ابتدای زیر آرایه مورد نظر و مجموع اجزایش آن را در یک شی از کلاس arrayInformation به نام myarray می ریزد و آن را به عنوان خروجی تابع بر می گرداند.
حالا نوبت تابع اصلی برنامه است که برزگ ترین زیر آرایه را بر می گرداند :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | arrayInformation find_max_subarray(int *arr, int n, int low, int high) { arrayInformation leftArray; arrayInformation rightArray; arrayInformation midArray; arrayInformation myarray; if (low == high) { myarray.sum = arr[high]; myarray.low = low; myarray.high = high; } else { int mid = (low + high) / 2; leftArray = find_max_subarray( arr, n, low, mid); rightArray = find_max_subarray( arr, n, mid + 1, high); midArray = find_max_crossing_subarray( arr, n, low, mid, high); if (leftArray.sum > rightArray.sum) { if (leftArray.sum > midArray.sum) { myarray = leftArray; } else { myarray = midArray; } } else { if (rightArray.sum > midArray.sum) { myarray = rightArray; } else { myarray = midArray; } } } return myarray; } |
آرگومان ها تابع find_max_subarray :
int *arr : آرایه است که قرار است پردازش روی آن انجام شود و به صورت pointer به تابع فرستاده شده است.
int n: تعداد اعضای آرایه arr است.
int low: نقطه آغاز آرایه ای است که می خواهیم بزرگ ترین زیر دامنه ی آن را پیدا کنیم.
int high:نقطه آخر آرایه ای است که می خواهیم بزرگ ترین زیر دامنه ی آن را پیدا کنیم.
در اول تابع شرطی وجود دارد که شرط پایان فراخوانی بازگشتی است که می گوید اگر Low برابر با High بود یا به عبارتی آرایه که در آن دنبال کوچک ترین زیر آرایه می گردیم کلا یک خانه داشت ، بزرگ ترین زیر آرایه آن خودش است.
اگر شرط برقرار نبود به else می رود و در آن جا دو بار خود find_max_subarray فرا خوانی می شود و یک بار برای سمت چپ Mid یک بار برای سمت راست Mid و یک بار هم تابع find_max_crossing_subarray فراخوانی می شود. همین طور که می بینید مقدار بازگشت شده از سه فراخوانی بالا با هم مقایسه می شود و بزرگ ترین آن ها به عنوان مقدار خروجی find_max_subarray باز گردانده می شود .
در زیر کد برنامه پیدا کردن Maximum subarry را با زبان سی پلاس پلاس همراه با یک مثال فراخوانی می بینید :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 | // maximum sub array - divide and conquer.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> using namespace std; class arrayInformation { public: int sum;//sum of sub array element int low;//sub array start location int high;//sub array end location }; //find max crossing subarray arrayInformation find_max_crossing_subarray(int *arr, int n, int low, int mid, int high) { arrayInformation myarry; int leftSum = -2000000000; int rightSum = -2000000000; int sum = 0; for (int i = mid; i >= low; i--) { sum += arr[i]; if (sum > leftSum) { leftSum = sum; myarry.low = i; } } sum = 0; for (int i = mid+1; i <= high; i++) { sum += arr[i]; if (sum > rightSum) { rightSum = sum; myarry.high = i; } } myarry.sum = rightSum + leftSum; return myarry; } arrayInformation find_max_subarray(int *arr, int n, int low, int high) { arrayInformation leftArray; arrayInformation rightArray; arrayInformation midArray; arrayInformation myarray; if (low == high) { myarray.sum = arr[high]; myarray.low = low; myarray.high = high; } else { int mid = (low + high) / 2; leftArray = find_max_subarray( arr, n, low, mid); rightArray = find_max_subarray( arr, n, mid + 1, high); midArray = find_max_crossing_subarray( arr, n, low, mid, high); if (leftArray.sum > rightArray.sum) { if (leftArray.sum > midArray.sum) { myarray = leftArray; } else { myarray = midArray; } } else { if (rightArray.sum > midArray.sum) { myarray = rightArray; } else { myarray = midArray; } } } return myarray; } //open-mind.ir int main() { arrayInformation maximumArray; int *arr = new int[9]; arr[0] = 0; arr[1] = 5; arr[2] = 6; arr[3] = -100; arr[4] = 20; arr[5] = 15; arr[6] = -2; arr[7] = -50; arr[8] = 10; maximumArray = find_max_subarray(arr, 8, 0, 8); cout << "array start at: " << maximumArray.low << endl; cout << "array end at : " << maximumArray.high << endl; cout << "array sum : " << maximumArray.sum << endl; return 0; } |
اگر الگوریتم دیگری دارید یا این برنامه را با زبان دیگر نوشته اید کدتان را برای ما ارسال کنید.
+ کد جدید :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 | // maximum subarray.cpp : Defines the entry point for the console application. //#include "stdafx.h" #include <iostream> #include <iterator> #include <vector> #include <list> #include <cmath> #include <numeric> #include <limits> using namespace std; //this structure hold pointers to start and end of intervals //and sum of element of intervals template<typename Iter, typename Element> struct intervals { Iter beginOfIntervals; //pointer to begin of interval Iter endOfIntervals; //pointer to end of interval Element sumOfIntervals; //hold sum of elements of interval }; //find maximum subarray that cross the mid of array template<typename InputIter, typename Element> intervals<InputIter, Element> Find_Max_Crossing_SubArray( InputIter low, InputIter mid,InputIter high, Element Init) { //claculate the left side of maximum crossing subarray Element sum = 0; intervals<InputIter, Element> leftSum; leftSum.sumOfIntervals = numeric_limits<Element>::min(); InputIter i = mid; while(true) { sum += *i; if (sum > leftSum.sumOfIntervals) { leftSum.sumOfIntervals = sum; leftSum.beginOfIntervals = i; } if(low != i) { i--; } else { break; } } //claculate the right side of maximum crossing subarray sum = Init; intervals<InputIter, Element> rightSum; rightSum.sumOfIntervals = numeric_limits<Element>::min(); i = mid + 1; while(true) { sum += *i; if (sum > rightSum.sumOfIntervals) { rightSum.sumOfIntervals = sum; rightSum.endOfIntervals = i; } if(i != high) { i++; } else { break; } } intervals<InputIter, Element> MaxCrossingArray; MaxCrossingArray.beginOfIntervals = leftSum.beginOfIntervals; MaxCrossingArray.endOfIntervals = rightSum.endOfIntervals; MaxCrossingArray.sumOfIntervals = leftSum.sumOfIntervals + rightSum.sumOfIntervals; return MaxCrossingArray; } //find maximum subarray of input array //this function implements a divide and conquer algorithm //for finding maximum subarray template<typename InputIter, typename Element> intervals<InputIter, Element> Find_Max_SubArray(InputIter low, InputIter high, Element Init) { intervals<InputIter, Element> Max_subArray; if(low == high) { Max_subArray.beginOfIntervals = low; Max_subArray.endOfIntervals = high; Max_subArray.sumOfIntervals = *low; } else { InputIter mid = low + floor(distance(low,high) / 2); //recursively calculate maximum subarray in //the left side of the array's middle intervals<InputIter, Element> left = Find_Max_SubArray(low, mid, 0); //recursively calculate maximum subarray in //the right side of the array's middle intervals<InputIter, Element> righ = Find_Max_SubArray(mid + 1, high, 0); //calculate maximum subarray that //crosses middle of array intervals<InputIter, Element> middle = Find_Max_Crossing_SubArray(low, mid, high, 0); //these If return maximum subarray among three subarray: //left of middle,right of middle, crossing middle of array if(left.sumOfIntervals > righ.sumOfIntervals && left.sumOfIntervals > middle.sumOfIntervals) { Max_subArray = left; } else { if(righ.sumOfIntervals > left.sumOfIntervals && righ.sumOfIntervals > middle.sumOfIntervals) { Max_subArray = righ; } else { Max_subArray = middle; } } } return (Max_subArray); } int main() { vector<int> vecInt = { 13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 }; intervals<vector<int>::iterator, int> MaxSubArray = Find_Max_SubArray( vecInt.begin() , vecInt.end() - 1 ,0); cout << "Array: "; for(auto &a: vecInt) { cout << a << ", "; } cout << endl; //print result cout << "Maximum Subarray: "; vector<int>::iterator i = MaxSubArray.beginOfIntervals; while(true) { cout << *i << " ,"; if( i != MaxSubArray.endOfIntervals) { i++; } else { cout << endl; break; } } cout << "Sum of maximum subarray: " << MaxSubArray.sumOfIntervals<< endl; // return 0; } |
سلام
واقعن کارتون فوق العاده اس من خیلی گشتم تا یه جایی رو پیدا کنم که انقد قشنگ و خوب توضیح داده باشه
با اینکه منبع آموزشی زیاده ولی واقعن کیفیت هاشون پایینه و اصلن در این حد نیستت
اگه میشه کد ها رو با زبان جاوا بزارین
بازم ممنون
تشکر فراوان
اقا دوست داشتم بازم تشکر کنم
بازم خیلی گلی
🙂 تشکر اصلا شرمنده کردی مارو – بازم تشکر می کنم بابت لطفت.
اقا فقط بهت میگم خیلی گلی
دستت درد نکنه
سلام
امکان اش هست این برنامه رو با زبان c هم بذارید
ممنون میشم
تقریبا همین سی پلاس پلاس
سلام اقای دلیرانی خیلی ازتون ممنونم واقعا این سایت خیلی بهم کمک کرده جواب بیشتر سوالاتم رو از اینجا گرفتم
خیلی خوشحالم توانستیم کمک کنیم