首页 > ACM题库 > HDU-杭电 > HDU 1204 糖果大战-概率-[解题报告] C++
2013
12-04

HDU 1204 糖果大战-概率-[解题报告] C++

糖果大战

问题描述 :

生日Party结束的那天晚上,剩下了一些糖果,Gandon想把所有的都统统拿走,Speakless于是说:“可以是可以,不过我们来玩24点,你不是已经拿到了一些糖果了吗?这样,如果谁赢一局,就拿走对方一颗糖,直到拿完对方所有的糖为止。”如果谁能算出来而对方算不出来,谁就赢,但是如果双方都能算出或者都不能,就算平局,不会有任何糖果的得失。
Speakless是个喜欢提前想问题的人,既然他发起了这场糖果大战,就自然很想赢啦(不然可就要精光了-_-)。现在他需要你的帮忙,给你他每局赢的概率和Gardon每局赢的概率,请你给出他可能获得这场大战胜利的概率。

输入:

每行有四个数,Speakless手上的糖果数N、Gardon手上的糖果数M(0<=N,M<=50)、一局Speakless能解答出来的概率p、一个问题Gardon能解答出来的概率q(0<=p,q<=1)。

输出:

每行一个数,表示Speakless能赢的概率(用百分比计算,保留到小数点后2位)。

样例输入:

50 50 0.5 0.5
10 10 0.51 0.5
50 50 0.51 0.5

样例输出:

0.50
0.60
0.88

 

转自:http://friends119119.blog.163.com/blog/static/12434199520100299446587/

首先要说明几点:

   1. 这是一道数学题, 对学过随机过程的来说非常easy, 就是一个非常简单的Markov 过程. 不然的话会感觉无从下手, 想彻底搞明白的话,建议看看随机过程的书.
   2. 出题人喜欢玩儿些文字游戏, 设置了一些很无聊的陷阱, 非常无趣.
   3. 代码简单, 但要注意几个条件判断的顺序.
   4. bbs上有人给出了一些公式, 不过可惜其中的数学公式有问题的!.

  我们用Xt表示t时刻S君手中的糖果数, 则{Xt,t=0, 1, 2…..}是一个Markov Chain. 其状态转移概率为
                    P00=PNN=1, 这里N = m+n
                    Pi, i+1=p(1-q), Pi, i-1=(1-p)q, Pi, i=1-p(1-q)-q(1-p), i=1, 2, 3…., N-1; (*)
该MC的状态有3类{0}, {1, 2, …, N-1}, 以及{N}, 其中第二类是非常返的, 第一三类是常返的, 因为每个一非常返态通常仅到达有穷多次, 所以在进行可以在进行有穷多次博弈后, S君或者最终赢得所有糖果, 或者输掉所有糖果.
  这里我们的定义fi=fiN=Pr(S君经过有限次博弈赢得N个糖果|X0=i), 这里fi是一个条件概率, 就是开始的时候有i个糖果, 最中赢得N个糖果的概率. 从(*)式可以知道, 当我们有在某时刻t有i个糖果, 我们可以有三种途径可以最终赢得N个糖果. 1. 赢得一个糖果, 概率是p(1-q), 这是下一个时刻t+1G君就有了i+1个糖果. 2. 输掉比赛, 在下一个时刻变成了i-1个糖果, 概率是q(1-p). 3. 打成平手, 下一个时刻还有i个糖果, 概率是1-p(1-q)-q(1-p).
这样我么就可以得到如下公式
                   fi=p(1-q)*fi+1+q(1-p)*fi-1+(1-p(1-q)-q(1-p))*fi
令 P=p(1-q), Q=q(1-p), K=Q/P, 则
                fi+1-fi=K(fi-fi-1)
fi+1-fi是简单的等比数列, 则 fi+1-fi=Ki(f1-f0). 注意到fN=1,  f0=0, 这里N=m+n;
       f2-f1=Kf1
       f3-f2=K2f1
       …………….
         fn-fn-1=Kn-1f1
                   …………..
                   fm+n-fm+n-1=Km+n-1f1
相加一下, fn=(1+K+K2+…+Kn-1)f1, fn+m=(1+K+K2+…+Km+n-1)f1
所以fn=(1+K+K2+…+Kn-1)/(1+K+K2+…+Km+n-1), k!=1时, 可以化简为fn=(1-Kn)/(1-Km+n)
Done!
下面是个AC的代码, enjoy!

1.#include <stdio.h> 
2.#include <math.h> 
3.const double EPS = 1e-12; 
4.
5.inline void solve(int n, int m, double p, double q) { 
6.    if(n==0) { 
7.        printf("0.00\n"); 
8.    } 
9.    else if(m==0) { 
10.        printf("1.00\n"); 
11.    } 
12.    else if(p==0.0||q==1.0) { 
13.        printf("0.00\n"); 
14.    } 
15.    else { 
16.        double lamda = q*(1-p)/(p*(1-q)); 
17.        if(fabs(lamda-1.0)<EPS) { 
18.            printf("%.2lf\n", double(n)/(m+n)); 
19.        } 
20.        else { 
21.            double res = (1-pow(lamda, n))/(1-pow(lamda, m+n)); 
22.            printf("%.2lf\n", res); 
23.        } 
24.    } 
25.} 
26.
27.int main() 
28.{ 
29.    int n, m; 
30.    double p, q; 
31.    while(scanf("%d%d%lf%lf", &n, &m, &p, &q)!=EOF) { 
32.        solve(n, m, p, q); 
33.    } 
34.    return 0; 
35.}