「java求子集」集合求子集个数算法

今天给各位分享java求子集的知识，其中也会对集合求子集个数算法进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、子集和问题的一个实例为〈S,t〉。其中，S={ x1， x2，…， xn}是一个正整数的集合，c是一个正整数。子集和
• 2、如何根据集合中的元素个数 求子集个数，有公式没
• 3、求子集个数，非空子集个数，非空真子集个数的公式以及公式来历
• 4、这段求子集和的C语言，到底怎么递归和终结的？

子集和问题的一个实例为〈S,t〉。其中，S={ x1， x2，…， xn}是一个正整数的集合，c是一个正整数。子集和

给定n 个整数的集合X={x1，x2，...，xn}和一个正整数y，编写一个回溯算法，

在X中寻找子集Yi，使得Yi中元素之和等于y。

#include stdio.h#include conio.h

int len; // 输入长度.

int sum; // 和.

int *data; // 数据.

char *output; // 所求子集元素，与输入数据对应，'Y'为取.

// 获取输入.

void GetInput(){

int i;

printf("输入集合个数: ");

scanf("%d", len);

while(len = 0){

printf("集合个数必须大于0: ");

scanf("%d", len);

}

data = new int[len];

output = new char[len];

for(i = 0; i len; i++){

printf("输入第%d个数: ", i+1);

scanf("%d", data[i]);

output[i] = 'N';

}

printf("输入子集和: ");

scanf("%d", sum);

while(sum = 0){

printf("子集和必须大于0: ");

scanf("%d", len);

}

}

// 回朔求解:有解返回非0值，无解返回0.

int GetRes(){

int p = 0; // 指向当前值.

int temp = 0; // 当前子集合和.

while(p = 0){

if('N' == output[p]){

// 选中当前项.

output[p] = 'Y';

temp += data[p];

if(temp == sum){

return 1;

}

else if(temp sum){

output[p] = 'N';

temp -= data[p];

}

p++;

}

if(p = len){

// 开始回朔.

while('Y' == output[p-1]){

p--;

output[p] = 'N';

temp -= data[p];

if(p 1){

return 0;

}

}

while('N' == output[p-1]){

p--;

if(p 1){

return 0;

}

}

output[p-1] = 'N';

temp -= data[p-1];

}

}

return 0;

}

// 打印结果.

void PrintRes(){

int i;

printf("\r\n所求子集为: ");

for(i = 0; i len; i++){

if('Y' == output[i]){

printf("%d ", data[i]);

}

}

}

void main(){

GetInput();

if(GetRes()){

PrintRes();

}

else{

printf("无解！");

}

printf("\r\nPress any key to continue.");

getch();

}

如何根据集合中的元素个数 求子集个数，有公式没

有公式的

元素有n个

则子集数是2的n次方个

真子集个数就是2的n次方-1个

而非空真子集个数就是2的n次方-2个

求子集个数，非空子集个数，非空真子集个数的公式以及公式来历

子集个数为2^n。

非空子集为2^n-1。

非空真子集为2^n-2。

如果你学了排列组合的话。

那么久可以理解。

子集：N个元素中取0个、取一个、取2个，取N个。

然后相加=2^n，其余的就减以下就可以了。

集合里有一个元素，2个元素，3个元素分别把他们的子集，非空子集、非空真子集算出来，就能发现规律了。

性质

一、根据子集的定义，我们知道A⊆A。也就是说，任何一个集合是它本身的子集。

二、对于空集∅，我们规定∅⊆A，即空集是任何集合的子集。

说明：若A=∅，则∅⊆A仍成立。

证明：给定任意集合A，要证明∅是A的子集。这要求给出所有∅的元素是A的元素；但是，∅没有元素。对有经验的数学家们来说，推论“∅没有元素，所以∅的所有元素是A 的元素"是显然的；但对初学者来说，有些麻烦。 因为∅没有任何元素，如何使"这些元素"成为别的集合的元素？ 换一种思维将有所帮助。

这段求子集和的C语言，到底怎么递归和终结的？

代码有点小问题，无伤大雅。这个问题其实比排序还好理解，小朋友都说简单哩。首先，包是从小到大的升序，如果前面的包超重了，换后面的包必定超重，因此if的判断就很简单。现在具体来看代码，最上一个if，是包匹配的情形，输出后就结束了，意味着先前所有指向它的递归都可以逐级返回了。看你的注释，正好相反，下面的else可是没机会执行了哦，这里你读错了。如果没匹配？此时就有两条路，一条是把当前包加进来，一条是不要当前包，你没体会出来，所以下面的两个if也无法真正理解了。这个问题其实更像穷举，即第一个包要，不要可以分出两条路，第二包在第一个包要的基础上分两条路，在不要第一个包的基础上仍分两条路，依次类推，1变2，2变4，4变8，所有的情况都无遗漏，直到满足条件或证明这条路不通，在纸上画个图就象树枝分叉一样

关于java求子集和集合求子集个数算法的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。