2023-09-27：用go語言，在一個 n x n 的國際象棋棋盤上，一個騎士從單元格 (row, col
2023-09-27：用go語言，在一個 n x n 的國際象棋棋盤上，一個騎士從單元格 (row, column) 開始，
并嘗試進行 k 次移動。行和列是 從 0 開始 的，所以左上單元格是 (0,0)，
右下單元格是 (n - 1, n - 1)，象棋騎士有8種可能的走法，
每次移動在基本方向上是兩個單元格，然后在正交方向上是一個單元格，類似馬走日，
每次騎士要移動時，它都會隨機從8種可能的移動中選擇一種(即使棋子會離開棋盤)，然后移動到那里。
騎士繼續(xù)移動，直到它走了 k 步或離開了棋盤。
返回 騎士在棋盤停止移動后仍留在棋盤上的概率。
輸入: n = 3, k = 2, row = 0, column = 0。
輸出: 0.0625。
來自左程云。
答案2023-09-27：
這段代碼實現(xiàn)了一個求解國際象棋棋盤上騎士留在棋盤上的概率的函數(shù)。函數(shù)knightProbability接收四個參數(shù)：n表示棋盤大小，k表示騎士的移動次數(shù)，row和column表示騎士的初始位置。
主要的函數(shù)是process2，它使用動態(tài)規(guī)劃的思想來求解。首先，根據(jù)當(dāng)前位置和剩余移動次數(shù)，計算出騎士在當(dāng)前位置的概率。如果當(dāng)前位置已經(jīng)計算過，則直接返回之前的結(jié)果。否則，根據(jù)題目要求，將當(dāng)前位置向8個可能的方向移動，并將每個方向的概率除以8，然后遞歸計算騎士在下一步位置的概率，并將所有可能的結(jié)果相加得到當(dāng)前位置的概率。最后，將計算的結(jié)果記錄在dp數(shù)組中，以便之后的計算可以直接使用。
在主函數(shù)中，給定了初始參數(shù)n=3，k=2，row=0，column=0，然后調(diào)用knightProbability函數(shù)計算騎士停止移動后留在棋盤上的概率，并將結(jié)果打印出來。
總的時間復(fù)雜度：由于每個位置最多計算一次，而每個位置的計算需要遍歷所有剩余移動次數(shù)，所以總的時間復(fù)雜度為O(n^2 * k)。
總的額外空間復(fù)雜度：dp數(shù)組的大小為nnk，所以總的額外空間復(fù)雜度為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++完整代碼如下：
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完整代碼如下：
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;
}
