c++ - 计算 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$ person 删除它们并递归执行此操作，直到没有 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$的人在有问题的队列中条件是:

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

证明到此结束:)。