学步园

1. 递归求解

// Virtual.cpp : 定义控制台应用程序的入口点。<br /> #include "stdafx.h"<br /> #include <iostream><br /> using namespace std;<br /> /*<br /> 求幂积最简单的<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>思想就是从最后一个元素倒着来遍历所有元素，比如说最后一个就是自己"c" ；<br /> 倒数第二个：首先把自己和幂积里面已有的所有元素做乘积("bc")，然后加到幂积里,此时为{c,bc};最后再加上自己"b",{b,c,bc}<br /> 倒数第三个：把自己（a）和幂积中所有元素做乘积{ab,ac,abc}，加到幂积集合中，此时幂积中为：{b,c,bc,ab,ac,abc};最后再加上自己本身"a",为：{a,b,c,bc,ab,ac,abc}.<br /> */<br /> #define MAX_LENGTH 100 //幂集的最大个数 </p> <p>/*pArr为输入的字符串，i为正在处理的字符，pResult为存储结果，num统计共有多杀个幂集*/<br /> void powerSet(char *pArr, int i, char *pResult, int &num)<br /> {<br /> char tempArr[MAX_LENGTH];<br /> strcpy(tempArr, pResult);<br /> if (i >= strlen(pArr))<br /> {<br /> printf("{%s}/n", pResult);<br /> num++;<br /> }<br /> else<br /> {<br /> powerSet(pArr, i+1, tempArr, num);<br /> strncat(tempArr, (pArr+i), 1);<br /> powerSet(pArr, i+1, tempArr, num);<br /> }<br /> } </p> <p>int main()<br /> {<br /> char *pstr = "ABC";<br /> char *pres = new char[MAX_LENGTH];<br /> memset(pres, 0, sizeof(char)*MAX_LENGTH);<br /> int num = 0; </p> <p> powerSet(pstr, 0, pres, num);<br /> }</p> <p>本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/wangyangkobe/archive/2010/10/10/5931480.aspx#

2. 利用二进制与幂集的关系

// Virtual.cpp : 定义控制台应用程序的入口点。<br /> #include "stdafx.h"<br /> #include <iostream><br /> #include <string><br /> using namespace std; </p> <p>/*<br /> 二进制法求一个集合的幂集<br /> 作者：blackmanba<br /> 时间：2010年10月10日<br /> */<br /> /*x的二进制表示可以用来表示s的一个子集：对于x的第i位，如果为1，则此子集包含s的第i个元素，否则不包含。<br /> 因此，只要遍历 [0,2^n)的整数区间，就能列举出s的所有子集，这些子集的集合就是s的幂集*/ </p> <p>/*arr为输入的字符串，n为该数组的元素个数, result为存储结果的字符串数组*/<br /> void powerSet(char *arr, int n, char* result[])<br /> {<br /> int max_length = 2<<(n-1);//幂集的最大个数 </p> <p> for (int i=0; i<max_length; i++)<br /> {<br /> string temp = "";<br /> for (int j=0; j<n; j++)<br /> {<br /> if (i & (1<<j))//判断每一个i的二进制中哪一位是1，若为1，将对应的位选中<br /> {<br /> temp += *(arr+n-j-1);<br /> }<br /> }<br /> strcpy(result[i], temp.c_str());<br /> }<br /> } </p> <p>int main()<br /> {<br /> char *arr = "ABC";<br /> char *res[8];//n为"ABC"幂集的个数<br /> for (int i=0; i<8; i++)<br /> {<br /> res[i] = new char[4];<br /> } </p> <p> powerSet(arr, 3, res); </p> <p> for (int i=0; i<8; i++)<br /> {<br /> printf("{%s}/n", res[i]);<br /> } </p> <p> //释放内存<br /> for(int i=0; i<8; i++)<br /> {<br /> delete []res[i];<br /> }<br /> }</p> <p>本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/wangyangkobe/archive/2010/10/10/5931480.aspx#