ZJUT 1317 掷飞盘 （高斯解期望问题）
题目：有m个人，围成一个圈，有两个飞盘，1/2的概率往左往右掷，最初两个飞盘相隔n，问两个飞盘到一个人手中的期望次数为多少。
http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1317
每一次掷飞盘，有4种方案，两个都顺时针，两个都逆时针，一顺一逆。
对于这4种方案，造成飞盘间隔的变化是有规律的 我们令E[i]表示间隔为i时到目标状态的所需步数
那么E[i]=(2*E[i]+E[i-2]+E[i+2])/4。其中E[0]是目标状态为 0
E[n]为所求。
可以发现间隔的范围是 0-m/2，如果大于m/2可以转换一下。
一开始可能处理得非常麻烦，分了很多情况以及奇偶
不过可以直接转换，如果出现负的则转正，如果出现大于上界，则取另外一边的。
开始的WA是因为没有考虑到有一些状态不可达，又忽视了这个重要的地方。
先搜索一遍，标记可以到达的状态，并编号，然后对于这些状态建立方程
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<cmath>
#define LL long long
#define MOD 1000000007
#define eps 1e-6
#define zero(a) fabs(a)<eps
using namespace std;
int n,m,num[105],cnt,tot;
double a[105][105];
void debug(int n){
for(int i=0;i<n;i++){
for(int j=0;j<=n;j++)
printf("%.2f ",a[i][j]);
printf("\n");
}
}
int get(int x){
if(x<0) x=-x;
if(x>tot) x=m-x;
return x;
} www.zzzyk.com
void dfs(int x){
num[x]=cnt++;
int t=get(x-2);
if(num[t]==-1) dfs(t);
t=get(x+2);
if(num[t]==-1) dfs(t);
}
bool gauss(int n){
int i,j;
for(i=0,j=0;i<n&&j<n;j++){
int k;
for(k=i;k<n;k++)
if(!zero(a[k][j]))
break;
if(k<n){
if(i!=k)
for(int r=j;r<=n;r++) swap(a[i][r],a[k][r]);
double tt=1/a[i][j];
for(int r=j;r<=n;r++)
a[i][r]*=tt;
for(int r=0;r<n;r++)
if(r!=i){
for(int t=n;t>=j;t--)
a[r][t]-=a[r][j]*a[i][t];
}
i++;
}
}
for(int r=i;r<n;r++)
if(!zero(a[r][n]))
return false;
return true;
}
int main(){
while(scanf("%d%d",&m,&n)!=EOF){
if(n>m/2) n=m-n;
if(n==0){printf("0.00\n");continue;}
if(m%2==0&&n==1) {printf("INF\n");continue;}
tot=m/2;
memset(num,-1,sizeof(num));
cnt=0;
dfs(n);
if(num[0]==-1) {printf("INF\n");continue;}
memset(a,0,sizeof(a));
a[num[0]][num[0]]=1;
for(int i=1;i<=tot;i++){
if(num[i]!=-1){
int j=num[i];
a[j][j]=-2;a[j][cnt]=-4;
int t=get(i-2);
a[j][num[t]]++;
t=get(i+2);
a[j][num[t]]++;
}
}
// debug(cnt);
if(gauss(cnt)){
for(int i=0;i<cnt;i++)
if(zero(a[i][num[n]]-1))
printf("%.2f\n",a[i][cnt]);
}
else
puts("INF");
}
return 0;
}
补充：软件开发 , C++ ,
