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

impor服务器托管网t "fmt"

func knightProbability(n int, k int, row int, column int) float64 {
	dp := make([][][]float64, n)
	for i := 0; i = n || 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>>) -> f64 {
    if r = n || 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 
#include 
using namespace std;

double process2(int n, int rest, int r, int c, vector>>& dp) {
    if (r = n || 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>> dp(n, vector>(n, vector(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 

c完整代码如下：

#include 
#include 

double process2(int n, int rest, int r, int c, double*** dp) {
    if (r = n || c = n) {
        return 0;
    }
    if (dp[r][c][rest] != -1) {
        ret服务器托管网urn 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 

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: Linux安装达梦数据库DM8

1、简介描述 DM8是达梦公司在总结DM系列产品研发与应用经验的基础上，坚持开放创新、简洁实用的理念，推出的新一代自研数据库。DM8吸收借鉴当前先进新技术思想与主流数据库产品的优点，融合了分布式、弹性计算与云计算的优势，对灵活性、易用性、可靠性、高安全性等方面…