logo

TechCodeview

Probabilidade do Cavalo permanecer no tabuleiro de xadrez

Experimente no GfG Practice ' title=

Dado um n * n tabuleiro de xadrez e o cavaleiro posição (x-y) cada vez que o cavalo se move, ele escolhe um dos oito movimentos possíveis uniformemente em aleatório (mesmo que a peça saia do tabuleiro) e movimentos lá. O cavaleiro continua movendo-se até que tenha feito exatamente k se move ou tem mudou-se o tabuleiro de xadrez. A tarefa é encontrar o probabilidade que o cavaleiro restos no quadro depois que tiver parou em movimento.

Observação: Um cavalo de xadrez pode fazer oito movimentos possíveis. Cada movimento consiste em duas células na direção cardinal e depois uma célula na direção ortogonal.

Exemplos:  



Entrada: n = 8 x = 0 y = 0 k = 1
Saída: 0,25
Explicação: O cavalo começa em (0 0) e depois de dar um passo ficará dentro do tabuleiro em apenas 2 das 8 posições que são (1 2) e (2 1). Assim, a probabilidade será 2/8 = 0,25.

Entrada : n = 8 x = 0 y = 0 k = 3
Saída: 0,125

Entrada: n = 4 x = 1 y = 2 k = 4
Saída: 0,024414

Índice

Usando Dp de cima para baixo (memoização) - O(n*n*k) Tempo e O(n*n*k) Espaço

A probabilidade do cavalo permanecer no tabuleiro de xadrez após k movimentos é igual à média da probabilidade do cavalo nas oito posições anteriores após k - 1 movimentos. Da mesma forma, a probabilidade após k-1 movimentos depende da média da probabilidade após k-2 movimentos. A ideia é usar memorização para armazenar as probabilidades dos movimentos anteriores e encontrar sua média para calcular o resultado final.
Para isso crie um Memorando de matriz 3D[][][] onde memorando[i][j][k] armazena a probabilidade do cavaleiro estar na célula (i j) após k movimentos. Se k for zero, ou seja, o estado inicial é alcançado retornar 1 caso contrário, explore as oito posições anteriores e encontre a média de suas probabilidades.

C++ 
// C++ program to find the probability of the // knight to remain inside the chessboard #include    using namespace std; // recursive function to calculate // knight probability double knightProbability(int n int x int y int k   vector<vector<vector<double>>> &memo){  // Base case initial probability  if(k == 0) return 1.0;  // check if already calculated  if(memo[x][y][k] != -1) return memo[x][y][k];  vector<vector<int>> directions = {{1 2} {2 1} {2 -1}  {1 -2} {-1 -2} {-2 -1} {-2 1} {-1 2}};  memo[x][y][k] = 0;  double cur = 0.0;  // for every position reachable from (xy)  for(auto d:directions){  int u = x + d[0];  int v = y + d[1];  // if this position lie inside the board  if (u >= 0 && u < n && v >= 0 && v < n)  cur += knightProbability(n u v k-1 memo) / 8.0;  }  return memo[x][y][k] = cur; } // Function to find the probability double findProb(int n int x int y int k) {  // Initialize memo to store results  vector<vector<vector<double>>> memo(n   vector<vector<double>>(n  vector<double> (k+1 -1)));  return knightProbability(n x y k memo); } int main(){  int n = 8 x = 0 y = 0 k = 3;  cout << findProb(n x y k) << endl;  return 0; }
Java 
// Java program to find the probability of the // knight to remain inside the chessboard class GfG {  // recursive function to calculate  // knight probability  static double knightProbability(int n int x   int y int k double[][][] memo) {  // Base case initial probability  if (k == 0) return 1.0;  // check if already calculated  if (memo[x][y][k] != -1) return memo[x][y][k];  int[][] directions = {{1 2} {2 1} {2 -1} {1 -2}  {-1 -2} {-2 -1} {-2 1} {-1 2}};  memo[x][y][k] = 0;  double cur = 0.0;  // for every position reachable from (x y)  for (int[] d : directions) {  int u = x + d[0];  int v = y + d[1];  // if this position lies inside the board  if (u >= 0 && u < n && v >= 0 && v < n)  cur += knightProbability(n u v k - 1 memo) / 8.0;  }  return memo[x][y][k] = cur;  }  // Function to find the probability  static double findProb(int n int x int y int k) {  // Initialize memo to store results  double[][][] memo = new double[n][n][k + 1];  for (int i = 0; i < n; i++) {  for (int j = 0; j < n; j++) {  for (int m = 0; m <= k; m++) {  memo[i][j][m] = -1;  }  }  }  return knightProbability(n x y k memo);  }  public static void main(String[] args) {  int n = 8 x = 0 y = 0 k = 3;  System.out.println(findProb(n x y k));  } }
Python 
# Python program to find the probability of the # knight to remain inside the chessboard # recursive function to calculate # knight probability def knightProbability(n x y k memo): # Base case initial probability if k == 0: return 1.0 # check if already calculated if memo[x][y][k] != -1: return memo[x][y][k] directions = [ [1 2] [2 1] [2 -1] [1 -2] [-1 -2] [-2 -1] [-2 1] [-1 2] ] memo[x][y][k] = 0 cur = 0.0 # for every position reachable from (x y) for d in directions: u = x + d[0] v = y + d[1] # if this position lies inside the board if 0 <= u < n and 0 <= v < n: cur += knightProbability(n u v k - 1 memo) / 8.0 memo[x][y][k] = cur return cur # Function to find the probability def findProb(n x y k): # Initialize memo to store results memo = [[[-1 for _ in range(k + 1)] for _ in range(n)] for _ in range(n)] return knightProbability(n x y k memo) n x y k = 8 0 0 3 print(findProb(n x y k))
C# 
// C# program to find the probability of the // knight to remain inside the chessboard using System; class GfG {  // recursive function to calculate  // knight probability  static double KnightProbability(int n int x   int y int k double[] memo) {  // Base case initial probability  if (k == 0) return 1.0;  // check if already calculated  if (memo[x y k] != -1) return memo[x y k];  int[] directions = {{1 2} {2 1} {2 -1} {1 -2}  {-1 -2} {-2 -1} {-2 1} {-1 2}};  memo[x y k] = 0;  double cur = 0.0;  // for every position reachable from (x y)  for (int i = 0; i < 8; i++) {  int u = x + directions[i 0];  int v = y + directions[i 1];  // if this position lies inside the board  if (u >= 0 && u < n && v >= 0 && v < n) {  cur += KnightProbability(n u v k - 1 memo) / 8.0;  }  }  return memo[x y k] = cur;  }  // Function to find the probability  static double FindProb(int n int x int y int k) {  // Initialize memo to store results  double[] memo = new double[n n k + 1];  for (int i = 0; i < n; i++) {  for (int j = 0; j < n; j++) {  for (int m = 0; m <= k; m++) {  memo[i j m] = -1;  }  }  }  return KnightProbability(n x y k memo);  }  static void Main() {  int n = 8 x = 0 y = 0 k = 3;  Console.WriteLine(FindProb(n x y k));  } }
JavaScript 
// JavaScript program to find the probability of the // knight to remain inside the chessboard // recursive function to calculate // knight probability function knightProbability(n x y k memo) {  // Base case initial probability  if (k === 0) return 1.0;  // check if already calculated  if (memo[x][y][k] !== -1) return memo[x][y][k];  const directions = [  [1 2] [2 1] [2 -1] [1 -2]  [-1 -2] [-2 -1] [-2 1] [-1 2]  ];  memo[x][y][k] = 0;  let cur = 0.0;  // for every position reachable from (x y)  for (let d of directions) {  const u = x + d[0];  const v = y + d[1];  // if this position lies inside the board  if (u >= 0 && u < n && v >= 0 && v < n) {  cur += knightProbability(n u v k - 1 memo) / 8.0;  }  }  return memo[x][y][k] = cur; } // Function to find the probability function findProb(n x y k) {  // Initialize memo to store results  const memo = Array.from({ length: n } () =>  Array.from({ length: n } () => Array(k + 1).fill(-1)));  return knightProbability(n x y k memo).toFixed(6); } const n = 8 x = 0 y = 0 k = 3;  console.log(findProb(n x y k));

Saída 
0.125

Usando Dp Bottom-Up (Tabulação) - Tempo O(n*n*k) e Espaço O(n*n*k)

A abordagem acima pode ser otimizada usando baixo para cima tabulação reduzindo o espaço extra necessário para pilha recursiva. A ideia é manter um 3 Matriz D dp[][][] onde dp[i][j][k] armazena a probabilidade do cavaleiro estar na célula (eu j) depois k se move. Inicialize o 0º estado de DP com valor 1 . Para cada movimento subsequente, o probabilidade de cavaleiro será igual para média de probabilidade de anterior 8 posições depois k-1 se move.

C++ 
// C++ program to find the probability of the // knight to remain inside the chessboard #include    using namespace std; // Function to find the probability double findProb(int n int x int y int k) {  // Initialize dp to store results of each step  vector<vector<vector<double>>> dp(n   vector<vector<double>>(n  vector<double> (k+1)));    // Initialize dp for step 0  for (int i = 0; i < n; ++i) {  for (int j = 0; j < n; ++j) {  dp[i][j][0] = 1.0;  }  }  vector<vector<int>> directions = {  {1 2} {2 1} {2 -1} {1 -2}   {-1 -2} {-2 -1} {-2 1} {-1 2}  };  for (int move = 1; move <= k; move++) {    // find probability for cell (i j)  for (int i = 0; i < n; ++i) {  for (int j = 0; j < n; ++j) {  double cur = 0.0;  // for every position reachable from (xy)  for (auto d:directions) {  int u = i + d[0];  int v = j + d[1];  // if this position lie inside the board  if (u >= 0 && u < n && v >= 0 && v < n)  cur += dp[u][v][move - 1] / 8.0;  }  // store the result  dp[i][j][move] = cur;  }  }  }  // return the result  return dp[x][y][k]; } int main(){  int n = 8 x = 0 y = 0 k = 3;  cout << findProb(n x y k) << endl;  return 0; }
Java 
// Java program to find the probability of the // knight to remain inside the chessboard import java.util.*; class GfG {  // Function to find the probability  static double findProb(int n int x int y int k) {  // Initialize dp to store results of each step  double[][][] dp = new double[n][n][k + 1];  for (int i = 0; i < n; i++) {  for (int j = 0; j < n; j++) {  dp[i][j][0] = 1;  }  }  int[][] directions = {  {1 2} {2 1} {2 -1} {1 -2}   {-1 -2} {-2 -1} {-2 1} {-1 2}  };  for (int move = 1; move <= k; move++) {  // find probability for cell (i j)  for (int i = 0; i < n; ++i) {  for (int j = 0; j < n; ++j) {  double cur = 0.0;  // for every position reachable from (x y)  for (int[] d : directions) {  int u = i + d[0];  int v = j + d[1];  // if this position lies inside the board  if (u >= 0 && u < n && v >= 0 && v < n) {  cur += dp[u][v][move - 1] / 8.0;  }  }  // store the result  dp[i][j][move] = cur;  }  }  }  // return the result  return dp[x][y][k];  }  public static void main(String[] args) {  int n = 8 x = 0 y = 0 k = 3;  System.out.println(findProb(n x y k));  } }
Python 
# Python program to find the probability of the # knight to remain inside the chessboard # Function to find the probability def findProb(n x y k): # Initialize dp to store results of each step dp = [[[0 for _ in range(k + 1)] for _ in range(n)] for _ in range(n)] for i in range(n): for j in range(n): dp[i][j][0] = 1.0 directions = [[1 2] [2 1] [2 -1] [1 -2] [-1 -2] [-2 -1] [-2 1] [-1 2]] for move in range(1 k + 1): # find probability for cell (i j) for i in range(n): for j in range(n): cur = 0.0 # for every position reachable from (x y) for d in directions: u = i + d[0] v = j + d[1] # if this position lies inside the board if 0 <= u < n and 0 <= v < n: cur += dp[u][v][move - 1] / 8.0 # store the result dp[i][j][move] = cur # return the result return dp[x][y][k] if __name__ == '__main__': n x y k = 8 0 0 3 print(findProb(n x y k))
C# 
// C# program to find the probability of the // knight to remain inside the chessboard using System; class GfG {  // Function to find the probability  static double findProb(int n int x int y int k) {  // Initialize dp to store results of each step  double[] dp = new double[n n k + 1];  for (int i = 0; i < n; i++) {  for (int j = 0; j < n; j++) {  dp[i j 0] = 1.0;  }  }  int[] directions = {{1 2} {2 1} {2 -1} {1 -2}   {-1 -2} {-2 -1} {-2 1} {-1 2}};  for (int move = 1; move <= k; move++) {  // find probability for cell (i j)  for (int i = 0; i < n; ++i) {  for (int j = 0; j < n; ++j) {  double cur = 0.0;  // for every position reachable from (x y)  for (int d = 0; d < directions.GetLength(0); d++) {  int u = i + directions[d 0];  int v = j + directions[d 1];  // if this position lies inside the board  if (u >= 0 && u < n && v >= 0 && v < n) {  cur += dp[u v move - 1] / 8.0;  }  }  // store the result  dp[i j move] = cur;  }  }  }  // return the result  return dp[x y k];  }  static void Main(string[] args) {  int n = 8 x = 0 y = 0 k = 3;  Console.WriteLine(findProb(n x y k));  } }
JavaScript 
// JavaScript program to find the probability of the // knight to remain inside the chessboard // Function to find the probability function findProb(n x y k) {  // Initialize dp to store results of each step  let dp = Array.from({ length: n } () =>   Array.from({ length: n } () => Array(k + 1).fill(0))  );  // Initialize dp for step 0  for (let i = 0; i < n; ++i) {  for (let j = 0; j < n; ++j) {  dp[i][j][0] = 1.0;  }  }    let directions = [[1 2] [2 1] [2 -1] [1 -2]   [-1 -2] [-2 -1] [-2 1] [-1 2]];  for (let move = 1; move <= k; move++) {    // find probability for cell (i j)  for (let i = 0; i < n; i++) {  for (let j = 0; j < n; j++) {  let cur = 0.0;  // for every position reachable from (x y)  for (let d of directions) {  let u = i + d[0];  let v = j + d[1];  // if this position lies inside the board  if (u >= 0 && u < n && v >= 0 && v < n) {  cur += dp[u][v][move - 1] / 8.0;  }  }  // store the result  dp[i][j][move] = cur;  }  }  }  // return the result  return dp[x][y][k].toFixed(6); } let n = 8 x = 0 y = 0 k = 3; console.log(findProb(n x y k));

Saída 
0.125

Usando Dp otimizado para espaço - Tempo O(n*n*k) e Espaço O(n*n)

A abordagem acima requer apenas anterior estado de probabilidades para calcular o atual estado assim apenas o anterior loja precisa ser armazenada. A ideia é criar dois Matrizes 2D anteriorMove[][] e atualMove[][] onde

  • prevMove[i][j] armazena a probabilidade do cavalo estar em (i j) até o movimento anterior. É inicializado com valor 1 para estado inicial.
  • currMove[i][j] armazena a probabilidade do estado atual.

Opere de forma semelhante à abordagem acima e em fim de cada iteração atualizar anteriorMove[][] com valor armazenado em atualMove[][].

C++ 
// C++ program to find the probability of the // knight to remain inside the chessboard #include    using namespace std; // Function to find the probability double findProb(int n int x int y int k) {  // dp to store results of previous move  vector<vector<double>> prevMove(n vector<double>(n 1));  // dp to store results of current move  vector<vector<double>> currMove(n vector<double>(n 0));  vector<vector<int>> directions = {  {1 2} {2 1} {2 -1} {1 -2}   {-1 -2} {-2 -1} {-2 1} {-1 2}  };  for (int move = 1; move <= k; move++) {    // find probability for cell (i j)  for (int i = 0; i < n; ++i) {  for (int j = 0; j < n; ++j) {  double cur = 0.0;  // for every position reachable from (xy)  for (auto d:directions) {  int u = i + d[0];  int v = j + d[1];  // if this position lie inside the board  if (u >= 0 && u < n && v >= 0 && v < n)  cur += prevMove[u][v] / 8.0;  }  // store the result  currMove[i][j] = cur;  }  }  // update previous state  prevMove = currMove;  }  // return the result  return prevMove[x][y]; } int main(){  int n = 8 x = 0 y = 0 k = 3;  cout << findProb(n x y k) << endl;  return 0; }
Java 
// Java program to find the probability of the // knight to remain inside the chessboard class GfG {  // Function to find the probability  static double findProb(int n int x int y int k) {  // dp to store results of previous move  double[][] prevMove = new double[n][n];  for (int i = 0; i < n; i++) {  for (int j = 0; j < n; j++) {  prevMove[i][j] = 1.0;  }  }  // dp to store results of current move  double[][] currMove = new double[n][n];  int[][] directions = {  {1 2} {2 1} {2 -1} {1 -2}  {-1 -2} {-2 -1} {-2 1} {-1 2}  };  for (int move = 1; move <= k; move++) {  // find probability for cell (i j)  for (int i = 0; i < n; ++i) {  for (int j = 0; j < n; ++j) {  double cur = 0.0;  // for every position reachable from (xy)  for (int[] d : directions) {  int u = i + d[0];  int v = j + d[1];  // if this position lies inside the board  if (u >= 0 && u < n && v >= 0 && v < n)  cur += prevMove[u][v] / 8.0;  }  // store the result  currMove[i][j] = cur;  }  }  // update previous state  for (int i = 0; i < n; i++) {  System.arraycopy(currMove[i] 0 prevMove[i] 0 n);  }  }  // return the result  return prevMove[x][y];  }  public static void main(String[] args) {  int n = 8 x = 0 y = 0 k = 3;  System.out.println(findProb(n x y k));  } }
Python 
# Python program to find the probability of the # knight to remain inside the chessboard def findProb(n x y k): # dp to store results of previous move prevMove = [[1.0] * n for _ in range(n)] # dp to store results of current move currMove = [[0.0] * n for _ in range(n)] directions = [ [1 2] [2 1] [2 -1] [1 -2] [-1 -2] [-2 -1] [-2 1] [-1 2] ] for move in range(1 k + 1): # find probability for cell (i j) for i in range(n): for j in range(n): cur = 0.0 # for every position reachable from (xy) for d in directions: u v = i + d[0] j + d[1] # if this position lies inside the board if 0 <= u < n and 0 <= v < n: cur += prevMove[u][v] / 8.0 # store the result currMove[i][j] = cur # update previous state prevMove = [row[:] for row in currMove] # return the result return prevMove[x][y] if __name__ == '__main__': n x y k = 8 0 0 3 print(findProb(n x y k))
C# 
// C# program to find the probability of the // knight to remain inside the chessboard using System; class GfG {  // Function to find the probability  static double findProb(int n int x int y int k) {  // dp to store results of previous move  double[] prevMove = new double[n n];  for (int i = 0; i < n; i++)  for (int j = 0; j < n; j++)  prevMove[i j] = 1.0;  // dp to store results of current move  double[] currMove = new double[n n];  int[] directions = {  {1 2} {2 1} {2 -1} {1 -2}  {-1 -2} {-2 -1} {-2 1} {-1 2}  };  for (int move = 1; move <= k; move++) {  // find probability for cell (i j)  for (int i = 0; i < n; ++i) {  for (int j = 0; j < n; ++j) {  double cur = 0.0;  // for every position reachable from (xy)  for (int d = 0; d < directions.GetLength(0); d++) {  int u = i + directions[d 0];  int v = j + directions[d 1];  // if this position lies inside the board  if (u >= 0 && u < n && v >= 0 && v < n)  cur += prevMove[u v] / 8.0;  }  // store the result  currMove[i j] = cur;  }  }  // update previous state  Array.Copy(currMove prevMove n * n);  }  // return the result  return prevMove[x y];  }  static void Main() {  int n = 8 x = 0 y = 0 k = 3;  Console.WriteLine(findProb(n x y k));  } }
JavaScript 
// JavaScript program to find the probability of the // knight to remain inside the chessboard function findProb(n x y k) {  // dp to store results of previous move  let prevMove = Array.from({ length: n }   () => Array(n).fill(1.0));  // dp to store results of current move  let currMove = Array.from({ length: n }   () => Array(n).fill(0.0));  const directions = [  [1 2] [2 1] [2 -1] [1 -2]  [-1 -2] [-2 -1] [-2 1] [-1 2]  ];  for (let move = 1; move <= k; move++) {  // find probability for cell (i j)  for (let i = 0; i < n; i++) {  for (let j = 0; j < n; j++) {  let cur = 0.0;  // for every position reachable from (xy)  for (let d of directions) {  let u = i + d[0];  let v = j + d[1];  // if this position lies inside the board  if (u >= 0 && u < n && v >= 0 && v < n)  cur += prevMove[u][v] / 8.0;  }  // store the result  currMove[i][j] = cur;  }  }  // update previous state  prevMove = currMove.map(row => [...row]);  }  // return the result  return prevMove[x][y].toFixed(6); } let n = 8 x = 0 y = 0 k = 3; console.log(findProb(n x y k));

Saída 
0.125
Criar questionário