UVA 11427 Excpect the Expected 期望+递推

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
double f[111][111];//f[i][j]表示玩了i盘，共赢了j盘的概率
int main()
{
    int T,tt=0;
    scanf("%d",&T);
    while(T--)
    {
        int i,j,k,n,m,x,y,ans;
        double p,q;
        scanf("%d/%d%d",&x,&y,&n);
        p=1.0*x/y;
        memset(f,0,sizeof(f));
        f[0][0]=1;
        for(i=1;i<=n;i++)
        {
            f[i][0]=f[i-1][0]*(1-p);
            for(j=1;j*y<=i*x;j++)
            {
                f[i][j]=f[i-1][j]*(1-p)+f[i-1][j-1]*p;
            }
        }
        q=0;
        for(i=0;i*y<=n*x;i++)
            q+=f[n][i];
        ans=(int)(1/q);
        printf("Case #%d: %d\n",++tt,ans);
    }
    return 0;
}
/*
题意：玩纸牌，每天最多玩n盘，每盘胜率为p，每天会一直玩下去直到赢的概率大于p，若有一天玩n盘都还没使胜率大于p则结束，
        求玩的天数的期望。
方法：每天玩纸牌独立，可以先求玩一天失败的概率q，再求期望。用f[i][j]表示玩了i盘，共赢了j盘的概率。则可以得到递推式：
        f[i][j]=f[i-1][j]*(1-p)+f[i-1][j-1]*p;边界处理:f[0][0]=1,其余全是0.还要注意f[i][0]=f[i-1][0]*(1-p);
        
      求得q后,EX=q+2*q*(1-q)+3*q*(1-q)*(1-q)+...
      令s=EX/q,s=1+2*(1-q)+3*(1-q)*(1-q)+...,(1-q)*s=(1-q)+2*(1-q)*(1-q)+3*(1-q)^3+...
      推出EX=s-(1-q)*s=1+(1-q)+(1-q)^2+...=1*(1-(1-q)^n)/q=1/q(n=∞)
*/