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.
Dans cette méthode, nous élaborerons une formule : en appliquant la combinatoire à la situation actuelle, cette formule nous fournira le résultat.
Il s'agit de la syntaxe C++ que nous pouvons utiliser comme entrée pour résoudre le problème donné -
#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; }
205
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.
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!