首页 > 其他 > 详细

UVA概率练习[2]

时间:2017-03-05 16:01:58      阅读:163      评论:0      收藏:0      [点我收藏+]

UVa11021 Tribbles

你有K个麻球。一个只会存活一天。在死亡之前,一个麻球有P_i的概率生出i个麻球(i=0,1,…,n-1)。m天后所有麻球都死亡的概率是多少?(包含在第m天前全部死亡的情况)


 

麻球之间是独立的,只算一个麻球就行了

直接枚举生出几只麻球算概率

技术分享
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1005;
const double eps=1e-8;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<0||c>9){if(c==-)f=-1;c=getchar();}
    while(c>=0&&c<=9){x=x*10+c-0;c=getchar();}
    return x*f;
}
int n,m,k;
double p[N],f[N];
double Pow(double a,int b){
    double re=1.0;
    for(;b;b>>=1,a*=a)
        if(b&1) re*=a;
    return re;
}
int main(){
    freopen("tribbles.in","r",stdin);
    freopen("tribbles.out","w",stdout);
    int T=read(),cas=0;
    while(T--){
        n=read();k=read();m=read();
        for(int i=0;i<n;i++) scanf("%lf",&p[i]);
        f[1]=p[0];
        for(int i=2;i<=m;i++){
            f[i]=p[0];
            double po=1;
            for(int j=1;j<n;j++) po*=f[i-1],f[i]+=p[j]*po;
        }
        printf("Case #%d: %.7lf\n",++cas,Pow(f[m],k));
    }
}
View Code



Uva11427 Expect the Expected

我喜欢玩纸牌接龙。每次我都有p的概率赢,1-p的概率输。游戏程序会统计我获胜盘数的百分比。如果我一直玩下去,这个百分比就会在p*100%左右浮动。但我仍不满足。

这是我的计划。每天,我都会玩纸牌接龙。如果我赢了,我就高高兴兴地去睡觉。如果我输了,我就一直玩下去直到我这天获胜盘数的百分比严格大于p。这时,我就会宣布胜利,然后高高兴兴地去睡觉。你可以看到,每天我都可以宣布自己保持了获胜比例大于p*100%。我打败了数学规律!

如果你感觉这里好像有什么奇怪的东西,那你就对了。我不可能永远这么做,因为我每天玩的游戏盘数有限。我每天至多玩n盘游戏。那么,这个机智的计划在因为这一限制失败前,执行天数的数学期望是多少?值得注意的是,答案至少为1,因为我至少要玩一天才能发现计划失败了。


 

每天晚上独立,算一天晚上失败的概率

$f[i][j]$表示$i$局赢了$j$局.....

设失败概率$Q=\sum f[n][j]: \frac{j}{n}\le p$

然后加权上天数求期望,列出来发现是无穷级数.......

然后看白书,成功得到解法

好吧说个靠谱的:猜测既然是无穷级数前面的系数应该没影响吧,套公式

$\sum\limits_{i=1}^{\infty}x^{ik}=\frac{1}{1-x^k}$

 

 

 

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1005;
const double eps=1e-8;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<0||c>9){if(c==-)f=-1;c=getchar();}
    while(c>=0&&c<=9){x=x*10+c-0;c=getchar();}
    return x*f;
}
int n,m,k;
double p[N],f[N];
double Pow(double a,int b){
    double re=1.0;
    for(;b;b>>=1,a*=a)
        if(b&1) re*=a;
    return re;
}
int main(){
    freopen("tribbles.in","r",stdin);
    freopen("tribbles.out","w",stdout);
    int T=read(),cas=0;
    while(T--){
        n=read();k=read();m=read();
        for(int i=0;i<n;i++) scanf("%lf",&p[i]);
        f[1]=p[0];
        for(int i=2;i<=m;i++){
            f[i]=p[0];
            double po=1;
            for(int j=1;j<n;j++) po*=f[i-1],f[i]+=p[j]*po;
        }
        printf("Case #%d: %.7lf\n",++cas,Pow(f[m],k));
    }
}

 

UVA概率练习[2]

原文:http://www.cnblogs.com/candy99/p/6505614.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!