本人是一名大一计算机小白,想从现在开始学习ACM的一些知识,不求取得特别厉害的奖项,只希望在编程能力上得到提升,我会在博客上记录一些题目,主要就当作记笔记啦,要是有人看的话,也希望和同道中人一起学习交流,相互促进!!可能目前写的内容比较水,希望大家谅解!!
关于子集生成问题 问题简述关于子集的生成问题,在直观上可以理解为对原有集合中元素的选择,用1、0表示在子集中有无该元素,那么任一集合A的子集个数即为2^|A|个,可以将其所有子集用有穷01序列表示。
c++实现要打印出集合的所有子集,就需要遍历该集合的所有有穷01序列(变量i从0到2^|A|-1),再将每一个01序列中数位上为1的元素打印出来即可。故可使用一个二重循环,首先遍历所有01序列,然后比较二进制各个数位上是1还是0判断是否打印该元素。
c++代码以字符串集合为例。
#include
using namespace std;
void print_subset(int n,string a[])
{
for(int i=0;i<(1<<n);i++)//i:0-2^n,每个i的二进制数对应一个子集,一次打印一个子集
{
for(int j=0;j<n;j++) //打印一个子集
if(i&(1<<j)) //从i的最低位开始逐个检查每一位 若为1 打印
cout<<a[j]<<" ";
cout<>n;//集合元素个数
string a[n];
for(int i=0;i>a[i];//输入集合元素
print_subset(n,a);
}