本文主要是介绍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（赌徒破产问题 概率论）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
