uva 11427

题目大意：每天晚上你都玩纸牌，如果第一次赢了就高高兴兴地去睡觉；如果输了就接着玩，假设每盘游戏获胜的的概率都是p，且各盘游戏相互独立。你是一个固执的完美主义者，因此会一直玩到当晚获胜局数的比例严格大于p时才停止，然后高高兴兴地去睡觉。当然，晚上的时间有限，最懂只玩n盘游戏，如果获胜比例一直不超过p的话，你只能垂头丧气地去睡觉，以后再也不玩纸牌了。你的任务是计算出平均情况下，你会玩多少个晚上的纸牌。

分析：每天晚上的情况相互独立，因此先研究单独一天的情况，计算出只玩一晚上纸牌时，“垂头丧气地去睡觉”的概率Q。

设d(i,j)表示前i局中每局结束后的获胜比例均不超过p，且前i局一共获胜j局的概率，则根据全概率公式有：j/i<=p时d(i,j)=d(i-1,j)*(1-p)+d(i-1,j-1)*p,其他d(i,j)=0,边界为d(0,0)=1,d(0,1)=0。则d(n,0)+d(n,1)+...d(n,n)就是所求的Q（玩n把只赢i把（符合j/i<=p）的概率和）

下面用数学期望的定义来计算游戏总天数X的数学期望。

X=1概率为Q。

X=2概率为Q（1-Q）：第一天高高兴兴（概率为1-Q），第二天垂头丧气（概率Q）。

X=3概率为Q（1-Q）^2:前两天高高兴兴（概率为（1-Q）^2），第二天垂头丧气（概率Q）。

……

X=k概率为Q（1-Q）^(k-1):前k-1天高高兴兴（概率为（1-Q）^(k-1)）,第k天垂头丧气（概率Q）。

因此数学期望E（X）=Q+2Q(1-Q)+3Q(1-Q)^2+4Q(1-Q)^3……无穷级数求极限

E(X)/Q=1+2(1-Q)+3(1-Q)^2+4(1-Q)^3…… （1）

E(X)/Q*(1-Q)=(1-Q)+2(1-Q)^2+3(1-Q)^3+4(1-Q)^4…… （2）

由（1）-（2）得（等比数列求和公式sn=a1*(1-q^n)/(1-q)）

E(X)=(1-(1-Q)^n)/Q-n(1-Q)^n=1/Q (0<（1-Q）<1,当n趋向于无穷大的时候lim(1-Q)^n=0)

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int Max=;

double d[Max][Max];

int main()

{

    int t,a,b,i,j,Case,n;

    double p,Q;

    cin>>t;

    for(Case=;Case<=t;Case++)

    {

        scanf("%d/%d %d",&a,&b,&n);

        p=(double)a/b;

        memset(d,0.0,sizeof(d));

        d[][]=1.0;d[][]=0.0;

        for(i=;i<=n;i++)

        {

            for(j=;b*j<=a*i;j++)

            {

                d[i][j]=d[i-][j]*(-p);

                if(j) d[i][j]+=d[i-][j-]*p;

            }

        }

        Q=0.0;

        for(i=;i*b<=a*n;i++) Q+=d[n][i];

        printf("Case #%d: %d\n",Case,(int)(/Q));

    }

    return ;

}

巴特西

uva 11427

最新文章

热门文章