PDA

View Full Version : زیر مجموعه های k عضوی



SYSMAN
دوشنبه 25 اردیبهشت 1385, 22:24 عصر
با سلام
می خواهم با c یک برنامه بنویسم که یک مجموعه از اعداد حقیقی را بگیره و و تعداد زیر مجموعه های k عضوی آن را نمایش بده.
به عنوان مثال اگر مجموعه {1،2،3،4} را داشته باشیم و بخواهیم زیر مجموعه ای از آن را که 2 عضوی باشند به دست بیاریم باید چه جوری الگوریتم آن را طراحی کرد؟

raha_hakhamanesh
چهارشنبه 27 اردیبهشت 1385, 12:20 عصر
با سلام
منو ببخشید اگه خوب اطلاع رسانی نکردم
ببینید از این روشی که می گم استفاده کنید نظرتون رو بگید مشکل عمده کارهای در ارتباط با مجموعه ها است برای همین باید یه مجموعه رو با روشهایی مثلا ماتریس دو بعدی شبیه سازی کرد . حالا ...
فرض کنید یک مجموعه nتایی داریم تمام حالتهای اون مجموعه در ترکیبهایی دودویی قرار دارند ( مطمئن باشید ) سپس برای اینکه زیر مجموعه های k عضوی اون رو بدست بیاریم کافیه تمام ترکیبهایی که به ازای k عنصر غیر صفر باشند رو به دست بیاریم مثال دوستمون برای 4 عضو بود رو نگاه کنید
0=0000
1=0001
2=0010
3=0011
4=0100
5=0101
6=0110
7=0111
8=1000
9=1001
10=1010
11=1011
12=1100
13=1101
14=1110
15=1111

خوب ترکیب های سه تایی شماره های 7و11و13و14که شامل گروه های(چپ به راست) bcd,acd,abd,abc هستند
اگه اشتباه نکرده باشم فکر می کنم خط رو بهتون دادم بقیه اش با خودتون
با آرزوی موفقیت همه ایرانیان

MShirzadi
چهارشنبه 29 خرداد 1387, 01:14 صبح
این شیوه برای بدست آوردن ترکیب در مجموعه های بزرگ از order بالایی برخورداره.
الگوریتم بهینه تری ندارید برای این کار؟؟

MShirzadi
پنج شنبه 30 خرداد 1387, 20:52 عصر
بای دوستانی که دنبال تابعی برای این کا می گردن::
من یه تابه به زیبان جاوا پیدا گردم توی لینک زیر:
http://www.merriampark.com/comb.htm#Archery
از اساتید هم عذر خواهی می کنم که در این انجمن Source Code گذاشتم.
چون کار منو خیلی راه انداخت گفتم شاید دوستان هم نیاز داشته باشن.

s_davod_m@yahoo.com
یک شنبه 23 فروردین 1388, 15:29 عصر
لطفأ شبه کد تابع مربوط به یافتن زیرمجموعه های k عضوی یک مجموعه n عضوی را بیان کنید.

kashaneh
چهارشنبه 26 فروردین 1388, 20:28 عصر
دوست عزیز به فایل ضمیمه مراجعه کنید... درک مفهوم آن کار خیلی سختی نیست... موفق باشی

newamir
پنج شنبه 27 فروردین 1388, 23:08 عصر
من نفهمیدم تعداد زیرمجموعه ها رو میخوای یا خودشون رو؟!
اگر تعدادشون رو میخوای (در واقع میخوای مقدار ترکیبk از n را حساب کنی) یه الگوریتم dynamic با زمان اجرای اوی n*k براش هست که از اتحاد پاسکال استفاده میکنه. ادامه راه حل ساده س. در غیر اینصورت زمان اجراش حداقل همون k از n میشه که ممکنه بزرگ باشه.

art_master
یک شنبه 30 خرداد 1389, 20:55 عصر
من خود زیر مجموعه ها رو میخوام ! راستی سلام

art_master
یک شنبه 30 خرداد 1389, 21:00 عصر
بالاخره به جوابت رسیدی ؟ میشه واسه منم توضیح بدی ! آخه منم سوال تورو دارم