 /**//*
题意:在一个圆形靶(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;
}
|