C语言算法 输出当前集合的所有子集

2021/7/3 20:51:21

本文主要是介绍C语言算法 输出当前集合的所有子集,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

对输入的正整数n,输出{0,1,...,n-1}的所有子集。例如,输入3时,输出如下:

{},{0},{1},{0,1},{2},{0,2},{1,2},{0,1,2}

 

这个题目可以考虑用二进制的方法来反映排列组合(输入数字3对应3位二进制数,3位二进制数共有8种写法,而包含三个元素的集合的排列组合方式也有8种),就直接拿下面的这个表格来举例子:

当二进制数为000的时候,默认为空集

当最低位为1其余高位为0的时候,代表当前集合为{0};

当次地位为1其余位为0的时候,代表当前集合为{1};

当高位为1其余低位0的时候,代表当前集合位{2};

以上三种可以任意组合,比如011代表{0,1}、111代表{0,1,2}、010代表{1};

而且这里值得注意的是,二进制对应的数可以组合成有顺序的序号

子集序号trans对应的二进制数
{} 0 000
{0} 1 001
{1} 2 010
{0,1} 3 011
{2} 4 100
{0,2} 5 101
{1,2} 6 110
{0,1,2} 7 111

直接上代码:

int main(){
    int num;//这个集合有多少个数
    scanf("%d",&num);
    int cnt=(int)pow(2, num)-1;//总共有多少个子集
    
    for(int i=0;i<=cnt;i++){
        printf("{");
        
        int trans=i;//当前的数字
        int set_num=0;//集合中需要填写的数字
        int comma_sign=0;//逗号
        while (trans) {//根据当前的数字求解其二进制,根据二进制来求集合
            if(trans%2==1){
                if(!comma_sign){
                    printf("%d",set_num);
                    ++comma_sign;
                }
                else{
                    printf(",%d",set_num);
                    ++comma_sign;
                }
            }
            ++set_num;
            trans/=2;
        }
        if(i!=cnt)
            printf("},");
        else
            printf("}");
//
//        if(!((i+1)%5))
//            printf("\n");
    }
    printf("\n");
}

为了解决集合中应该写入数字几的问题(比如集合中有1,2,3,此时当前子集是几个数字,数字是多少的子集组合),这里引入了数字set_num=0变量,当检测到低位存在数字1的时候,先输出当前set_num的值0,然后令set_num自加

当再次检测到次低位存在1到时候,输出set_num当前的值1,并再次令set_num自加,这是为了如果再次检测到高位为1的存在的时候可以输出2

这样说很抽象,我举个例子:

当当前序号为7的时候:

7首先会进入while判断,对7进行2的取余操作得1,那么意味着有低位存在,也就是当前子集当中含0元素,打印当前set_num,接着令set_num自加得1备用

对7进行除2操作(继续转2进制)得3赋给原数

3再次进入到while判断,对3进行2的取余操作得1,那么意味着有次低位存在,也就是当前子集当中含1元素,打印当前set_num,接着令set_num自加备用

。。。



这篇关于C语言算法 输出当前集合的所有子集的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程