设计算法以求解从集合{1..n}中选取k(k
来源:学生作业帮 编辑:搜狗做题网作业帮 分类:数学作业 时间:2024/06/17 13:34:55
设计算法以求解从集合{1..n}中选取k(k
C(k,n-1)=∏(n-k,n-1)/k!
C(k-1,n-1)=∏(n-k+1,n-1)/(k-1)!
C(k-1,n)+C(k-1,n-1)
=∏(n-k,n-1)/k!+∏(n-k+1,n-1)/(k-1)!
=∏(n-k,n-1)/k!+k·∏(n-k+1,n-1)/k!
=[(n-k)·∏(n-k+1,n-1)!+k·∏(n-k+1,n-1)]/(k-1)!
=[n·∏(n-k+1,n-1)]/k!
=∏(n-k+1,n)]/k!
=C(k,n)
即:C(k-1,n)+C(k-1,n-1)=C(k,n)
说简单点,就是杨辉三角形的元素算法.
此原理应用到你的问题上,重点是:结果集合的每个元素又是个集合.
若通用集合类Set(其实java中Set就是);
new Set{value...}为构造方法,-{value..}为集合差,+{value...}为集合和,Set(i)和集合第i个元素;
对于n个元素的集合Sn,如果有函数Set combine(k,Sn),产生n个元素中选k个元素集合的集合;那么,当a是n个元素中的任意一个时,combine(k,Sn)=combine(k,Sn-{a})+combine(k-1,Sn-{a}).
由此可以产生递归算法:
Set Sn=new Set{a0,a1,...an-1};
Set result=Sn.combine(k,Sn);
.
.
function Set combine(int count,Set S){
if(count==S.size()){
return new Set{S};//这是集合S仅为结果集的一个元素
}
if(count+1==S.size()){
Set result=new Set{};
for(Element a:S){
result+=new Set{S-{a}};//集合依次排除一个元素产生的子集作为结果的一个元素
}
return result;
}
Set S2=combine(count-1,S-S(0));//对应YH公式的后一项,S(0)为集合S的第一个元素
for(Set Si:S2){
Si+={S(0)};//Si是缺了一个元素的
}
Set S1=combine(count,S-S(0));//这个是个数整好的,YH公式的前一项
return S1+S2;//YH公式
}
这个问题比较有意思,不知道谁出的.没有中学组合知识或YH公式,真困难了.
要是谁有更好算法,不妨交流一下.
这题分给的够低了,纯属兴趣做一下玩.
C(k-1,n-1)=∏(n-k+1,n-1)/(k-1)!
C(k-1,n)+C(k-1,n-1)
=∏(n-k,n-1)/k!+∏(n-k+1,n-1)/(k-1)!
=∏(n-k,n-1)/k!+k·∏(n-k+1,n-1)/k!
=[(n-k)·∏(n-k+1,n-1)!+k·∏(n-k+1,n-1)]/(k-1)!
=[n·∏(n-k+1,n-1)]/k!
=∏(n-k+1,n)]/k!
=C(k,n)
即:C(k-1,n)+C(k-1,n-1)=C(k,n)
说简单点,就是杨辉三角形的元素算法.
此原理应用到你的问题上,重点是:结果集合的每个元素又是个集合.
若通用集合类Set(其实java中Set就是);
new Set{value...}为构造方法,-{value..}为集合差,+{value...}为集合和,Set(i)和集合第i个元素;
对于n个元素的集合Sn,如果有函数Set combine(k,Sn),产生n个元素中选k个元素集合的集合;那么,当a是n个元素中的任意一个时,combine(k,Sn)=combine(k,Sn-{a})+combine(k-1,Sn-{a}).
由此可以产生递归算法:
Set Sn=new Set{a0,a1,...an-1};
Set result=Sn.combine(k,Sn);
.
.
function Set combine(int count,Set S){
if(count==S.size()){
return new Set{S};//这是集合S仅为结果集的一个元素
}
if(count+1==S.size()){
Set result=new Set{};
for(Element a:S){
result+=new Set{S-{a}};//集合依次排除一个元素产生的子集作为结果的一个元素
}
return result;
}
Set S2=combine(count-1,S-S(0));//对应YH公式的后一项,S(0)为集合S的第一个元素
for(Set Si:S2){
Si+={S(0)};//Si是缺了一个元素的
}
Set S1=combine(count,S-S(0));//这个是个数整好的,YH公式的前一项
return S1+S2;//YH公式
}
这个问题比较有意思,不知道谁出的.没有中学组合知识或YH公式,真困难了.
要是谁有更好算法,不妨交流一下.
这题分给的够低了,纯属兴趣做一下玩.
求大侠解答,设计算法求解从集合{1...n}中选取k(k
1.设集合A是由1,k²,k²+k+2为元素组成的集合,求实数k的取值范围.
已知集合A={k²-k,2k}求实数k取值范围
设计一个算法,把K进制数a(共有n位)化为十进制数B,如何编写程序?
1.已知A={k²-k,2k}是含有2个元素的集合,求实数K的的取值范围
1.设集合M={x丨-1≤x<2} ,N ={x丨x-k≤0}.若M∩N≠空集(符号打不出来),则k的取值范围( )
计算从n个人中选k个人组成委员会的不同组合数 用C语言函数递归
设集合M{x|-1≤x<2},N={|x-k≤0}.若M∩N≠空集,则k的取值范围是
求解k²-k>2^k
已知集合M={x|x2+6x-16>0},N={x|(x-k)(x-k-2)≤0},M∩N≠φ则k的取值范围是
已知集合M={x|x2+6x-16>0},N={x|(x-2k)(x-k-2)≤0},M∩N≠φ则k的取值范围是
已知集合M={x|x+6x-16﹥0},N={x|(x-k)(x-k-2)≤0},若M∩N=空集,则实数K的取值范围.