/**//* 题意:在一个圆形靶(20个数字)上,A,B两人扔飞镖 A是随意扔,B是朝着目标扔,不过有可能扔中目标的左右两格 起始,每个人有分值n,扔中某个数字n-该数字,如果该数字>n,则不减 谁先减为0,谁赢 现计算A,B两人各先扔时,赢的概率(每一次,两人是轮流扔的)
由于投的次数可以无限的,其实确定状态只需要知道A,B目前的分数即可了!!
pA[n,m] 表示A当前分值为n,B为m时,A现在扔了后赢的概率 pB[n,m] 表示A当前分值为n,B为m时,B现在扔了后赢的概率 pA[n,m] = 1/20*∑ {(1-pB[n-i,m])} pB[n,m] = max{1/3*∑ (1-pA[n][m-d(i+j)])} 上式是对于n>20,m>20时成立的 n<20 || m<20时,因为有可能扔了后那个数字比自身还大,则不减,即 p[n,m] <- p[n,m] 由自身决定,有环,解这样的方程组可以迭代 ★★★★★ 现赋给他们最低限度的值,然后普通那样子算 ★★★★★ */ #include<cstdio> #include<algorithm>
using namespace std;
const int MAXN = 502;
double pA[MAXN][MAXN]; double pB[MAXN][MAXN];
int board[22] = {5,20,1,18,4,13,6,10,15,2,17,3,19,7,16,8,11,14,9,12,5,20};
inline int next(int a,int b){return a>=b?a-b:a;}
void init() { for(int i=0;i<MAXN;i++)pA[0][i] = 1.0; for(int i=0;i<MAXN;i++)pB[i][0] = 1.0;
for(int n=1;n<MAXN;n++) for(int m=1;m<MAXN;m++) { //最低限度的值 if(n<=20)pA[n][m] = 1/20.0;//扔中n的概率就是1/20 if(m<=20)pB[n][m] = 1/3.0;//扔中目标的概率就是1/3 for(int it = 0;it<50;it++) { //pA[n,m] = 1/20*∑ {(1-pB[n-i,m])} pA[n][m] = 0.0; for(int i=1;i<=20;i++) pA[n][m] += (1-pB[next(n,i)][m])/20.0; //pB[n,m] = max{1/3*∑ (1-pA[n][m-d(i+j)])} // = 1 - min{1/3*∑pA[n][m-d(i+j)]} double val = 1e300; for(int i=1;i<=20;i++) { double t = 0; for(int j=-1;j<=1;j++) t += pA[n][next(m,board[i+j])]; t/=3; val = min(val,t); } pB[n][m] = 1 - val; if(n>20 && m>20)break; } } }
int main() { // freopen("in","r",stdin); init(); int n; while(scanf("%d",&n),n) printf("%.12f %.12f\n",pA[n][n],pB[n][n]);
return 0; }
|