2

我试图解决这个 TopCoder 问题： http: //community.topcoder.com/stat ?c=problem_statement&pm=10863&rd=14150

但是，我的解决方案不好，我不明白为什么。

我了解那里给出的解决方案（下页：寻找 LotteryPyaterochka）：http ://apps.topcoder.com/wiki/display/tc/SRM+466

所以，总结一下我的问题：

我们正在玩一种特殊的彩票：

该彩票中的每张彩票都是一个 N 行 5 列的矩形网格，其中每个单元格包含一个介于 1 和 5*N 之间的整数，包括 1 和 5*N。一张票中的所有整数都是不同的。

彩票组织者随机选择 5 个不同的整数，每个整数介于 1 和 5*N 之间，包括 1 和 5*N。5 个整数的每个可能子集都具有相同的被选中概率。这些整数被称为中奖号码。当且仅当彩票有一行包含至少 3 个中奖号码时，该彩票才被视为中奖。

我们想知道中奖号码（因此，在同一行中至少有 3 个中奖号码）

所以，我坚持以下步骤：

选择出现在“中奖行”中的 5 个数字的方法数。

topCoder 解决方案说：

（#选择“中奖行”中出现的 5 个数字的方法）=

(#选择出现在“中奖行”中的x个中奖号码的方法) * (#选择5-x个“未中奖号码”的方法) =

(5 选择 x) * ((5N-5) 选择 (5-x))

由于该行中的中奖号码至少为 3，x 可以是 3 或 4 或 5。所以，我们有 (#ways of selection 出现在“中奖行”中的 5 个数字) =

(5选3)*((5N-5)选2)+(5选4)*((5N-5)选1)+(5选5)*((5N-5)选0))

我说的是：

（#选择“中奖行”中出现的 5 个数字的方法）=

（5个中奖号码中的3个号码）*（5N-5个未中奖号码中的2个完成行选择+之前未选择的2个中奖号码）=

(5N 选择 3) * ((5N-3)选择 2)

对于 N = 10，我的方法给出：（5 选择 3）*（47 选择 2）= 10810

而topcoder方法给出：((5选3) (45选2)+(5选4) (45选1)+(5选5)*(45选0))=10126

为什么我的方法不对？

谢谢

4

1 回答 1

2

假设中奖号码是 1、2、3、4 和 5。现在让我们看看包含中奖行中所有五个号码的彩票。

您的方法多次计算该票，因为它包含在以下计数中：

1 2 3 + two other numbers
1 2 4 + two other numbers
1 2 5 + two other numbers
1 3 4 + two other numbers
...

同样的事情也发生在有四个中奖号码的彩票上。

这就是为什么这些案件需要分开计算的原因。

于 2013-03-23T12:23:11.040 回答