Ở đây chúng ta sẽ thấy một bài toán xác suất ma trận. Chúng tôi có một ma trận hình chữ nhật. Chúng ta có thể di chuyển bốn hướng từ ô hiện tại với xác suất như nhau. Bốn hướng này là trái, phải, lên và xuống. Chúng ta phải tính xác suất sau khi N di chuyển từ vị trí M [i, j].
Ở đây chúng tôi sẽ làm một cái gì đó liên quan đến DFS. Chúng ta sẽ duyệt đệ quy qua từng phòng trong số bốn phòng có thể có từ phòng hiện tại. Sau đó, chúng tôi sẽ tính toán xác suất với một nước đi ít hơn. Vì mỗi hướng trong số bốn hướng có xác suất bằng nhau, thì mỗi hướng sẽ đóng góp 0,25 tổng xác suất. Nếu chúng ta vượt qua ranh giới của ma trận, chúng ta sẽ trả về 0, và 1 sẽ được trả về khi hoàn thành việc di chuyển N. Hãy để chúng tôi xem thuật toán để có được ý tưởng.
Thuật toán
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
Ví dụ
#include<iostream>
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);
} Đầu ra
Matrix Probability is 0.664062