۱۹-مهر-۱۳۸۶, ۱۱:۵۰:۲۷
۱۹-مهر-۱۳۸۶, ۱۳:۱۸:۲۵
من برای اینکار یک راه حل ارائه میکنم و شما خودت خیلی راحت الگوریتمش رو بنویس :
مثال ---> فکر کن ما سه تا عضو توی مجموعه داریم . خوب برای بدست آوردن تمام زیر مجموعه ها :
1 - میدونیم که زیر مجموعه های یک مجوعه k عضوی 2 به توان k زیر مجموعه دارند . پس میتونیم از خاصیت مشابهی که در اعداد مبنای 2 وجود داره استفاده کنیم . پس ابتدا تمام اعداد 3 بیتی ( بخاطر اینکه 3 عضو داریم ) رو در مبنای 2 ( باینری ) بدست میاریم . میشه 2 به توان 3 یعنی 8 تا عدد باینری بشکل زیر :
2 - حالا به اعداد در مبنای 2 دقت کن و به این شکل برو جلو . رقم اول از سمت چپ نشانه عضو اول مجوعه ، رقم دوم عضو دوم و رقم سوم نشانگر عضو سوم مجموعه شماست . هر جا که صفر بود یعنی اون عضو توی زیرمجموعه نیست و هر جا یک بود یعنی هست !
این یعنی مثلا 000 هیچ کدام از عضو های مجموعه پس نشانگر زیر مجموعه تهی هست . ( تهی زیر مجموعه هر مجموعه ای هست )
یا 011 یعنی زیر مجوعه ای شامل عضو دوم و سوم مجموعه اصلی . یا 111 یعنی زیر مجموعه ای شامل تمام عضوهای اول و دوم و سوم ( هر مجموعه ای زیر مجموعه خودش هم هست ) و ..... الی آخر !
بگذار مثال هم بزنم تا بهتر روشن بشه . مجموعه ای داریم بشکل { 3,15,11 }
خب زیر مجموعه ای این مجموعه رو از روی همون کد ها اینطور میشه بدست آورد :
مثال ---> فکر کن ما سه تا عضو توی مجموعه داریم . خوب برای بدست آوردن تمام زیر مجموعه ها :
1 - میدونیم که زیر مجموعه های یک مجوعه k عضوی 2 به توان k زیر مجموعه دارند . پس میتونیم از خاصیت مشابهی که در اعداد مبنای 2 وجود داره استفاده کنیم . پس ابتدا تمام اعداد 3 بیتی ( بخاطر اینکه 3 عضو داریم ) رو در مبنای 2 ( باینری ) بدست میاریم . میشه 2 به توان 3 یعنی 8 تا عدد باینری بشکل زیر :
کد:
Dec Binary
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 1112 - حالا به اعداد در مبنای 2 دقت کن و به این شکل برو جلو . رقم اول از سمت چپ نشانه عضو اول مجوعه ، رقم دوم عضو دوم و رقم سوم نشانگر عضو سوم مجموعه شماست . هر جا که صفر بود یعنی اون عضو توی زیرمجموعه نیست و هر جا یک بود یعنی هست !
این یعنی مثلا 000 هیچ کدام از عضو های مجموعه پس نشانگر زیر مجموعه تهی هست . ( تهی زیر مجموعه هر مجموعه ای هست )
یا 011 یعنی زیر مجوعه ای شامل عضو دوم و سوم مجموعه اصلی . یا 111 یعنی زیر مجموعه ای شامل تمام عضوهای اول و دوم و سوم ( هر مجموعه ای زیر مجموعه خودش هم هست ) و ..... الی آخر !
بگذار مثال هم بزنم تا بهتر روشن بشه . مجموعه ای داریم بشکل { 3,15,11 }
خب زیر مجموعه ای این مجموعه رو از روی همون کد ها اینطور میشه بدست آورد :
کد:
مجموعه تهی = 000
{11} = 001
{15} = 010
{11 , 15 } = 011
{3} = 100
{11 , 3 } = 101
{ 15 , 3 } = 110
{ 3,15,11 } = 111