- 在线时间
- 1 小时
- 最后登录
- 2015-11-4
- 注册时间
- 2015-10-21
- 听众数
- 9
- 收听数
- 0
- 能力
- 0 分
- 体力
- 9 点
- 威望
- 0 点
- 阅读权限
- 10
- 积分
- 4
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 2
- 主题
- 1
- 精华
- 0
- 分享
- 0
- 好友
- 3
升级 80% 该用户从未签到 - 自我介绍
- w
|
请教各位大神一个组合数学的问题:' @! c5 T+ o A: y; A' D% F4 s
4 ^0 b* I: ]) ^" s6 J) ]
1:在m个样本中(45<=m<=54),随机选出n个样本(7<=n<=25)。从刚才这n个样本中,再随机选出k个样本(4<=k<=7)组成一些组合,那么这些组合有S1(也就是C(n,k))个。再从n个样本中选出s个样本(3<=s<=7),这样就有S2(也就是C(n,s))个组合。7 x) b9 _% k8 U8 g, p2 _
/ g/ t0 ~$ ?$ s0 c$ `! ]2:我们知道,S1的组合当中,某些组合中的元素,覆盖了S2的组合当中某一个或者某几个组合的所有元素。, X* a8 _ j7 l1 o
例如:S1的组合当中有一个组合是a1(a,b,c,d,e),S2的组合当中有一个组合是b1(b,d,e),另一个组合是b2(a,c,d)。那么a1中的元素就覆盖了b2,b3中的所有元素,这样相当于覆盖了两个S2中的组合。
- m2 |0 U0 o, n
4 E. J9 y3 h8 T0 a6 U现在,要求S1的组合当中最少要有多少个像a1这样的组合,就能覆盖S2中的所有元素。并列出这些组合。: c) C3 o: c4 \# k. v
0 x) B- W, `! h2 h1 `. p
举例:
; u, Z9 ~1 X8 c/ k! n$ V假设从m=45个样本中,随机抽取n=7个样本(假设这些样本是A,B,C,D,E,F,G),k=6,s=5,那么S1=C(7,6)=7,S2=C(7,5)=21。在S1当中,只需要最少如下6个组合,就可以覆盖S2中组成所有组合的元素。
; b% y, z5 a! r4 p3 A: u% V' Y" l) c8 j/ |7 q: `
1. A,B,C,D,E,G 2. A,B,C,D,F,G 3. A,B,C,E,F,G$ |3 U+ G# A( z% o* B
4. A,B,D,E,F,G 5. A,C,D,E,F,G 6. B,C,D,E,F,G
* C$ f- l1 a, T2 w/ G, b% f1 r! v( @& w& J$ _: N3 B
% i+ s! K1 t5 M2 c, V" \小弟想知道怎么编程解决这个问题?或者有没有什么数学方法,能直接找出这些最小的组合?
) J0 A2 l. O6 D5 k3 Q4 ^. {& a. h) G& b7 a
原题是英文的,如附件:/ |0 M% a( F8 F" H$ ^1 I
英语原文.pdf
(283.04 KB, 下载次数: 1)
) m* h9 |9 ]2 ^9 }1 z. u
4 |) |+ ]2 g( a
2 y. z+ O! Q% _. r9 X R/ y$ G! T2 N8 V
: G9 [/ p% n- r( j |
zan
|