QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 7558|回复: 0
打印 上一主题 下一主题

请教各位大神一个组合数学的问题

[复制链接]
字体大小: 正常 放大
mathm0del        

1

主题

9

听众

4

积分

升级  80%

该用户从未签到

自我介绍
w
跳转到指定楼层
1#
发表于 2015-10-21 15:12 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
请教各位大神一个组合数学的问题:
& P, }7 z4 i6 `  ~* D, y3 P
! A; C6 b3 d  h1 a, i3 L1:在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))个组合。1 R: @2 ?! |7 Q  Q1 Q( A
6 x( S/ k+ @6 h7 Q* F: O
2:我们知道,S1的组合当中,某些组合中的元素,覆盖了S2的组合当中某一个或者某几个组合的所有元素。
: o  }$ z, d0 y: A例如:S1的组合当中有一个组合是a1(a,b,c,d,e),S2的组合当中有一个组合是b1(b,d,e),另一个组合是b2(a,c,d)。那么a1中的元素就覆盖了b2,b3中的所有元素,这样相当于覆盖了两个S2中的组合。# z: ~7 y$ X' @* r8 }6 q2 u! v

" {% g% D. Q7 `1 p& t: M3 J) c' T现在,要求S1的组合当中最少要有多少个像a1这样的组合,就能覆盖S2中的所有元素。并列出这些组合。
0 t# o& R9 J) f! h3 {( D, B
- S% W  N" r  L( p" q$ n! z( \3 ~举例:( C( {/ j) }! T# W: t  e
假设从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中组成所有组合的元素。  K+ Y. m* ^( R: i! a; ~

( v  u! t" Q0 v8 h" a1. A,B,C,D,E,G  2. A,B,C,D,F,G  3. A,B,C,E,F,G2 T: Q, I. t1 h  k7 H
4. A,B,D,E,F,G  5. A,C,D,E,F,G  6. B,C,D,E,F,G6 V) m' d) z- B8 G* M; K, I% g: O& c
8 f4 B- h- b$ v
+ e/ H9 x! R; ?& _. \8 `5 z
小弟想知道怎么编程解决这个问题?或者有没有什么数学方法,能直接找出这些最小的组合?
% {9 }. e$ |6 B6 [$ \! T# r/ o9 A" U: H% A8 G* L; n& p
原题是英文的,如附件:
8 O# F: k) N+ I' i" K  y 英语原文.pdf (283.04 KB, 下载次数: 1)
% M" p- y, W3 b4 R' r0 z& k# ^! P: P( x- P/ T
5 F6 g3 Z: D+ n+ i+ _, r
# X3 _: ]  u9 X
7 }$ s/ P2 f! z* s- [
zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
您需要登录后才可以回帖 登录 | 注册地址

qq
收缩
  • 电话咨询

  • 04714969085
fastpost

关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

手机版|Archiver| |繁體中文 手机客户端  

蒙公网安备 15010502000194号

Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

GMT+8, 2026-4-29 19:05 , Processed in 0.422613 second(s), 63 queries .

回顶部