本文主要是介绍Gambler's Ruin(赌徒破产问题 概率论),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
赌徒破产问题,做tc时遇到,顺便拿来好好研究下
英文原版地址为:Gambler's Ruin
问题如下:
一个赌徒有h枚金币,每次有概率a获得一枚金币或者概率(1-a)丢掉一枚金币,直到其所有的金币总数达到N或0则游戏结束,求赌徒最终赢得N枚金币的概率P(N|h)。
对于两个状态我们可以确定,即P(N|N)=1、P(N|0)=0。同时得出状态转移公式(概率的推导和普通的DP还是很不一样的,好好体会下):
P(N|h) = a*P(N|h+1) + (1-a)*P(N|h-1)
这类公式可以表示为二阶线性递归关系,其特征多项式为(自行百度):
x^2 - 1/a * x + (1-a)/a = 0
求出特征方程的根为1和r=(1-a)/a,针对a==1/2的情况需要特殊处理。得到公式的通解为:
P(N|h) = A*(1^h) + B*(r^h)
根据已知条件P(N|N)=1、P(N|0)=0得:
1 = A + B*(r^N)
0 = A + B
A = -1/(r^N - 1)、B = 1/(r^N - 1)
得到最终解 P(N|h) = (r^h - 1)/(r^N - 1)
但是当a==1/2时,特征方程有重根,因此这种情况下通解为
P(N|h) = A+B*h
A = 0、B=1/N
即 P(N|h) = h/N
再来看topcoder srm 667 div1 500的题
Problem Statement | |||||||||||||
There are N cats sitting around a circle. The cats are numbered 0 throughN-1 in clockwise order. Note that as they sit around a circle, catN-1 is adjacent to cat 0. The cats are playing a game and the winner will get a prize! The game looks as follows:
In other words, the winner is the last cat to touch the ball. Note that cat 0 holds the ball at the beginning, and this does count as holding the ball. Hence, if there is more than one cat, cat 0 can never win the game. Cat K wonders what is the probability that she will win the prize. You are given the intsN,K, and p. Return the probability that catK wins. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Limits | |||||||||||||
| |||||||||||||
Notes | |||||||||||||
- | Your return value must have an absolute or relative error smaller than or equal to 1e-6 | ||||||||||||
Constraints | |||||||||||||
- | N will be between 3 and 1,000,000,000, inclusive. | ||||||||||||
- | K will be between 1 and N-1, inclusive. | ||||||||||||
- | p will be between 1 and 999,999,999, inclusive. | ||||||||||||
Examples | |||||||||||||
0) | |||||||||||||
| |||||||||||||
1) | |||||||||||||
| |||||||||||||
2) | |||||||||||||
| |||||||||||||
3) | |||||||||||||
| |||||||||||||
4) | |||||||||||||
| |||||||||||||
5) | |||||||||||||
| |||||||||||||
6) | |||||||||||||
|
题意:
N只猫围成一圈玩游戏,顺时针编号0~N-1,N-1与0相邻。游戏规则如下:
、一开始编号0的猫拿着一个球
、每个回合中手里拿球的猫抛硬币,该硬币有P/1000000000的概率正面朝上,(1-P/1000000000)的概率反面朝上
、如果硬币正面朝上,则该猫 j 把球传给编号为(1+j)%N的猫,否则传给编号为(j-1+N)%N的猫
、该游戏持续进行直到每只猫至少拿到一次球。且最终拿球的猫赢得游戏
现在给定N K P,求出编号为K的猫赢得游戏的概率。
分析:
1. 如果最终猫K拿到球并结束游戏,那么之前一回合必然是猫K-1或K+1拿球,且除K外的猫都至少拿过一次球。则最终的结果为P(K+1,K-1) + P(K-1,K+1),既猫K+1先拿到球的前提下K-1拿到球的概率加上猫K-1先拿到球的前提下K+1拿到球的概率。这样就可以了,因为当全局只剩下K没有拿过球,K必然是最后一个拿到球的。
2. 这种情况和赌徒破产问题有什么类似之处呢?再来回顾下赌徒破产问题,该问题求的是当前有h枚金币的情况下,赢得N枚金币的概率。不如我们换一种表述方式,即该赌徒一开始最多能连续输掉h枚金币。放到这题的环境中,我们假设顺时针走等于金币加一,逆时针走等于金币减一。
3. 以求解P(K-1,K+1)为例,需要将其拆分为两种概率的乘积:P(a)=从0出发向左走最多到达K+2,且向右走必然到达K-1;P(b)=从K-1出发向右最多到达K-1,且向左走必然到达K+1;这样一来就可以套赌徒破产问题了。
4. 大于1.0的浮点数求幂可能会爆,需要控制一下
总结:
概率真是tm的神奇
#include <cstdio>
#include <iostream>
#include <string>
#include<assert.h>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
typedef long long int ll;
#define rp(i,b) for(int i=(0),__tzg_##i=(b);i<__tzg_##i;++i)
#define rep(i,a,b) for(int i=(a),__tzg_##i=(b);i<__tzg_##i;++i)
#define repd(i,a,b) for(int i=(a),__tzg_##i=(b);i<=__tzg_##i;++i)
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
const double Denominator = 1e9;
const double eps = 1/Denominator;
struct CatsOnTheCircle {double gamblers_ruin(int n, int h, double p) {double q = 1.0-p;if (fabs(p-q) < eps)return 1.0*h/n;if (q > p)return 1-gamblers_ruin(n, n-h, q);double r = q/p;return (pow(r,h)-1)/(pow(r,n)-1);}double getProb(int N, int K, int _p){double p = _p/Denominator;double q = 1.0-p;double o = gamblers_ruin(N-2, N-K-1, p);double u = gamblers_ruin(N-2, K-1, q);return o*gamblers_ruin(N-1, 1, q) + u*gamblers_ruin(N-1, 1, p);}
};
这篇关于Gambler's Ruin(赌徒破产问题 概率论)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!