Programmation en C++, trouver le nombre de chemins d'un point à un autre dans une grille

Dans cet article, on nous pose un problème dans lequel nous devons trouver le nombre total de chemins du point A au point B, où A et B sont des points fixes, c'est-à-dire A est le point du coin supérieur gauche de la grille et B est le point du coin inférieur droit de la grille, par exemple −

Input : N = 5
Output : 252

Input : N = 4
Output : 70

Input : N = 3
Output : 20

Dans le problème donné, nous pouvons formaliser la réponse et dériver le résultat à travers des observations simples.

Méthode pour trouver la solution

Dans cette méthode, nous dérivons une formule par observation selon laquelle lorsque nous traversons la grille de A à B, nous devons aller à droite n fois et descendre n fois, ce qui signifie que nous devons tout trouver combinaisons de chemins possibles, nous obtenons donc la formule de combinaison de (n+n) et n.

Exemple

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

Sortie

252

Explication du code ci-dessus

Dans ce code, nous calculons la formule combinée de 2*n à n, car nous savons que du point A au point B, nous avons besoin exactement de deux directions 2 *n opérations sur , c'est-à-dire qu'il y a n opérations dans un sens et n opérations dans l'autre sens, on trouve donc toutes les combinaisons possibles de ces opérations, c'est-à-dire (2*n)!/ (n! + n! ) . La complexité temporelle globale du programme donné est O(1), ce qui signifie que notre complexité ne dépend pas du n donné.

Conclusion

Dans cet article, nous avons abordé le problème de trouver le nombre d'itinéraires d'un point à un autre point dans une grille. Nous avons également appris un programme C++ pour ce problème et notre approche complète pour le résoudre. Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. Nous espérons que cet article vous a été utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!