Discussion :

[Fredo123456]

Bonsoir à tous j'ai un projet à faire en langage C, je bloque sur l'énoncé depuis longtemps et je n'arrive pas du tt à comprendre comme résoudre ce programme:

On cherche à énumérer des triplets d'entiers (x,y,z) répondant à l'égalité suivante: x² + y² = z²
avec x<=y et z<=1000
Ce programme doit être le plus rapide possible.

Pouvez vous m'éclaircir davantage sur la méthode svp?
Doit on faire appelle à un tableau?
Merci

[Sve@r]

Bonsoir à tous j'ai un projet à faire en langage C, je bloque sur l'énoncé depuis longtemps et je n'arrive pas du tt à comprendre comme résoudre ce programme:

On cherche à énumérer des triplets d'entiers (x,y,z) répondant à l'égalité suivante: x² + y² = z²
avec x<=y et z<=1000
Ce programme doit être le plus rapide possible.

Pouvez vous m'éclaircir davantage sur la méthode svp?
Doit on faire appelle à un tableau?
Merci

Ben non, pas besoin de tableau. Une boucle sur "z" de 0 à 1000; une boucle sur "x" de 0 à z, une boucle sur "y" de 0 à x
On regarde si x² + y² = z² si oui on affiche
Si non et si x² + y² > z² on interromp la boucle "y" et l'algo est terminé.

[Rukia]

Ben non, pas besoin de tableau. Une boucle sur "z" de 0 à 1000; une boucle sur "x" de 0 à z, une boucle sur "y" de 0 à x
On regarde si x² + y² = z² si oui on affiche
Si non et si x² + y² > z² on interromp la boucle "y" et l'algo est terminé.

et comment verifier tu que x<=y ???
j'ai pas compris cette ligne si x² + y² > z² on interromp la boucle "y"

[Sve@r]

et comment verifier tu que x<=y ???

Ben parce que y part de x !!!

j'ai pas compris cette ligne si x² + y² > z² on interromp la boucle "y"

La boucle "y" est la 3° (la plus imbriquée). Si x² + y² > z² on la breake et on retourne donc sur la boucle "x"

Tu peux éviter les 0, non ?

Oui évidemment...

Tu peux aussi améliorer en supprimant la 3ème boucle :
si z et x sont déterminés, il suffit de vérifier que z2 - x2 est un carré et est inférieur à x2.

Effectivement on peut supprimer la boucle "y" mais ca implique alors de calculer la racine carrée de z² - x² et de vérifier si cette racine est entière. Ce calcul peut être "un peu" long et ne pas correspondre aux contraintes "algorithme très rapide".
Ou alors on stocke toutes les nombres entre 1 et 1000000 dont les racines sont entières dans un tableau et on regarde si z² - x² est égal à un nombre de ce tableau...

cette méthode marche mais c'est loin d'etre rapide, tu a en face de toi une boucle qui va etre repeté 1000000 fois pour faire les tests, 1 Million de tests.
comme la il s'agit d'une cas particuliere du fameux theoreme de Fermat, tu dois fouiller un peu dans tes cours pour chercher la solution de ce system.
les triplets qui sont une solution de cette equation verifient :

m<n , m et n sont premier entre eux.
x=2*m*n
y=n²-m²
z=n²+m²

comme z<1000, on en deuit que n<90, donc on fait deux boucle, une sur n, et a l interieur de cette boucle une autre sur m, et voila, au lieu de 1 millions de comparaison et tout on a fait juste 1000

Joli. Si les formules sont exactes ça évite un paquet de boucles. Comme quoi, contrairement aux affirmations de certains cancres, les maths c'est utile...

[fremen167]

Ce calcul peut être "un peu" long et ne pas correspondre aux contraintes "algorithme très rapide".
Ou alors on stocke toutes les nombres entre 1 et 1000000 dont les racines sont entières dans un tableau et on regarde si z² - x² est égal à un nombre de ce tableau...

Je serai très surpris que le calcul de racine carré soit plus long que ta troisième boucle... et avec l'autre optimisation que j'ai proposé (racine(2)), ça doit être très rapide... mais beaucoup moins que la méthode mathématique. J'avais trouvé cette méthode (par "triplets de Pythagore"), mais je ne suis pas sûr qu'on génère tous les triplets de cette manière.

[pseudocode]

Joli. Si les formules sont exactes ça évite un paquet de boucles. Comme quoi, contrairement aux affirmations de certains cancres, les maths c'est utile...

Oui, les formules sont exactes. Il suffit de prendre un complexe (a+ib) quelconque et de l'elever au carré pour trouver les formules.

A noter que si m,n sont premiers entre eux alors on n'obtient que les triplets primitifs. Donc pour une liste exhaustive, il faut prendre tous les m,n.

[luchio13579]

Ayant un programme légèrement similaire a celui ci, je me permet de poster ici pour éviter de faire un nouveau post.
Je dois aussi utiliser dans un programme l'égalité de Fermat tel que x^2+y^2=z^2.
J'ai compris ce qui a été dit précédement sur ce qu'à dit "siegfried64", mais étant particulièrement mauvais en C, je voulais savoir de qu'elle boucle tu parleS, une boucle FOR ? Je commence a peine la prog, je voudrais juste savoir quelle boucle il faut utiliser, je me débrouillerais pour le faire marcher ...
Merci d'avance !

[fremen167]

Ben non, pas besoin de tableau. Une boucle sur "z" de 0 à 1000; une boucle sur "x" de 0 à z, une boucle sur "y" de 0 à x
On regarde si x² + y² = z² si oui on affiche
Si non et si x² + y² > z² on interromp la boucle "y" et l'algo est terminé.

Tu peux éviter les 0, non ?

Tu peux aussi améliorer en supprimant la 3ème boucle :
si z et x sont déterminés, il suffit de vérifier que z2 - x2 est un carré et est inférieur à x2.

[fremen167]

Et pour être sûr que y sera inférieur à x, tu peux faire partir ta deuxième boucle de z / (racine de 2) car si x < à cette valeur,
x2 < z2 / 2 ==> y2 > z2 /2.

[siegfried64]

cette méthode marche mais c'est loin d'etre rapide, tu a en face de toi une boucle qui va etre repeté 1000000 fois pour faire les tests, 1 Million de tests.
comme la il s'agit d'une cas particuliere du fameux theoreme de Fermat, tu dois fouiller un peu dans tes cours pour chercher la solution de ce system.
les triplets qui sont une solution de cette equation verifient :

m<n , m et n sont premier entre eux.
x=2*m*n
y=n²-m²
z=n²+m²

comme z<1000, on en deuit que n<90, donc on fait deux boucle, une sur n, et a l interieur de cette boucle une autre sur m, et voila, au lieu de 1 millions de comparaison et tout on a fait juste 1000