2023-09-27：用 go 语言，在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，并尝试进行 k 次移动。行和列是从 0 开始的，所以左上单元格是 (0

作者：福大大架构师每日一题

2023-09-27
北京
本文字数：3460 字
阅读完需：约 11 分钟

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表示骑士的初始位置。

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

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

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

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

go 完整代码如下：

package main
import "fmt"
func knightProbability(n int, k int, row int, column int) float64 {  dp := make([][][]float64, n)  for i := 0; i < n; i++ {    dp[i] = make([][]float64, n)    for j := 0; j < n; j++ {      dp[i][j] = make([]float64, k+1)      for t := 0; t <= k; t++ {        dp[i][j][t] = -1      }    }  }  return process2(n, k, row, column, dp)}
func process2(n, rest, r, c int, dp [][][]float64) float64 {  if r < 0 || r >= n || c < 0 || c >= n {    return 0  }  if dp[r][c][rest] != -1 {    return dp[r][c][rest]  }  var ans float64  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  return ans}
func main() {  n, k, row, column := 3, 2, 0, 0  result := knightProbability(n, k, row, column)  fmt.Println(result)}

复制代码

rust 完整代码如下：

fn knight_probability(n: i32, k: i32, row: i32, column: i32) -> f64 {    let mut dp = vec![vec![vec![-1.0; (k+1) as usize]; n as usize]; n as usize];
    return process2(n, k, row, column, &mut dp);}
fn process2(n: i32, rest: i32, r: i32, c: i32, dp: &mut Vec<Vec<Vec<f64>>>) -> f64 {    if r < 0 || r >= n || c < 0 || c >= n {        return 0.0;    }    if dp[r as usize][c as usize][rest as usize] != -1.0 {        return dp[r as usize][c as usize][rest as usize];    }
    let mut ans = 0.0;    if rest == 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[r as usize][c as usize][rest as usize] = ans;    return ans;}
fn main() {    let n = 3;    let k = 2;    let row = 0;    let column = 0;    println!("{}", knight_probability(n, k, row, column));}

复制代码

c++完整代码如下：

#include <iostream>#include <vector>using namespace std;
double process2(int n, int rest, int r, int c, vector<vector<vector<double>>>& dp) {    if (r < 0 || r >= n || c < 0 || c >= n) {        return 0;    }    if (dp[r][c][rest] != -1) {        return dp[r][c][rest];    }    double ans = 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;    return ans;}
double knightProbability(int n, int k, int row, int column) {    vector<vector<vector<double>>> dp(n, vector<vector<double>>(n, vector<double>(k + 1, -1.0)));    return process2(n, k, row, column, dp);}
int main() {    int n = 3, k = 2, row = 0, column = 0;    double result = knightProbability(n, k, row, column);    cout << "Result: " << result << endl;    return 0;}

复制代码

c 完整代码如下：

#include <stdio.h>#include <stdlib.h>
double process2(int n, int rest, int r, int c, double*** dp) {    if (r < 0 || r >= n || c < 0 || c >= n) {        return 0;    }    if (dp[r][c][rest] != -1) {        return dp[r][c][rest];    }    double ans = 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;    return ans;}
double knightProbability(int n, int k, int row, int column) {    double*** dp = (double***)malloc(n * sizeof(double**));    for (int i = 0; i < n; i++) {        dp[i] = (double**)malloc(n * sizeof(double*));        for (int j = 0; j < n; j++) {            dp[i][j] = (double*)malloc((k + 1) * sizeof(double));            for (int t = 0; t <= k; t++) {                dp[i][j][t] = -1;            }        }    }    double result = process2(n, k, row, column, dp);    for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            free(dp[i][j]);        }        free(dp[i]);    }    free(dp);    return result;}
int main() {    int n = 3, k = 2, row = 0, column = 0;    double result = knightProbability(n, k, row, column);    printf("Probability: %f\n", result);    return 0;}