سوال در مورد مجموعه و زیر مجموعه....

[BABANOEL]

با سلام خدمت دوستان

من چند روزی هست که میخوام برنامه ای بنویسم برای زیر مجموعه ها اما روش و الگوریتن خاصی بلد نیستم و به ذهنم نمیرسه
برنامه ای که مجموعه ی صحیح و مثبت اعداد از ورودی دریافت کن و زیر مجموعه ی اونها رو چاپ کنه!!!
یعنی مجموع ای رو از ورودی دریافت و به زیر مجموعه هاش افرازش کنه و زیر مجموعه هاشو از تک عضوی و دو عضوی و.... و تهی چاپ کنه.
لطفا منو کمکم کنید و اگر هم برنامه ای دارید برام بذارید ممنون میشم البته سورسشو

[shahmohammadi]

سلام.
بهتر بود توی قسمت الگوریتم سوالتون رو مطرح می کردین.

یک روش استفاده از روش backtrack هست که به صورت الفبایی چاپ می کنه، یک روش استفاده از شمارش باینری هست، اگر هم بخاهیم اول زیر مجموعه های تک عضوی بعد دو عضوب بعد...رو چاپ کنیم باید در یک حلقه مثلا i که از 1 تا تعداد اعداد یعنی n پیش می ره در هر گامش ترکیبات i شی از n شی رو بدست بیاریم:
در مورد روش باینری قبلا بحث شده پس من روش اول رو توضیح می دم.
backtrack:
الگوریتم های بک ترک عموما به شکل زیر هستند و برای مسائل زیادی کار برد دارند.

initialize;

repeat

if current partial solution is extendable then extend else reduce;

if current solution is acceptable then report it;

until search is over

حالت extend زمانی اتفاق می افتد که ما یک قدم به جلو برویم (الان مثالشو می بینید)، و حالت reduce زمانی اتفاق می افتد که ما نتوانیم به جلو برویم.
برای اینکه با این الگورم مجموعه زیر مجموعه ها رو بدست بیاریم به روش زیر عمل می کنیم.
فرض کنید 5 تا عضو داریم. 1و2و3و4و5. (می تونید هر کدوم رو اندیس فرض کنید اینطوری عمومیت مساله حفض میشه یعنی هر جا گفتیم 5 رو چاپ کن تو آرایه بیاییم عنصرو 5 ام رو چاپ کنیم.). زیر مجموعه هاشو به طور الفبایی مرتب می کنیم. (انگار یه سری اسم رو به تربیت الفبا مرتب می کنیم):

1   12   123   1234   12345

               1235

         124   1245

         125

    13   134   1345

         135

    14   145

    15

2   23   234   2345

         235

    24   245

    25

3   34   345

    35

4   45

5

الگوریم ما باید بیاد اینها رو یکی یکی چاپ کنه.
حالت extend یا گسترش زمانی اتفاق می افته که در یه سطر پیش می ریم. یعنی آخرین عضو زیر مجموعه کوچکتر از 5 باشه.
حالت reduce یا کاهش زمانی اتفاق می افته که یک پایین بیاییم. یعنی آخرین عضو زیر مجموعه برابر با 5 بشه.
الگوریتم:

read( n); r ← 0; x[r] ← 0;

repeat

if x[r]<n then extend else reduce;

print out x[1], x[2], . . . , x[r]

until x[1] = n

extend ≡ {x[r+1] ← x[r] + 1; r ← r + 1}

reduce ≡ {r ← r − 1; x[r] ← x[r] + 1}

[BABANOEL]

مرسی از شما
میشه برنامه ی کلی او برای n ورودی هم بنویسید؟
و اگر زحمتی نیست باینری هم توضیح بدید البته با برنامه اش...
خیلی ممنون

[shahmohammadi]

میشه برنامه ی کلی او برای n ورودی هم بنویسید؟

چند تا انتصاب و جمع و چاپ ساده می خاد:

#include <cstdlib>

#include <iostream>



using namespace std;



int X[11];



int main(int argc, char *argv[])

{

    int n,r=0;

    cout<<"Enter Number Of Members in The Set: (<10) ";

    cin>>n;

    X[r]=r;

    do{

       if(X[r]<n){

          X[r+1]=X[r]+1;

          r++;}

       else{

          r--;

          X[r]++;}



       cout<<"{";

       for(int i=1;i<=r;i++)

       {

         cout<<X[i];

         (i!=r)?cout<<',':cout<<'}';

       }

       cout<<"\n";

    }while(X[1]!=n);

    system("PAUSE");

    return EXIT_SUCCESS;

}

روش شمارشی یا باینری هم به صورت زیر هست:
فرض کنید یه مجموعه سه عضوی داریم: {a,b,c}
می آییم از 0 تا (2 به توان 3 ) رو می شمریم. (داخل حلقه).
در هر قدم از حلقه می آییم بیت هاشو بررسی می کنیم. اگر بیت اول 0 باشه یعنی عضو اول در زیر مجموعه نیست. اگر یک باشه یعنی عضو اول عضو زیر مجموعه هست. و به این ترتیت تمام بیت هاشو بررسی می کنیم.
اعداد زیر در گام های مختلف به ترتیب می آن و زیر مجموعه هایی که باهاشون نوشتم رو نشون می دن:
000 زیر مجموعه تهی
001 {a}
010 {b}
011 {a,b}
100 {c}
101 {a,c}
110 {b,c}
111 {a,b,c}

این هم زیاد سخت نیست. اما اگر در نوشتنش دچار مشکل شدید می تونیم دوباره کمک کنیم.

[BABANOEL]

ممنون دوست خوبم.
اما مشکل من توی نوشتن این برنامه این هست که نمیدونم چطوری این بیتها رو به آرایه نسبت بدم و موقعیت یکهاشو تشخیص بدم مثلا خونه ی دهم و 8 و 3 آرایه یک شده حالا چطور خونه های متناظرشون رو نمایش بدم؟
اگه لطف کنید برنامشو واسم بذارید ممنون میشم و یا اینکه توضیحی بدید از توضیح خوبتون درباره ی الگوریتم بالا هم ممنون خیلی ساده و کامل توضیح داده بودید و من متوجه شدم

[shahmohammadi]

تو این برنامه فرض کردم که مجموعه ی من شامل اعداد 0 تا n هست. اگه بخایم یه مجموعه از کاربر بگیرید می تونید به جای چاپ i مثلا a[i] رو چاپ کنید. یعنی عضو iام:

#include <cstdlib>

#include <conio.h>

#include <iostream>

#include <math.h>



using namespace std;



int main(int argc, char *argv[])

{

    int count,Max;

    int n,i,temp;

    cout<<"Enter Number Of Members In Set:(<16) ";

    cin>>n;

    

    Max=(int)pow(2,n);

    for(count=0;count<Max;count++)

    {

       temp=count;

       for(i=0;temp>0;temp/=2,i++)

        if(temp%2==1)

           cout<<i<<", ";

       cout<<"\n"    ;

    }

    getch();

    return 0;

}

[BABANOEL]

باز هم از زحماتتون ممنونم