首页 > > 程序设计 > C/C++ >

适合小白的暴力求子集方法，了解一下？

2018-06-17 20:52:50来源：未知阅读 ()

前言

　　最近在上C++课的时候老师留了一道课后作业，求n个数字的全部子集，比如说输入6就打印{1， 2， 3， 4，5， 6}的全部子集。

　　当时我脑中第一反应就是用递归枚举随便打一打啊，不过后来有位同学问我思路，突然不知所措，因为我们当时才讲了基本数据类型和while、if、for这几种控制选择结构，数组函数神马的都还没有讲，那么，用这些最基本的知识要怎么做呢？

　　虽然道理上讲是所有的算法问题都能用控制结构的堆叠嵌套来解决，不过落实到代码上真的有点无力。

　　我也尝试去网上找答案，不过不管换了多少关键字搜索，基本上都是那么几种求法，增量构造啦、二进制啦、位向量啦。。。看着一个比一个高级，可搜了好久也没有找到最最最最最原始的方法，后来我想了一段时间并汲取了网上的一些思想，写了一个简单的暴力枚举算法。

思路

　　n个元素的集合的子集数就是2的n次幂嘛（貌似是初中讲的，不清楚的翻笔记去啦），所以外层循环就是循环2的n次幂次。

　　for (int i=0; i<pow(2, n); i++)
　　{

　　}

　　内部实现的话就是先用temp储存一下i的值，然后用for循环确定集合中的每个元素是否应该被打印出来，那么如何确定呢？即判断temp的奇偶，而且每次内部for循环都改变temp的值。

        temp=i;
        for(j=0; j<n; j++)
        {
            if (temp%2 != 0)
            {
                cout<<j+1;
            }
            temp=temp/2;
        }
        cout<<" }"<<endl;

完整代码

　　可以加一些花括号逗号之类的易于区分自己中的每个元素（不过我的代码好像有点问题，晚上再改吧，毕竟基电作业还没写QAQ）

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int i, j, n, temp;
    cin>>n;
    for(i=0; i<pow(2,n); i++)
    {
        temp=i;
        cout<<"{ ";
        for(j=0; j<n; j++)
        {
            if (temp%2 != 0)
            {
                cout<<j+1;
                if (j != n-1)
                    cout<<", ";
            }
            temp=temp/2;
        }
        cout<<" }"<<endl;
    }
    return 0;
}

　　新的代码可以判断输入的元素是否有重复，如果重复的话就把多余的元素删除后再求其子集；同时，新的方法可以输入任意类型的字符串（本来就是用字符串来接收的啊）。

#include <cmath>
#include <iostream>

using namespace std;

int main()
{
    int i,j;
    int n;
    int temp, count;
    string s1;
    cout<<"请输入集合中元素的个数"<<endl;
    cin>>n;

    // 判断输入的元素是否重复
    string *input = new string[n];
    for (int t=0; t<n; t++)
    {
        cin>>s1;
        count = 0;
        for (int k=0; k<t; k++)
            if (input[k] == s1)
            {
                count++;
                n--;
                t--;
            }
        if (0 == count)
            input[t] = s1;
    }

    //动态创建数组
    string *s = new string[n];
    for (int i=0; i<n; i++)
        s[i] = input[i];

    for(i=0; i<pow(2,n); i++)
    {
        //外层循环循环2的n次幂次
        temp=i;
        cout<<"{ ";
        for(j=0; j<n; j++)
        {
            if (temp%2 != 0)
            {
                cout<<s[j];
                if (j != n-1)
                    cout<<" ";
            }
            temp = temp / 2;

        }
        cout<<" }"<<endl;
    }

    //清除数组的内存空间
    delete[] s;
    delete[] input;
}