logo

TechCodeview

Wahrscheinlichkeit, dass Springer auf dem Schachbrett bleibt

Probieren Sie es bei GfG Practice aus ' title=

Gegeben a n*n Schachbrett und die Ritter Position (x y) Jedes Mal, wenn der Springer ziehen soll, wählt er einheitlich einen von acht möglichen Zügen zufällig (auch wenn die Figur vom Schachbrett verschwinden würde) und bewegt sich Dort. Der Ritter geht weiter bewegen, bis es genau gemacht hat k bewegt oder hat zog los das Schachbrett. Die Aufgabe besteht darin finden Die Wahrscheinlichkeit dass der Ritter Überreste auf der Planke nachdem es das getan hat gestoppt bewegen.

Notiz: Ein Schachspringer kann acht mögliche Züge machen. Jede Bewegung besteht aus zwei Zellen in einer Himmelsrichtung und dann einer Zelle in einer orthogonalen Richtung.

Beispiele:  



Eingang: n = 8 x = 0 y = 0 k = 1
Ausgabe: 0,25
Erläuterung: Der Springer beginnt bei (0 0) und liegt nach einem Schritt nur auf 2 von 8 Positionen innerhalb des Bretts, nämlich (1 2) und (2 1). Somit beträgt die Wahrscheinlichkeit 2/8 = 0,25.

Eingabe: n = 8 x = 0 y = 0 k = 3
Ausgabe: 0,125

Eingang: n = 4 x = 1 y = 2 k = 4
Ausgabe: 0,024414

Inhaltsverzeichnis

Verwendung von Top-Down-Dp (Memoisierung) – O(n*n*k) Zeit und O(n*n*k) Raum

Die Wahrscheinlichkeit, dass der Springer nach k Zügen auf dem Schachbrett bleibt, ist gleich der durchschnittlichen Wahrscheinlichkeit, dass der Springer nach k - 1 Zügen an den vorherigen acht Positionen verbleibt. Ebenso hängt die Wahrscheinlichkeit nach k-1 Zügen vom Durchschnitt der Wahrscheinlichkeit nach k-2 Zügen ab. Die Idee ist zu verwenden Auswendiglernen um die Wahrscheinlichkeiten früherer Züge zu speichern und ihren Durchschnitt zu ermitteln, um das Endergebnis zu berechnen.
Erstellen Sie dazu eine 3D-Array-Memo[][][] Wo Memo[i][j][k] speichert die Wahrscheinlichkeit, dass sich der Springer nach k Zügen in der Zelle (i j) befindet. Wenn k Null ist, ist der Anfangszustand erreicht Rückkehr 1 Andernfalls untersuchen Sie die vorherigen acht Positionen und ermitteln Sie den Durchschnitt ihrer Wahrscheinlichkeiten.

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));

Ausgabe 
0.125

Verwenden von Bottom-Up Dp (Tabulation) – O(n*n*k) Zeit und O(n*n*k) Raum

Der obige Ansatz kann mit optimiert werden von unten nach oben Tabellierung reduziert den zusätzlichen Platzbedarf für rekursive Stapel. Die Idee ist, eine 3 beizubehalten D-Array dp[][][] Wo dp[i][j][k] speichert die Wahrscheinlichkeit, dass der Ritter in der Zelle ist (i j) nach k bewegt sich. Initialisieren Sie die 0 Zustand von dp mit Wert 1 . Für jeden weiteren Zug die Wahrscheinlichkeit des Ritters wird sein gleich Zu Durchschnitt der Wahrscheinlichkeit von vorherige 8 Positionen danach k-1 bewegt sich.

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));

Ausgabe 
0.125

Verwendung von raumoptimiertem Dp – O(n*n*k) Zeit und O(n*n) Raum

Der obige Ansatz erfordert nur vorherige Zustand der Wahrscheinlichkeiten zur Berechnung der aktuell so angeben nur Die vorherige Store müssen gespeichert werden. Die Idee ist, zwei zu schaffen 2D-Arrays prevMove[][] Und currMove[][] Wo

  • prevMove[i][j] speichert die Wahrscheinlichkeit, dass der Springer bis zum vorherigen Zug bei (i j) war. Es wird mit dem Wert 1 für den Anfangszustand initialisiert.
  • currMove[i][j] speichert die Wahrscheinlichkeit des aktuellen Zustands.

Gehen Sie ähnlich wie oben beschrieben vor und bei Ende jeder Iteration update prevMove[][] mit gespeichertem Wert currMove[][].

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));

Ausgabe 
0.125
Quiz erstellen