- 在线时间
- 1 小时
- 最后登录
- 2015-11-4
- 注册时间
- 2015-10-21
- 听众数
- 9
- 收听数
- 0
- 能力
- 0 分
- 体力
- 9 点
- 威望
- 0 点
- 阅读权限
- 10
- 积分
- 4
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 2
- 主题
- 1
- 精华
- 0
- 分享
- 0
- 好友
- 3
升级 80% 该用户从未签到 - 自我介绍
- w
|
请教各位大神一个组合数学的问题:6 t1 ?* V7 R3 n; N B
1 l2 m& E1 B8 h3 |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))个组合。
- k3 @: h/ H5 Q. y$ u& U3 J) V' V8 n1 i' ^; c; E
2:我们知道,S1的组合当中,某些组合中的元素,覆盖了S2的组合当中某一个或者某几个组合的所有元素。
$ L* c' q6 F9 P. r; t& J7 t例如:S1的组合当中有一个组合是a1(a,b,c,d,e),S2的组合当中有一个组合是b1(b,d,e),另一个组合是b2(a,c,d)。那么a1中的元素就覆盖了b2,b3中的所有元素,这样相当于覆盖了两个S2中的组合。
9 K: i0 O6 ]9 S4 \
# {9 F2 k- T. E7 ^" z& Z现在,要求S1的组合当中最少要有多少个像a1这样的组合,就能覆盖S2中的所有元素。并列出这些组合。9 k$ u% P% Q. M4 Z
. t( }* ]( Y. l z" a: v8 G/ D举例:
p( p0 z7 c" R# L: V( k1 y假设从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中组成所有组合的元素。
- U. a2 Q' e4 f# Z' } k! j2 U; }9 X, y$ E' C8 u8 X
1. A,B,C,D,E,G 2. A,B,C,D,F,G 3. A,B,C,E,F,G4 r, D3 v% b8 q1 E7 c% ~
4. A,B,D,E,F,G 5. A,C,D,E,F,G 6. B,C,D,E,F,G& K! k* d0 d& r# D7 i+ Q
+ X' s; s |3 e- q
( c& K9 X1 [7 f- B9 r% o( b
小弟想知道怎么编程解决这个问题?或者有没有什么数学方法,能直接找出这些最小的组合?
& T g, S9 W: ?3 U" I( g
" o/ ?1 i* h: w+ N( D: N原题是英文的,如附件:
' | B' f# E8 J4 j. z2 V% f; A
英语原文.pdf
(283.04 KB, 下载次数: 1)
6 W& A7 \0 x0 e+ \' T" h. _
5 S$ c( A4 f! g8 @5 c5 K* r& x2 C2 U# L# |; o/ k
' e9 K( {5 W& y& ]! s
, ^7 d; R$ K! ]+ G! G. I |
zan
|