数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++实现象棋骑士概率
假设我们有一个NxN的棋盘，一个骑士从第r行第c列开始，尝试走恰好K步。此处行和列的索引从0开始，因此左上角的方格是(0, 0)，右下角的方格是(N-1, N-1)。
骑士从一个方格可以移动到8个不同的方格，如下图所示：
每次骑士移动时，它都会随机选择八种可能的移动方式之一。骑士会一直移动，直到它走了恰好K步或移出了棋盘。我们需要找到骑士在停止移动后仍然留在棋盘上的概率。
例如，如果输入为3, 2, 0, 0，则输出为0.0625。这是因为有两步移动（到(1,2)，(2,1)）会使骑士停留在棋盘上。现在，从这两个位置中的每一个位置开始，也有两步移动会使骑士停留在棋盘上。因此，骑士停留在棋盘上的总概率为0.0625。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个方向数组dir，例如：[[-2,-1], [-2, 1],[2,-1], [2, 1], [1,2], [1,-2], [-1,2], [-1,-2]]
- 定义递归方法solve()，它将接收x、y、n、k和三维数组dp作为参数
- 如果x >= n 或 y >= n 或 x < 0 或 y < 0，则返回0
- 如果k为0，则返回1
- 如果dp[k,x,y]不为-1，则返回dp[k,x,y]
- dp[k, x, y] := 0
- 对于i从0到7
- dp[k,x,y] := solve(x+dir[i,0], y + dir[i, 1], n, k – 1, dp)
- 返回dp[k,x,y]
- 在主方法中，执行以下操作：
- 创建一个大小为(k + 1) x N x N的三维数组。将其全部填充为-1
- 返回solve(r, c, N, k, dp) / (8^K)
让我们来看下面的实现来更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
int dir[8][2] = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
class Solution {
public:
double solve(int x, int y, int n, int k, vector < vector < vector < double > > >& dp){
if(x >= n || y >= n || x < 0 || y < 0 ) return 0.0;
if(k == 0) return 1.0;
if(dp[k][x][y] != -1) return dp[k][x][y];
dp[k][x][y] = 0;
for(int i = 0; i < 8; i++){
dp[k][x][y] += solve(x + dir[i][0], y + dir[i][1], n, k - 1, dp);
}
return dp[k][x][y];
}
double knightProbability(int N, int K, int r, int c) {
vector < vector < vector < double > > > dp (K + 1, vector < vector < double > >(N, vector < double >(N, -1))) ;
return solve(r, c, N, K, dp) / pow(8, K);
}
};
main(){
Solution ob;
cout << (ob.knightProbability(3, 2, 0, 0));
}输入
3 2 0 0
输出
0.0625
更新于：2020年5月4日
339 次浏览
广告