Matriisin todennäköisyyskysymys
Kun otetaan huomioon suorakaiteen muotoinen matriisi, voimme siirtyä nykyisestä solusta 4 suuntaan yhtä todennäköisesti. 4 suuntaa on oikea vasen yläosa tai alaosa. Laske todennäköisyys, että N: n siirtymisen jälkeen tietystä sijainnista (I J) matriisissa, emme ylitä matriisin rajoja missään vaiheessa.
Suosittelemme, että minimoi selain ja kokeilet tätä ensin.
Ajatuksena on suorittaa jotain samanlaista kuin DFS. Kuljemme rekursiivisesti jokaisessa 4 sallittua suuntaa ja jokaiselle havaitulle solulle lasketaan vaadittava todennäköisyys yhdellä vähemmän liikkeellä. Koska kumpaankin suuntaan on yhtä todennäköisyys, jokainen suunta edistää 1/4 kyseisen solun kokonaistodennäköisyydestä, ts. 0,25. Palaamme 0, jos astumme matriisin ulkopuolelle ja palautamme 1, jos N -vaiheet suoritetaan ilman matriisin rajojen ylittämistä.
Alla on yllä olevan idean toteutus:
C++ /// C++ program to find the probability // that we do not cross boundary of a // matrix after N moves. #include using namespace std ; // check if (x y) is valid matrix coordinate bool isSafe ( int x int y int m int n ) { return ( x >= 0 && x < m && y >= 0 && y < n ); } // Function to calculate probability // that after N moves from a given // position (x y) in m x n matrix // boundaries of the matrix will not be crossed. double findProbability ( int m int n int x int y int N ) { // boundary crossed if ( ! isSafe ( x y m n )) return 0.0 ; // N steps taken if ( N == 0 ) return 1.0 ; // Initialize result double prob = 0.0 ; // move up prob += findProbability ( m n x - 1 y N - 1 ) * 0.25 ; // move right prob += findProbability ( m n x y + 1 N - 1 ) * 0.25 ; // move down prob += findProbability ( m n x + 1 y N - 1 ) * 0.25 ; // move left prob += findProbability ( m n x y - 1 N - 1 ) * 0.25 ; return prob ; } // Driver code int main () { // matrix size int m = 5 n = 5 ; // coordinates of starting point int i = 1 j = 1 ; // Number of steps int N = 2 ; cout < < 'Probability is ' < < findProbability ( m n i j N ); return 0 ; }
C /// C program to find the probability // that we do not cross boundary of a // matrix after N moves. #include #include // check if (x y) is valid matrix coordinate bool isSafe ( int x int y int m int n ) { return ( x >= 0 && x < m && y >= 0 && y < n ); } // Function to calculate probability // that after N moves from a given // position (x y) in m x n matrix // boundaries of the matrix will not be crossed. double findProbability ( int m int n int x int y int N ) { // boundary crossed if ( ! isSafe ( x y m n )) return 0.0 ; // N steps taken if ( N == 0 ) return 1.0 ; // Initialize result double prob = 0.0 ; // move up prob += findProbability ( m n x - 1 y N - 1 ) * 0.25 ; // move right prob += findProbability ( m n x y + 1 N - 1 ) * 0.25 ; // move down prob += findProbability ( m n x + 1 y N - 1 ) * 0.25 ; // move left prob += findProbability ( m n x y - 1 N - 1 ) * 0.25 ; return prob ; } // Driver code int main () { // matrix size int m = 5 n = 5 ; // coordinates of starting point int i = 1 j = 1 ; // Number of steps int N = 2 ; printf ( 'Probability is %f' findProbability ( m n i j N )); return 0 ; } // This code is contributed by kothavvsaakash.
Java // Java program to find the probability // that we do not cross boundary // of a matrix after N moves. import java.io.* ; class GFG { // check if (x y) is valid // matrix coordinate static boolean isSafe ( int x int y int m int n ) { return ( x >= 0 && x < m && y >= 0 && y < n ); } // Function to calculate probability // that after N moves from a given // position (x y) in m x n matrix // boundaries of the matrix will // not be crossed. static double findProbability ( int m int n int x int y int N ) { // boundary crossed if ( ! isSafe ( x y m n )) return 0.0 ; // N steps taken if ( N == 0 ) return 1.0 ; // Initialize result double prob = 0.0 ; // move up prob += findProbability ( m n x - 1 y N - 1 ) * 0.25 ; // move right prob += findProbability ( m n x y + 1 N - 1 ) * 0.25 ; // move down prob += findProbability ( m n x + 1 y N - 1 ) * 0.25 ; // move left prob += findProbability ( m n x y - 1 N - 1 ) * 0.25 ; return prob ; } // Driver code public static void main ( String [] args ) { // matrix size int m = 5 n = 5 ; // coordinates of starting point int i = 1 j = 1 ; // Number of steps int N = 2 ; System . out . println ( 'Probability is ' + findProbability ( m n i j N )); } } // This code is contributed by KRV.
Python3 # Python3 program to find the probability # that we do not cross boundary of a # matrix after N moves. # check if (x y) is valid matrix coordinate def isSafe ( x y m n ): return ( x >= 0 and x < m and y >= 0 and y < n ) # Function to calculate probability # that after N moves from a given # position (x y) in m x n matrix # boundaries of the matrix will # not be crossed. def findProbability ( m n x y N ): # boundary crossed if ( not isSafe ( x y m n )): return 0.0 # N steps taken if ( N == 0 ): return 1.0 # Initialize result prob = 0.0 # move up prob += findProbability ( m n x - 1 y N - 1 ) * 0.25 # move right prob += findProbability ( m n x y + 1 N - 1 ) * 0.25 # move down prob += findProbability ( m n x + 1 y N - 1 ) * 0.25 # move left prob += findProbability ( m n x y - 1 N - 1 ) * 0.25 return prob # Driver code if __name__ == '__main__' : # matrix size m = 5 n = 5 # coordinates of starting po i = 1 j = 1 # Number of steps N = 2 print ( 'Probability is' findProbability ( m n i j N )) # This code is contributed by PranchalK
C# // C# program to find the probability // that we do not cross boundary // of a matrix after N moves. using System ; class GFG { // check if (x y) is valid // matrix coordinate static bool isSafe ( int x int y int m int n ) { return ( x >= 0 && x < m && y >= 0 && y < n ); } // Function to calculate probability // that after N moves from a given // position (x y) in m x n matrix // boundaries of the matrix will // not be crossed. static double findProbability ( int m int n int x int y int N ) { // boundary crossed if ( ! isSafe ( x y m n )) return 0.0 ; // N steps taken if ( N == 0 ) return 1.0 ; // Initialize result double prob = 0.0 ; // move up prob += findProbability ( m n x - 1 y N - 1 ) * 0.25 ; // move right prob += findProbability ( m n x y + 1 N - 1 ) * 0.25 ; // move down prob += findProbability ( m n x + 1 y N - 1 ) * 0.25 ; // move left prob += findProbability ( m n x y - 1 N - 1 ) * 0.25 ; return prob ; } // Driver code public static void Main () { // matrix size int m = 5 n = 5 ; // coordinates of starting point int i = 1 j = 1 ; // Number of steps int N = 2 ; Console . Write ( 'Probability is ' + findProbability ( m n i j N )); } } // This code is contributed by nitin mittal.
PHP // PHP program to find the probability // that we do not cross boundary of a // matrix after N moves. // check if (x y) is valid // matrix coordinate function isSafe ( $x $y $m $n ) { return ( $x >= 0 && $x < $m && $y >= 0 && $y < $n ); } // Function to calculate probability // that after N moves from a given // position (x y) in m x n matrix // boundaries of the matrix will // not be crossed. function findProbability ( $m $n $x $y $N ) { // boundary crossed if ( ! isSafe ( $x $y $m $n )) return 0.0 ; // N steps taken if ( $N == 0 ) return 1.0 ; // Initialize result $prob = 0.0 ; // move up $prob += findProbability ( $m $n $x - 1 $y $N - 1 ) * 0.25 ; // move right $prob += findProbability ( $m $n $x $y + 1 $N - 1 ) * 0.25 ; // move down $prob += findProbability ( $m $n $x + 1 $y $N - 1 ) * 0.25 ; // move left $prob += findProbability ( $m $n $x $y - 1 $N - 1 ) * 0.25 ; return $prob ; } // Driver code // matrix size $m = 5 ; $n = 5 ; // coordinates of starting point $i = 1 ; $j = 1 ; // Number of steps $N = 2 ; echo 'Probability is ' findProbability ( $m $n $i $j $N ); // This code is contributed by nitin mittal. ?>
JavaScript < script > // JavaScript program to find the probability // that we do not cross boundary of a // matrix after N moves. // check if (x y) is valid matrix coordinate function isSafe ( x y m n ){ return ( x >= 0 && x < m && y >= 0 && y < n ); } // Function to calculate probability // that after N moves from a given // position (x y) in m x n matrix // boundaries of the matrix will not be crossed. function findProbability ( m n x y N ){ // boundary crossed if ( ! isSafe ( x y m n )) return 0.0 ; // N steps taken if ( N == 0 ) return 1.0 ; // Initialize result let prob = 0.0 ; // move up prob += findProbability ( m n x - 1 y N - 1 ) * 0.25 ; // move right prob += findProbability ( m n x y + 1 N - 1 ) * 0.25 ; // move down prob += findProbability ( m n x + 1 y N - 1 ) * 0.25 ; // move left prob += findProbability ( m n x y - 1 N - 1 ) * 0.25 ; return prob ; } // Driver code // matrix size let m = 5 n = 5 ; // coordinates of starting point let i = 1 j = 1 ; // Number of steps let N = 2 ; document . write ( 'Probability is ' + findProbability ( m n i j N )); < /script>
Tulos
Probability is 0.875
