精华内容
下载资源
问答
  • 1.对于一个大小为n的数集,求出该数集的每个"非空子集"的方差之和对10°+7取模的结果。 附件1说明:第一行一个正整数口表示集合大小,第二行几个整数表示集合中的元素。/ /求集合的所有子集的算法(1): 对于任意集合...

    /题目:
    注:要求提交程序源代码和执行结果,编程语言不限。
    1.对于一个大小为n的数集,求出该数集的每个"非空子集"的方差之和对10°+7取模的结果。
    附件1说明:第一行一个正整数口表示集合大小,第二行几个整数表示集合中的元素。
    /

    /求集合的所有子集的算法(1):
    对于任意集合A,元素个数为n(空集n=0),其所有子集的个数为2^n个
    如集合A={a,b,c},其子集个数为8;对于任意一个元素,在每个子集中,
    要么存在,要么不存在,对应关系是:
    a->1或a->0
    b->1或b->0
    c->1或c->0
    映射为子集:
    (a,b,c)
    (1,1,1)->(a,b,c)
    (1,1,0)->(a,b )
    (1,0,1)->(a, c)
    (1,0,0)->(a )
    (0,1,1)->( b,c)
    (0,1,0)->( b )
    (0,0,1)->( c)
    (0,0,0)->@ (@表示空集)
    算法(1):
    观察以上规律,与计算机中数据存储方式相似,故可以通过一个整型数(int)与
    集合映射000…000 ~ 111…111(0表示有,1表示无,反之亦可),通过该整型数
    逐次增1可遍历获取所有的数,即获取集合的相应子集。
    在这里提一下,使用这种方式映射集合,在进行集合运算时,相当简便,如
    交运算对应按位与&,{a,b,c}交{a,b}得{a,b}<—>111&110==110
    并运算对应按位或|,
    差运算对应&~。
    /

    /求集合的所有子集的算法(1):
    设函数f(n)=2^n (n>=0),有如下递推关系f(n)=2
    f(n-1)=2*(2f(n-2))
    由此可知,求集合子集的算法可以用递归的方式实现,对于每个元素用一个映射列表marks,标记其在子集中的有无
    很显然,在集合元素个数少的情况下,算法(1)优于算法(2),因为只需通过加法运算,便能映射出子集,
    而算法(2)要递归调用函数,速度稍慢。但算法(1)有一个严重缺陷,集合的个数不能大于在计算机中一个整型数的位数,
    一般计算机中整型数的为32位。对于算法(2)就没这样限制。
    /

    /求 方差和 的算法:
    求每个子集的均值和方差
    然后求所有子集方差和
    /

    #include<iostream>
    #include<vector>
    #include<numeric>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    
    double s = 0.0;
    
    double average(vector<int>& subset)//计算均值
    {
    	double sum = accumulate(subset.begin(), subset.end(), 0.0);
    	double mean = sum / subset.size();
    
    	return mean;
    }
    
    double variance(vector<int>& subset, double mean)
    {
    	double accum = 0.0;
    	std::for_each(subset.begin(), subset.end(), [&](const double d) {
    		accum += pow(d - mean, 2);
    		});
    	if (accum == 0) return 0;
    	else return accum/subset.size();
    }
    
    void print1(const vector<int>& a, int mark, int length)
    {
    	bool allZero = true;
    	int limit = 1 << length;
    	double mean = 0.0, accum = 0.0;
    	vector<int>temp;
    	cout << "子集:";
    	for (int i = 0; i < length; ++i)
    	{
    		if (((1 << i) & mark) != 0) //mark第i+1位为1,表示取该元素
    		{
    			allZero = false;
    			cout << a[i] << " ";
    			temp.push_back(a[i]);
    		}
    	}
    
    	if (allZero == true) 
    	{ 
    		cout << "空集"; 
    		cout << "     均值:无";
    		cout << "     方差:无";
    	}
    	else 
    	{
    		cout << "     均值:";
    		mean = average(temp);
    		cout << mean;
    
    		cout << "     方差:";
    		accum = variance(temp, mean);
    		cout << accum;
    	}
    	
    	s += accum;
    
    	cout << endl;
    }
    void subset1(const vector<int>& a, int length)
    {
    	if (length > 31) return;
    
    	int lowFlag = 0; //对应000...000
    	int highFlag = (1 << length) - 1; //对应111...111
    
    	for (int i = lowFlag; i <= highFlag; ++i)
    	{
    		print1(a, i, length);
    	}
    }
    
    void print2(vector<int>& a, vector<bool>& marks, int length)
    {
    	double mean = 0.0, accum = 0.0;
    	vector<int>temp;
    	bool allFalse = true;
    
    	cout << "子集:";
    	for (int i = 0; i < length; ++i)
    	{
    		if (marks[i] == true)
    		{
    			allFalse = false;
    			cout << a[i] << "  ";
    			temp.push_back(a[i]);
    		}
    	}
    
    	if (allFalse == true)
    	{
    		cout << "空集";
    		cout << "     均值:无";
    		cout << "     方差:无";
    	}
    	else
    	{
    		cout << "     均值:";
    		mean = average(temp);
    		cout << mean;
    
    		cout << "     方差:";
    		accum = variance(temp, mean);
    		cout << accum;
    	}
    
    	s += accum;
    
    	cout << endl;
    }
    
    
    void subset2(vector<int>& a, vector<bool>& marks, int m, int n, int length)
    {
    	if (m > n) 	print2(a, marks, length);
    	else
    	{
    		marks[m] = true;
    		subset2(a, marks, m + 1, n, length);
    		marks[m] = false;
    		subset2(a, marks, m + 1, n, length);
    	}
    }
    
    int main()
    {
    	int n;
    	vector<int>set;//set表示集合
    	cin >> n;
    	
    	for (int i = 0, x; i < n; i++)
    	{
    		cin >> x;
    		set.push_back(x);
    	}
    	if (n < 32) subset1(set, n);
    	else
    	{
    		vector<bool> marks(n, 0);
    		subset2(set, marks, 0, n - 1, n);
    	}
    
    	cout << "方差和 对10的9次方+7 取模 结果:";
    	cout << (int)s % int(pow(10, 9) + 7) << endl;
    
    	return 0;
    }
    

    集合的非空子集方差和

    展开全文
  • 列出一个集合的所有非空子集

    千次阅读 2012-10-16 19:19:18
    整体思路 description: 我们先看一个例子 ...非空子集有 {a}  |-->{a, b ,c }-->{a, b ,c ,d} {a, b}-->|  |-->{a, b ,d} {a, c}-->{a, c ,d} {a, d} {b}   {b, c}-->{b ,c ,d} {b, d}
    整体思路
    
    description:
    我们先看一个例子
    A={a, b ,c ,d}
    非空子集有
    {a}
         |-->{a, b ,c }-->{a, b ,c ,d}
    {a, b}-->|
         |-->{a, b ,d}  
    {a, c}-->{a, c ,d}
    {a, d}

    {b}
        
    {b, c}-->{b ,c ,d}

    {b, d}  

    {c}
    {c, d}

    {d}
    通过上面的例子你是不是发现一个规律,
    子集{a}、{b}、{c}、{d}分别是空集与未添加到子集中元素{a, b, c, d}中的某一个组合成。
    子集{a, b}、{a, c}、{a, d}分别是子集{a}与未添加到子集中元素{b, c, d}中的某一个组合成。
    子集{a, b ,c }和{a, b ,c }分别是子集{a, b}与未添加到子集中元素{c, d}中的某一个组合成。

    子集{a, b ,c ,d}分别是子集{a, b ,c}与未添加到子集中元素{d}中的某一个组合成。

    下面是代码

    #include <stdio.h>
    #include <stdlib.h>
    
    
    int count = 0;	//表示第几个子集
    
    void print(char *str)
    {	
    	printf("%d: %s\n", ++count, str);
    }
    
    //start表示还未添加到子集中的元素的开始位置
    //end表示集合最后一个元素的位置
    //在子集中的元素
    void sub_list(char *start, char *end, char *str)
    {
    	char *p = start;
    	int len = strlen(str);
    	while( p <= end )	//想自己中依次添加未放入子集中的元素,一次一个
    	{
    		str[len] = *p;  //子集中添加一个未放入子集的元素。
    		str[len+1] = 0;
    		print(str);
    		p++;
    		sub_list(p, end, str);//递归计算在本子集基础上的产生的子集。
    		str[len] = 0;  
    	}
    }
    
    int main()
    {
    	char sub[] = "abcdef";
    	char str[255];
    	memset(str, 0, 255*sizeof(char));
    	printf(" collent {%s} : \n", sub);
    	sub_list(sub, &sub[strlen(sub)-1], str );
    }







    展开全文
  • 给定一个int数组A和数组的大小int n,请返回A的所有非空子集。保证A的元素个数小于等于20,且元素互异。各子集内部从大到小排序,子集之间字典逆序排序,见样例。  测试样例:[123,456,789]  * 返回{[789,456,...
     给定一个int数组A和数组的大小int n,请返回A的所有非空子集。保证A的元素个数小于等于20,且元素互异。各子集内部从大到小排序,子集之间字典逆序排序,见样例。
     测试样例:[123,456,789]

     * 返回{[789,456,123],[789,456],[789,123],[789],[456 123],[456],[123]}

     */

    1.先写一个算法,请返回A的所有子集(包含空集)。

    public ArrayList<ArrayList<Integer>> getSubsets(int[] A, int n) {
    		ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
    		Arrays.sort(A);
    		lists.add(new ArrayList<Integer>());//加入空集。
    		int index = 0;
    		while (index < n) {			
    			// 注意:每次加入集合后会改变原来的集合,无法继续从集合中取出元素。
    			// 必须通过一个中间参数moreSubsets来保存中间结果,最后加入allSubsets。
    			ArrayList<ArrayList<Integer>> moreSub = new ArrayList<ArrayList<Integer>>();
    			for (ArrayList<Integer> set : lists) {
    				ArrayList<Integer> newlist = new ArrayList<Integer>();
    				newlist.addAll(set);
    				newlist.add(0,A[index]);
    				moreSub.add(newlist);
    			}
    			lists.addAll(0, moreSub);//按字典顺序逆序输出
    			//lists.addAll(moreSub);按字典顺序输出
    			index++;
    		}
    		return lists;
    	}
    2.下面介绍:没有空集 且 按字典顺序逆序输出的算法
    注意:由于没有了空集,每次都要单独加入自己。遍历原来的集合(加入自己)。

    	public ArrayList<ArrayList<Integer>> getSubsets2(int[] A, int n) {
    		ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
    		Arrays.sort(A);
    		int index = 0;
    		while (index < n) {
    			//遍历原来的集合(加入自己),再单独加入自己(由于没有了空集)。
    			//两者没有先后顺序。也可加入自己,再遍历原来的集合
    			// 注意:每次加入集合后会改变原来的集合,无法继续从集合中取出元素。
    			// 必须通过一个中间参数moreSubsets来保存中间结果,最后加入allSubsets。
    			ArrayList<ArrayList<Integer>> moreSub = new ArrayList<ArrayList<Integer>>();
    			//lists没有元素的话,直接跳过。
    			for (ArrayList<Integer> set : lists) {
    				ArrayList<Integer> newlist = new ArrayList<Integer>();
    				newlist.add(A[index]);
    				newlist.addAll(set);
    				moreSub.add(newlist);
    			}
    			//加入自己
    			ArrayList<Integer> list = new ArrayList<Integer>();		
    			list.add(A[index]);
    			moreSub.add(list);
    			lists.addAll(0, moreSub);
    			index++;
    		}
    		return lists;
    	}



    展开全文
  • 请编写一个方法,返回某集合的所有非空子集。 给定一个int数组A和数组的大小int n,请返回A的所有非空子集。保证A的元素个数小于等于20,且元素互异。各子集内部从大到小排序,子集之间字典逆序排序,见样例。 ...

    题目描述

    请编写一个方法,返回某集合的所有非空子集。

    给定一个int数组A和数组的大小int n,请返回A的所有非空子集。保证A的元素个数小于等于20,且元素互异。各子集内部从大到小排序,子集之间字典逆序排序,见样例。

    测试样例:

    [123,456,789]
    返回:{[789,456,123],[789,456],[789,123],[789],[456 123],[456],[123]}

    class Subset {
    public:
        vector<vector<int> > getSubsets(vector<int> A, int n) {
            // write code here
            sort(A.begin(), A.end());
            int size = 1 << n;
            vector<vector<int> >subsets;
            for (int i = size - 1; i > 0; --i) {
                vector<int> subset;
                for (int j = n - 1; j >= 0; --j) {
                    if ((i >> j) & 1) {
                        subset.push_back(A[j]);
                    }
                }
                subsets.push_back(subset);
            }
            return subsets;
        }
    };

     

    展开全文
  • 集合元素的所有非空子集

    千次阅读 2015-08-27 22:10:57
    现有一个包含N个元素的集合S,求集合S的所有非空子集? 例如:集合S包含三个元素{a, b, c},则它的所有非空子集为: {a}, {b}, {c}, {a, b}, {a, c}, {b, c} 和{a, b, c}。 这里先用位操作的思路来求解,具体方法...
  • 字符串的非空子集 import java.util.*; public class _非空子集 { public static List<String> sList = new ArrayList<String>(); public static void main(String[] args) { Scanner sc = new ...
  • C语言求非空子集

    千次阅读 2018-05-09 22:45:03
    例如,当n=4 时,集合{1,2,3,4}可以划分为15 不同的非空子集如下:{{1},{2},{3},{4}},{{1,2},{3},{4}},{{1,3},{2},{4}},{{1,4},{2},{3}},{{2,3},{1},{4}},{{2,4},{1},{3}},{{3,4},{1...
  • 一个数组的非空子集

    千次阅读 2020-03-27 17:40:40
    //求一个数组的子集 #include <vector> #include<iostream> using namespace std; vector<vector<int>>A; void subset(int a[], int n) { int count = 1 << n;//子集个数 左移就相当...
  • Python---按字典序输出集合的所有非空子集 通过使用模拟二进制减法以判断每次选取的具体元素。其中flag[ ]为模拟二进制数,初始化全为1,当flag[0]为0时结束循环。下标为0位不作为选取(用来判断是否结束),从下标...
  • 非空子集个数计算

    千次阅读 2015-03-24 13:51:26
    题目:n元素的集合{1,2,.....,n},可以划分为若干个非空子集,如,当n=4时,集合{1,2,3,4}可以划分为15不同的非空子集如下: 由4个子集组成: {{1},{2},{3},{4}} 由3个子集组成: {{1,2},{3},{4}} {{1,3},{2},{4}} {{1,4...
  • 前言最近在实现论文《Learning Actionlet Ensemble for 3D Human Action Recognition》的过程中,遇到需要找出一个集合的所有子集的问题,于是在网上查找了一些资料,发现利用格雷码可以轻松地解决这类问题。...
  • 输出一个字符串数组所有非空子集

    千次阅读 2015-02-03 22:11:15
    前几天导师让写一个数据挖掘的算法,用到了一个一个字符串数组子集的程序,现在总结一下,说不定下次还可以用到。 java 代码如下: package com.xing.test; import java.util.Arrays; import java.util....
  • 非空子集个

    千次阅读 2016-07-23 15:50:22
    求元素数为偶数的非空子集有多少个 ,知道公式 2^(n-1)(mod)-1 ;就很简单了 记得是要 对1000000007取模!! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include __ int64 f ( _...
  • * 生成集合的所有子集(本算法中没有把空集作为子集返回,如果需要,请自行添加) * 本算法采用递归实现 * @param sourceSet * @param result */ public void buildSubSet(List sourceSet, List ...
  • 非空子集

    千次阅读 2014-09-28 10:29:43
    问题:  给定正整数n,计算出n元素的集合{1,2,....,n}可以划分为多少个不同的非空集合? ...非空子集分别是: {1} {4} {6} {8} {1, 4} {1, 6} {1, 8} {4, 6} {
  • * 求一个集合(元素唯一)的子串的个数 * * @author 楠 * */ public class Test02 { public static void main(String[] args) { // TODO Auto-generated method stub char[] arr = { 'a', 'b', 'c' }; ...
  • A的所有非空子集

    千次阅读 2018-01-25 19:30:41
    请编写一个方法,返回某集合的所有非空子集。 给定一个int数组A和数组的大小int n,请返回A的所有非空子集。保证A的元素个数小于等于20,且元素互异。各子集内部从大到小排序,子集之间字典逆序排序,见样例。 测试...
  • 题解:观察测试样例,会发现每子集的选择规律与二进制((2^n) - 1)到 1 的顺序生成的规律是一致的,样例中n=3,2^n-1=7,用二进制表示为111,其中每位的1表示数组中的三数都选择。 class Subset { public: ...
  • 假如有一个n个元素的集合,那么它的非空子集有2的次方-1个,而一个n位的二进制数除去0刚好可以表示2的n次方-1种状态。刚好可以建立对应的联系,因此只需要检测二进制数所表示的每一种状态1的位置,把对应位置的角标...
  • public class BinaryAlgorithm { /** * 在linux系统中 1,2,4分别代表 ... * 可以看出任意非空子集的和 各不相同 * 利用这样的特性可以计算 一个集合的子集 */ public List&lt;String&...
  • Apriori算法求集合非空子集java代码     public class Test { public static void main(String[] args) { String str="abcd" ; //用Set集合保存结保证内容重复 Set&lt;String&gt;....
  • 非空子集 思路: 其实主要理解HashSet即可,利用HashSet集合的不重复原则。 利用HashSet嵌套 public Set<Set<Integer>> getSubsets2(int[] A, int n) { Set<Set<Integer>> res = new ...
  • 【算法】求非空子集的三种思路

    千次阅读 2020-04-16 19:15:51
    简化:编写一个方法,返回int数组的所有非空子集。 (n个元素的集合的子集个数:2^n - 1) 二、思路及代码 思路一:递归 对每个元素,都可以选择进入或者不进入子集。 因此,求n个元素的子集,可以分解成:求出n-1...
  • 非空子集之二进制法

    2021-01-24 23:01:44
    非空子集之二进制法 思路: 比如现在n=3; 那么2的n3次方为8; 1:0001 2:0010 3:0011 4:0100 5:0101 6:0110 7:0111 8:1000 其实上面的也就代表着下例: 1:[1] 2:[2] 3:[2,1] 4:[3] 5:[3,1] 6:[3,2] 7:[3,2,1] 8:[] ...
  • 、全排列 全排列如果使用递归来实现的话是元素与元素交换的问题,而如果使用迭代实现的话是把当前字符加在已形成字符的前面或后面的问题。这里分别使用迭代,普通递归和多路递归+回溯实现。 迭代实现 //迭代...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,123
精华内容 1,649
关键字:

一个集合有多少个非空子集