資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告