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语言算法 输出当前集合的所有子集的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23增量更新怎么做?-icode9专业技术文章分享
- 2024-11-23压缩包加密方案有哪些?-icode9专业技术文章分享
- 2024-11-23用shell怎么写一个开机时自动同步远程仓库的代码?-icode9专业技术文章分享
- 2024-11-23webman可以同步自己的仓库吗?-icode9专业技术文章分享
- 2024-11-23在 Webman 中怎么判断是否有某命令进程正在运行?-icode9专业技术文章分享
- 2024-11-23如何重置new Swiper?-icode9专业技术文章分享
- 2024-11-23oss直传有什么好处?-icode9专业技术文章分享
- 2024-11-23如何将oss直传封装成一个组件在其他页面调用时都可以使用?-icode9专业技术文章分享
- 2024-11-23怎么使用laravel 11在代码里获取路由列表?-icode9专业技术文章分享
- 2024-11-22怎么实现ansible playbook 备份代码中命名包含时间戳功能?-icode9专业技术文章分享