Heim > Backend-Entwicklung > C++ > Ein Matrixwahrscheinlichkeitsproblem?

Ein Matrixwahrscheinlichkeitsproblem?

WBOY
Freigeben: 2023-08-28 20:37:06
nach vorne
1016 Leute haben es durchsucht

Ein Matrixwahrscheinlichkeitsproblem?

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.

Algorithmus

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
Nach dem Login kopieren

Beispiel

#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);
}
Nach dem Login kopieren

Ausgabe

Matrix Probability is 0.664062
Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonEin Matrixwahrscheinlichkeitsproblem?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Verwandte Etiketten:
Quelle:tutorialspoint.com
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage