In diesem Artikel erhalten wir ein Problem, bei dem wir die Gesamtzahl der Pfade von Punkt A zu Punkt B ermitteln müssen, wobei A und B Fixpunkte sind, d. h. A ist der obere linke Eckpunkt im Raster und B ist der untere rechte Eckpunkt im Gitter, z. B. −
Input : N = 5 Output : 252 Input : N = 4 Output : 70 Input : N = 3 Output : 20
In dem gegebenen Problem können wir die Antwort formalisieren und das Ergebnis durch einfache Beobachtungen ableiten.
Bei dieser Methode leiten wir eine Formel durch Beobachtung ab, dass wir beim Überqueren des Gitters von A nach B n-mal nach rechts und n-mal nach unten gehen müssen, was bedeutet, dass wir alle finden müssen mögliche Pfadkombinationen, also erhalten wir die Kombinationsformel von (n+n) und n.
#include<bits/stdc++.h>
using namespace std;
int fact(int n){ // factorial function
if(n <= 1)
return 1;
return n * fact(n-1);
}
int main() {
int n = 5; // given n
int answer = 0; // our answer
answer = fact(n+n); // finding factorial of 2*n
answer = answer / (fact(n) * fact(n)); // (2*n)! / (n! + n!)
cout << answer << "\n";
}252
In diesem Code berechnen wir die kombinierte Formel von 2*n zu n, weil wir wissen, dass wir von Punkt A nach Punkt B genau zwei Richtungen 2 benötigen *n Operationen auf , das heißt, es gibt n Operationen in eine Richtung und n Operationen in die andere Richtung, also finden wir alle möglichen Kombinationen dieser Operationen, also (2*n)!/ (n! + n!) . Die Gesamtzeitkomplexität des gegebenen Programms beträgt O(1), was bedeutet, dass unsere Komplexität nicht vom gegebenen n abhängt.
In diesem Artikel haben wir ein Problem besprochen, die Anzahl der Routen von einem Punkt zu einem anderen Punkt in einem Raster zu ermitteln. Wir haben auch ein C++-Programm für dieses Problem und unseren vollständigen Lösungsansatz kennengelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen schreiben. Wir hoffen, dass dieser Artikel für Sie hilfreich war.
Das obige ist der detaillierte Inhalt vonErmitteln Sie beim Programmieren in C++ die Anzahl der Pfade von einem Punkt zu einem anderen in einem Raster. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
