首页 > ACM题库 > UVA > Uva-11427-Expect the Expected [概率]
2013
12-11

Uva-11427-Expect the Expected [概率]

题目大意:每天晚上你都玩纸牌,如果第一次赢了就高高兴兴地去睡觉;如果输了就接着玩,假设每盘游戏获胜的的概率都是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=105;
double d[Max][Max];

int main()
{
    int t,a,b,i,j,Case,n;
    double p,Q;
    cin>>t;
    for(Case=1;Case<=t;Case++)
    {
        scanf("%d/%d %d",&a,&b,&n);
        p=(double)a/b;
        memset(d,0.0,sizeof(d));
        d[0][0]=1.0;d[0][1]=0.0;
        for(i=1;i<=n;i++)
        {
            for(j=0;b*j<=a*i;j++)
            {
                d[i][j]=d[i-1][j]*(1-p);
                if(j) d[i][j]+=d[i-1][j-1]*p;
            }
        }
        Q=0.0;
        for(i=0;i*b<=a*n;i++) Q+=d[n][i];
        printf("Case #%d: %d\n",Case,(int)(1/Q));
    }
    return 0;
}

转自:http://www.tuicool.com/articles/ZfI3e2


  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  2. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢