数学研发论坛

 找回密码
 欢迎注册
查看: 1309|回复: 3

[擂台] 集合与子集合

[复制链接]
发表于 2008-12-31 21:14:41 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
n,m,k ∈Z,且n>m>k.
一个n个元素的集合A,其含m个元素的全部子集合B有$C_n^m$个,其含k个元素的全部子集合C有$C_n^k$个,B的每个含元素含k个元素的子集合$C_m^k$个(当然互相之间可能有重叠)
试在子集合B中选择数目最少的 num  个集合,使其子集囊括子集合C

要求1:     编写函数 Mincount(int n,int m,int k) 计算num 的值.
要求2:     num<10000 时,输出该num个子集合
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-1-11 09:10:19 | 显示全部楼层
比如:
A={1,2,3,4,5}
B={{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5}}
C={{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}}
由于
{{1,2,3},{1,4,5},{2,4,5},{3,4,5}} 的2元素子集即可囊括子集合C,所以
Mincount(5,3,2)=4
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-1-11 09:15:02 | 显示全部楼层
同理:
Mincount(6,3,2)=6
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-1-12 14:29:15 | 显示全部楼层
很难么?我试了试递归,没搞定。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-8-24 13:00 , Processed in 0.123942 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表