Un problème de probabilité matricielle ?-C++-php.cn

Un problème de probabilité matricielle ?

WBOY

Libérer： 2023-08-28 20:37:06

avant

1016 Les gens l'ont consulté

Un problème de probabilité matricielle ?

Ici, nous verrons un problème de probabilité matricielle. Nous avons une matrice rectangulaire. Nous pouvons nous déplacer dans quatre directions à partir de la cellule actuelle avec une probabilité égale. Les quatre directions sont gauche, droite, haut et bas. Nous voulons calculer la probabilité après N mouvements à partir de la position M[i,j].

Ici, nous allons faire certaines choses liées à DFS. Nous allons parcourir récursivement les quatre salles possibles en partant de la salle actuelle. Ensuite, nous calculons la probabilité de faire un pas de moins. Puisque les quatre directions ont des probabilités égales, chaque direction contribuera à hauteur de 0,25 à la probabilité totale. Nous renverrons 0 si une frontière matricielle est franchie et 1 lorsque N mouvements sont effectués. Regardons l'algorithme pour avoir cette idée.

Algorithme

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

Copier après la connexion

Exemple

#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);
}

Copier après la connexion