计算 FUNPROB 的概率

Question

关于 - FUNPROB

解决办法是：

int N, M;
while(1) {
    scanf("%d %d", &N, &M);
    if (0 == N && 0 == M) break;

    if (N > M) printf("0.000000\n");
    else {
        double res = (double) (M-N+1) / (M+1);
        printf("%.6f\n", res);
    }   
}   

我的问题是关于线路

res = (M-N+1) / (M+1);

如何得出这样计算概率的结论？

Answer 1

起初很明显，如果N>M概率为零。

现在我想用指示N来证明。考虑M>0我想证明N=<M我们所拥有的 每一个res = (M-N+1) / (M+1)，N=0因为很明显概率是1。

因为N=1将每个身体5$以任意顺序排列在队列中，现在对于与10$您在一起的一个人来说，除了在队列前面之外，他可以将他放在任何地方，这样您就可以在M+1可用的位置之间进行M+1-1选择。所以N=1你有：res = (M-1+1) / (M+1)

假设公式对N=<k我想证明的每个人都是正确的，如果N=k+1公式仍然正确。对于放M人5$并且k人在任意队列$ 10。我们假设这res = (M-K+1) / (M+1)是处理这个队列的概率，每个人都可以获得他的票。如果10$有人落后于5$人，请考虑此队列中的工作队列之一，删除它们并递归执行此操作，直到没有5$人为止。这会起作用，因为正如我上面所说的，队列中的第一个人是10$一个，而且我还说过，将这个人放入队列N<M的概率是K+1在其中选择一个位置，M-k+1因为我们k 10$从队列中删除了这个人。这就像我们所说的N=1所以我们把概率K+1次5$人在队列为：((M-k) - 1 +1) / ((M - k) +1)（*），并指示我们有一个工作伫列，概率N=k是：(M-k +1) / (M +1)（* ）从（）和（*），我们把概率K+1人10$及M人与5$在问题的条件是队列：

[((Mk) - 1 +1) / ((M - k) +1)] * [(Mk +1) / (M +1)] = ((Mk) - 1 +1) / (M +1) ) = (M-(k+1) +1) / (M +1)

这是证明的结尾:)。

Answer 2

找到了答案。问题关键词是戴克词和加泰罗尼亚数。@Ali 的答案证明答案是正确的，但没有解释我们如何得出这个数字。

1. 意识到如果 M < N，则概率为 0。

2. 如果M>=N，则是有变化的必要条件但不是充分条件。你需要有正确的队列中的人的顺序。例如。M=3, N=2 MMMNN 正确，而 NNMMM 不正确。所以我们必须过滤掉不正确的可能队列。

可以根据在一个时间步长中向上/向下的路径来考虑问题。X 轴是时间轴，+Y 轴是 M，-Y 轴是 N。如果我们从 (0, 0) 开始，每个 M 向上遍历 1 个单元，每个 N 遍历 -1 个单元，那么我们总是在 (M+ N，MN）。

我们的答案是：（从 (0, 0) 到 (M+N, MN) 的路径总数 - 至少一次低于 X 轴的路径）/路径总数。

求解上述给出的答案为（M-N+1）/（M+1）。

*分子中的第二项使用反射原理。如果您想了解更多详细信息，请添加评论，我会更新答案。

最后一部分https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem#Variant:_ties_allowed