Riterio tikimybė likti šachmatų lentoje
Išbandykite „GfG Practice“. 
Išvestis
Išvestis
Išvestis
Atsižvelgiant į a n*n šachmatų lenta ir riteris padėtis (x y) kiekvieną kartą, kai riteris turi judėti, jis pasirenka vieną iš aštuonių galimų judesių tolygiai atsitiktinis (net jei figūrėlė nukristų nuo šachmatų lentos) ir juda ten. Riteris tęsiasi juda tol, kol pagamins tiksliai k juda arba turi pasitraukė šachmatų lenta. Užduotis yra rasti į tikimybė kad riteris lieka ant lenta po to, kai turi sustojo juda.
Pastaba: Šachmatų riteris gali atlikti aštuonis galimus ėjimus. Kiekvienas judesys yra dvi ląstelės kardinaline kryptimi, tada viena langelis statmena kryptimi.
Pavyzdžiai:
Įvestis: n = 8 x = 0 y = 0 k = 1
Išvestis: 0.25
Paaiškinimas: Riteris pradeda nuo (0 0) ir žengęs vieną žingsnį atsiguls lentoje tik 2 iš 8 pozicijų, kurios yra (1 2) ir (2 1). Taigi tikimybė bus 2/8 = 0,25.Įvestis: n = 8 x = 0 y = 0 k = 3
Išvestis: 0,125Įvestis: n = 4 x = 1 y = 2 k = 4
Išvestis: 0,024414
Turinio lentelė
- Naudojant Dp iš viršaus į apačią (atmintinė) – O(n*n*k) laikas ir O(n*n*k) erdvė
- Naudojant Dp iš apačios į viršų (tabulinė lentelė) – O(n*n*k) laikas ir O(n*n*k) erdvė
- Erdvės optimizavimas Dp – O(n*n*k) laikas ir O(n*n) erdvė
Naudojant Dp iš viršaus į apačią (atmintinė) – O(n*n*k) laikas ir O(n*n*k) erdvė
C++Riterio tikimybė likti šachmatų lentoje po k ėjimų yra lygi riterio tikimybės vidurkiui ankstesnėse aštuoniose pozicijose po k - 1 ėjimo. Panašiai tikimybė po k-1 judesių priklauso nuo tikimybės vidurkio po k-2 judesių. Idėja yra naudoti atmintinė išsaugoti ankstesnių ėjimų tikimybes ir rasti jų vidurkį galutiniam rezultatui apskaičiuoti.
Norėdami tai padaryti, sukurkite a 3D masyvo atmintinė[][][] kur atmintinė[i][j][k] išsaugo tikimybę, kad riteris bus langelyje (i j) po k judesių. Jei k yra nulis, t.y. pasiekiama pradinė būsena grąžinti 1 kitu atveju ištirkite ankstesnes aštuonias pozicijas ir suraskite jų tikimybių vidurkį.
// 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 ));
Išvestis
0.125
Naudojant Dp iš apačios į viršų (tabulinė lentelė) – O(n*n*k) laikas ir O(n*n*k) erdvė
C++Aukščiau pateiktą metodą galima optimizuoti naudojant iš apačios į viršų lentelių sudarymas, sumažinantis papildomą erdvę, reikalingą rekursiniam dėkui. Idėja yra išlaikyti 3 D masyvas dp[][][] kur dp[i][j][k] išsaugo tikimybę, kad riteris bus langelyje (i j) po to k juda. Inicijuoti 0 būsena dp su verte 1 . Kiekvienam paskesniam judesiui tikimybė bus riteris lygus į vidutinis tikimybės ankstesnis 8 pozicijos po k-1 juda.
// 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 ));
Išvestis
0.125
Erdvės optimizavimas Dp – O(n*n*k) laikas ir O(n*n) erdvė
C++Aukščiau pateiktas požiūris reikalauja tik ankstesnis tikimybių būsena apskaičiuoti srovė konstatuoti taip tik į ankstesnis parduotuvę reikia saugoti. Idėja yra sukurti du 2d masyvai prevMove[][] ir currMove[][] kur
- prevMove[i][j] išsaugo tikimybę, kad riteris bus ties (i j) iki ankstesnio judėjimo. Jis inicijuojamas pradinės būsenos reikšme 1.
- currMove[i][j] išsaugo esamos būsenos tikimybę.
Veikite panašiai kaip aukščiau pateiktas metodas ir pabaiga kiekvienos iteracijos atnaujinti prevMove[][] su saugoma verte 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 ));
Išvestis
0.125Sukurti viktoriną
