Et spørsmål om matrise sannsynlighet
Gitt en rektangulær matrise kan vi bevege oss fra gjeldende celle i 4 retninger med like sannsynlighet. De 4 retningene er til venstre på topp eller bunn. Beregn sannsynligheten for at vi ikke vil krysse grensene for matrisen på noe punkt etter N, etter N beveger seg fra en gitt posisjon (i J) i matrisen.
Vi anbefaler deg på det sterkeste å minimere nettleseren din og prøve dette selv først.
Tanken er å utføre noe som ligner på DFS. Vi krysser rekursivt i hver av de 4 tillatte retningen, og for hver celle som oppstår beregner vi den nødvendige sannsynligheten med ett mindre trekk. Ettersom hver retning har like sannsynlighet vil hver retning bidra til 1/4 av total sannsynlighet for den cellen, dvs. 0,25. Vi returnerer 0 hvis vi går utenfor matrisen og returnerer 1 hvis n trinn er fullført uten å krysse matriksgrenser.
Nedenfor er implementeringen av ideen ovenfor:
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>
Produksjon
Probability is 0.875
