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

今天药忘吃喽~ 2022-10-14 14:54 78阅读 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 条评论，78人围观）

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

相关阅读

相关快速计算a的n次方（快速幂&&运算取模规则）

使用pow(a,n)计算 a n a^n an，时间复杂度是 O ( n ) O(n) O(n) （返回值是int，使用long就收可能出问题）使用快速幂可以把时间复杂

骑猪看日落/ 2022年11月13日 14:28/ 0 赞/ 227 阅读

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

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

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

相关 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 赞/ 79 阅读

相关 a的n次方的高效算法

a^b的高效算法 LZ之所以要贴上这个算法，是因为LZ的一个朋友用这个小算法考过LZ，我当时想到了这个算法，思想有了，但是没有实现出来，但是我朋友用递归的方法写的，但是递归

布满荆棘的人生/ 2022年08月01日 03:12/ 0 赞/ 142 阅读

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

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

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

相关快速幂求x的n次方

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

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

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

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

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

相关输入一个正整数N，输出所有正整数M ，满足 M小于等于 N , M等于a三次方加b三次方等于c三次方加d三次方

public class PowTest { public static void main(String[] args) {

以你之姓@/ 2022年02月23日 19:46/ 0 赞/ 157 阅读

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

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

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

相关求a的n次方

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

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