算法高手请进!!!(不限语言,最好用java,解决后一定给分,不够再加) 小弟有一算法问题想请教:有n个数(1,2,...n,n>3),现在甲从中任意抽取m(m=2,...n-1)个,乙要如何提取m个数,提取多少次,用什么算法,才能保证其中一定有甲提取的m个数中的k个(k=m-1)?另:当k=m-2,m-3时呢? 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 题目似乎没有说完整。是说必须甲提取的数中有k个在乙提取的m个数中吗?我的想法:1,乙随机提取m个数。2,甲从乙提取的m个数中随机提取k个数3,甲从乙提取m个数之后剩下的n-m个数中随机提取m-k个数。 C(m,k)表示m中取k个。次数是:C(m,k)*C(n-m,m-k)+C(m,k+1)*C(n-m-1)+.......+C(m,m)*C(n-m,0) 举个例子:n = 6(1,2,3,4,5,6)甲提取:m = 5个数k = 4乙提取必须提取:1,2,3,4,51,2,3,5,61,3,4,5,61,2,4,5,62,3,4,5,6可满足条件,才能保证甲提取的5个数中,任意四个数一定在乙提取的某一组数中 举个例子:n = 6(1,2,3,4,5,6)甲提取:m = 5个数k = 4乙提取必须提取:1,2,3,4,51,2,3,5,61,3,4,5,61,2,4,5,62,3,4,5,6可满足条件,才能保证甲提取的5个数中,任意四个数一定在乙提取的某一组数中==============================1 2 3 4 6也满足你的条件吧你一共是6种那我的答案变为C(5,4)*C(1,1)+C(5,5)*C(1,0)=5*1+1*1=6满足条件啊 hi:ttaallkk1 我是说最少情况!!!不然答案就很简单了,就是C(6,5),推广到一般就是C(n,m) C(m,k)表示m中取k个。次数是:C(m,k)*C(n-m,m-k)+C(m,k+1)*C(n-m-1)+.......+C(m,m)*C(n-m,0)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~这种方法就是对的,你应该好好看看,好好想想! 哎呀 (m-1)*(m-2)*.....(1)次 int h=1;for(i=m-1;i>1;i--){h*=i;}h就是次数 写错了(n)*(n-1)*(n-2)*---(n-m+2)int h=1;for(int i=1;i<m-1;i++){ h*=(n-i);}h是次数 呵呵, 两个贴子, 两边都转转. 我得到了一个更小的数, 但不知道是不是最小的:C(n-m+k, k)取数方法为: 先取m-k个数放在一边( 以后不管怎么取, 这几个数都不变了), 再在剩下的n-m+k个数中取k 个, 取遍这n-m+k个中的所有k 组合即完成任务. 可以这样来理解:共有n个数,甲从中提取m个数(记为数组a[m]),乙如何提取m个数(假设提取的可能有t组长度为m的数组,记为b[t][m]),才能保证提取的所有m个数(数组b)中,一定有一组包括甲提取的m个数(数组a)中的k(k<m)个?如果k=m时,答案为c(n,m),现在问题是k=m-1,m-2...其中c(n,m)为在n中提取m个数的组合 ttaallkk1(j2ee_lover) ( ) 信誉:100 2006-6-15 15:25:17 得分: 0 举个例子:n = 6(1,2,3,4,5,6)甲提取:m = 5个数k = 4乙提取必须提取:1,2,3,4,51,2,3,5,61,3,4,5,61,2,4,5,62,3,4,5,6可满足条件,才能保证甲提取的5个数中,任意四个数一定在乙提取的某一组数中==============================1 2 3 4 6也满足你的条件吧你一共是6种那我的答案变为C(5,4)*C(1,1)+C(5,5)*C(1,0)=5*1+1*1=6满足条件啊 对你举的例子提个疑问,n =6甲提取:m = 5个数k = 4 的情况下,乙只要取一次就可以保证 取的5个数中肯定有4个在甲取的数内了,‘你的分析方法是对的,但结果我觉得是 c(n,m)-(C(m,k)*C(n-m,m-k)+C(m,k+1)*C(n-m-1)+.......+C(m,m)*C(n-m,0))+1.实际上C(m,k)*C(n-m,m-k)+C(m,k+1)*C(n-m-1)+.......+C(m,m)*C(n-m,0)只是"保证其中一定有甲提取的m个数中的k个"的所有组合数,假设其为C;对于题目的提取次数来说,当剩下提取的次数小于C的时候,一定可以"保证其中一定有甲提取的m个数中的k个"; 关于 C( n-m+k, k) 为要求的最小数的证明(此要求为对于甲所取的数中任意 k 个都可以在乙取的某一组中出现)。设基本集合为:S={1, 2, 3, ... , n},并令 S1 = { 1, 2, ... , m-k },S2 = { m-k+1, m-k+2, ... , n} 若存在 L < C( n-m+k, k) ,使得取 L 组,就可以满足要求,则取 L = C( n-m+k, k ) - 1 也可以满足要求。 现在来看 S2 中的所有 k 组合,因为 S2 中的 k 组合有 C( n-m+k, k ) 个,根据抽屉原理,则必有两个不同的 k 组合在同一组中,则在这一组中至少含有 S2 中的 k+1 个元素,也最多含有S1中的m-k-1个元素,所以S1中至少有一个元素未被包含在该组中,设其为t1。交换 S1,S2 中的元素t1, m-k+1,变成新的 S1' 和 S2' 。 对于新的集合S1',S2' 继续按照上面的推理,我们又可以得到 t2 不在某一组中,同样交换 t2, m-k+2得到新的集合S1'' 和 S2'',依次类推,我们可以得到集合T={t1, t2, ... , t_(n-m+k), t_(n-m+k+1)}(注意:T的元素个数比S2的多一个),该集合中的任意一个元素都不在所有组的交集内。所以我们知道这些组的交集元素个数不会超过 m-k-1。 对于 n 个元素的集合,可覆盖它的若干个 m 元子集的交的元素个数为2m-n,结合上面的结论,知:m-k-1<2m-n 即: n < m+k+1时产生了矛盾,故假设不成立。综上在 n, m, k 满足不等式 n < m+k+1 时,所需最少抽取组数为:C( n-m+k, k)另外 m-k-1 = 0 时表明交集为空,即乙取的各组数中有不相交的两组,这要满足要求只能是k=1。而在k=1时用上面的公式显然不对。 上面最后一句表述有误,不应该说存在不相交的两组就可以得出k只能是1。其实我是想说在 k=1 时C( n-m+k , k) 显然不是最小的。也可以找到其他例子,说明:n >= m+k+1 时,C( n-m+k, k ) 还不够小。 问题简化:对N个数中的任一种 k 个数的组合,我要每次取 m 个数(k >= m <= n),必须取多少组, 才能保证这 k 个数一定同时在某一组 m 当中?输入: int n,int m,int k输出: 提取次数 包含 k 的 m 共有: c(m-k,n)种m 共有: c(n,m)种取法不包含 k 的 m 共有: c(n,m)-c(m-k,n)种所以只要取: c(n,m)-c(m-k,n)+1 次,就可保证期待大家评定... 小弟有一算法问题想请教:有n个数(1,2,...n,n>3),现在甲从中任意抽取m(m=2,...n-1)个,乙要如何提取m个数,提取多少次,用什么算法,才能保证其中一定有甲提取的m个数中的k个(k=m-1)?另:当k=m-2,m-3时呢?我对题目的理解是这样的,结合彩票的玩法就可以理解了。假如是36选7的彩票,全中为1等奖,中6个为2等奖。题目的意思就是怎样买多少组才能够保证至少可以中一个2等奖。解题的思路如下:从m个数中取k个有c(m,k)种方法;从n-m个数种取m-k个数有c(n-m, m-k)种方法。那么乙从n个数种任意取m个数,其中有恰好k个在甲取的m个数中的取法有c(m,k)*c(n-m,m-k)种。同理,乙从n个数种任意取m个数,其中有恰好k+1个在甲取的m个数中的取法有c(m,k+1)*c(n-m,m-k-1)种。所以乙从n个数种任意取m个数,其中至少包含甲取的m个数种的k个的取法有:x = c(m,k)*c(n-m,m-k) + c(m,k+1)*c(n-m,m-k-1) +...+c(m,m)*c(n-m,0)而乙从n个数中任意取m个数的取法一共有:y = c(n,m)种方法。所以,为了保证乙取的数种至少有一组至少包含甲取的数中的k个,应该取y-x+1次,即c(n,m) - ( c(m,k)*c(n-m,m-k) + c(m,k+1)*c(n-m,m-k-1)+...+c(m,m)*c(n-m,0) )种方法。 上面最后一句写错了,应该是:c(n,m) - ( c(m,k)*c(n-m,m-k) + c(m,k+1)*c(n-m,m-k-1)+...+c(m,m)*c(n-m,0) )次。 crazy_lazy_pig(疯狂懒猪):^_^afrag() 的二等奖彩票:对头!组合是怎么定义的好像有点乱,我就按“C(m,k)表示m中取k个。”更正下自己的答案:----------------------------------------------------包含 k 的 m 共有: c(n,m-k)种m 共有: c(n,m)种取法不包含 k 的 m 共有: c(n,m)-c(n,m-k)种所以只要取: c(n,m)-c(n,m-k)+1 次,就可保证期待大家评定......----------------------------------------------------btw:CSDN的回复不能编辑,不然会少很多垃圾贴的吧,我这已经是第五贴了,同样声明,上面的作废,呵呵 to: soholi(天涯孤棹) 和 afrag()思路是正确的, 结果是存在的, 但是你们给出的是存在性证明, 并没有给出构造性的算法?问题的关键是怎么取这几组数, 如果转化成买彩票的理论, 那么就是彩民都关心的问题: 怎么买这几组号码? 单单给个组数是不够的. 还有个问题就是, 彩民在买彩票时, 中奖号码还没出来呢. 不好意思,前面说的例子不对:下面这个例子是最佳选择例如:n=6(1,2,3,4,5,6)m=5k=4实际上乙只取这一组好就满足条件:1,2,3,4,5不管甲取6种可能中的哪一组数(1,2,3,4,5 1,2,3,4,6 1,2,3,5,61,2,4,5,61,3,4,5,62,3,4,5,6)都至少有4个数是在乙取的哪一组数中 你的意思我已经明白了,程序就是按这个写的,上星期五走得匆忙,现把完整的几个C#程序奉上,大家运行下看看(很快写出来的,性能最低的了,而且用的ulong型,N不能超过20),结果不超过20的都可以手工对照一下,呵呵,例如:GetAdvice(5,3,2) = 4GetAdvice(6,3,2) = 11GetAdvice(6,4,2) = 1GetAdvice(6,4,3) = 7GetAdvice(6,5,4) = 1...GetAdvice(13,7,7) = 1716GetAdvice(13,7,6) = 1674 GetAdvice(13,7,5) = 1359GetAdvice(13,7,4) = 659GetAdvice(13,7,3) = 134GetAdvice(13,7,2) = 8GetAdvice(13,7,1) = 1信不信由你,随便买一张都能得个末等奖;花 3432 块钱就能保证得头奖——当然其它的不可能都是空奖啦;“至少”还有 1 个四等奖、10 个五等奖、202 个六等奖、1502 个七等奖!加 42张票*2块钱每张=84块钱 就能从二等奖到一等奖^_^当然规则是 m 个号码里的数字各不相同且取法不能有重复。private ulong GetAdvice(ulong n, ulong m, ulong k){// 乙最少要取的次数,请保证输入正确或自行添加判断逻辑 ulong answer = 0; for (ulong i = 1; i <= k; i++) { answer += C(n - m, m - k + i) * C(m, k - i); } return answer + 1;//鸽巢原理}private ulong C(ulong n, ulong m){// 在 n 中取 m 个数的组合数 if (n < m) { return 0; } else if (n == m){return 1;}//有无皆可 else if (m == 1 || n == m + 1){return n;}//有无皆可 else { return P(n, m) / P(m, m); }}private ulong P(ulong n, ulong m){// 在 n 中取 m 个数的排列数 if (n < m) { return 0; } else { return Factorial(n) / Factorial(n - m); }}private ulong Factorial(ulong n){// 取 n 的阶乘 if (n < 0) { throw new Exception("取阶乘时输入了非法 n 值"); } else if (n == 0 || n == 1) { return 1; } else { return n * Factorial(n - 1); }}啥时结贴,呵呵 GetAdvice(6,3,2) = 11 是你这个程序的答案吗? 如果是, 那么你的算法是有问题的. 很简单的想法: 10组是肯定可以的:(1, 2, 3) (1, 2, 4) (1, 2, 5) (1, 2, 6) (1, 3, 4) (1, 3, 5) (1, 3, 6) (1, 4, 5) (1, 4, 6) (1, 5, 6)其实, 还可以再少点:(1, 2, 3) (4, 5, 6) (3, 4, 5) (1, 2, 4) (1, 2, 5) (1, 2, 6) (1, 3, 6)如果是要满足甲抽取的3个数中有一组能在乙的这些组中的一组中出现, 则可以再少点:(1, 2, 3) (1, 2, 4) (1, 2, 5) (3, 4, 5) TO:crazy_lazy_pig(疯狂懒猪),咱们分歧在于:你要得到,我要得不到,呵呵编号:{1 2 3 4 5 6}甲任取设为:{2 3 4}则即不同含2、3,也不同含2、4,也不同含3、4的共有十种:152,153,154,162,163,164,562,563,564,156取到第十一种则一定同时含{2 3 4}中的两个!GetAdvice(6,3,2) = 11——至于要得到,针对(6,3,2),那么让(1 2 3 4 5 6)的 n=6 个中任 k=2 个在每次取 m=3 时至少有一次在一起就行了,12 12313-14 14515-16 16223-24 24525-26-34 34535-36 36445-46-56 56*结果是 6 次多一点,取 7 次能保证需要了,信息冗余又怎么优化呢?以下仅是猜测,不知各位有兴趣看下对否?在 n 个当中任意去除 m-k 个,对(1 2 3 4 5)重列如下:12 12313-14 14515-23-24 24525-34 34535-45-结果是 4 次!对 (6,3,2),结果从 11,到 7,再到 4(不论猜测是否正确),有不少进步呢! BTW:crazy_lazy_pig(疯狂懒猪)的(1,2,3)(1,2,4)(1,2,5)(3,4,5)与上面得出的 (1,2,3)(1,4,5)(2,4,5)(3,4,5) 等价于“让(1 2 3 4 5)的 5 个中任 2 个在每次取 3 个时至少有一次在一起”那么怎样求出所有的等价方案?新问题? to: soholi(天涯孤棹) 楼主就是要我们优化的, 关键是现在找不到一个确切可行的优化方案, 对现在这里提出来的几种方法我都可以找出反例, 证明其不是最优(包括我自己提出的). 找等价方案是没必要的, 关键是怎么缩小提取的组数, 会缩了, 也自然能找到等价方案了. to: crazy_lazy_pig(疯狂懒猪) 和 还在关注这个问题的朋友“让 n 个中任 k 个在每次取 m 个时至少有一次在一起”猜测“让 n-(m-k) 个中任 k 个在每次取 m 个时至少有一次在一起”对 (6,3,2) 来说,按我的两次穷举时的作法——顺序,是能用算法形式化的,数值大一点完全可以交给计算机去做。最坏的情况是 11 次,我能确保的情况是 7 次,按猜测,4 次是理论上的下限。猜测在 (6,4,2) 时也是成立的。(7,5,3)多一点:1 2 3 4 5 6 7123 12345124-125-126 12673127-134-135-136-137-145-146 14675147-156-157-167-17234-235-236-237-245-246 24675247-256-257-267-27345-346 34675347-356-357-367-37456-457-467-47567-57677结果是 5;猜测时去掉任 m-k=2 个重新编号——(5,5,3)还用做吗?1 2 3 4 5123 12345124-125-134-135-145-15234-235-245-25345-35455结果是 1;提一下,GetAdvice(7,5,3) = 1。 同意soholi的分析,对于n较小可以看出来,但n数值大了就不好办了 对任一含 n-m+k 个元素的集合共有 i = C(n-m+k,k) 种大小为 k 的子集做大小为 m 的子集对它们进行(覆盖?)至少需要多少个 关于九九乘法表的最后一个的显示问题,大家都看看,有新的可以贴贴 新手求教啊。。关于Hadoop 关于String一个非常非常奇怪的问题~~~~· 请问这种是什么编码“%B7%A2%C8%E7%D1%A9”?? 急求在线 菜鸟问问题,求解答!! Pattern p = Pattern.compile("[,\\s]+"); 这里 p 是对象吗? 请问 VB 中的 MSFlexGrid 控件的 DataSource 属性如何用法 ? JBuilder5的高手们,帮帮我吧!!! java awt 右键弹出菜单问题 基础问题? 将16进制字符串转换成10进制整数中的一点小疑问???
我的想法:
1,乙随机提取m个数。
2,甲从乙提取的m个数中随机提取k个数
3,甲从乙提取m个数之后剩下的n-m个数中随机提取m-k个数。
C(m,k)*C(n-m,m-k)+C(m,k+1)*C(n-m-1)+.......+C(m,m)*C(n-m,0)
n = 6(1,2,3,4,5,6)
甲提取:m = 5个数
k = 4
乙提取必须提取:
1,2,3,4,5
1,2,3,5,6
1,3,4,5,6
1,2,4,5,6
2,3,4,5,6
可满足条件,才能保证甲提取的5个数中,任意四个数一定在乙提取的某一组数中
n = 6(1,2,3,4,5,6)
甲提取:m = 5个数
k = 4
乙提取必须提取:
1,2,3,4,5
1,2,3,5,6
1,3,4,5,6
1,2,4,5,6
2,3,4,5,6
可满足条件,才能保证甲提取的5个数中,任意四个数一定在乙提取的某一组数中
==============================
1 2 3 4 6也满足你的条件吧你一共是6种那我的答案变为C(5,4)*C(1,1)+C(5,5)*C(1,0)=5*1+1*1=6
满足条件啊
C(n,m)
C(m,k)*C(n-m,m-k)+C(m,k+1)*C(n-m-1)+.......+C(m,m)*C(n-m,0)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
这种方法就是对的,你应该好好看看,好好想想!
int h=1;
for(i=m-1;i>1;i--)
{
h*=i;
}
h就是次数
for(int i=1;i<m-1;i++)
{
h*=(n-i);
}
h是次数
共有n个数,甲从中提取m个数(记为数组a[m]),乙如何提取m个数(假设提取的可能有t组长度为m的数组,记为b[t][m]),才能保证提取的所有m个数(数组b)中,一定有一组包括甲提取的m个数(数组a)中的k(k<m)个?
如果k=m时,答案为c(n,m),现在问题是k=m-1,m-2...
其中c(n,m)为在n中提取m个数的组合
举个例子:
n = 6(1,2,3,4,5,6)
甲提取:m = 5个数
k = 4
乙提取必须提取:
1,2,3,4,5
1,2,3,5,6
1,3,4,5,6
1,2,4,5,6
2,3,4,5,6
可满足条件,才能保证甲提取的5个数中,任意四个数一定在乙提取的某一组数中
==============================
1 2 3 4 6也满足你的条件吧你一共是6种那我的答案变为C(5,4)*C(1,1)+C(5,5)*C(1,0)=5*1+1*1=6
满足条件啊
对你举的例子提个疑问,
n =6
甲提取:m = 5个数
k = 4 的情况下,乙只要取一次就可以保证 取的5个数中肯定有4个在甲取的数内了,‘你的分析方法是对的,
但结果我觉得是 c(n,m)-(C(m,k)*C(n-m,m-k)+C(m,k+1)*C(n-m-1)+.......+C(m,m)*C(n-m,0)
)+1.
实际上C(m,k)*C(n-m,m-k)+C(m,k+1)*C(n-m-1)+.......+C(m,m)*C(n-m,0)只是"保证其中一定有甲提取的m个数中的k个"的所有组合数,假设其为C;
对于题目的提取次数来说,当剩下提取的次数小于C的时候,一定可以"保证其中一定有甲提取的m个数中的k个";
若存在 L < C( n-m+k, k) ,使得取 L 组,就可以满足要求,则取 L = C( n-m+k, k ) - 1 也可以满足要求。
现在来看 S2 中的所有 k 组合,因为 S2 中的 k 组合有 C( n-m+k, k ) 个,根据抽屉原理,则必有两个不同的 k 组合在同一组中,则在这一组中至少含有 S2 中的 k+1 个元素,也最多含有S1中的m-k-1个元素,所以S1中至少有一个元素未被包含在该组中,设其为t1。交换 S1,S2 中的元素t1, m-k+1,变成新的 S1' 和 S2' 。
对于新的集合S1',S2' 继续按照上面的推理,我们又可以得到 t2 不在某一组中,同样交换 t2, m-k+2得到新的集合S1'' 和 S2'',依次类推,我们可以得到集合T={t1, t2, ... , t_(n-m+k), t_(n-m+k+1)}(注意:T的元素个数比S2的多一个),该集合中的任意一个元素都不在所有组的交集内。所以我们知道这些组的交集元素个数不会超过 m-k-1。
对于 n 个元素的集合,可覆盖它的若干个 m 元子集的交的元素个数为2m-n,结合上面的结论,知:m-k-1<2m-n 即:
n < m+k+1
时产生了矛盾,故假设不成立。综上在 n, m, k 满足不等式 n < m+k+1 时,所需最少抽取组数为:C( n-m+k, k)另外 m-k-1 = 0 时表明交集为空,即乙取的各组数中有不相交的两组,这要满足要求只能是k=1。而在k=1时用上面的公式显然不对。
其实我是想说在 k=1 时C( n-m+k , k) 显然不是最小的。也可以找到其他例子,说明:n >= m+k+1 时,C( n-m+k, k ) 还不够小。
才能保证这 k 个数一定同时在某一组 m 当中?
输入: int n,int m,int k
输出: 提取次数
m 共有: c(n,m)种取法
不包含 k 的 m 共有: c(n,m)-c(m-k,n)种
所以只要取: c(n,m)-c(m-k,n)+1 次,就可保证
期待大家评定...
有n个数(1,2,...n,n>3),现在甲从中任意抽取m(m=2,...n-1)个,乙要如何提取m个数,提取多少次,用什么算法,才能保证其中一定有甲提取的m个数中的k个(k=m-1)?
另:当k=m-2,m-3时呢?我对题目的理解是这样的,结合彩票的玩法就可以理解了。假如是36选7的彩票,全中为1等奖,中6个为2等奖。题目的意思就是怎样买多少组才能够保证至少可以中一个2等奖。解题的思路如下:
从m个数中取k个有c(m,k)种方法;
从n-m个数种取m-k个数有c(n-m, m-k)种方法。
那么乙从n个数种任意取m个数,其中有恰好k个在甲取的m个数中的取法有
c(m,k)*c(n-m,m-k)种。
同理,乙从n个数种任意取m个数,其中有恰好k+1个在甲取的m个数中的取法有
c(m,k+1)*c(n-m,m-k-1)种。
所以乙从n个数种任意取m个数,其中至少包含甲取的m个数种的k个的取法有:
x = c(m,k)*c(n-m,m-k) + c(m,k+1)*c(n-m,m-k-1) +...+c(m,m)*c(n-m,0)
而乙从n个数中任意取m个数的取法一共有:
y = c(n,m)种方法。
所以,为了保证乙取的数种至少有一组至少包含甲取的数中的k个,应该取
y-x+1次,即
c(n,m) - ( c(m,k)*c(n-m,m-k) + c(m,k+1)*c(n-m,m-k-1)+...+c(m,m)*c(n-m,0) )种方法。
c(n,m) - ( c(m,k)*c(n-m,m-k) + c(m,k+1)*c(n-m,m-k-1)+...+c(m,m)*c(n-m,0) )次。
afrag() 的二等奖彩票:对头!
组合是怎么定义的好像有点乱,我就按“C(m,k)表示m中取k个。”更正下自己的答案:
----------------------------------------------------
包含 k 的 m 共有: c(n,m-k)种
m 共有: c(n,m)种取法
不包含 k 的 m 共有: c(n,m)-c(n,m-k)种
所以只要取: c(n,m)-c(n,m-k)+1 次,就可保证
期待大家评定......
----------------------------------------------------
btw:CSDN的回复不能编辑,不然会少很多垃圾贴的吧,我这已经是第五贴了,同样声明,上面的作废,呵呵
问题的关键是怎么取这几组数, 如果转化成买彩票的理论, 那么就是彩民都关心的问题: 怎么买这几组号码? 单单给个组数是不够的. 还有个问题就是, 彩民在买彩票时, 中奖号码还没出来呢.
下面这个例子是最佳选择
例如:
n=6(1,2,3,4,5,6)
m=5
k=4
实际上乙只取这一组好就满足条件:1,2,3,4,5
不管甲取6种可能中的哪一组数
(
1,2,3,4,5
1,2,3,4,6
1,2,3,5,6
1,2,4,5,6
1,3,4,5,6
2,3,4,5,6
)
都至少有4个数是在乙取的哪一组数中
GetAdvice(5,3,2) = 4
GetAdvice(6,3,2) = 11
GetAdvice(6,4,2) = 1
GetAdvice(6,4,3) = 7
GetAdvice(6,5,4) = 1
...
GetAdvice(13,7,7) = 1716
GetAdvice(13,7,6) = 1674
GetAdvice(13,7,5) = 1359
GetAdvice(13,7,4) = 659
GetAdvice(13,7,3) = 134
GetAdvice(13,7,2) = 8
GetAdvice(13,7,1) = 1
信不信由你,随便买一张都能得个末等奖;
花 3432 块钱就能保证得头奖——当然其它的不可能都是空奖啦;
“至少”还有 1 个四等奖、10 个五等奖、202 个六等奖、1502 个七等奖!
加 42张票*2块钱每张=84块钱 就能从二等奖到一等奖^_^
当然规则是 m 个号码里的数字各不相同且取法不能有重复。private ulong GetAdvice(ulong n, ulong m, ulong k)
{// 乙最少要取的次数,请保证输入正确或自行添加判断逻辑
ulong answer = 0;
for (ulong i = 1; i <= k; i++)
{
answer += C(n - m, m - k + i) * C(m, k - i);
}
return answer + 1;//鸽巢原理
}
private ulong C(ulong n, ulong m)
{// 在 n 中取 m 个数的组合数
if (n < m)
{
return 0;
}
else if (n == m){return 1;}//有无皆可
else if (m == 1 || n == m + 1){return n;}//有无皆可
else
{
return P(n, m) / P(m, m);
}
}
private ulong P(ulong n, ulong m)
{// 在 n 中取 m 个数的排列数
if (n < m)
{
return 0;
}
else
{
return Factorial(n) / Factorial(n - m);
}
}
private ulong Factorial(ulong n)
{// 取 n 的阶乘
if (n < 0)
{
throw new Exception("取阶乘时输入了非法 n 值");
}
else if (n == 0 || n == 1)
{
return 1;
}
else
{
return n * Factorial(n - 1);
}
}
啥时结贴,呵呵
(1, 2, 3) (1, 2, 4) (1, 2, 5) (1, 2, 6) (1, 3, 4) (1, 3, 5) (1, 3, 6) (1, 4, 5) (1, 4, 6) (1, 5, 6)其实, 还可以再少点:
(1, 2, 3) (4, 5, 6) (3, 4, 5) (1, 2, 4) (1, 2, 5) (1, 2, 6) (1, 3, 6)如果是要满足甲抽取的3个数中有一组能在乙的这些组中的一组中出现, 则可以再少点:
(1, 2, 3) (1, 2, 4) (1, 2, 5) (3, 4, 5)
编号:{1 2 3 4 5 6}
甲任取设为:{2 3 4}
则即不同含2、3,也不同含2、4,也不同含3、4的共有十种:
152,153,154,162,163,164,562,563,564,156
取到第十一种则一定同时含{2 3 4}中的两个!
GetAdvice(6,3,2) = 11——至于要得到,针对(6,3,2),那么让(1 2 3 4 5 6)的 n=6 个中任 k=2 个在每次取 m=3 时至少有一次在一起就行了,
12 123
13-
14 145
15-
16 162
23-
24 245
25-
26-
34 345
35-
36 364
45-
46-
56 56*
结果是 6 次多一点,取 7 次能保证需要了,信息冗余又怎么优化呢?以下仅是猜测,不知各位有兴趣看下对否?
在 n 个当中任意去除 m-k 个,对(1 2 3 4 5)重列如下:
12 123
13-
14 145
15-
23-
24 245
25-
34 345
35-
45-
结果是 4 次!
对 (6,3,2),结果从 11,到 7,再到 4(不论猜测是否正确),有不少进步呢!
与上面得出的 (1,2,3)(1,4,5)(2,4,5)(3,4,5) 等价于
“让(1 2 3 4 5)的 5 个中任 2 个在每次取 3 个时至少有一次在一起”
那么怎样求出所有的等价方案?新问题?
猜测“让 n-(m-k) 个中任 k 个在每次取 m 个时至少有一次在一起”
对 (6,3,2) 来说,按我的两次穷举时的作法——顺序,是能用算法形式化的,数值大一点完全可以交给计算机去做。
最坏的情况是 11 次,我能确保的情况是 7 次,按猜测,4 次是理论上的下限。
猜测在 (6,4,2) 时也是成立的。(7,5,3)多一点:
1 2 3 4 5 6 7123 12345
124-
125-
126 12673
127-
134-
135-
136-
137-
145-
146 14675
147-
156-
157-
167-
17
234-
235-
236-
237-
245-
246 24675
247-
256-
257-
267-
27
345-
346 34675
347-
356-
357-
367-
37
456-
457-
467-
47
567-
57
67
7
结果是 5;
猜测时去掉任 m-k=2 个重新编号——(5,5,3)还用做吗?
1 2 3 4 5123 12345
124-
125-
134-
135-
145-
15
234-
235-
245-
25
345-
35
45
5
结果是 1;提一下,GetAdvice(7,5,3) = 1。
共有 i = C(n-m+k,k) 种大小为 k 的子集
做大小为 m 的子集对它们进行(覆盖?)
至少需要多少个