Discussion :

[Onelove]

bonjour, j'ai un algo qui calcul le pgcd de deux nombres n1 et n2
Je dois prouver cette algo mais je ne sais pas vraiment comment le faire. Je l'ai fais tourner pour les première valeurs( n1 = 1 et n2 =2) mais je ne sais pas comment le prouver pour n valeurs.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
FonctionPGCD(T1,T2 :tableau) :entier
    pgcd, p1, p2 :entier
      Début
           pgcd←1; p1←1; p2←1;
 
    Tant Que(p1≤Taille1) et (p2≤taille2)Répéter
        Si T1[p1,1]=T2[p2,1]
           Alors
           m←min(T1[p1,2],T2[p2,2])
           pgcd←pgcd * [T1[p1,1]]^m
           p1←p1 + 1
           p2←p2 + 1
 
       Sinon Si T1[p1,1] < T2[p2,1]
          Alors p1←p1+1
       Sinon p2←p2+1
      Fin Si
    Fin Si
  Fin Tant Que
Retour
pgcd
Fin

[TiranusKBX]

Personnellement je pencherais plus pour

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
FonctionPGCD(x1,x2) :entier
    calc, p1, p2 :entier
    calc = x1; p1 = x1; p2 = x2;
    si x2 plus grand que calc :
        calc = x2;
 
    Tant Que p1 est diférent de p2 Répéter
        Si x1 modulo calc égale 0
           p1 = calc;
        Si x2 modulo calc égale 0
           p2 = calc;
        calc = calc - 1;
    Fin Tant Que
    Retour p1
Fin

cela devrait marcher mais je n'ai pas testé

[Onelove]

Merci pour ta réponse, mais le premier algo est trèèèèèèès mal optimisé et il m'est imposé, et je sais pas vraiment comment on "prouve" un algo, enfin le démontrer. En bref prouvez qu'il calcul le pgcd

[TiranusKBX]

pour prouver le fonctionnement d'un algorithme l'on doit démontrer que pour toutes valeur x et y la fonction
retourne bien la même chose que ce que l'on utilise habituellement en maths en gros tu doit convertir l'algo en expression et comparer
avec les démonstration mathématiques habituelle, en gros que des maths mon pauvre

[Onelove]

Okay, merci

[TiranusKBX]

mais de rien