max sub array

الگوریتم و کد پیدا کردن بزرگ ترین زیر آرایه با ++C [آپدیت]

max sub array

به روز رسانی: کد جدیدی به انتهای مطلب اضافه شده است – این کد با تمام  container های سی پلاس که دسترسی تصادفی دارند کار می کند.

بزرگ ترین زیر آرایه ( maximum sub array ) :

پیدا کردن بزرگ ترین زیرآرایه در یک آرایه یکی از بهترین سوال ها برای پی بردن به ارزش روش تقسیم و حل است.در این سوال شما یک آرایه  (مجموعه) دارید و می خواهید بزرگ ترین زیرآرایه را در آن پیدا کنید .

ابتدا بگذارید مفهوم زیر آرایه را بیان کنیم : زیر آرایه بخشی از آرایه است که  تمام اجزای آن پشت سر هم آمده اند.برای مثال آرایه زیر را در نظر بگیرید :

-۱۰ , ۲ , ۳ , -۲ , ۶ , -۴ , ۶ , ۸ , -۴ , ۴ , -۵۰ , -۹

تعدادی از زیر آرایه ها آرایه بالا این ها می شوند:

-۱۰ , ۲ , ۳

-۴ , ۴ , ۴ , -۵۰

۶ , ۸ ,  -۴ ,  ۴

الگوریتم شما چیست ؟ اولین الگوریتمی که به ذهن بیشتر افراد می رسد   پیدا کردن تمام زیر آرایه ها است این الگوریتم  هزینه اش از مرتبه n^2 است .ولی ما در این پست الگوریتمی را بر مبنای روش تقسیم و حل ( divide and conquer ) ارایه می دهیم که از مرتبه  n*log n  است.

الگوریتم پیدا کردن بزرگ ترین زیر آرایه با استفاده از روش تقسیم و حل (Divide and conquer) :

هر آرایه ای با هر تعداد عضوی دارای این سه مشخصه است یکی خانه آغاز آرایه  (Low) و یکی هم خانه ی آخر آرایه (High) و دیگر هم خانه ی وسط (Mid) آرایه که در عکس زیر آن ها را مشخص کرده ام :

max sub array

همین طور که در شکل بالا می بینید هر زیر آرایه حتما در یکی از این سه مکان قرار می گیرد :

۱- زیر آرایه ای که کلا در قسمت چپ Mid است که با رنگ سبز مشخص شده است.

۲- زیر آرایه ای که کلا در سمت راست Mid است که با زنگ قهوه ای مشخص شده است.

۳ – زیر آرایه ای که از Mid می گذرد و بخشی از آن در سمت راست Mid قرار دارد و بخشی از آن در سمت چپ Mid قرار دارد که با رنگ آبی مشخص شده است.

 

پیدا کردن بزرگ ترین زیر آرایه ای که جز قسمت سوم است بسیار آسان است و می توان آن را با تابع ای با هزینه ی n به دست آورد.

از آنجایی که توابع ما سه مقدار : خانه آغاز زیر آرایه ، خانه پایان زیر آرایه و مجموع اعضای زیر آرایه  را باید بر گرداند من کلاس زیر را تعریف کرده ام:

ابتدا کد این تابع را در ببینید تا آن را را تو ضیح دهیم :

کد بالا تابع find_max_crossing_subarray است که قرار است بزرگترین زیر آرایه ای را که از Mid می گذرد پیدا کند.

آرگومان ها :

int *arr : آرایه است که قرار است پردازش روی آن انجام شود و به صورت pointer به تابع فرستاده شده است.

int n: تعداد اعضای آرایه arr است.

int low: نقطه آغاز آرایه ای است که می خواهیم بزرگ ترین زیر دامنه ی آن را که از مرکز آن می گذرد پیدا کنیم.

int mid : نقطه وسط آرایه ای است که می خواهیم بزرگ ترین زیر دامنه ی آن را که از مرکز آن می گذرد پیدا کنیم.

int high:نقطه آخر آرایه ای است که می خواهیم بزرگ ترین زیر دامنه ی آن را که از مرکز آن می گذرد پیدا کنیم.

حلقه ی for اول قسمت چپ زیر آرایه که از مرکز می گذرد را پیدا می کند و مجموع اعضای آن و نقطه ی شروع آن را پیدا می کند.

حلقه ی for دوم قسمت راست زیر آرایه که از مرکز می گذرد را پیدا می کند و مجموع اعضای آن و نقطه ی آخر آن را پیدا می کند.

و  بعد مشخص شدن انتها و ابتدای زیر آرایه مورد نظر و مجموع اجزایش آن را در یک شی از کلاس arrayInformation به نام 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 را با زبان سی پلاس پلاس همراه با یک مثال فراخوانی می بینید :

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

 

+ کد جدید :

 

 

 

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۷ دیدگاه

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *