集合与子集合

northwolves · 发表于 2008-12-31 21:14:41

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

您需要登录才可以下载或查看，没有账号？欢迎注册

×

设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个子集合

northwolves · 发表于 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

northwolves · 发表于 2009-1-11 09:15:02

同理: Mincount(6,3,2)=6

northwolves · 发表于 2009-1-12 14:29:15

很难么？我试了试递归，没搞定。

账号		自动登录	找回密码
密码			欢迎注册

[擂台] 集合与子集合

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