【问题描述】对于给定的正整数n（n>=1），求1~n构成的集合的幂集（即由1~n的集合中所有子集构成的集合，包括全集和空集）
直接穷举法
设集合a[0..2]={1.2.3},其所有集合元素对应的二进制位及其十进制数如表所示。
集合元素 对应的二进制位 对应的十进制数 {} 000 0 {1} 100 4 {2} 010 2 {1,2} 110 6 {3} 001 1 {1,3} 101 5 {2,3} 011 3 {1,2,3} 111 7其实就是输出{1,2,3}在0~7所表示的二进制的所在的1的位置。
源程序如下：
#include <iostream> using namespace std; //二进制数变化 void inc(int b[],int n) { for (int i = 0; i < n;i++) { if (b[i]) { //将元素1改为0 b[i] = 0; } else { //将元素0改为1并退出for循环 b[i] = 1; break; } } } //求幂集 void PSet(int a[],int b[],int n) { int i, k; int pw = (int)pow(2, n); //求2的n次方 cout << "1~"<<n<<"的幂集为：" << endl; for ( i = 0; i < pw;i++) { cout << "{"; for (k = 0; k < n;k++) { if (b[k]) { //输出二进制位中为1的所对应的{1,2,3..n}所在的位置的数 cout <<" "<< a[k]; } } cout << "}"; inc(b, n); //变更二进制数 } cout << endl; } int main() { int n = 0; cout << "请输入n的数" << endl; cin >> n; int *a=new int [n]; //用数组a表示1-n的十进制数 int *b = new int[n]; //用数组b表示二进制位 for (int i = 0; i < n;i++) { a[i] = i + 1; //a初始化为1,2,3..n b[i] = 0; //b初始化为{0,0,0..} } PSet(a,b,n); system("pause"); return 0; }输出结果为：
请输入n的数 5 1~5的幂集为： {}{ 1}{ 2}{ 1 2}{ 3}{ 1 3}{ 2 3}{ 1 2 3}{ 4}{ 1 4}{ 2 4}{ 1 2 4}{ 3 4}{ 1 3 4}{ 2 3 4}{ 1 2 3 4}{ 5}{ 1 5}{ 2 5}{ 1 2 5}{ 3 5}{ 1 3 5}{ 2 3 5}{ 1 2 3 5}{ 4 5}{ 1 4 5}{ 2 4 5}{ 1 2 4 5}{ 3 4 5}{ 1 3 4 5}{ 2 3 4 5}{ 1 2 3 4 5} 请按任意键继续. . .
【算法分析】
算法中pw循环次，不考虑幂集输出，inc()的时间复杂度为O(n)，所以算法的时间复杂度为O(n*)，属于指数级的算法。
