Maison > développement back-end > C++ > le corps du texte

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

王林
Libérer: 2023-09-09 09:53:08
avant
1278 Les gens l'ont consulté

É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
Copier après la connexion

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;
}
Copier après la connexion

Sortie

205
Copier après la connexion

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!

Étiquettes associées:
source:tutorialspoint.com
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal