当前位置 博文首页 > m0_53521757的博客：蛮力法求解幂集问题
直接穷举求解，将1-n存放到数组a中，求解问题变为构造集合a的所有子集合。设集合a[0…2]={1,2,3},其所有集合元素对应的二进制位及其十进制位如下表所示。
| 集合元素 | 对应的二进制位 | 对应的十进制位 |
|---|---|---|
| { } | — | — |
| {1} | 001 | 1 |
| {2} | 010 | 2 |
| {1,2} | 011 | 3 |
| {3} | 100 | 4 |
| {1,3} | 101 | 5 |
| {2,3} | 110 | 6 |
| {1,2,3} | 111 | 7 |
因此对于含有n（n≥1）个元素的集合a，求幂集的过程如下
for(i=0;i<2^n;i++) //穷举a的所有集合元素并输出
{ 将i转换为二进制b；
输出b中为1的位对应的a元素构成的一个集合元素；
}
采用直接穷举法求a={1,2，3}的幂集的完整程序如下：
//蛮力法求解幂集问题
#include <stdio.h>
#include <math.h>
#define MaxN 10
void inc(int b[],int n) //将b表示的二进制数增1
{
for(int i=0;i<n;i++) //遍历数组b
{
if(b[i]==1) //将元素1改为0
b[i]=0;
else
{
b[i]=1; //将元素改为0改为1并退出for循环（因为只增加1）
break;
}
}
}
void PSet(int a[],int b[],int n) //求幂集
{
int i,k;
int pw=pow((float)2,n); //求2^n
printf("1-%d的幂集：\n",n);
for(i=0;i<pw;i++) //执行2^n
{
printf("{ ");
for(k=0;k<n;k++) //执行n次
{
if(b[k]==1)
printf("%d ",a[k]);
}
printf(" } ");
inc(b,n); //b表示的二进制数增1
}
printf("\n");
}
void main()
{
int n=3;
int a[MaxN],b[MaxN];
for(int i=0;i<n;i++)
{
a[i]=i+1; //a初始化为{1,2,3}
b[i]=0; //b初始化为{0,0,0}
}
PSet(a,b,n);
}
输出结果
