2

所以我在业余时间一直在解决一个问题，但我被困住了。这就是我所在的地方。我有一个数字 40。它代表球员。我得到了其他数字 39, 38, .... 10。这些代表前 30 名玩家的分数 (1 -30)。其余的球员（31-40）有一些未知的分数。我想做的是找出有多少分数组合与给定数据一致。

所以举个更简单的例子：如果你有 3 个玩家。一个人的得分为 1。那么得分的可能组合数为 3 (0,2; 2,0; 1,1)，其中 (a,b) 代表玩家一和玩家二的获胜次数， 分别。(3,0) 的组合不起作用，因为没有人可以赢得 3 场胜利。(0,0) 也行不通，因为我们总共需要 3 场胜利（而 0,0 则无法获得）。

我找到了可能的游戏总数。这是玩的总局数，也就是总胜局数。（没有平局。）最后，我有一个变量来表示每位玩家的最大胜利（比玩家总数少一。没有玩家可以拥有更多。）

我尝试通过将 N 次胜利分配给每个玩家然后减去不符合标准的组合来找到唯一组合的数量。例如，要找出许多方法让 5 个人获得 10 次胜利，而每个人获得的胜利不超过 4 次，您可以使用：C(14,4) - C(5,1)*C(9,4) + C (5,2)*C(4,4) = 381。C(14,4) 来自公式 C(n+k-1, k-1)（我相信谷歌酒吧和条带）。接下来是选择带有 5 的那些（不允许），但添加我们减去两次的那些。

是的，必须有一个更简单的方法。最后，数字变得如此之大，以至于我不确定我的计算机能否充分处理它们。我们讨论的是 C(780, 39)，即 1.15495183 × 10^66。无论如何，应该有更好的方法来做到这一点。

回顾一下，你有 40 个人。前 30 人的分数是 10 - 39，后 10 人的分数未知。您可以生成多少符合标准的分数：所有分数加起来就是可能的总获胜次数，每位玩家不再获得 39 次胜利。

想法？

4

1 回答 1

2

生成函数：

由于这个问题更多的是关于数学，但仍然在一个编程 QA 站点上，让我给你一个部分解决方案，它使用符号代数（如 Maple of Mathematica）适用于许多这些问题。我强烈建议你拿一本介绍组合学的书，这类问题在那里得到了解答。

首先前 30 名得分为 10-39（总分 735）的选手有点扯淡——我们要做的是解决另一个问题，剩下的 10 名选手得分可能在(0...39) 的范围。

如果我们将玩家的可能得分视为多项式：

f(x) = x^0 + x^1 + x^2 + ... x^39

例如，如果 x^2 的值是 2 的分数，请考虑一下它的样子

f(x)^10

这代表了所有 10 名玩家的综合得分，即。的系数x^385是 2002，表示 10 名玩家有 2002 种方式得分 385。Wolfram Alpha（一种编程语言 IMO）可以为我们评估这一点。

如果您想知道有多少种可能的方法，只需在x=1表达式中替换为 8,140,​​406,085,191,601，恰好是 39^10（不足为奇！）

为什么这很有用？

虽然我知道对一些人来说，为一个可以在纸上解决的简单问题设置所有这些机制似乎很愚蠢——当问题变得混乱时（并且可以进行渐近分析），生成函数的方法很有用。考虑同样的问题，但现在我们限制玩家只能得分质数（2,3,5,7,11,...）。他们中的 10 个人可以通过多少种可能的方式获得一个特定的数字，比如 344？只需修改您的f(x)：

f(x) = x^2 + x^3 + x^5 + x^7 + x^11 ...

并重复这个过程！（我明白了 [x^344]f(x)^10 = 1390）。

于 2012-03-16T13:58:39.763 回答