totomm
Bonjour,
Il s'agit de triangles à cotés entiers (Suite à discussion initiée par 0^0 dans le forum "Enigmes").
le sommet A est à l'origine des coordonnées et [AB], le plus grand coté, sur l'axe des abscisses.
Ce code est adaptable pour des triangles non-scalènes.
Le langage choisi est un langage strictement typé pour assurer que certains calculs se font bien sur des entiers.
Programme pour déterminer les triangles scalènes de cotés entiers possédant au moins un point M à distance entière de chaque sommet..
Le programme est un module (.vb) dans Visual Basic express 2010
L' option "Strict On" garantit que les calculs sur entiers Long dans la partie "recalcul sur entiers" s'effectuent bien sur des "Long" sans aucune introduction de décimales.
Voir() est une procédure (non donnée) de création simultanée de fichier en plus de l'affichage sur console.
Option Explicit On
Option Strict On
Imports System.Math
Module TrianglesEntiers_M
Sub TrianglesEntiers()
Dim nombre As Integer = 0
Dim Max As Long = 120
Dim CM, Yc2, Ym2 As Long
Dim xc, yc, xm, ym As Double
For AC As Long = 1 To Max
Dim AC2 As Long = AC * AC
For BC As Long = AC + 1 To Max + 1
Dim BC2 As Long = BC * BC
For AB As Long = BC + 1 To AC + BC - 1
Dim AB2 As Long = AB * AB
For AM As Long = 1 To AB - 1
Dim AM2 As Long = AM * AM
For BM As Long = AB - AM + 1 To Max
Dim BM2 As Long = BM * BM
xc = (AC2 + AB2 - BC2) / (2 * AB)
yc = Sqrt(AC2 - xc ^ 2)
xm = (AM2 + AB2 - BM2) / (2 * AB)
ym = Sqrt(AM2 - xm ^ 2)
If ym * xc - (xm * yc) + 0.001 < 0 And ym * (xc - AB) - (yc * (xm - AB)) - 0.001 > 0 Then
'M est intérieur
Dim CMd As Double = Sqrt((xm - xc) ^ 2 + (ym - yc) ^ 2)
CM = CInt(CMd + 0.000000001)
If Abs(CM - CMd) < 0.000001 Then
' recalcul sur entiers
Dim xcL, xmL As Long
xcL = AC2 + AB2 - BC2
xmL = AM2 + AB2 - BM2
Yc2 = 4 * AB2 * AC2 - (xcL * xcL) '4*AB*AB*yc*yc
Ym2 = 4 * AB2 * AM2 - (xmL * xmL) '4*AB*AB*ym*ym
Dim G As Long = 2 * AB2 * (AC2 + AM2 - (CM * CM)) - ((AB2 + AM2 - BM2) * (AC2 + AB2 - BC2))
If G * G = Yc2 * Ym2 Then
nombre += 1
Voir("N° " & nombre & " : " & AC & " " & BC & " " & AB & " " & AM & " " & BM & " " & CM)
If nombre = 1001 Then Exit Sub
End If
End If
else
exit for ' dès que M est extérieur
End If
Next
Next
Next
Next
Next
End Sub 'TrianglesEntiers()
End Module
0-0
Re,
Il faudra bien que je m'y mette un jour...
@+
yoshi
Bonjour,
J'ai traduit aussi scrupuleusement que possible du VB en Python, mais j'ai un plantage au 3e tour ici :
ym = sqrt(AM2 - xm**2)
Voilà ce que me donne print(xm,AM2,AB2,AC2,BC2) placé juste avant cette ligne :
0.1 1 25 9 16
-1.0 1 25 9 16
-2.3 1 25 9 16
et le résultat de AM2-xm**2 est -4.29...
ou avec les quotients entiers :
0 1 25 9 16
-1 1 25 9 16
-3 1 25 9 16
-8
Donc l'erreur est "normale"... sauf que le passage de -4.29 à -8 simplement en substituant // à / me paraît louche !
J'ai dû rater quelque chose avant, mais quoi... Je n'ai plus le temps de chercher pour le moment.
Pour information, en Python (j'ai découvert ça depuis peu) :
>>> sqrt(225).is_integer()
True
>>> sqrt(224).is_integer()
False
>>>
@+
totomm
Bonsoir,
@ yoshi : Que c'est difficile de ne pas transmettre les bugs initiaux des programmes !!
J'ai eu aussi ce bug sur sqrt d'une valeur négative parce que BM croit jusqu'à Max.
Pourtant j'y avais pensé dès que j'ai commencé à écrire le programme, mais j'ai oublié de transmettre ce que j'avais aouté :
else
exit for ' dès que M est extérieur
juste avant le dernier "end if" qui précède les "next".
Cela empèche BM de progresser et renvoie au AM suivant, xm ne peut plus être < 0 : je viens de l'insérer au post #1
Les 1001 triangles sont calculés en 2 mn 57s et non 14 min 57 s.
Sauf nouvel oubli. Cordialement : totomm
yoshi
Bonsoir,
Rectifié, plus de plantage...
Le prog tourne... sans résultats.
Donc j'ai un autre problème ailleurs.
Probablement déjà la transcription de :
1) CM = CInt(CMd + 0.000000001)
CInt : j'ai cherché une doc où j'ai cru lire
CInt(8,43) --> 8
CInt(8,51) --> 9
Ce serait l'arrondi à l'entier le plus proche ?
Quel est le but de l'ajout de 0.000000001 ?
2) If Abs(CM - CMd) < 0.000001 Then
Test si CM -CMd très proche de 0 (à 10^-6 près) ?
Donc, j'ai fixé Max à 20 et je lui ai fait afficher AB, AC, BC dans cet ordre.
Arrêt à 37, 19, 20 sans rien trouver...
Je teste l'arrondi à l'entier : pas plus de succès.
from math import sqrt
def triangles(Max, nombre):
for AC in range(1,Max):
AC2 = AC**2
for BC in range(AC + 1, Max + 1):
BC2 = BC**2
for AB in range(BC + 1,AC + BC - 1):
AB2 = AB**2
for AM in range(1, AB - 1):
AM2 = AM**2
for BM in range(AB - AM + 1,Max):
print(AB,AC,BC)
BM2 = BM**2
xc = (AC2 + AB2 - BC2)//(2 * AB)
yc = sqrt(AC2 - xc**2)
xm = (AM2 + AB2 - BM2)//(2 * AB)
ym = sqrt(AM2 - xm**2)
if ym * xc - (xm * yc) + 0.001 < 0 and ym * (xc - AB) - (yc * (xm - AB)) - 0.001 > 0:
#M est intérieur
CMd = sqrt((xm - xc)**2 + (ym - yc)**2)
CM = round((CMd + 0.0000001),0)
if abs(CM - CMd) < 0.000001:
#recalcul sur entiers
xcL = AC2 + AB2 - BC2
xmL = AM2 + AB2 - BM2
Yc2 = 4 * AB2 * AC2 - (xcL**2) #4*AB*AB*yc*yc
Ym2 = 4 * AB2 * AM2 - (xmL**2) #4*AB*AB*ym*ym
G = 2 * AB2 * (AC2 + AM2 - CM**2) - ((AB2 + AM2 - BM2) * (AC2 + AB2 - BC2))
if G**2 == Yc2 * Ym2:
nombre += 1
print("N°",nombre," : ",AC,BC,AB," --- ",AM,BM,CM)
if nombre == 11: # j'ai demandé l'arrêt à 11 et non 1001 pour test
return
else:
break
nombre = 0
Max = 20
triangles(Max, nombre)
Je verrai ça plus tard
@+
totomm
Bonsoir,
J'ai vu dès la 2ème ligne : AC2 = AC**2
AC2 va être un nombre flottant. il faut AC2=AC*AC pour que AC2 soit un nombre entier...
Voici mon code qui donne (Pyton 3.2) exactement les mêmes 1001 triangles que le programme en Visual Basic
mais en Python il met environ 23 minutes (idle GUI sous Windows, interprété), sans créer de fichier,
alors que Vb (compilé et sous debugger) met moins de 3 minutes (en créant aussi un fichier en plus de l'affichage console
from math import sqrt
def trianglesEntiers():
nombre, max=0,121
for ac in range(1,max):
ac2=ac*ac
for bc in range(ac+1,max+1):
bc2=bc*bc
for ab in range(bc+1,ac+bc-1):
ab2=ab*ab
for am in range(1,ab-1):
am2=am*am
for bm in range(ab-am+1,max):
bm2=bm*bm
xc = (ac2+ab2-bc2)/(2*ab)
yc = sqrt(ac2-xc**2)
xm = (am2+ab2-bm2)/(2*ab)
ym = sqrt(am2-xm**2)
if ym*xc-(xm*yc)+0.001 < 0 and ym * (xc-ab)-(yc*(xm-ab))-0.001 > 0:
#M est intérieur
cmd=sqrt((xm - xc) ** 2 + (ym - yc) ** 2)
cm=int(cmd+0.000000001)
if abs(cm-cmd)<0.000001:
#recalcul avec entiers
xcl=ac2+ab2-bc2
xml=am2+ab2-bm2
yc2=4*ab2*ac2-(xcl*xcl)
ym2=4*ab2*am2-(xml*xml)
g=2*ab2*(ac2+am2-(cm*cm))-((ab2+am2-bm2)*(ac2+ab2-bc2))
if g*g==yc2*ym2:
nombre+=1
print("N°",nombre," :",ac,bc,ab,am,bm,cm)
if nombre==1001:
return
else:
break
trianglesEntiers()
yoshi
Bonsoir,
Merci.
AC2 va être un nombre flottant. il faut AC2=AC*AC pour que AC2 soit un nombre entier...
C'est que j'ai remplacé partout !
Mais là quelque chose méchappe :
vous êtes en train de dire que
\(AC^2 \ne AC*AC\) au niveau typage !
Il va falloir que je vérifie ça...
J'avais déjà lu qu'en Python AC*AC était un peu plus rapide que AC², mais encore jamais que l'un était un flottant et l'autre non !
@+
totomm
Re-Bonsoir,
Je n'ai pas trouvé comment arrêter (sortir de l’exécution) quand on veut terminer depuis une boucle for imbriquée...
Ce pourquoi j'ai utilisé une procédure def car le return fonctionne alors !
Je reprends la constatation
Si la comparaison if g*g==yc2*ym2: se fait sur des flottants, il suffit qu'une 15ème décimale soit différente (!!!) pour faire échouer ce qui serait vrai entre entiers
Cordialement : totomm
yoshi
Re,
Je n'ai pas trouvé comment arrêter (sortir de l’exécution) quand on veut terminer depuis une boucle for imbriquée...
Ce pourquoi j'ai utilisé une procédure def car le return fonctionne alors !
Même raison !
@+
totomm
ReBonsoir,
Dès que l'on utilise une opération autre que multiplication pour élever à une puissance, on passe en flottant (double en général)
x=2**3 donne x en flottant, x=2*2*2 donne x en entier : C'est le piège de Python qui donne par ailleurs des programmes plus lisible et plus faciles à écrire que VB. C'est la grande différence, avec les inconvénients de ses avantages entre un langage typé (VB) et non typé (Python).
Mais je ne connais pas suffisamment Python pour savoir si on peut forcer son comportement (typage dynamique vers statique) comme le fait l'option "strict on" avec VB.
Ainsi avec VB, s'il m'arrive d'écrire x=y^2 avec x déclaré entier (ou entier long), j'ai un avertissement.
Cordialement
EDIT du 04/07/2014 NON : En Python, X=2**3 est bien du type 'int' de même que x=2^3 en Visual Basic si x est déclaré integer.
L'opération "élever à la puissance" est dans le cas du VB "effectuée en flottant", mais une conversion est faite éventuellement suivant le type déclaré. En Python je suppose que cela dépend du type des 2 nombres utilisés ?
yoshi
Dès que l'on utilise une opération autre que multiplication pour élever à une puissance, on passe en flottant (double en général)
x=2**3 donne x en flottant, x=2*2*2 donne x en entier : C'est le piège de Python (...)
Quel piège ?
Pourtant, voyez ces vérifications :
- directe :
>>> type(2**3)
<class 'int'>
- indirecte :
>>> (2**3).is_integer()
Traceback (most recent call last):
File "<pyshell#3>", line 1, in <module>
(2**3).is_integer()
AttributeError: 'int' object has no attribute 'is_integer'
>>>
Alors ?
@+
totomm
Bonjour,
@ yoshi : Je peux m'être trompé en faisant des hypothèses sur Python que je connais insuffisamment....
Et j'ai regardé plus avant votre programme : xc et xm doivent être calculés en division normale, pas en division entière (euclidienne)...
Le principe de mon programme c'est de trouver la longueur d'un [CM] suffisamment proche d'un entier pour avoir alors un entier dont on vérifie sa pertinence.
Et mieux vaut peut-être convertir CM en entier par CM = int() que par CM=round() qui pourrait (?) renvoyer une valeur entière représentée en flottant...
totomm
Bonjour,
avec type(x) on voit que 3**2 est bien du type entier, mais round(2.00001,0) reste du type float et vaut 2.0
EDIT : J'ai donc modifié (EDIT) mon post #10
Avec les 2 // en / pour xc et xm dans le programme de yoshi : C'est OK, mais CM reste du type float
Avec round() remplacé par int() , Max =121 et if nombre=1001 : Résultat exactement identique pour programme yoshi et programme VB de totomm
yoshi
Bonjour
Ok, objection valable pour round().
Je plaide les circonstances atténuantes : je n'ai pas VB et j'ai cherché un équivalent à CInt...
J'ai pensé à int, mais int(3.85)--> 3 alors que, sauf erreur, en VB CInt(3,85) --> 4 : si c'est bien le cas, la nuance de taille quand même ! D'où l'emploi du round() insuffisamment réfléchi :
pour simuler le CInt, j'aurais dû écrire int(round(2.00001,0)).
D'autre part, je ne savais pas quelle était la "philosophie" précise sous-tendant vos calculs.
Idel pour le : la doc consultée m'a dit qu'en VB le / désignait le quotient entier : apparemment, c'est donc inexact !
Je vais devoir comparer votre version avec la mienne de très près, parce que je viens de remettre / en lieu et place de // et corriger round() en int(round()), je n'ai pas plus de résultats qu'hier...
Même punition en mettant seulement int().
J'ai donc encore raté autre chose...
J'ai pourtant adapté votre programme ainsi :
j'ai copié/collé votre prog dans Python 3.4 et fait les modifs ligne après ligne pour être sûr de ne rien inventer...
Bon, là, je n'ai plus le temps, peut-être d'ici 2-3 h...
@+
totomm
bonjour,
Voila exactement votre code avec 3 lignes modifiées plus Max=121 :
from math import sqrt
def triangles(Max, nombre):
for AC in range(1,Max):
AC2 = AC**2
for BC in range(AC + 1, Max + 1):
BC2 = BC**2
for AB in range(BC + 1,AC + BC - 1):
AB2 = AB**2
for AM in range(1, AB - 1):
AM2 = AM**2
for BM in range(AB - AM + 1,Max):
#print(AB,AC,BC)
BM2 = BM**2
xc = (AC2 + AB2 - BC2)/(2 * AB)
yc = sqrt(AC2 - xc**2)
xm = (AM2 + AB2 - BM2)/(2 * AB)
ym = sqrt(AM2 - xm**2)
if ym * xc - (xm * yc) + 0.001 < 0 and ym * (xc - AB) - (yc * (xm - AB)) - 0.001 > 0:
#M est intérieur
CMd = sqrt((xm - xc)**2 + (ym - yc)**2)
#CM = round((CMd + 0.0000001),0)
CM=int(CMd + 0.0000001)
if abs(CM - CMd) < 0.000001:
#recalcul sur entiers
xcL = AC2 + AB2 - BC2
xmL = AM2 + AB2 - BM2
Yc2 = 4 * AB2 * AC2 - (xcL**2) #4*AB*AB*yc*yc
Ym2 = 4 * AB2 * AM2 - (xmL**2) #4*AB*AB*ym*ym
G = 2 * AB2 * (AC2 + AM2 - CM**2) - ((AB2 + AM2 - BM2) * (AC2 + AB2 - BC2))
if G**2 == Yc2 * Ym2:
nombre += 1
print("N°",nombre," : ",AC,BC,AB," --- ",AM,BM,CM)
if nombre == 11: # j'ai demandé l'arrêt à 11 et non 1001 pour test
return
else:
break
nombre = 0
Max = 121
triangles(Max, nombre)
et le résultat de l'exécution :
Python 3.2.2 (default, Sep 4 2011, 09:07:29) [MSC v.1500 64 bit (AMD64)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
N° 1 : 8 19 22 --- 6 17 4
N° 2 : 12 57 59 --- 8 54 6
N° 3 : 13 30 32 --- 6 28 8
N° 4 : 14 38 39 --- 8 34 8
N° 5 : 16 38 44 --- 12 34 8
N° 6 : 16 39 43 --- 13 34 7
N° 7 : 16 70 76 --- 14 64 9
N° 8 : 16 71 73 --- 11 63 13
N° 9 : 17 38 43 --- 12 35 7
N° 10 : 17 73 80 --- 21 61 13
N° 11 : 18 20 26 --- 15 13 9
>>>
Vous pouvez supprimer ce post après l'avoir vu. Cordialement totomm
yoshi
RE,
Effectivement, votre version tourne...
J'ai donc comparé point par point avec les dernières modifs de ce matin (pas retouché depuis) : conforme !
Je l'ai donc relancé et maintenant il tourne !
Invraisemblable... C'est bien la première fois que ça m'arrive.
Désolé, mais j'ai quelques soucis domestiques en ce moment avec ma chère vieille (88 ans) mère : ça m'accapare pas mal.
Bon l'important est qu'il fonctionne.
Je vais pouvoir essayer de gagner du temps.
Merci
@+
totomm
Bonjour,
Sans doute Max était resté â 20 en avant-dernière ligne. Le plus petit côté AB est de 22...
0-0
Bonjour
Serait-il très compliqué de modifier le programme de façon à ce qu'il donne aussi les cas où certaines d'entre les valeurs AB, BC, AC, AM, BM et CM sont égales?
Il permettrait ainsi de fournir la liste complète de tous les triangles entiers ABC possibles "ayant un point M intérieur à distances entières des sommets" pour un "Max" donné, ce qui serait vraiment parfait.
@+
totomm
Bonjour,
@0^0 : Bien des choses ne sont pas si compliquées, donc faisables. Et chacun peut en faire une partie.
Si vous voulez "la liste complète de tous les triangles entiers ABC possibles…",
il faut peut-être définir un classement de tous ces triangles : Je vous suggère un classement par périmètres croissants.
Définissez donc comment cela pourrait être et donnez les 20 premiers de votre classement.
0-0
Bonjour,
totomm a écritBien des choses ne sont pas si compliquées, donc faisables. Et chacun peut en faire une partie.
Que j'aimerais que certaines choses "pas si compliquées" aux dires des uns, me soient plus familières... Ainsi, je pourrais tenter de participer comme je le souhaiterais, même si ce n'est que pour une petite part...
Or je suis tout juste en train de découvrir les bases 'Python': je précise que je ne connaissais encore rien de rien à la programmation il n'y a que quelques jours de cela...
totomm a écrit"Si vous voulez "la liste complète de tous les triangles entiers ABC possibles…",
il faut peut-être définir un classement de tous ces triangles : Je vous suggère un classement par périmètres croissants.
Définissez donc comment cela pourrait être et donnez les 20 premiers de votre classement.
Je planche sur la question depuis un certain temps sans guère avancer...
Au départ je recherchais une formule permettant d'attribuer à tout triangle une seule valeur qui dépendrait à la fois de son aire et de son périmètre, valeur permettant un classement et qui serait en théorie la même pour tous les triangles ayant une même aire et un même périmètre.
Cela dit, j'en arrive aussi à me dire que considérer seulement le Périmètre est sans doute plus adéquat (???) ou en tout cas au moins plus pratique, à défaut de mieux...
Je dis cela dans le sens que pour un périmètre donné, il existe une aire minimale égale à 0 (soit celle du triangle plat correspondant) et une aire maximale égale à celle du triangle équilatéral ayant ce périmètre, soit:
\(S_{max} = \left(\frac{Périmètre}{3}\right)^2.\frac{\sqrt{3}}{4}\), alors que ce n'est pas le cas si l'on considère seulement les aires...
> En effet, pour chaque aire donnée, il y a bien un périmètre minimal correspondant: encore celui d'un triangle équilatéral, mais pas de périmètre maximal défini, car ce dernier peut être infini... Ce serait bien gênant pour un triangle à qui l'on attribuerait une valeur qui ne l'est pas*!
*
note: autrement dit: infinie...
Mis à part cela, et à part si j'ai raté quelque chose, je ne vois pas en quoi un tel classement serait finalement nécessaire pour obtenir l'ensemble des triangles adéquats possibles - en y incluant ceux possédants des dimensions égales - pour un "Max" choisi, arbitraire certes....
@+