Trouver le triangle ayant la plus grande surface et afficher ses coordonnées [Résolu]

[SmErT]

Salut a tous.

Voilà le problème.
On donne un nombre de points dans un repaire cartésien A, B, C, D…
Il faut trouver la surface de tous les triangles possible calculer la surface et dire le quelle est le plus grand on affichant ces coordonner et sa surfsce.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
REM triangle
INPUT "n="; n
IF n < 3 THEN
    PRINT "avec le nombre de point que vous avez donne vous ne pouvez pas avoir de triangle"
ELSE
    'TRIANGLE = prob(n)
    'PRINT "nous avons une probabilité de "; TRIANGLE; "triangle avec "; n; " de points."
 
END IF
 
FUNCTION g_point ()
m = 2
RANDOMIZE TIMER
DIM a(n, m)
FOR i = 1 TO n
    FOR j = 1 TO m
        a(i, j) = (RND * 10)    ////génère une table de point avec des nombre aléatoire 
    NEXT j
NEXT i
END FUNCTION
 
'FUNCTION CalculAire (Ax, Ay, Bx, By, Cx, Cy)
'CalculAire = ABS((Ax * (By - Cy) + Bx * (Cy - Ay) + Cx * (Ay - By)) / 2)      /////trouve la surface avec ses coordonne.
'CalculAire = 1 / 2 * ABS((Ax * Cy) - (Ax * By) + (Bx * Ay) - (Bx * Cy) + (Cx * By) - (Cx * Ay))
'END FUNCTION
 
FUNCTION prob (n)
F = 1
G = 6
H = 1
l = n - 3
FOR i = 1 TO n                       ///////////// calque le nombre des triangles possible 
    F = F * i
NEXT i
FOR i = 1 TO l
    H = H * i
NEXT i
prob = F / (H * G)
END FUNCTION

Mon plus grand problème est de faire une table genre
ABC
ABD
ACD
BCD

Pas ABC ACB CBA car c’est la même chose

A D C
|x,y | x,y| x,y |aire1


Puis de comparer le résultat avec la fonction max et afficher le les coordonne est le résultat de la surface maximal.

Code :

1
2
3
4
5
6
7
8
9
 
INPUT "max elements"; n
DIM A(n)
max = A(1)
FOR i = 1 TO n
    IF A(i) > max THEN max = A(i)
NEXT i
PRINT "Max="; max
END

si vous avez d’autre idée n’hésiter pas
merci.

[AdmChiMay]

Tu dis que tu veux éliminer les les triplets identiques ? Donc faut les identifier et les classer !

Cela devrait suffire comme réponse...

Bon, de loin : si tu dis la lettre 'X', c'est que tu peux l'identifier ? donc que tu en as un identificateur, dans ton programme ? (que cet identificateur s'appelle 'X' ou 'Data_23').

Vu de loin : tu fais des boucles imbriquées pour sélectionner toutes les possibilités. Ok.
Ensuite tu ne veux pas de doublons ? Alors construis ta liste des triplets uniques, et range-là ailleurs. Comment ? ben, par exemple, entre autres, tu tries ton triplet : DAC devient ACD (avec des quadruplets, on aurait pu avoir ACDC, mais bon, je m'égare), et tu vérifies que ce ACD n'existe pas déjà dans ta liste. Ça, c'est certainement ce que le sujet ne disait pas.

Tu prends les questions dans le bon ordre, et ça va tout de suite mieux. Et cela te montre là ou le sujet qu'on t'a posé suppose que tu identifies toi-même les éléments manquants sur le chemin entre la question et le programme qui tourne. C'est valable pour tous les TPs.

[SmErT]

salut.
dite comment je peux générée çà ?

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
si j'ai 
a
b
c
 
abc
------------------------
si j'ai
 
a
b
c
d
 
abc
abd
acd
bcd
 
------------------------
si j'ai
 
a
b
c
d
e
 
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
 
.
.
.
ext

merci.

[AdmChiMay]

Bonsoir,

Si tu sais poser ta méthode sur une feuille avec un crayon, c'est presque plus que du yaka pour terminer... Cela te donne une première manière de faire, parfois plus bulldozer que subtile, mais avec le mérite de fonctionner.

Regardes bien.
Tu as n sommets, ce qui te donne une variable.
Tu cherche des triplets, donc :
- Tu prends un premier sommet : ça pourrait pas te donner un indice de boucle qui parcourt la liste pour sélectionner le premier sommet ? Et tu peux deviner (heu, justifier) la valeur de départ et de fin de l'indice ?
- Tu prends un second sommet : ça te donnerait pas par hasard un second indice de boucle, avec une valeur de début et de fin ?
- Tu prends un troisième sommet : ne serait-on pas par le plus grand des z'hasards dans le même cas ?
Et tu dois pouvoir dire pourquoi ce n'est pas la peine de revenir en arrière avec tes indices.

Au milieu de ces trois boucles, il faut prendre des décisions : 3 indices, donc trois sommets. On a dit les mettre dans l'ordre : ce serait pas une fonction annexe ? Une fois dans l'ordre, vérifier que c'est pas déjà dans ta liste : tiens, on dirait une autre fonction possible. Si c'est ok, on ajoute à la liste : tiens, encore une fonction.
Et puisqu'on a parlé de liste de triplets, faut aussi penser à décrire et initialiser la structure de données qui va avec.

Bon, si je vais plus loin, je te donne la réponse toute cuite en Pascal/Basic francisé, et ce n'est pas vraiment le but du forum.
Observes bien ce que tu fais à la main, l'algorithme ou le programme s'écrivent presque tous seuls dans la foulée.

[SmErT]

Salut.
merci pour ta repense AdmChiMay

Donc voilà, pour ne pas dire que j’ai ne rien fais et que j’attente de vous une repense toute cuite.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
 
CLS
REM triqngle
OPTION BASE 1 'Tout les tableaux commence par 1 et non 0
INPUT "n="; n
RANDOMIZE TIMER
DIM a(n, 2)
 
PRINT
PRINT "------------------------Generateur coordonnées-------------------------------"
PRINT
 
FOR i = 1 TO n
    FOR j = 1 TO 2
        a(i, j) = INT(RND * 50)
        PRINT a(i, j),
    NEXT j
    PRINT
NEXT i
 
PRINT
PRINT "---------------Calcule de la longueur des cotes de triangle--------------------"
PRINT
 
PRINT w
w = probligne(n)
longligne = 0
DIM ligne(w, 5)
m = 0
FOR i = 1 TO n - 1
    FOR j = i + 1 TO n
        m = m + 1
        ligne(m, 1) = a(i, 1)
        ligne(m, 2) = a(i, 2)
        ligne(m, 3) = a(j, 1)
        ligne(m, 4) = a(j, 2)
        longligne = SQR((ligne(m, 3) - ligne(m, 1)) ^ 2 + (ligne(m, 4) - ligne(m, 2)) ^ 2)
        ligne(m, 5) = longligne
        PRINT ligne(m, 1), ligne(m, 2), ligne(m, 3), ligne(m, 4), ligne(m, 5)
    NEXT j
NEXT i
 
 
PRINT
PRINT "--------------------Calcule de la surface  de triangle -----------------------"
PRINT
 
't = prob
DIM triangle(100, 4)
DIM o AS INTEGER, p AS INTEGER, q AS INTEGER
h = 0
z = 0
FOR o = 1 TO n - 2
 
    FOR p = o TO n - 1
 
        FOR q = p + 1 TO n
            h = h + 1
 
            PRINT ligne(o, 5), ligne(p, 5), ligne(q, 5)
 
            'triangle(h, 1) = ligne(o, 5)
            'triangle(h, 2) = ligne(p, 5)
            'triangle(h, 3) = ligne(q, 5)
            'z = ((triangle(h, 1) + triangle(h, 2) + triangle(h, 3)) / 2)
            'PRINT z
            'striangle = SQR(z * (z - triangle(h, 1)) * (z - triangle(h, 2)) * (z - triangle(h, 3)))
            'triangle(h, 4) = striangle
            'PRINT triangle(h, 1), triangle(h, 2), triangle(h, 3), triangle(h, 4)
        NEXT q
    NEXT p
NEXT o
 
'FUNCTION probtriangle(n)
'F = 1
'G = 6
'h = 1
'l = n - 3
'FOR i = 1 TO n
'    F = F * i
'NEXT i
'FOR i = 1 TO l
'   h = h * i
'NEXT i
probtriangle = F / (l * G)
'END FUNCTION
 
 
 
FUNCTION probligne (n)
F = 1
G = 2
h = 1
l = n - 2
FOR i = 1 TO n
    F = F * i
NEXT i
FOR i = 1 TO l
    h = h * i
NEXT i
probligne = F / (l * G)
END FUNCTION

Mon problème c’est dans la partie ou ont calcule la surface de triangle, le prog prend tous les cas possible. Avec n point il fait n !/3 !
Mais moi je cherche que n !/((n-3)1*3 !)
Par exemple :
Pour 3 point ==> un triangle
Pour 4 point ==> 4 triangle
Pour 5 point ==> 10 triangle ext

Je cherche le moine de filtrer les cas qui m’intéresse pas.

merci

[AdmChiMay]

Bonjour,

Mon Basic date un peu (a minima de l'Apple //e), ou alors c'est du VBA-Excel, mais on devrait se comprendre. Je me positionne sur l'aspect méthode, donc algorithmique. Je comprends tes lignes, mais pas tout :
- dimensionnement du tableau à 1..n, initialisation de l'aléatoire
- générer les n coordonnées
jusque là, ok. Mais après :
- calcul de la longueur des côtés,
- calcul des surfaces.
Il manque une partie de ce que j'ai cité :
- générer la structure de données pour les triplets triés dans l'ordre
- utiliser cette structure de données pour calculer tes surfaces.

Et je pense que ta réponse (enfin, celle attendue) ne tient pas en 30 lignes de codes. Biscotte ne pas avoir de doublons dans les triangles... Donc attends-toi à suer encore un peu.

Ton tableau est "a" : je préfèrerai un nom plus "causant". Tu pourrais dire "tableauPoints", "nuage_points", ou simplement "TP" si tu veux faire court. Donc TP est un tableau de points. Il te manque, à mon avis, le tableau identifiant les triplets, par exemple : Triangles[]. Je vois, là ponctuellement vite fait, 2 choix : sur une ligne du tableau placer les trois points "en entier", donc les 6 coordonnées ou juste placer l'indicateur du point visé. Par indicateur, je veux dire le n° du point dans TP : un entier nous suffira donc. Du coup, on doit avoir quelque chose comme Triangles[z,3]. On compte de 1 à z pour les triangles, et de 1 à 3 pour les sommets.
_ Le problème maintenant : quelle valeur pour z ? Une manière brute, type âge de la massue, serait de dire que au pire n!. Une version âge de bronze serait n(n-1)(n-2). Un raisonnement par récurrence donne quelque chose comme : le nombre de sous-ensemble distincts de 3 éléments parmi n. As-tu vu les dénombrements en math/proba ? Cela donne quelque chose comme C(n,3)=n!/6/(n-3)! A vérifier avec google, ou plutôt wikipedia. Bref, nous avons une valeur de z.

Tu dois d'abord trouver la liste des triplets uniques. Donc remplir le tableau Triangles, donc trois boucles imbriquées : une pour chaque sommet. Comme je le mentionnait avant, au milieu des trois boucles, vérifier si tu connais ce déjà ce triplet, et si non, l'ajouter à Triangles. Grosso modo (je ne mets que l'ossature) :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
'-- Initialisation de TP
z = ... 'appel à une fonction par exemple
DIM Triangles(z,3)
'Au fait, il faut aussi une variable pour connaitre le nombre de triangles déjà inscrits dans Triangles, par exemple nbTri (à toi de l'initialiser)
 
'-- Génération des points dans TP
bla bla bla bli
 
'-- Recherche des triangles
FOR i = 1 TO (z-2) DO
  FOR j = (i+1) TO  (z-1) DO
    FOR k = (j+1) TO z DO
      '> les sommets sont les points {i,j,k}
      '-- Si le triangle n'est pas connu, l'insérer dans la liste
      IF triangle_inconnu(TP,Triangles, i,j,k, nbTri)  ' Je pense que tu peux expliquer les valeurs extrêmes
                                                        ' et la liste choisie de paramètres
        THEN ajoute_triangle (Triangles, i,j,k, nbTri)
        ' Là, normalement, nbTri revient incrémenté de 1
    NEXT k
  NEXT 
NEXT i
 
'-- Maintenant, on peut boucler sur les triangles
FOR i = 1 to nbTri DO
  'Calcul de la surface
  Tu choisis ton organisation : tu as 3 points, leurs coordonnées, c'est le la géométrie 2D...
NEXT i
 
'-- Fonction triangle_inconnu
Il te faut parcourir Triangles pour savoir si les points TP(i,...) TP(j,...) TP(k,...) forment un triangle déjà connue dans Triangles. Il peut être utile, pour des raisons de clarté (et de facilité à débugger), de faire une fonction de comparaison de 2 poins).
 
'-- Fonction ajoute_triangle
Là, c'est un des points (sans jeu de mots) les plus faciles.

Je ne m'étends volontairement pas sur tes calculs de lignes et surfaces. De toutes façons, tu peux commencer par te générer un tableau TP en constante, à la main, avec des points "bien choisis", pour démarrer.

Bon, tu vois : faire à la main, et décomposer encore et encore, pour avoir des morceaux simples (ou presque). Mais c'est vrai, il te reste quelques lignes à taper...

Bon Couragne !

[SmErT]

salut a tous.
Donc voilà en se basons sur l'aide que j'ai us je suis arrivée à la fin de se exo

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
REM triqngle
BEEP
INPUT "n="; n
m = 2
h = 0
s = 0
u = 1
h = 0
k = prob(n)
CLS
IF n < 3 THEN
    PRINT
    PRINT "Avec le nombre de poit que vous aver donne vous pouvez pas avoire de triangle"
    PRINT
ELSE
    RANDOMIZE TIMER
    DIM a(n, m)
    FOR i = 1 TO n
        FOR j = 1 TO m
            a(i, j) = INT(RND * 50)
            'PRINT a(i, j),
        NEXT j
        'PRINT
    NEXT i
    '----------------------------------------------------------------
    DIM triangle(k, 7)
    DIM o AS INTEGER, p AS INTEGER, q AS INTEGER
    PRINT
    FOR o = 1 TO n - 2
        FOR p = o + 1 TO n - 1
            FOR q = p + 1 TO n
                h = h + 1
                triangle(h, 1) = a(o, 1)
                triangle(h, 2) = a(o, 2)
                triangle(h, 3) = a(p, 1)
                triangle(h, 4) = a(p, 2)
                triangle(h, 5) = a(q, 1)
                triangle(h, 6) = a(q, 2)
                xA = triangle(h, 1)
                yA = triangle(h, 2)
                xB = triangle(h, 3)
                yB = triangle(h, 4)
                xC = triangle(h, 5)
                yC = triangle(h, 6)
                s = ABS(((xB - xA) * (yC - yA)) - ((xC - xA) * (yB - yA))) / 2
                triangle(h, 7) = s
                'PRINT xA; yA; xB; yB; xC; yC, s
            NEXT q
        NEXT p
    NEXT o
    PRINT
    '----------------------------------------------------------------
    max = triangle(1, 7)
    s = 0
    FOR i = 2 TO k
        s = triangle(i, 7)
        IF s > max THEN u = i
    NEXT i
    PRINT "le triangle qui a la plus grande aire a pour coordoner:"
    PRINT "A("; triangle(u, 1); ","; triangle(u, 2); ")",
    PRINT "B("; triangle(u, 3); ","; triangle(u, 4); ")",
    PRINT "C("; triangle(u, 5); ","; triangle(u, 6); ")"
    PRINT "et une aire de "; triangle(u, 7)
END IF
 
FUNCTION prob (n)
F = 1
G = 6
H = 1
l = n - 3
FOR i = 1 TO n
    F = F * i
NEXT i
FOR i = 1 TO l
    H = H * i
NEXT i
prob = F / (H * G)
END FUNCTION

merci a vous.