HDU1204 糖果大战（概率论）

题目大意：生日Party结束的那天晚上，剩下了一些糖果，Gandon想把所有的都统统拿走，Speakless于是说：“可以是可以，不过我们来玩24点，你不是已经拿到了一些糖果了吗？这样，如果谁赢一局，就拿走对方一颗糖，直到拿完对方所有的糖为止。”如果谁能算出来而对方算不出来，谁就赢，但是如果双方都能算出或者都不能，就算平局，不会有任何糖果的得失。

Speakless是个喜欢提前想问题的人，既然他发起了这场糖果大战，就自然很想赢啦（不然可就要精光了-_-）。现在他需要你的帮忙，给你他每局赢的概率和Gardon每局赢的概率，请你给出他可能获得这场大战胜利的概率。

原题链接点击打开链接

题目解析：令f(i)表示Speakless的第i个糖果时的概率；

则可有题知p(1-q)表示Speakless赢得概率为f(i+1);

q(1-p)表示Speakless输得概率为f(i-1);

1-p(1-q)-q(1-p)表示平局的概率为f(i);

因此：

f(i) = p(1-q)*f(i+1) + q(1-p)*f(i-1) + (1-p(1-q)-q(1-p))*f(i)
稍微变形：
p(1-q)*(f(i+1)-f(i)) = q(1-p)*(f(i)-f(i-1))令g(i)=f(i)-f(i-1),
则有p(1-q)*g(i) = q(1-p)g(i-1),即g(i)是等比数列,
设k=q(1-p)/(p(1-q))，则g(i) = k*g(i-1)g(1) = f(1)-f(0)
g(2) = f(1)-f(0)
...
g(n) = f(n)-f(n-1)
...
g(n+m) = f(n+m)-f(n+m-1)
将上面的各个等式相加的：g(1)+g(2)+...+g(n+m)=f(n+m)-f(0)=1
g(1)+g(2)+...+g(n+m)=g(1)*(1-k^(n+m))/(1-k)
g(1)+g(2)+...+g(n)=g(1)*(1-k^(n))/(1-k)
回到开始定义，我们知道f(0)=0 (表示已经输了)，f(n+m)=1(表示已经赢了)
g(1)=f(1)-f(0)=f(1)
因此g(1)+g(2)+...+g(n+m) = f(1)*(1-k^(n+m))/(1-k)=1............................................（1）
g(1)+g(2)+...+g(n) = f(1)*(1-k^(n))/(1-k)=f(n)...................................................（2）

我们要求的就是f(n)，在（2）式中，只要f(1)是未知的，因此需要更（1）先求出f(1).最终f(n)=(1-k^n)/(1-k^(m+n))

需要注意的几个地方：N==0、M==0、p==0、q==0、p==q集易做图殊情况！

#include<iostream>  
#include<iomanip>  
#include<cmath>  
using namespace std; 
int main() 
{ 
    int n,m; 
    double p,q,ans,k; 
    while(cin>>n>>m>>p>>q) 
    { 
        if(n==0){cout<<"0.00"<<endl;continue;} 
        if(m==0){cout<<"1.00"<<endl;continue;} 
        if(p==0||q==1){cout<<"0.00"<<endl;continue;} 
        if(p==1||q==0){cout<<"1.00"<<endl;continue;} 
        if(p==q)ans=1.0*n/(n+m); 
        else 
            { 
                k=q*(1-p)/(p*(1-q)); 
                 ans=(1.0-pow(k,n))/(1.0-pow(k,n+m)); 
            } 
            cout<<fixed<<setprecision(2)<<ans<<endl; 
               /<SPAN style="FONT-SIZE: 10px">*setprecision</SPAN>控制输出流显示浮点数的数字个数，如果和fixed合用的话，可以控制小数点右面的位数 
               头文件为#include<iomanip>*/ 
    } 
 
return 0; 
} 

#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
int main()
{
    int n,m;
    double p,q,ans,k;
    while(cin>>n>>m>>p>>q)
    {
        if(n==0){cout<<"0.00"<<endl;continue;}
        if(m==0){cout<<"1.00"<<endl;continue;}
        if(p==0||q==1){cout<<"0.00"<<endl;continue;}
        if(p==1||q==0){cout<<"1.00"<<endl;continue;}
        if(p==q)ans=1.0*n/(n+m);
        else
            {
                k=q*(1-p)/(p*(1-q));
                 ans=(1.0-pow(k,n))/(1.0-pow(k,n+m));
            }
            cout<<fixed<<setprecision(2)<<ans<<endl;
               /*setprecision控制输出流显示浮点数的数字个数，如果和fixed合用的话，可以控制小数点右面的位数
               头文件为#include<iomanip>*/
    }
return 0;
}

补充：软件开发 , C++ ,