Computer >> Máy Tính >  >> Lập trình >> lập trình C

Một câu hỏi xác suất ma trận?

Ở đâ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