تحلیل الگوریتم ایجاد زیر مجموعه ای از یک مجموعه

[fazel-d]

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

int main()

{

int i,j,m,n;

clrscr();

printf("enter number : ");

scanf("%d",&n);

char a[100];

for(i=0;i<n;i++)

{

  printf("x%d=",i+1);

  scanf("%d",&a[i]);

}

for(j=0;j<pow(2,n);j++)

{

   m=j;

   printf("{");

   for(i=0;i<=j;i++)

    {

      if(m%2==1)

       {

         printf("%d",a[i]);

         printf(",");

         m=(m-1)/2;

       }

      else m=m/2;

    }

   printf("}\n");

}

getch();

return 0;

}

در واقع علت اینکه از فرد بودن عدد برای بدست آوردن اندیس آرایه استفاده می کنه چیست؟ چه رابطه بین الگوریتم به کار رفته با بدست آوردن زیر مجموعه وجود دارد؟

[shahmohammadi]

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

برای مثال:
وقتی مجموعه مون پنج عضو داشته باشه تمام اعداد پنج بیتی (از 0 تا یکی کمتر از 2 به توان 5) رو می شمریم و هر کدوم رو متناظر با یه زیر مجموعه می دونیم.
هر بیت از این عدد معادل یه عضو از مجموعه است که وقتی صفر باشه یعنی عضو در زیر مجموعه نیست و وقتی 1 باشه یعنی هست (و چاپش می کنیم).

در این برنامه حلقه فور متغیر جی برای شمارش اعداد است و حلقه داخلیش بیت های عدد j رو بررسی می کنه اگه بیتی یک بود (if(m%2==1)) عضو متناظر با اون بیت رو چاپ می کنه و در غیر این صورت m رو تقسیم بر دو می کنه که این کار بیت های با لاتر رو یکی به جلو می آره تا در دفعه بعد اونا بررسی شن.

موفق باشید.

[shahmohammadi]

در ضمن می تونین خط آخر حلقه رو هم به صورت زیر بنویسین:

printf("%c}\n",8);

کاراکتر 8 همون بک اسلشه که ویر گول آخرین عضو رو پاک می کنه.

[fazel-d]

در این برنامه حلقه فور متغیر جی برای شمارش اعداد است و حلقه داخلیش بیت های عدد j رو بررسی می کنه اگه بیتی یک بود (if(m%2==1)) عضو متناظر با اون بیت رو چاپ می کنه

دقیقا مساله من هم همین جاست که چرا از باقیمانده تقسیم برای پیدا کردن اندیس آرایه استفاده می کنه.

منطق ریاضیاتی اون چیه؟ آیا همون تبدیل عدد decimal به binary هست؟ فکر کنم همین طور باشه!

[shahmohammadi]

دقیقا مساله من هم همین جاست که چرا از باقیمانده تقسیم برای پیدا کردن اندیس آرایه استفاده می کنه.

منطق ریاضیاتی اون چیه؟ آیا همون تبدیل عدد decimal به binary هست؟ فکر کنم همین طور باشه!

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

[fazel-d]

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

مثلا اگر ما 3=n در نظر بگیریم در آنشورت ما یک آرایه 3 خانه ای داریم از اعداد 1 تا 3 که در واقع این اعداد همان ترکیب های ما را می سازند. تعداد کلیه ی ترکیبات ما 3^2 است( 2 به توان 3==>8 تا ترکیب). این قضیه برای یک مجموعه n عضوی برابر با 2 به توان n است.

-------
در این لحظه یه سری به مدار منطقی می زنیم.
اگر خاطرتون باشه یه گیت منطقی می تونست n ورودی داشته باشه با یک خروجی.! حال اگر ورودی گیت ما برابر با 3 باشه آنگاه ما 8 ترکیب متفاوت از صفرها و یکها داریم.
A B C
0 0 0
0 0 1
0 1 0
...
...
1 1 1
------

ما نیز با استناد بر قضیه مذکور، ترکیبات یک مجموعه 3 عضوی را می سازیم
اگر ما نیز به جای A,B,C به ترتیب اعداد 1و2و3 قرار دهیم (A=1 , B=2, C=3) آنگاه می توانیم این ترکیبات را بسازیم. چگونه؟
به این ترتیب که از روش تبدیل عدد Decimal به Binary استفاده می کنیم یعنی همان تقسیم بر 2

به عنوان مثال:
عدد صفر که در Binary mode برابر با (0 0 0) است از تقسیم 0 بر 2 حاصل می شود و چون که باقیمانده حاصل از تقسیم صفر است پس هیچ انتخابی از 1 یا 2 و یا 3 وجود ندارد که این، همان زیر مجموعه تهی است.

عدد یک را مد نظر بگیرید(1 0 0)
زمانی که عدد یک می خواهد تبدیل به باینری شود وارد حلقه for داخلی می شود که شرط

      if(m%2==1)

       {

         printf("%d",a[i]);

         printf(",");

         m=(m-1)/2;

       }

      else m=m/2;

بررسی می کند که آیا باقیمانده یک است آنگاه مقدار i متناظر با آن در آرایه یک عضوی از زیر مجموعه را برمیگرداند. در این مثال زمانی که 0=i است باقیمانده 1 بر 2 برابر با یک است. پس اولین عضو آرایه (array[0])به عنوان اولین عضو زیرمجموعه انتخاب می شود


مثالی دیگر: عدد 3 (1 1 0)
A B C
0 1 1
یا به عبارتی
1 2 3
1 1 0

زمانی که 0=i است 2%3 برابر با یک است پس Arr[0 انتخاب می شود( همان عدد یک درون آرایه). مقدار خارج قسمت به جای عدد 3 می نشیند
حال وقتی 1=i است 2%1 برابر یا یک و Arr[1 انتخاب می شود و
2=i شود 2%0 برابر با صفر است که وارد قسمت IF نمی شود.

نتیجه اینکه عدد 3 یعنی سومین ترکیب ما. یعنی سومین زیرمجموعه برابر با {1,2} است