算法高手请进！！！（不限语言，最好用java，解决后一定给分，不够再加）

题目似乎没有说完整。是说必须甲提取的数中有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，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
满足条件啊

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...
其中ｃ（ｎ，ｍ）为在ｎ中提取ｍ个数的组合

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，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个"；

关于　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=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个数是在乙取的哪一组数中

你的意思我已经明白了，程序就是按这个写的，上星期五走得匆忙，现把完整的几个C#程序奉上，大家运行下看看（很快写出来的，性能最低的了，而且用的ulong型，N不能超过20），结果不超过20的都可以手工对照一下，呵呵，例如：
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);
    }
}
啥时结贴，呵呵

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 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(不论猜测是否正确)，有不少进步呢！

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 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
结果是１；提一下，GetAdvice(7,5,3) = 1。

同意soholi的分析，对于n较小可以看出来，但n数值大了就不好办了

对任一含 n-m+k 个元素的集合
共有 i = C(n-m+k,k) 种大小为 k 的子集
做大小为 m 的子集对它们进行(覆盖?)
至少需要多少个

调试易

算法高手请进！！！（不限语言，最好用java，解决后一定给分，不够再加）

解决方案 »