Knight'ın satranç tahtasında kalma olasılığı
GfG Practice'de deneyin 
Çıkış
Çıkış
Çıkış
Verilen bir n*n satranç tahtası ve şövalye konum (xy) At her hareket edeceğinde sekiz olası hamleden birini eşit olarak seçer. rastgele (taş satranç tahtasından düşse bile) ve hamle Orası. Şövalye devam ediyor tam olarak yapılana kadar hareket ediyor k hareket ediyor veya var taşındı satranç tahtası. Görev, bulmak the olasılık o şövalye kalıntılar üzerinde pano sahip olduktan sonra durduruldu hareket ediyor.
Not: Bir satranç atı sekiz olası hamle yapabilir. Her hareket, ana yönde iki hücre, ardından dik yönde bir hücredir.
Örnekler:
Giriş: n = 8 x = 0 y = 0 k = 1
Çıkış: 0,25
Açıklama: At (0 0)'dan başlar ve bir adım attıktan sonra tahtanın içinde (1 2) ve (2 1) olmak üzere 8 konumdan yalnızca 2'sinde yer alır. Böylece olasılık 2/8 = 0,25 olacaktır.Giriş : n = 8 x = 0 y = 0 k = 3
Çıkış: 0,125Giriş: n = 4 x = 1 y = 2 k = 4
Çıkış: 0.024414
İçerik Tablosu
- Yukarıdan Aşağıya Dp'yi Kullanma (Notlandırma) - O(n*n*k) Zaman ve O(n*n*k) Boşluk
- Aşağıdan Yukarıya Dp (Tablolama) Kullanımı - O(n*n*k) Zaman ve O(n*n*k) Uzay
- Alanı Optimize Edilmiş Dp Kullanma - O(n*n*k) Zaman ve O(n*n) Uzay
Yukarıdan Aşağıya Dp'yi Kullanma (Notlandırma) - O(n*n*k) Zaman ve O(n*n*k) Boşluk
C++Atın k hamleden sonra satranç tahtasında kalma olasılığı, atın k - 1 hamleden sonra önceki sekiz pozisyonda kalma olasılığının ortalamasına eşittir. Benzer şekilde k-1 hamle sonrası olasılık, k-2 hamle sonrası olasılığın ortalamasına bağlıdır. Fikir kullanmaktır not alma önceki hareketlerin olasılıklarını depolamak ve nihai sonucu hesaplamak için ortalamalarını bulmak.
Bunu yapmak için bir 3 boyutlu dizi notu[][][] Neresi not[i][j][k] k hamleden sonra atın (i j) hücresinde olma olasılığını saklar. Eğer k sıfır ise, yani başlangıç durumuna ulaşılır dönüş 1 Aksi halde önceki sekiz konumu araştırın ve olasılıklarının ortalamasını bulun.
// 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 ));
Çıkış
0.125
Aşağıdan Yukarıya Dp (Tablolama) Kullanımı - O(n*n*k) Zaman ve O(n*n*k) Uzay
C++Yukarıdaki yaklaşım kullanılarak optimize edilebilir altüst özyinelemeli yığın için gereken ekstra alanı azaltan tablolama. Fikir 3'ü korumaktır D dizisi dp[][][] Neresi dp[i][j][k] şövalyenin hücrede olma olasılığını saklar (ben j) sonrasında k hareket eder. Başlat 0. durumu dp değeri olan 1 . Sonraki her hareket için olasılık şövalye olacak eşit ile ortalama olasılığı öncesi 8 pozisyon sonra k-1 hareket eder.
// 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 ));
Çıkış
0.125
Alanı Optimize Edilmiş Dp Kullanma - O(n*n*k) Zaman ve O(n*n) Uzay
C++Yukarıdaki yaklaşım gereklilikler sadece öncesi hesaplamak için olasılık durumu akım bu şekilde devlet sadece the öncesi mağazanın saklanması gerekiyor. Fikir iki tane yaratmaktır 2 boyutlu diziler öncekiMove[][] Ve CurrMove[][] Neresi
- prevMove[i][j], atın önceki hamleye kadar (i j)'de olma olasılığını saklar. Başlangıç durumu için 1 değeriyle başlatılır.
- currMove[i][j] mevcut durumun olasılığını saklar.
Yukarıdaki yaklaşıma benzer şekilde çalışın ve son her yinelemenin öncekiMove'u güncelle[][] değeri saklanan 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 ));
Çıkış
0.125Test Oluştur
