Sannolikhet för riddare att stanna kvar på schackbrädet
Prova det på GfG Practice 
Produktion
Produktion
Produktion
Givet a n*n schackbräde och den riddare placera (x y) varje gång riddaren ska flytta väljer den ett av åtta möjliga drag jämnt kl slumpmässig (även om pjäsen skulle försvinna från schackbrädet) och rör sig det. Riddaren fortsätter flytta tills den har gjort exakt k rör sig eller har flyttade iväg schackbrädet. Uppgiften är att hitta de sannolikhet att riddaren rester på styrelse efter att det har gjort det stannade rörlig.
Notera: En schackriddare kan göra åtta möjliga drag. Varje drag är två celler i en kardinal riktning sedan en cell i en ortogonal riktning.
Exempel:
Input: n = 8 x = 0 y = 0 k = 1
Produktion: 0,25
Förklaring: Riddaren börjar vid (0 0) och efter att ha tagit ett steg kommer den att ligga inne på brädan i endast 2 av 8 positioner som är (1 2) och (2 1). Sannolikheten blir alltså 2/8 = 0,25.Ingång: n = 8 x = 0 y = 0 k = 3
Produktion: 0,125Input: n = 4 x = 1 y = 2 k = 4
Produktion: 0,024414
Innehållsförteckning
- Använda Top-Down Dp (Memoization) - O(n*n*k) Tid och O(n*n*k) Space
- Använda Bottom-Up Dp (Tabulering) - O(n*n*k) Tid och O(n*n*k) Mellanrum
- Använda Space Optimized Dp - O(n*n*k) Tid och O(n*n) Space
Använda Top-Down Dp (Memoization) - O(n*n*k) Tid och O(n*n*k) Space
C++Sannolikheten för riddare att stanna kvar på schackbrädet efter k drag är lika med genomsnittet av sannolikheten för riddare vid tidigare åtta positioner efter k - 1 drag. Likaså beror sannolikheten efter k-1 drag på genomsnittet av sannolikheten efter k-2 drag. Tanken är att använda memoisering för att lagra sannolikheterna för tidigare drag och hitta deras medelvärde för att beräkna det slutliga resultatet.
För att göra det skapa en 3d array memo[][][] där memo[i][j][k] lagrar sannolikheten för riddare att vara i cell (i j) efter k drag. Om k är noll, dvs. initialtillståndet nås retur 1 annars utforska tidigare åtta positioner och hitta medelvärdet av deras sannolikheter.
// 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 ));
Produktion
0.125
Använda Bottom-Up Dp (Tabulering) - O(n*n*k) Tid och O(n*n*k) Mellanrum
C++Ovanstående tillvägagångssätt kan optimeras med hjälp av nedifrån och upp tabulering som minskar det extra utrymme som krävs för rekursiv stack. Tanken är att behålla en 3 D array dp[][][] där dp[i][j][k] lagrar sannolikheten för att riddare är i cellen (i j) efter k rör sig. Initiera 0:e tillstånd av dp med värde 1 . För varje efterföljande drag sannolikhet av riddare kommer att bli lika till genomsnitt av sannolikheten för tidigare 8 positioner efter k-1 rör sig.
// 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 ));
Produktion
0.125
Använda Space Optimized Dp - O(n*n*k) Tid och O(n*n) Space
C++Ovanstående tillvägagångssätt kräver endast tidigare sannolikhetstillstånd för att beräkna nuvarande ange sålunda endast de tidigare butik måste lagras. Tanken är att skapa två 2d-matriser prevMove[][] och currMove[][] där
- prevMove[i][j] lagrar sannolikheten för riddare att vara på (i j) upp till föregående drag. Den initieras med värdet 1 för initialtillstånd.
- currMove[i][j] lagrar sannolikheten för aktuellt tillstånd.
Fungerar liknande tillvägagångssättet ovan och vid avsluta av varje iteration uppdatera prevMove[][] med värde lagrat i currMove[][].
// 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 ));
Produktion
0.125Skapa frågesport
