मैट्रिक्स संभावना प्रश्न

यहां हम एक मैट्रिक्स संभावना समस्या देखेंगे। हमारे पास एक आयताकार मैट्रिक्स है। हम वर्तमान सेल से चार दिशाओं में समान संभावना के साथ जा सकते हैं। ये चार दिशाएं बाएं, दाएं, ऊपर और नीचे हैं। हमें M[i, j] स्थिति से N चालों के बाद संभावना की गणना करनी है।

यहां हम DFS से संबंधित कुछ करेंगे। हम वर्तमान कक्ष से चार संभावित कक्षों में पुनरावर्ती रूप से पार करेंगे। फिर हम एक कम चाल के साथ संभावना की गणना करेंगे। चूंकि चारों दिशाओं में समान संभावना है, इसलिए प्रत्येक दिशा कुल संभावना का 0.25 योगदान देगी। यदि हम मैट्रिक्स सीमा पार करते हैं, तो हम 0 लौटाएंगे, और जब N चाल पूरी हो जाएगी तो 1 लौटाया जाएगा। आइए एल्गोरिदम देखें ताकि विचार मिल सके।

एल्गोरिदम

matProb(m, n, x, y, N)

Begin   if x,y is not in matrix boundary m, n, then return 0   if N is 0 , then return 1   prob := 0   prob := prob + matProb(m, n, x-1, y, N-1) * 0.25   prob := prob + matProb(m, n, x+1, y, N-1) * 0.25   prob := prob + matProb(m, n, x, y+1, N-1) * 0.25   prob := prob + matProb(m, n, x, y-1, N-1) * 0.25   return prob End

उदाहरण

#include using namespace std; bool isSafe(int x, int y, int m, int n) { //function to check whether (x,y)     is in matrix or not     if(x >= 0 && x < m && y >= 0 && y < n){         return true;     }     return false; } double matProb(int m, int n, int x, int y, int N) {     if (!isSafe(x, y, m, n)) //if coundary is crossed         return 0.0;     if (N == 0) //when N is 0, or N is completed, return 1         return 1.0;     double probability = 0.0;     probability += matProb(m, n, x - 1, y, N - 1) * 0.25; //move left     probability += matProb(m, n, x, y + 1, N - 1) * 0.25; //move up     probability += matProb(m, n, x + 1, y, N - 1) * 0.25; //move right     probability += matProb(m, n, x, y - 1, N - 1) * 0.25; //move down     return probability; } int main() {     int m = 7, n = 8;     int x = 1, y = 1;     int N = 4;     cout << "Matrix Probability is " << matProb(m, n, x, y, N); }

आउटपुट

Matrix Probability is 0.664062