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

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

شاید بدونید که در مباحث ریاضی مبحثی نه چندان ساده ولی شیرین به نام آنالیز ترکیبی داریم که بیشتر کارش اینه که حالت های مختلف یک اتفاق رو بشماره. ساده ترین حالتش یه تاس رو پرتاب کنیم هوا چند حالت امکان داره روی زمین قرار بگیره؟! مسلما شش تا . حالا اگه دوتا تاس رو انداختیم بالا چند حالت ؟!‌ طبق اصل ضرب ۳۶ حالت خواهیم داشت. ( اصلا قصد صحبت در مورد اینا رو ندارم)

خب بذارید یه حالت دیگه رو بررسی کنیم. اگه شما بخواهید از یه سری شی متمایز ( مثلا یه سری آدم) که تعدادشون n تا است k  نفر رو برای کوه نوردی انتخاب کنید چند حالت امکان داره؟ مثلا مدیر یه مدرسه به چند حالت میتونه از بین ۲۰ نفر از دانش آموزای یک کلاس ۴ نفر رو برای نظافت دستشویی های مدرسه انتخاب کنه؟خخخ

وقتی صحبت از انتخاب k نفر از n نفر میشه و ترتیب انتخاب ها مهم نیست (الان میگم یعنی چی مهم نیست ) باید از فرمول ترکیب استفاده کنیم که با نماد C(n,k) مشخص میشه. و مقدارش برابر هست با  : ( تصویر از ویکی پدیا)eed76baaa00cf639ad1c1cecd11247f1

اما اینکه گفتم ترتیب انتخاب مهم نیست یعنی چی ؟‌ ببینید اگه همون مدیر بخواد از ۲۰ نفر ۳ نفر رو به عنوان رتبه ۱و۲و۳ کلاس انتخاب کنه اینکه آقای سعید دادخواه به عنوان رتبه یک انتخاب بشه و یا رتبه دو ویا سه باهم متفاوت هستش ولی وقتی برای تمیز کردن دستشویی انتخاب میشد مهم نبود نفر اول بود که انتخاب میشد یا نفر دوم یا … پس منظور از اهمیت ترتیب انتخاب اینه.

خب حالا میخوایم یه تابع به نام comb بنویسیم که دوتا int n , int k  دریافت کنه مقدار بالا رو محاسبه کنه. چه راهی به ذهنتون میرسه؟ اول بیایم فاکتوریل n رو حساب کنیم بعد تقسیم بر مخرجش کنیم؟ راه خوبیه ولی راه زیبا تری میخوایم

استفاده از شیوه تفرقه بینداز و حکومت کن

یکی از شیوه های طراحی الگوریتم شیوه Divide And Conquer هستش یعنی تفرقه بینداز و حکومت کن. فکر کنم تاریخچه اش هم مربوط به انگلیسی هاست که منطقشون اینه که برای حکومت بر مردمی باید بینشون تفرقه انداخت.

ولی این شیوه چطوریه؟ میگه که وقتی میتونی سوالی رو بشکنی به دو یا چند سوال کوچکتر این کار رو بکن و سوال های کوچکتر رو حل کن و بعد سوال اصلی رو حل کن. مثلا فرض کنید میخوایم آرایه ای از اعداد رو که به صورت زیر هستش مرتب کنیم:

۵ ۴ ۴۴ ۶ ۹۰ ۱۲ ۲  ۱۲

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

Merge-sort-example-300pxخب آیا میشه از شیوه تقسم و غلبه (همین که الان گفتیم )‌برای محاسبه ترکیب k از n استفاده کرد. بعله میشه. به فرمول زیر دقت کنید:

86c0a465077ef0ad2e48791723cc0ee0خیلی عالیه ! ما تونستیم ترکیب k از n رو به دو قسمت تقسیم کنیم. برای درک این فرمول این اثبات شهودی رو بخونید :‌ وقتی میخوایم از بین ۲۰ دانش آموز ۴ تا واسه تمیز کردن دشویی انتخاب کنیم مث این میمونه که این حالت رو در نظر بگیریم که سعید دادخواه رو از قبل انتخاب کردیم ( قسمت اول فرمول) و از بقیه ۱۹ نفر سه نفر رو انتخاب می کنیم ( ترکیب k-1 از n-1 ) یا این حالت که اصن بی خیال سعید دادخواه شدیم و از ۱۹ نفر دیگه ۴ نفر رو انتخاب کنیم ( قسمت دوم ترکیب k از n-1 )

خب پس با این فرمول میتونیم مقدار ترکیب k از n  رو حساب کنیم. با این فرض که میدونیم که ترکیب n از n ( یعنی انتخاب n نفر از n نفر)‌میشه یک ( فقط یک حالت امکان داره از n نفر n نفر رو انتخاب کرد ) و ترکیب ۰ نفر از n نفر هم میشه یک بازم. با این تفاسیر میشه تابع زیر رو برای محاسبه ترکیب k از n نوشت.

خب حالا Dynamic Programming چی میگه این وسط. واقع قضیه اینه که استفاده از شیوه Divide and Conquer برای این مساله Order زمانی مناسبی نداره ( یعنی خیلی الکی طول می کشه) باید دقت کرد که شیوه تقسیم و غلبه (همون divide and conquer) فقط برای مسایلی مناسب است که سایز  مسایل کوچکتری که در اثر تقسیم بدست میاد خیلی کوچکتر از سایز مساله اصلی باشه در حالی که اینجا اینطور نیست . مساله اصلی ترکیب k از n هستش در حالی که ریز مساله ترکیب k-1 از n-1 . نکته دوم اینه که شیوه تقسیم و غلبه جایی بدرد میخوره که مسایل ریز ( که در اثر تقسیم به دست آمده اند) با هم همپوشانی نداشته باشند. یعنی ممکنه یه جایی از ریز مساله ها یه مقداری رو حساب کنیم که قبلا هم حساب شده. مرض که نداریم هی حساب کنیم.

در این مواقع بهتره از شیوه Dynamic Programming استفاده کنیم که در قسمت بعدی در موردش صحبت میکنیم.

کلا موافقید این مباحث هم مطرح بشه؟! سخت که نیست؟! به عمه ام کاری نداشته باشید خواهشاwp-monalisa icon

 

 

۳۱,۷۴۷ total views, 3 views today

Print Friendly, PDF & Email

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

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

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

avatar
7 Comment threads
5 Thread replies
0 دنبال کنندگان
 
Most reacted comment
داغ ترین نخ نظرات
9 کامنت گذاران
ماندانااقبالNimaعلیرضاreza1 کامنت گذاران اخیر
  مشترک شو!  
جدیدترین قدیمی‌ترین دارای بیشترین امتیاز
میخوام باخبر شم از
Behnam
Member
Behnam

خسته نباشید اقا سعید … 
به نظر من که خیلی جالبه … خیلی کنجکاو شدم که بدونم با این Dynamic Programming چه کارهایی میشه کرد؟!!!!!!
در کل خوب بود … من که موافقم … 

qtmil
عضو

بسیار عالی و مفید

HadiAbbasi
عضو

عالی…

reza1
Member
reza1

سلام
آخرش نفهمدیدم دادخواه دسشویی را شست یا دوباره زیر کار در رفت 😀
 

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

جان؟؟

Nima
Guest
Nima

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

اقبال
Guest
اقبال

اقا دم ت گرم این کدت خ ب کارم اومد تو اعداد بزرگ فقط این روش جواب میده…
کدم هی ارور میخورد یه جاش از تابع انتخاب استفاده میکردم از این روشت استفاده کردم درست شد
دم ت گرم

ماندانا
Guest
ماندانا

سلام مرسی از مطلب مفید. فقط یه سوال:
اگه من دوتا گروه داشته باشم و بخوام اعضای این گروه باهم ترکیب یک به چند داشته باشن چه باید بکنم؟