韩国网站怎么打开,下载登录微信,深圳博大建设集团网站,360网站兼容模式转载自#xff1a;http://blog.csdn.net/yzl20092856/article/details/39995085
求集合的所有子集的算法
对于任意集合A#xff0c;元素个数为n#xff08;空集n0#xff09;#xff0c;其所有子集的个数为2^n个
如集合A{a,b,c},其子集个数为8#xff1b;对于任意一个…转载自http://blog.csdn.net/yzl20092856/article/details/39995085
求集合的所有子集的算法
对于任意集合A元素个数为n空集n0其所有子集的个数为2^n个
如集合A{a,b,c},其子集个数为8对于任意一个元素在每个子集中
要么存在要么不存在对应关系是
a-1或a-0
b-1或b-0
c-1或c-0
映射为子集
(a,b,c)
(1,1,1)-(a,b,c)
(1,1,0)-(a,b )
(1,0,1)-(a, c)
(1,0,0)-(a )
(0,1,1)-( b,c)
(0,1,0)-( b )
(0,0,1)-( c)
(0,0,0)-(表示空集)
算法1
观察以上规律与计算机中数据存储方式相似故可以通过一个整型数int与
集合映射000...000 ~ 111...1110表示有1表示无反之亦可通过该整型数
逐次增1可遍历获取所有的数即获取集合的相应子集。
在这里提一下使用这种方式映射集合在进行集合运算时相当简便如
交运算对应按位与{a,b,c}交{a,b}得{a,b}---111110110
并运算对应按位或|
差运算对应~。
算法2
设函数f(n)2^n (n0)有如下递推关系f(n)2*f(n-1)2*(2*f(n-2))
由此可知求集合子集的算法可以用递归的方式实现对于每个元素用一个映射列表marks标记其
在子集中的有无
很显然在集合元素个数少的情况下算法1优于算法2因为只需通过加法运算便能映射
出子集而算法2要递归调用函数速度稍慢。但算法1有一个严重缺陷集合的个数不能大于在
计算机中一个整型数的位数一般计算机中整型数的为32位。对于算法2就没这样限制。 1. templateclass T
2. void print(T a[],int mark,int length)
3. {
4. bool allZerotrue;
5. int limit1length;
6. for(int i0;ilength;i)
7. {
8. if(((1i)mark)!0) //mark第i1位为1表示取该元素
9. {
10. allZerofalse;
11. couta[i] ;
12. }
13. }
14. if(allZerotrue)
15. {
16. cout;
17. }
18. coutendl;
19. }
20.
21. templateclass T
22. void subset(T a[],int length)
23. {
24. if(length31) return;
25. int lowFlag0; //对应000...000
26. int highFlag(1length)-1; //对应111...111
27. for(int ilowFlag;ihighFlag;i)
28. {
29. print(a,i,length);
30. }
31.
32. } 算法二templateclass T
void print(T a[],bool marks[],int length)
{ bool allFalsetrue; for(int i0;ilength;i) { if(marks[i]true) { allfalsefalse; couta[i] ; } } if(allFalsetrue) { cout; } coutendl; } templateclass T
void subset(T a[],bool marks[],int m,int n,int length)
{ if(mn) { print(a,marks,length); } else { marks[m]true; subset(a,marks,m1,n,length); marks[m]false; subset(a,marks,m1,n,length); } }
