c语言a的n次方减治法,输出一个集合的幂集（所有子集）

今天药忘吃喽~ 2022-10-14 14:54 112阅读 0赞

问题描述：如一个抽象集合\{1，2，3\}，它的所有子集包括\{\}，\{1\}，\{2\}，\{3\}，\{1,2\}，\{1,3\}，\{2,3\}，\{1,2,3\}共2的n次方个，此问题又叫求集合的幂集。

一、递归实现

减治法的减一的思想可以用到这个问题中来，对集合A=\{a1，a2，···，an\}，将其子集分为2组，一组为\{a1，···，an-1

\}的子集，一组为\{an\}，一旦我们得到了\{a1，···，an-1\}的所有子集列表，将列表中的每个元素都加上an，在把它们添加到列表中，以求得所有子集。下面是生成\{a1，a2，a3\}的子集示例：

![6548e334174a1c6b4fd5e7cb4ede36f9.png][]

注意生成子集的时候是从下至上生成子集的，意思是最后生成的空集。

代码实现参考了 http://www.geeksforgeeks.org/power-set/的思路

int SIZE = 5;

void printPowerSet2(char \*set, int set\_size)

\{

//递归出口，当当前集合不能够在分解为下一个子集的时候输出所有集合元素

if (set\_size == 0)

\{

printf("\{");

for (int i = 0; i < SIZE; i++)

if (set\[i\] != ' ')

printf("%c", set\[i\]);

printf("\}");

printf("\\n");

\}

else

\{

//直接递归，递归生成当前集合的所有下一个状态

printPowerSet2(set, set\_size - 1);

//动态生成子集合存储空间，通过使用空白字符替换每个位置的方式生成当前元素个数的每个子集

//递归的在生成子集中继续查找子集

if (set\_size > 0)

\{

char \*sub\_set = (char \*)malloc(sizeof(char)\*set\_size);

strcpy(sub\_set, set);

sub\_set\[set\_size - 1\] = ' ';

printPowerSet2(sub\_set, set\_size - 1);

\}

\}

\}

二、使用位运算

建立对于n个元素集合A=\{a1，a2，···，an\}的所有2的n次方个子集和长度为n的所有2的n次方个位串之间的一一对应关系，如果ai属于该子集，bi=1，如果ai不属于该子集，bi=0。

![462ae712ccd713b05767b14d5742aa90.png][]

思路来源： http://www.geeksforgeeks.org/power-set/

void printPowerSet(char \*set, int set\_size)

\{

int pow\_set\_size = pow(2, set\_size);

int counter, j;

for (counter = 0; counter < pow\_set\_size; counter++)

\{

for (j = 0; j < set\_size; j++)

\{

if (counter & (1 << j))

printf("%c", set\[j\]);

\}

printf("\\n");

\}

\}

解决该问题用了很长的时间，自己真的很菜，借鉴了许多其他人的思路，算不上自己原创，这里只是做一个总结，希望下一次遇到类似的问题能过有一些思路也好。

[6548e334174a1c6b4fd5e7cb4ede36f9.png]: /images/20221014/96e004ae91004983adbad93ecd06e56d.png
[462ae712ccd713b05767b14d5742aa90.png]: /images/20221014/cf689fed818248adb9e2814277fb487a.png

发表评论取消回复

表情：

评论列表（有 0 条评论，112人围观）

还没有评论，来说两句吧...

相关阅读

相关 C语言------求n的k次方

求n的k次方代码部分 include<stdio.h> double mypow(int n, int k) {

痛定思痛。/ 2023年10月09日 13:24/ 0 赞/ 62 阅读

相关 c++求a的b次方/次幂

![watermark,type\_d3F5LXplbmhlaQ,shadow\_50,text\_Q1NETiBA6LaFMzM4,size\_20,color\_FFFFF

r囧r小猫/ 2023年09月30日 10:43/ 0 赞/ 35 阅读

相关回溯法求一个集合的所有子集_回溯以查找所有子集

回溯法求一个集合的所有子集 Description: 描述： This is a standard interview problem to find out the s

短命女/ 2023年03月05日 12:35/ 0 赞/ 38 阅读

相关 2的n次方减一c语言,计算2的N次方........有什么错吗?

该楼层疑似违规已被系统折叠隐藏此楼查看此楼 int a\[MAX\]=0; \---------------- 这一句不对吧... 运行结果 Please Inpu

末蓝、/ 2022年10月15日 00:55/ 0 赞/ 191 阅读

相关 c语言a的n次方减治法,输出一个集合的幂集（所有子集）

问题描述：如一个抽象集合\{1，2，3\}，它的所有子集包括\{\}，\{1\}，\{2\}，\{3\}，\{1,2\}，\{1,3\}，\{2,3\}，\{1,2,3\}共2

今天药忘吃喽~/ 2022年10月14日 14:54/ 0 赞/ 113 阅读

相关输出集合的所有子集(幂集)-C语言

输出集合的所有子集(幂集)-C语言 include <stdio.h> define Length 4 char array[Length]

朴灿烈づ我的快乐病毒、/ 2022年07月24日 06:19/ 0 赞/ 193 阅读

相关快速幂求x的n次方

问题 O(logn)的时间复杂度求x的n次方，x为自然数，n为整数？举例解析如果 power=5 为奇数，result保存当前的多余的一个4，并在返回结果时一

缺乏、安全感/ 2022年07月16日 09:55/ 0 赞/ 280 阅读

相关 C语言——计算2的N次方

Description 任意给定一个正整数N（N≤100），计算2的N次方的值。 Input 输入只有一个正整数N。 Output 输出2的N次方的值。

超、凢脫俗/ 2022年03月22日 12:51/ 0 赞/ 624 阅读

相关【C语言】计算n的k次方

define _CRT_SECURE_NO_WARNINGS include<stdio.h> include<stdlib.h> includ

傷城~/ 2022年02月19日 10:27/ 0 赞/ 376 阅读

相关求a的n次方

此题面试时常有：解答方法有以下三种： 1。直接迭代求解，这个很简单，复杂度O(n)。 1。分治法。复杂度 logn 此方法有点凹，原理是：a的n次方可以分别对应两

曾经终败给现在/ 2021年11月08日 22:12/ 0 赞/ 366 阅读