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

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

新老客户大回馈,云服务器低至5折

前言

  最近在上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;
}

 


后记

  这次思考还是比较有意义的,以后学习算法的时候尽量先去用最原始的方式实现,然后计算时间复杂度、空间复杂度,再去用所谓高级一些的技巧优化,更为完善的代码晚上再整理贴出来吧。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Leetcode--Swap Nodes in Pairs(0024)

下一篇:BZOJ 3524: [POI2014]KUR-Couriers