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=∞)
*/