建设网站的新闻,网站建设入门教程视频教程,建网页网站,廊坊seo整站优化软件如果我们有一个求集合的所有子集(包括集合自身)的需求#xff0c;即有一个集合s,包括两个元素 a,b#xff0c;则其所有的子集为a,ab,b. 不难求得#xff0c;子集个数sn与原集合元素个数n之间的关系为#xff1a;sn2^n-1。 本文分别讲述两种实现方法#x… 如果我们有一个求集合的所有子集(包括集合自身)的需求即有一个集合s,包括两个元素 a,b则其所有的子集为a,ab,b. 不难求得子集个数sn与原集合元素个数n之间的关系为sn2^n-1。 本文分别讲述两种实现方法 一位图法 1构造一个和集合一样大小的数组A分别与集合中的某个元素相应数组A中的元素仅仅有两种状态“1”和“0”分别代表每次子集输出中集合中相应元素是否要输出。这样数组A能够看作是原集合的一个标记位图。 2数组A模拟整数“加一”的操作每“加一”之后就将原集合中全部与数组A中值为“1”的相相应的元素输出。 设原集合为a,b,c,d。数组A的某次“加一”后的状态为[1,0,1,1]则本次输出的子集为a,c,d。 详细代码例如以下 /*使用非递归的思想 假设有一个数组 大小为n那么就使用n 位的二进制 假设对应的位为1 那么就输出这个位 假设对应的位为0 那么就不输出这个位*//*使用位图的思想 构造一个位集合 大小和数组大小一样假设位图中对应的位为1,表示能够输出这个数组中的元素 假设位图中对应位为0 表示数组中对应位不输出这里模拟位图使用的数组 这里的重点是模拟数组加1的操作*//*使用数组模拟位图加1的操作 数组能够一直加1 直到数组内全部元素都是1函数返回值为bool 数组初始化最高位为1*/
#define MAX_LEN 10
void bitmap(char str[],const int n)
{bitsetMAX_LEN count;wang.set();int i0;unsigned long value wang.to_ulong();coutwang valueendl;int count0;while(value){bitsetMAX_LEN bit(value--);for(i0;ibit.size();i)if(bit[i])coutstr[i];coutendl;count;}coutcountendl;
}3时间复杂度O(n*2^n)。事实上在遍历输出子集的过程中。能够对程序做进一步的优化。比如。在第m次迭代中。仅仅须要遍历前k个元素klog2(m)1。这样不考虑数组模拟加一操作的话,总遍历次数为Sn(n-2)*2^n2,n2;Sn1,n1。尽管复杂度不变但总执行时间会降低。 4空间复杂度该方法每次迭代都是独立进行与上次迭代的结果没有不论什么关系。因此每次输出子集之后内存都能够被反复利用。仅仅须要一个与原集合相同大小的数组。空间复杂度为O(n)。 二递归迭代法 1採用递归迭代。详细步骤例如以下 设。原始集合sa,b,c,d子集结果为r 第一次迭代 ra 第二次迭代 ra ab b 第三次迭代 ra ab b ac abc bc c 第四次迭代 ra ab b ac abc bc c ad abd bd acd abcd bcd cd d 每次迭代都是上一次迭代的结果上次迭代结果中每一个元素都加上当前迭代的元素当前迭代的元素。 详细代码例如以下 /*上述方法不可用 明确递归的思想 以下每次都是输出back中的字符就可以 这次输出的子集就是上次输出的子集 这次迭代的元素 这次迭代的元素的本身*/
#if 1
void print(char* str)
{/*使用两个数组。一个记录上次迭代的结果 一个记录这次须要输出的结果 vec记录的是下次迭代须要參考的子集back记录的是參考vec迭代以后生成新的子集*/int count0;vectorchar vec;vectorchar back;int j;for(int i0;istrlen(str);i){if(i 0){vec.push_back(str[i]);vec.push_back(,);backvec;}else{for(j0;jback.size();j)if(back[j] ,){back.insert(back.begin() j,str[i]);j;}back.push_back(str[i]);back.push_back(,); }for(j0;jback.size();j){if(back[j] ,){printf(\r\n);count;}elseprintf(%c,back[j]);if(i)vec.push_back(back[j]);}backvec;}printf(sub_set count is %d \r\n,count);
}
#endif2时间复杂度 依据上述过程不难求的。第k次迭代的迭代次数为2^k-1。nk1。迭代n次总的遍历次数为2^(n1)-(2n),n1。 则时间复杂都为O(2^n)。 3空间复杂度 因为该算法。下一次迭代过程都须要上一次迭代的结果而最后一次迭代之后就没有下一次了。因此如果原始集合有n个元素。则在迭代过程中总共须要保存的子集个数为2^(n-1)-1,n1。但须要注意的是这里之考虑了子集的个数每一个子集元素的长度都视为1这点要注意。 总结 递归是非常耗时的。由于是递归在第一种方法时使用了C中的bitset,这种方法效率非常高在第二个方法中使用两个向量的目的是一个向量记录了这次迭代须要输出的集合一个向量是为了这次迭代须要參考上次输出的情况。
