Problème de méthode

Version imprimable

07/12/2007, 21h55
Fredo123456

Problème de méthode

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 :roll:
07/12/2007, 22h53
Sve@r

Citation:

Envoyé par 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 :roll:

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é.
07/12/2007, 23h05
Rukia

Citation:

Envoyé par Sve@r

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"
07/12/2007, 23h10
fremen167

Citation:

Envoyé par Sve@r

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.
07/12/2007, 23h14
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.
08/12/2007, 01h31
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
08/12/2007, 08h58
Sve@r

Citation:

Envoyé par Rukia-chan

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

Ben parce que y part de x !!!

Citation:

Envoyé par Rukia-chan

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"

Citation:

Envoyé par fremen167

Tu peux éviter les 0, non ?

Oui évidemment...

Citation:

Envoyé par Rukia-chan

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...

Citation:

Envoyé par 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

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...
08/12/2007, 11h50
fremen167

Citation:

Envoyé par Sve@r

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.
10/12/2007, 11h08
pseudocode

Citation:

Envoyé par Sve@r

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.
10/12/2007, 11h52
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 ! ;)
10/12/2007, 13h34
Rakken

Une boucle est une boucle, point barre.
Qu'on l'écrive avec un for, ou avec un while, ou, pourquoi pas, avec un goto, l'idée est toujours la même et ce qu'on peut faire avec une boucle, on peut le faire avec toute les boucles.
Bref, si tu commences la prog, il peut etre interessant de ne pas débuter direct avec ce genre d'exercice mais de passer par des choses plus simples, pour connaitre et apprendre a manipuler les mots clefs du langage, maitriser les concept mis en oeuvre dans ton algo.

Pour afficher les nombres de 1 à 1000, comment ferait-tu ? Quelle boucle ?
Un peu plus complexe (plusieurs boucles), mais toujours facile, un prog qui affiche les valeurs telle que x + y = z, avec z de un a 1000 et x et y positif.
Construit ton algo petit a petit et ca ira tout seul.
Avec ca, tu as déjà la base du programe de Sve@r. La méthode qu'il a proposé est très facile a coder, et peut se faire optimiser de facon intuitive assez facilement.
Après, le codage intuitif a ses propres limites, et c'est là qu'interviennent les math.
Bref, dans ton cas, y a pas 36 solutions, genre : au boulot ^_^

J'ai essayé de faire le maximum que j'ai put... je bloque sur la formule...je ne comprend pas ce que représente m et n? pouvez vous me donné quelques conseils
Merci beaucoup :(:oops:

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
 
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
int main()
{
    int x, y, z;
    int m, n, k;
 
 
 
    for(;;)
    {
           if(m<n)
           {
                  k=m;
                  m=n;
                  n=k;
           }
           if(m==n)
           {
                   printf("la valeur du PGCD est : %ld",m);
 
           }
    m=m-n;
    }
 
    if(m==1)
    {
            for(x=0;x<90;x++)
            {
                             x=2*m*n;
                             for{y=x;y<1000;y++)
                             {
                              y=n*n-m*m
                             }
                             z=n*n+m*m;
            }
    }             
 
system("pause")
return 0;
}

10/12/2007, 17h15
fremen167

Citation:

Envoyé par luchio13579

J'ai essayé de faire le maximum que j'ai put... je bloque sur la formule...je ne comprend pas ce que représente m et n? pouvez vous me donné quelques conseils
Merci beaucoup :(:oops:

Si tu ne comprends pas la méthode "mathématique", pourquoi ne pas utiliser la méthode simple qu'on t'a proposé ? Tu n'as aucune chance d'arriver à coder un algo que tu ne comprends pas :roll:
10/12/2007, 17h19
pseudocode

Completement d'accord avec fremen167. Code un algo que tu comprends, sinon c'est peine perdue.

Prend la méthode naive: 2 boucles for() imbriquées, l'une pour faire varier "x" et l'autre pour faire varier "y". Ensuite tu ajoutes un test "si x^2+y^2=10000^2 alors afficher x et y".
11/12/2007, 06h58
PRomu@ld

Citation:

J'ai essayé de faire le maximum que j'ai put...

Oulà, tiens toi-en à du pseudo code ..., le C ça sera pour plus tard. ;)