Hier sehen wir ein Matrixwahrscheinlichkeitsproblem. Wir haben eine rechteckige Matrix. Wir können uns von der aktuellen Zelle aus mit gleicher Wahrscheinlichkeit in vier Richtungen bewegen. Die vier Richtungen sind links, rechts, oben und unten. Wir wollen die Wahrscheinlichkeit nach N Bewegungen ausgehend von der Position M[i,j] berechnen.
Hier werden wir einige Dinge im Zusammenhang mit DFS tun. Wir werden die vier möglichen Räume ausgehend vom aktuellen Raum rekursiv durchqueren. Dann berechnen wir die Wahrscheinlichkeit, einen Schritt weniger zu machen. Da die vier Richtungen die gleiche Wahrscheinlichkeit haben, trägt jede Richtung 0,25 zur Gesamtwahrscheinlichkeit bei. Wir geben 0 zurück, wenn eine Matrixgrenze überschritten wird, und 1, wenn N Züge abgeschlossen sind. Schauen wir uns den Algorithmus an, um auf diese Idee zu kommen.
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);
}Matrix Probability is 0.664062
Das obige ist der detaillierte Inhalt vonEin Matrixwahrscheinlichkeitsproblem?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
