مهارت الگوریتم نویسیتون رو به خودتون ثابت کنید

[Sajjad1364]

با سلام
سؤال از این قراره که یه مجموعه داریم و میخایم تمام زیر مجموعه هاشو بدست بیاریم
مثال 1: مجموعه {1,2,3} زیر مجموعه هاش میشن

{1}, {2}, {3} , {1,2}, {1,3} , {2,3} ,{1,2,3} ومجموعه تهی که جمعا هشت تا میشه

مثال 2: مجموعه {1,2,3,4,5} که زیر مجموعه هاش از این قراره

{1}, {2}, {3} {4}, {5} , {1,2} , {1,3} {1,4} , {1,5} , {2,3}, {2,4}, {2,5} , {3,4} ,{3,5} ,{4,5}

{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5}

{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5} , {2,3,4,5}, {1,2,3,4,5} وآخرین زیر مجموعه تهی هستش جمعا 32

راهنمایی:همونطور که فهمیدید تعداد زیر مجموعه ها با احتساب زیر مجموعه تهی برابر با: دو بتوان N میباشد
N تعداد اعضا میباشد .از این فرمول برای درستی برنامه والگوریتمتون استفاده کنید.

در ضمن این مساله فقط برای اثبات تواناییهاتون به خود شماست و اصلا جنبه مسابقه ای نداره .

 

[Arash_j13]

الان کجا این مهارت الگوریتم نمی سی می خواد یکم ریاضی بلد باشید می تونید خیلی راحت یه شمارش رو مجموعه توانی پیدا کنید بعد خیلی راحت همون طور که می شمرید اعضار رو هم چاپ کیند یا اینکه تمام عدد های بین صفر تا n رو به صورت باینری بنویسید هر رقم نشون دهنده یک عضوه یک بودن یعنی هست و صفر بودن یعنی نیست بعد خیلی راحت تر از اونی که به نظر می رسه مسئله حل شده

 

[ARTA_ADOBE CO]

آرش جان با باینری مینویسی (باC )؟

 

[Arash_j13]

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

 

[ARTA_ADOBE CO]

خوب منم منظورم همین بود...

 

[Sajjad1364]

با سلام

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

البته درسته که با استفاده از ریاضی خیلی آسون میشه ولی بعضی مواقع نیاز هست از ریاضی استفاده نکنید.

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

 

[Arash_j13]

بدون ریاضی که نمی شه برای یه مسئله که ذاتا ریاضی هست الگوریتم نوشت
این پیاده سازی همون الگوریتمی هست که توضیح دادم (با کمک ارقام باینری)

#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

template <typename T>
void subset(const vector<T>&);

int power(int ,unsigned int);
char * D2B(int,char*);
int main()
{
	cout<<"count :";
	int count;
	cin>>count;
	vector<int> set(count);
	for(int i=0 ; i < count  ; cin>>set[i++]);
    subset(set);
	system("pause");
	return EXIT_SUCCESS;
}


char *D2B(int n , char *b)
{
    ltoa(n,b,2);
    return b;

}
template <typename T>
void subset(const vector<T> &r)
{
    char buffer[100];
    int k=1;
    long limit=power(2,r.size());
    for (int i=0 ; i < limit ; ++i)
    {
        cout<<endl<<k++<<" : ";
        D2B(i,buffer);
        char *p;
        for(p=buffer ; *p ;++p);
        --p;
        for(int j = 0 ;  p>=buffer; ++j,--p)
            if(*p=='1')
                cout<<r[j]<<"  ";
    }
    cout<<endl;

}

int power(int x,unsigned int n)
{
    if(n==0)
        return 1;
    return x*power(x,n-1);
}