نمایش نتایج 1 تا 6 از 6

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

  1. #1
    کاربر دائمی آواتار fazel-d
    تاریخ عضویت
    آذر 1386
    محل زندگی
    بورکینافاسو
    پست
    399

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

    منطق به کار گرفته شده در الگوریتم زیر چیست؟
    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;
    }

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


  2. #2
    کاربر دائمی آواتار shahmohammadi
    تاریخ عضویت
    فروردین 1390
    محل زندگی
    کلیبر
    پست
    475

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

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

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

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

    موفق باشید.

  3. #3
    کاربر دائمی آواتار shahmohammadi
    تاریخ عضویت
    فروردین 1390
    محل زندگی
    کلیبر
    پست
    475

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

    در ضمن می تونین خط آخر حلقه رو هم به صورت زیر بنویسین:
    printf("%c}\n",8);


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

  4. #4
    کاربر دائمی آواتار fazel-d
    تاریخ عضویت
    آذر 1386
    محل زندگی
    بورکینافاسو
    پست
    399

    Thumbs down نقل قول: تحلیل الگوریتم ایجاد زیر مجموعه ای از یک مجموعه

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

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

  5. #5
    کاربر دائمی آواتار shahmohammadi
    تاریخ عضویت
    فروردین 1390
    محل زندگی
    کلیبر
    پست
    475

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

    نقل قول نوشته شده توسط fazel-d مشاهده تاپیک
    دقیقا مساله من هم همین جاست که چرا از باقیمانده تقسیم برای پیدا کردن اندیس آرایه استفاده می کنه.

    منطق ریاضیاتی اون چیه؟ آیا همون تبدیل عدد decimal به binary هست؟ فکر کنم همین طور باشه!
    وقتی عددی فرد باشه، بیت اولش 1 و اگه زوج باشه 0 است. به همین دلیل از باقیمانده تقسیم بر 2 استفاده کرده.

  6. #6
    کاربر دائمی آواتار fazel-d
    تاریخ عضویت
    آذر 1386
    محل زندگی
    بورکینافاسو
    پست
    399

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

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

    مثلا اگر ما 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} است

برچسب های این تاپیک

قوانین ایجاد تاپیک در تالار

  • شما نمی توانید تاپیک جدید ایجاد کنید
  • شما نمی توانید به تاپیک ها پاسخ دهید
  • شما نمی توانید ضمیمه ارسال کنید
  • شما نمی توانید پاسخ هایتان را ویرایش کنید
  •