1
votes

Comparaison de deux triangles en C (3, 3, 4 et 4, 3, 3 par exemple)

J'ai besoin de trouver tous les triangles possibles dans un ensemble d'entiers. J'ai obtenu le résultat avec succès, mais j'ai de nombreux doublons, par exemple:

A (3, 3, 4) == B (4, 3, 3)

Je n'ai pas besoin de trouver des triangles similaires, j'ai besoin de savoir quand ils sont égaux.

J'ai essayé de sauvegarder mes triangles en tant que structures et je voulais les comparer:

struct triangle
{
    int a;
    int b;     // I stored all found triangles this way
    int c;
};

int getNumberOfDuplicates(struct triangle savedTriangles[], int size) {
    int count = 0;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            int a,b,c,x,y,z;
            if (i != j) {
                a = savedTriangles[i].a; b = savedTriangles[i].b; c = savedTriangles[i].c;
                x = savedTriangles[j].a; y = savedTriangles[j].b; z = savedTriangles[j].c;

            if (areTheSame) {  // Here I don't know how to compare them
                count++;
            }
        }
    }
}
return count;

Existe-t-il un moyen mathématique de les comparer? Ou n'importe quel moyen de programmation?

6 commentaires

donc si je comprends bien, vous considérez les triangles comme égaux lorsque les 3 nombres de la structure sont égaux dans n'importe quel ordre?

Oui! Exactement :)

@Etoile Ce serait moins de travail de modifier le code qui crée la liste des triangles pour qu'il ne génère pas de doublons.

Pour générer sans doublons: triez les longueurs d'arêtes disponibles. Considérez tous les triplets, en rejetant ceux qui ne satisfont pas à l'inégalité du triangle, comme vous devez déjà le faire, et rejetez également ceux qui contiennent une longueur égale à la longueur précédente dans la liste triée si cette longueur précédente n'est pas également dans le triple.

Vérifiez la manière mathématique dans ma réponse, cela peut être intéressant.

@Etoile L'autre chose à noter est que la logique actuelle compte les doublons plusieurs fois, même si areTheSame est remplacé par la bonne fonction de comparaison. Supposons par exemple que vous ayez un tableau avec 3 triangles identiques 3, 3, 4 , 3, 4, 3 , 4, 3, 3 , alors le code tel quel maintenant compterait 6 doublons, tandis que la bonne réponse devrait être 2 .

3 Réponses :

4
votes

La solution la plus simple serait de trier les trois nombres.

void swap(int *a, int *b) {
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

void bubble_sort(int *a, int *b, int *c) {
  if (a > b) swap(&a, &b);
  if (b > c) swap(&b, &c);
  if (a > b) swap(&a, &b);
}

À quel point il devrait être trivial de comparer s'ils sont égaux.

0 commentaires

2
votes

Vous devez apporter deux modifications à votre code:

Il suffit de comparer un triangle aux suiveurs uniquement, vous le comptez maintenant deux fois, ce qui vous donnera le double du résultat souhaité.
Triez les longueurs par ordre croissant en utilisant min et max , puis comparez-les.

Donc, votre code devrait ressembler à ceci:

for (int i = 0; i < size - 1; i++) {
    for (int j = i + 1; j < size; j++) {
        int a, b, c, x, y, z, s1, s2, ss1, ss2, p1, p2;
        a = savedTriangles[i].a; b = savedTriangles[i].b; c = savedTriangles[i].c;
        x = savedTriangles[j].a; y = savedTriangles[j].b; z = savedTriangles[j].c;
        s1 = a + b + c;
        ss1 = a * a + b * b + c * c;
        p1 = a * b * c;
        s2 = x + y + c;
        ss2 = x * x + y * y + z * z;
        p2 = x * y * z;
        if (s1 == s2 && ss1 == ss2 && p1 == p2)
            count++;
    }
}

Il existe un moyen mathématique en obtenant leur somme, leur produit et la somme de leurs carrés sans avoir besoin de les trier, tout triplet donnera un ensemble unique de résultats quel que soit leur ordre en fonction de cela , donc le code alternatif devrait ressembler à ceci:

for (int i = 0; i < size - 1; i++) {
    for (int j = i + 1; j < size; j++) { //Start from i + 1 not 0
        int a, b, c, x, y, z, a1, b1, c1, x1, y1, z1;
        a = savedTriangles[i].a; b = savedTriangles[i].b; c = savedTriangles[i].c;
        x = savedTriangles[j].a; y = savedTriangles[j].b; z = savedTriangles[j].c;
        a1 = min(a, min(b, c));
        c1 = max(a, max(b, c));
        b1 = a + b + c - a1 - c1;
        x1 = min(x, min(y, z));
        z1 = max(x, max(y, z));
        y1 = x + y + z - x1 - z1;

        if (a1 == x1 && b1 == y1 && c1 == z1)
            count++;
    }
}

int min (int a, int b)
{
    return a < b ? a : b;
}

int max (int a, int b)
{
    return a > b ? a : b;
}

1 commentaires

Ce dernier est une belle astuce mathématique (+1), et vous pouvez également utiliser ss1 = a*b + b*c + c*a la même manière (ce qui donnerait en fait les coefficients du polynôme ayant a, b, c comme les racines). Cela dit, la première approche min/max a moins de calculs et ne présente pas de risque de débordement en cas de grand nombre.

0
votes

En supposant que la liste est complète, chaque triangle sera répété pour chaque permutation de ses côtés a, b, c . Par conséquent, chaque triangle est un duplicata d'un avec a <= b <= c , il suffit donc de ne vérifier que ceux-ci, et de compter automatiquement tout triangle avec b < a ou c < b comme duplicata.

int getNumberOfDuplicates(struct triangle savedTriangles[], int size){
    int count = 0;
    for (int i = 0; i < size; i++){
        int a = savedTriangles[i].a,
            b = savedTriangles[i].b,
            c = savedTriangles[i].c;
        if(b < a || c < b){
            count++;
            continue;
        }
        for (int j = i + 1; j < size; j++){
            int x = savedTriangles[j].a,
                y = savedTriangles[j].b,
                z = savedTriangles[j].c;
            if(a == x && b == y && c == z){
                count++;
                break;
            }
        }
    }
    return count;
}

0 commentaires