计算FUNPROB的概率 [英] Calculating probability for FUNPROB

问题描述

关于-

Regarding - FUNPROB

The solution is :

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);
    }   
}   

My question is regarding line

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

How to arrive at the conclusion that the probability is calculated in this way ?

解决方案

Found the answer. The problem keywords are Dyck words and Catalan number. @Ali's answer is the proof that answer is correct but doesnt explain how we arrive at the number.

1. Realise that if M < N, probability is 0.

2. If M >= N, its a necessary condition for having change but not sufficient. You need to have the correct order of people in queue. For eg. M=3, N=2 MMMNN is correct while NNMMM is not correct. So we have to filter out incorrect possible queues.

The problem can be thought of in terms of paths that go up/down in one time step. X axis is time axis, +Y axis is M and -Y axis is N. If we start from (0, 0) traverse up 1 unit for each M and -1 unit for each N then we always end up at (M+N, M-N).

Our answer is: (Total number of paths from (0, 0) to (M+N, M-N) - Paths which go below X axis at least once) / Total number of paths.

Solving for above gives answer as (M-N+1)/(M+1).

*The second term in numerator comes using reflection principle. If you want more details, add a comment and I will update the answer.

for the last part https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem#Variant:_ties_allowed

这篇关于计算FUNPROB的概率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！