행렬 확률 문제인가요?-C++-php.cn

행렬 확률 문제인가요?

WBOY

풀어 주다： 2023-08-28 20:37:06

앞으로

1016명이 탐색했습니다.

행렬 확률 문제인가요?

여기서 행렬 확률 문제를 살펴보겠습니다. 직사각형 행렬이 있습니다. 현재 셀에서 동일한 확률로 네 방향으로 이동할 수 있습니다. 네 방향은 왼쪽, 오른쪽, 위, 아래입니다. 우리는 M[i,j] 위치에서 시작하여 N번 이동한 후의 확률을 계산하려고 합니다.

여기서 DFS 관련 작업을 해보겠습니다. 우리는 현재 방에서 시작하여 가능한 4개의 방을 재귀적으로 탐색할 것입니다. 그런 다음 한 단계 덜 걸릴 확률을 계산합니다. 네 방향의 확률은 동일하므로 각 방향은 전체 확률의 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<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);
}

로그인 후 복사