2023-09-27：用go语言，在一个 n x n 的国际象棋棋盘上，一个骑

2023-09-27：用go语言，在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，

并尝试进行 k 次移动。行和列是 从 0 开始 的，所以左上单元格是 (0,0)，

右下单元格是 (n - 1, n - 1)，象棋骑士有8种可能的走法，

每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格，类似马走日，

每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。

骑士继续移动，直到它走了 k 步或离开了棋盘。

返回 骑士在棋盘停止移动后仍留在棋盘上的概率。

输入: n = 3, k = 2, row = 0, column = 0。

输出: 0.0625。

来自左程云。

答案2023-09-27：

这段代码实现了一个求解国际象棋棋盘上骑士留在棋盘上的概率的函数。函数接收四个参数：表示棋盘大小，表示骑士的移动次数，和表示骑士的初始位置。

knightProbability

n

k

row

column

主要的函数是，它使用动态规划的思想来求解。首先，根据当前位置和剩余移动次数，计算出骑士在当前位置的概率。如果当前位置已经计算过，则直接返回之前的结果。否则，根据题目要求，将当前位置向8个可能的方向移动，并将每个方向的概率除以8，然后递归计算骑士在下一步位置的概率，并将所有可能的结果相加得到当前位置的概率。最后，将计算的结果记录在dp数组中，以便之后的计算可以直接使用。

process2

在主函数中，给定了初始参数n=3，k=2，row=0，column=0，然后调用函数计算骑士停止移动后留在棋盘上的概率，并将结果打印出来。

knightProbability

总的时间复杂度：由于每个位置最多计算一次，而每个位置的计算需要遍历所有剩余移动次数，所以总的时间复杂度为O(n^2 * k)。

总的额外空间复杂度：dp数组的大小为nnk，所以总的额外空间复杂度为O(n^2 * k)。

go完整代码如下：

packagemain
import"fmt"
funcknightProbability(nint,kint,rowint,columnint)float64{
dp:=make([][][]float64,n)
fori:=0;idp[i]=make([][]float64,n)
forj:=0;jdp[i][j]=make([]float64,k+1)
fort:=0;t<=k;t++{
dp[i][j][t]=-1
}
}
}
returnprocess2(n,k,row,column,dp)
}
funcprocess2(n,rest,r,cint,dp[][][]float64)float64{
ifr<0||r>=n||c<0||c>=n{
return0
}
ifdp[r][c][rest]!=-1{
returndp[r][c][rest]
}
varansfloat64
ifrest==0{
ans=1
}else{
ans+=(process2(n,rest-1,r-2,c+1,dp)/8)
ans+=(process2(n,rest-1,r-1,c+2,dp)/8)
ans+=(process2(n,rest-1,r+1,c+2,dp)/8)
ans+=(process2(n,rest-1,r+2,c+1,dp)/8)
ans+=(process2(n,rest-1,r+2,c-1,dp)/8)
ans+=(process2(n,rest-1,r+1,c-2,dp)/8)
ans+=(process2(n,rest-1,r-1,c-2,dp)/8)
ans+=(process2(n,rest-1,r-2,c-1,dp)/8)
}
dp[r][c][rest]=ans
returnans
}
funcmain(){
n,k,row,column:=3,2,0,0
result:=knightProbability(n,k,row,column)
fmt.Println(result)
}

rust完整代码如下：

fnknight_probability(n:i32,k:i32,row:i32,column:i32)->f64{
letmutdp=vec![vec![vec![-1.0;(k+1)asusize];nasusize];nasusize];
returnprocess2(n,k,row,column,&mutdp);
}
fnprocess2(n:i32,rest:i32,r:i32,c:i32,dp:&mutVec>>)->f64{
ifr<0||r>=n||c<0||c>=n{
return0.0;
}
ifdp[rasusize][casusize][restasusize]!=-1.0{
returndp[rasusize][casusize][restasusize];
}
letmutans=0.0;
ifrest==0{
ans=1.0;
}else{
ans+=(process2(n,rest-1,r-2,c+1,dp)/8.0);
ans+=(process2(n,rest-1,r-1,c+2,dp)/8.0);
ans+=(process2(n,rest-1,r+1,c+2,dp)/8.0);
ans+=(process2(n,rest-1,r+2,c+1,dp)/8.0);
ans+=(process2(n,rest-1,r+2,c-1,dp)/8.0);
ans+=(process2(n,rest-1,r+1,c-2,dp)/8.0);
ans+=(process2(n,rest-1,r-1,c-2,dp)/8.0);
ans+=(process2(n,rest-1,r-2,c-1,dp)/8.0);
}
dp[rasusize][casusize][restasusize]=ans;
returnans;
}
fnmain(){
letn=3;
letk=2;
letrow=0;
letcolumn=0;
println!("{}",knight_probability(n,k,row,column));
}

c++完整代码如下：

#include
#include
usingnamespacestd;
doubleprocess2(intn,intrest,intr,intc,vector>>&dp){
if(r<0||r>=n||c<0||c>=n){
return0;
}
if(dp[r][c][rest]!=-1){
returndp[r][c][rest];
}
doubleans=0;
if(rest==0){
ans=1;
}
else{
ans+=(process2(n,rest-1,r-2,c+1,dp)/8);
ans+=(process2(n,rest-1,r-1,c+2,dp)/8);
ans+=(process2(n,rest-1,r+1,c+2,dp)/8);
ans+=(process2(n,rest-1,r+2,c+1,dp)/8);
ans+=(process2(n,rest-1,r+2,c-1,dp)/8);
ans+=(process2(n,rest-1,r+1,c-2,dp)/8);
ans+=(process2(n,rest-1,r-1,c-2,dp)/8);
ans+=(process2(n,rest-1,r-2,c-1,dp)/8);
}
dp[r][c][rest]=ans;
returnans;
}
doubleknightProbability(intn,intk,introw,intcolumn){
vector>>dp(n,vector>(n,vector(k+1,-1.0)));
returnprocess2(n,k,row,column,dp);
}
intmain(){
intn=3,k=2,row=0,column=0;
doubleresult=knightProbability(n,k,row,column);
cout<<"Result:"<return0;
}

c完整代码如下：

#include
#include
doubleprocess2(intn,intrest,intr,intc,double***dp){
if(r<0||r>=n||c<0||c>=n){
return0;
}
if(dp[r][c][rest]!=-1){
returndp[r][c][rest];
}
doubleans=0;
if(rest==0){
ans=1;
}
else{
ans+=(process2(n,rest-1,r-2,c+1,dp)/8);
ans+=(process2(n,rest-1,r-1,c+2,dp)/8);
ans+=(process2(n,rest-1,r+1,c+2,dp)/8);
ans+=(process2(n,rest-1,r+2,c+1,dp)/8);
ans+=(process2(n,rest-1,r+2,c-1,dp)/8);
ans+=(process2(n,rest-1,r+1,c-2,dp)/8);
ans+=(process2(n,rest-1,r-1,c-2,dp)/8);
ans+=(process2(n,rest-1,r-2,c-1,dp)/8);
}
dp[r][c][rest]=ans;
returnans;
}
doubleknightProbability(intn,intk,introw,intcolumn){
double***dp=(double***)malloc(n*sizeof(double**));
for(inti=0;idp[i]=(double**)malloc(n*sizeof(double*));
for(intj=0;jdp[i][j]=(double*)malloc((k+1)*sizeof(double));
for(intt=0;t<=k;t++){
dp[i][j][t]=-1;
}
}
}
doubleresult=process2(n,k,row,column,dp);
for(inti=0;ifor(intj=0;jfree(dp[i][j]);
}
free(dp[i]);
}
free(dp);
returnresult;
}
intmain(){
intn=3,k=2,row=0,column=0;
doubleresult=knightProbability(n,k,row,column);
printf("Probability:%f\n",result);
return0;
}