برنامه ای برای نشان دادن تمام زیر مجموعه های یک مجموعه - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

وبـــلاگ هــفت خــط کــد


آموزش های برنامه نویسی
۳۱ نفر آنلاین
۰ عضو و ۳۱ مهمان در سایت حاضرند

برنامه ای برای نشان دادن تمام زیر مجموعه های یک مجموعه

0 امتیاز
187 بازدید

با سلام.برنامه ای می خوام که تمام زیر مجموعه های یک مجموعه n  عضوی را  به صورت بازگشتی و برنامه ای هم به صورت غیر بازگشتی نشان دهد . تعداد  اعضای مجموعه حداکثر 30 تا  می باشد. محتویات مجموعه ها به ازای هر n  به صورت زیر می باشد.یعنی ما می دانیم مجوعه چه عضو هایی دارد.

{1} : n=1

{1,2}: n=2

{1,2,3} n=3

{1,2,3,4}: n=4

... 

ببخشید بقیه توضیحاتو انگلیش گداشتم.آخه از یه سایت خارجی پرسیدم جواب ندادند.دیگه حوصله نداشتم اینجا دوباره فارسی توضیح بدم.خودمم نفهمیدم چی گفتم!

my algorithm that is for per subset exists one  number. these numbers are form 0 until (2^n)-1.allow me explain it with a example.
n=3
{ }     000     0
{1}    100     4
{2}     010    2
{3}     001    1
{1,2}  110    6
{1,3}  101    5
{2,3}   011   3
{1,2,3} 111  7
The third column show some number(fn) that i use in code.now we know per number of subset has to state(sn).0 or 1. this means it exists or not exists.now  i  should match fn and sn.and suggested way is use
#include <iostream>
using namespace std;
#include <conio.h>
#include <string.h>
int pow(int a,int b)
{
	int p=1;
	for(int i=0;i<b;i++)
		p=p*a;
	return p;
}
struct ar
{
	int  binary;
	int content;
};
int main()

{
	int testcase=0;
	int n;
	ar *a;
	a=new ar [2000];
	cin>>testcase;
	int i=0;
	while(i<testcase)
	{
		cin>>n;
		for(int j=0,k=1;j<n;j++,k++)
		{
			a[j].content=k;
			a[j].binary=2;
		}

	
	for(int p=0;p<pow(2,n)-1;p++)
	{
		cout<<'{';
	for(int m=0;m<n;m++)
	{
	  
		int b;
		b=a[m].binary&p;
		if(b==1)
		cout<<a[i].content<<' ';

	}
	  cout<<'}';
	}
	
	cout<<endl;
	i++;
	}
	return 0;
}
of bitwise operators.(operator &).and now i don't know what do and  thing with else thing

 

سوال شده بهمن 16, 1392  بوسیله ی nazafrin (امتیاز 13)   2
خودتون حوصله سوال پرسیدنو ندارید ما با چه حوصله ای جواب بدیم .

2 پاسخ

+4 امتیاز
 
بهترین پاسخ

با همون الگوریتم خودتون (یعنی بررسی در حالت باینری ) میشه درستش کرد : 

معمولی  : 

#include <iostream>
using namespace std;
int a[1000000],n;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<(1<<n);i++)
    {
        for(int j=0;j<=n;j++)
            if(i&(1<<j))
                cout << a[j] << ' ' ;
        cout << '\n' ;
    }
    return 0;
}

 

بازگشتی : 

#include <iostream>

using namespace std;

const int MAXN=10000;
int n,a[MAXN],x[MAXN];
void print(int nu[],int x[])
{
    for(int i=0;i<n;i++)
        if(x[i]==1)
            cout<<nu[i]<<' ';
    cout<<'\n';
}
void subset(int a[],int n)
{
    if(!n){print(a,x) ; return ;}
    x[n-1] = 0 ;
    subset(a,n-1) ;
    x[n-1] = 1 ;
    subset(a,n-1) ;
}
int main()
{
    cin >> n ;
    for(int i = 0 ; i < n ; i++)
        cin >> a[i] ;
    subset(a,n) ;
    return 0;
}

 

پاسخ داده شده بهمن 30, 1392 بوسیله ی amirhossein (امتیاز 157)   2
الگوریتمشو میشه توضیح بدین چرا اینکارو کردین؟
+1 امتیاز

سلام فرض کن برای همون 3 عضوی می خوای با روش زیر  کار کن :

0 تا 0 بردار با 3 تا 1 جایگشتشو حساب کن

1 دونه 0 بردار با 2 تا 1 جایگشتشو حساب کن.

2 تا 0 بردار با یک دونه 1 جایگشتشو حساب کن

3 تا 0 بردار با 0 تا 1 جایگشتشو حساب کن .

برای 4 عضو

0 تا 0 بردار با4  تا 1 جایگشتشو حساب کن

1 دونه 0 بردار با 3 تا 1 جایگشتشو حساب کن

و...

 

برای جایگشت هم از این سوال استفاده کن : جایگشت با حفظ ترتیب حروف

 

پاسخ داده شده بهمن 17, 1392 بوسیله ی BlueBlade (امتیاز 15,712)   13 16 85
...