Écrit en C++, trouvez le nombre de triangles formés par un ensemble de points sur trois droites

Maintenant nous avons plusieurs points présents dans les 3 lignes par exemple, nous devons découvrir combien de triangles ces points peuvent former

Input: m = 3, n = 4, k = 5
Output: 205

Input: m = 2, n = 2, k = 1
Output: 10

Nous allons appliquer quelques mathématiques combinatoires pour résoudre ce problème et formuler quelques formules pour résoudre ce problème. question.

Méthode de recherche de solutions

Dans cette méthode, nous élaborerons une formule : en appliquant la combinatoire à la situation actuelle, cette formule nous fournira le résultat.

Code C++ pour la méthode ci-dessus

Il s'agit de la syntaxe C++ que nous pouvons utiliser comme entrée pour résoudre le problème donné -

Exemple

#include <bits/stdc++.h>

#define MOD 1000000007

using namespace std;

long long fact(long long n) {
   if(n <= 1)
   return 1;
   return ((n % MOD) * (fact(n-1) % MOD)) % MOD;
}
long long comb(int n, int r) {
   return (((fact(n)) % MOD) / ((fact(r) % MOD) * (fact(n-r) % MOD)) % MOD);
}

int main() {
   int n = 3;
   int m = 4;
   int r = 5;
   long long linen = comb(n, 3); // the combination of n with 3.
   long long linem = comb(m, 3); // the combination of m with 3.
   long long liner = comb(r, 3); //the combination of r with 3.
   long long answer = comb(n + m + r, 3); // all possible comb of n, m , r with 3.
   answer -= (linen + linem + liner);
   cout << answer << "\n";
   return 0;
}

Sortie

205

Explication du code ci-dessus

Dans cette méthode, nous trouvons Tous combinaisons possibles de n+m+r et de trois nombres, c'est-à-dire comb(n+m+r, 3). Maintenant, vous savez que la condition pour que trois points deviennent un triangle est qu'ils ne peuvent pas être colinéaires, nous trouvons donc tous les points colinéaires possibles obtenus en additionnant les combinaisons de n, m, r, puis combinons cette somme avec n+ En soustrayant le changements dans les trois nombres m+r, nous obtenons la réponse et l’imprimons.

Conclusion

Cet article explique comment calculer combien de triangles peuvent être formés à partir d'un ensemble de points sur trois droites en appliquant la combinatoire. Nous avons également appris le programme C++ et la méthode complète (méthode normale) pour résoudre ce problème. Nous pouvons écrire le même programme dans d'autres langages comme C, Java, Python et d'autres langages. J'espère que cet article vous sera 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!