محاسبه ترکیب k شی از n شی با استفاده از Dynamic Programming قسمت دوم

سلام دوستان

توی قسمت قبلی حرف از تکنیک Divide and Conquer برای طراحی الگوریتم زدیم و واقع قضیه اینه که این شیوه یکی از شیوه های قدرتمند برای طراحی الگوریتم هستش ولی خب برخی از جاها همون طور که گفتیم کارایی که باید داشته باشه رو نداره. بذارید یه بار دیگه نگاهی به برنامه قبلی با تغییر زیر بندازیم:

من فقط یه cout اضافه کردم تا ببینم چه ترکیباتی حساب میشن. خروجی این برنامه حتما این نکته رو به شما خواهد گفت که  بعضی جاها مثلا با اینکه ترکیب ۲ از ۶ رو قبلا حساب کردیم بازم این حساب میشه یه جایی پایین تر.

cmbخب اینجا ست که پای Dynamic Programming یا برنامه نویسی پویا به کارمون میاد. گفتم قبلا اسمش زیباست ولی چیز خاصی نیست جز راهی برای طراحی الگوریتم. شیوه D&C (تقسیم غلبه) شیوه ای از بالا به پایین یا top-down approach هستش. یعنی مسئله اصلی رو در نظر میگیره سعی میکنه اینقدر مسئله رو بشکنه تا اینکه مسئله های ریز تر قابل حل باشن. شیوه برنامه نویسی پویا برخلاف D&C یه شیوه پایین به بالا یا Down-top Approach است یعنی از حل کردن مسائل ریز شروع میکنه تا اینکه برسه به مسئله بزرگ تر و اصلی.

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

حل مسئله ترکیب k از n به شیوه برنامه نویسی پویا

شاید با مثلث خیام ( پاسکال ) آشنا باشید. یا شایدم نه :))) به تصویر زیر نگاه کنید تا متوجه بشید این مثلث چگونه ساخته میشه! تصویر از ویکی پدیا (خدا پدرت رو بیامرزه ویکی)

220px-PascalTriangleAnimated2

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

86c0a465077ef0ad2e48791723cc0ee0خب اگه به تصویر زیر نگاهی بندازید شاید درک نحوه تولید مثلث خیام – پاسکال براتون روشن تر بشه:

triangle_khayamدر واقع ما اینجا یه آرایه دو بعدی داریم که فقط زیر قطر اصلیش برامون مهمه. جاهایی که ستون صفره مقدار همه سلول ها یک هست. در ضمن جایی که سطر و ستون با هم برابرند هم همینطور(چرا؟) مقدار بقیه سلول ها هم با فرمولی که اون پایین تصویر نوشته شده به دست میاد که دقیقا مثل همون فرمول بالاست. ایها الناس این سه تا شکل دارن یه چیز رو میگن 🙂  خب حالا اگه ما بخواهیم ترکیب k از n رو بدست بیاریم کافیه جدول بالا رو برای تعداد n تا سطر و k تا ستون حساب کنیم. عنصر n,k این جدول میشه اون چیزی که ما میخوایم.یعنی اگه شما بخواهید ترکیب ۲ از ۵ رو حساب کنید جدول بالا رو باید بسازید برای ۵+۱ تا سطر و ۲+۱ تا ستون. بعدم عدد داخل آرایه ۵ و ۲ میشه جواب ما یعنی ۱۰٫

همونطور که قبلا هم گفتم و اینجا هم واضحه ما برای محاسبه سطر i ام فقط نیاز به سطر i-1 داریم. پس اگه یه آرایه به اندازه k+1 داشته باشیم کفایت میکنه برامون.(و یه آرایه کمکی به همین اندازه برای نگه داری سطر قبلی که محاسبه کردیم)

خب بذارید مرحله به مرحله این کد رو بریم جلو :

تابع min که خیلی ساده است و مینیمم دو عدد رو بر میگردونه.

توی تابع combDP ما اولا دو آرایه به اندازه k+1 میگیریم و بعدش شروع میکنیم سطر به سطر کار مثلث خیام رو پر کنیم. سطر ها با i و ستون ها با j در حلقه ها مشخص میشن. حلقه اول از صفر شروع میشه و تا خود n جلو میره( طبق شکل قبلی دلیل واضحه) ولی حلقه دوم از صفر شروع میشه ولی تا مینیمم i,k بیشتر جلو نمیره. چرا تا k نره؟ اولا همونطور که از شکل جدول پیداست فقط کافیه نیمه پایینی جدول حساب بشه پس تا i رفتن برای j کفایت میکنه.یعن وقتی i = 1 هستش j هم تا یک ( صفرویک) میره جلو. وقتی i=2 شد j هم تا دو ( صفر و یک و دو ) میره جلو. (تا حالت مثلث مد نظرمون ایجاد بشه) ولی یه جایی سطر بیشتر از مقدار k میشه. لزومی نداره j رو تا i بریم جلو. به شکل زیر نگاه کنید تا متوجه بشید. فرض کنید میخوام ترکیب دو از پنج رو حساب کنم.

triangle_khayam_2اگر شرط حلقه دوم به جای مینیمم i,k همون n باشه با اینکه هدف ما محاسبه خونه سبز رنگ هستش ولی خونه های قرمز رنگ هم محاسبه میشه در حالی که محاسبه نکردن خونه های قرمز رنگ هیچ خللی به ادامه کار وارد نمیکنه. پس واسه همینه که ما تا جایی که i کوچکتر از k هست j  رو تا i میریم جلو ( سطر های صفر و یک  و دو رو دقت کنید که ستون ها هم تا صفر و یک و دو بیشتر جلو نرفتند.) ولی وقتی که i بزرگتر از k شد ( سطر های سه و چهار و پنج ) دیگه لزومی نداره j (ستونها) هم تا i برن جلو و تا همون K رفتن کفایت میکنه.آره!

۸,۵۸۶ total views, 6 views today

Print Friendly, PDF & Email

درباره ی سعید دادخواه

یه برنامه نویس !

4
دیدگاه بگذارید

avatar
2 Comment threads
2 Thread replies
0 دنبال کنندگان
 
Most reacted comment
داغ ترین نخ نظرات
3 کامنت گذاران
علیرضاسعید دادخواهNeoFighT کامنت گذاران اخیر
  مشترک شو!  
جدیدترین قدیمی‌ترین دارای بیشترین امتیاز
میخوام باخبر شم از
NeoFighT
Member
NeoFighT

سختهhttp://qtips.ir/wp-content/plugins/wp-monalisa/icons/wpml_bigsmile.gif

علیرضا
Guest
علیرضا

یا تا ۱ هفته دیگه وبسایتو آپدیت میکنی و پست جدید میذاری یا واست یه اتفاقی میافته که تا آخر عمرت در رنج و عذاب خواهی بود (ها ها ها ها……)
خسته شدیم از بس ریفرش کردیم دیدیم همون صفحه میاد .در ضمن یه برنامه با کیوت ۵.۲ واسه اندریود نوشتم تازه یادم افتاد گوشی ندارم تستش کنم 🙁 بسوره پدر بی پولی
امیدوارم کارات تموم شه و وقت آزاد پیدا کنی و بیای به وبلاگ سر بزنی
منتظرم……
پ ن:سطر اولو یه نفر یه جور دیگه واسم میل کرده بود 😀