PDA

View Full Version : یافتن تعداد زیرمجموعه‌های یک مجموعه



solaris1091
جمعه 12 دی 1382, 23:31 عصر
لطفا به من کمک کنید...
می خواهم یک برنامه به زبان c بنویسم بطوری که کلیه زیرمجموعه های یک
مجموعه n عضوی که مجموع عضوهای آن برابر عدد m باشد را پیدا کند.

B-Vedadian
شنبه 13 دی 1382, 09:28 صبح
با سلام،

الگوریتم باز گشتی زیر ممکن است کمک کند، با توجه به اینکه من نمیدانم چگونه زیر مجموعه ها را نشان میدهید و یا حتی اصلا نشان میدهید یا فقط ذخیره می کنید:

*: ورودیهای تابع:k تعداد اعضا، h که اعضایی که تاکنون انتخاب شده اند می باشد،m عدد مورد نظر، Collection از نوع لیست که اعضای مجموعه را در بر دارد.
- لسیت پویای «یافته» با اعضای عددی n بیتی را در نظر بگیر.

1- آیا k از 1 بزرگتر است؟
*-بلی: برو به 1
*-خیر: بره به 5
2- TempCollection را مانند Collecion بساز.
3- برای اندیس 1 الی k :
**1- عضو i ام Collection را از TempCollection پاک کن.
**2- تابع را با پارامترهای تعداد k-i، اعضای انتخاب شده <span dir=ltr>h shl (i-1)+1</span> ،عدد جدید <span dir=ltr>m-Collection[i]</span> و TempCollection فراخوانی کن.
4- باز گرد.
5- آیا <span dir=ltr>TempCollection[1]</span> برابر m است؟
*بلی: h shl 1+1 را به «یافته» اضافه کن.
*خیر: بازگرد.

aliprogramer
دوشنبه 26 دی 1384, 02:29 صبح
جواب سادس

فقط کافیه که اعداد 1 تا n رو یکی به یکی تبدیل به دودو یی کنی و ارقام متناظر با 1 های موجود در عدد رو به خروجی بدی

اَرژنگ
دوشنبه 26 دی 1384, 03:18 صبح
جواب سادس

فقط کافیه که اعداد 1 تا n رو یکی به یکی تبدیل به دودو یی کنی و ارقام متناظر با 1 های موجود در عدد رو به خروجی بدی
منظورتون از 1 تا n,



(2^n)-1


، مگر نه؟
روشه تمیزیه!

اَرژنگ
دوشنبه 26 دی 1384, 03:44 صبح
لطفا به من کمک کنید...
می خواهم یک برنامه به زبان c بنویسم بطوری که کلیه زیرمجموعه های یک
مجموعه n عضوی که مجموع عضوهای آن برابر عدد m باشد را پیدا کند.
http://mathworld.wolfram.com/SubsetSumProblem.html

m_niknikniknik
شنبه 25 فروردین 1386, 22:08 عصر
سلام. من به الگوریتم یافتن زیرمجموعه های یک مجموعه n عضوی که در یک حلقه : ابتدا زیرمجموعه های تک عضوی سپس دو عضوی , ...را به دست آورد (به زبان #c )نیاز دارم.
اگر ممکنه منو راهنمایی کنین.

majid.fe
یک شنبه 25 اسفند 1392, 00:14 صبح
به وبلاگ زیر هم یه سری بزنین. شاید به دردتون بخوره.
http://decoding.blogfa.com/