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