hdu_1024_糖果大战_201404021640
糖果大战
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 1886 Accepted Submission(s): 626
Speakless是个喜欢提前想问题的人,既然他发起了这场糖果大战,就自然很想赢啦(不然可就要精光了-_-)。现在他需要你的帮忙,给你他每局赢的概率和Gardon每局赢的概率,请你给出他可能获得这场大战胜利的概率。
10 10 0.51 0.5
50 50 0.51 0.5
0.60
0.88
#include <stdio.h>
#include <math.h>
int main()
{
int m,n;
double p,q,r,s;
while(scanf("%d %d %lf %lf",&n,&m,&p,&q)!=EOF)
{
if(m == )
printf("%.2lf\n",1.0);
else if(n == )
printf("%.2lf\n",0.0);
else if(p == ||q == )
printf("%.2lf\n",0.0);
else if(p == ||q == )
printf("%.2lf\n",1.0);
else
{
r = q*(-p)/(p*(-q));
if(fabs(r-1.0)<(1e-))
s = n*1.0/(n+m);
else
s = (-pow(r,n))/(-pow(r,m+n));
printf("%.2lf\n",s);
}
}
return ;
}
先来看一个例子,即赌徒输光问题:
(链接:http://www.cnblogs.com/hsqdboke/archive/2012/03/08/2384769.html)
另一种思路:
这是一个概率题,首先我们必须清楚我们要求的是什么!设f(i)表示Speakless有i颗糖果的时候赢的概率,我们要求的就是f(n)
则根据题意我们知道,这时候:
1.Speakless赢这一局的概率是p(1-q),即f(i)变成f(i+1)
2.Speakless输这一局的概率是q(1-p),即f(i)变成f(i-1)
3.Speakless平这一局的概率是1-p(1-q)-q(1-p),即f(i)变成f(i)
因此:
f(i) = p(1-q)*f(i+1) + q(1-p)*f(i-1) + (1-p(1-q)-q(1-p))*f(i)
稍微变形:
p(1-q)*(f(i+1)-f(i)) = q(1-p)*(f(i)-f(i-1))令g(i)=f(i)-f(i-1),
则有p(1-q)*g(i) = q(1-p)g(i-1),即g(i)是等比数列,
设k=q(1-p)/(p(1-q)),则g(i) = k*g(i-1)g(1) = f(1)-f(0)
g(2) = f(1)-f(0)
...
g(n) = f(n)-f(n-1)
...
g(n+m) = f(n+m)-f(n+m-1)
将上面的各个等式相加的:g(1)+g(2)+...+g(n+m)=f(n+m)-f(0)=1
g(1)+g(2)+...+g(n+m)=g(1)*(1-k^(n+m))/(1-k)
g(1)+g(2)+...+g(n)=g(1)*(1-k^(n))/(1-k)
回到开始定义,我们知道f(0)=0 (表示已经输了),f(n+m)=1(表示已经赢了)
g(1)=f(1)-f(0)=f(1)
因此g(1)+g(2)+...+g(n+m) = f(1)*(1-k^(n+m))/(1-k)=1............................................(1)
g(1)+g(2)+...+g(n) = f(1)*(1-k^(n))/(1-k)=f(n)...................................................(2)我们要求的就是f(n),在(2)式中,只要f(1)是未知的,因此需要更(1)先求出f(1).最终f(n)=(1-k^n)/(1-k^(m+n))需要注意的几个地方:N==0、M==0、p==0、q==0、p==q集中特殊情况!
(链接:http://hi.baidu.com/nicker2010/item/cb20f55ea60de63f94eb05ed)
最新文章
- asp.net后台注册js的四种方法
- DB2 SQLCODE 大全
- 在执行Action之间检验是否登录
- maven nexus deploy方式以及相关注意事项
- kudu
- Java实现多线程邮件发送
- install Nagios on Unbuntu Unix
- IOS 学习笔记 2015-03-22 OC-API-日期
- Java RMI简单例子HelloWorld
- Python学习笔记 — 函数
- Arrays和String单元测试 20175301
- [android]android项目的目录结构
- hadoop常见问题
- 使用IDEA新建Web工程启动报404的错误
- [微信开发] 微信JSAPI - 获取用户地理位置信息
- 《算法》BEYOND 部分程序 part 1
- javaScript 中的一些日常用法总结
- loadruner11 socket脚本-10053错误
- 初识iVew table表属性
- WCF服务上应用protobuf z