Prouver un algorithme

Version imprimable

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:

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

Personnellement je pencherais plus pour

Code:

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é

07/09/2014, 02h13
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
07/09/2014, 02h26
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 :aie:
07/09/2014, 05h42
Onelove

:aie::aie::aie::aie::aie:

Okay, merci :D
07/09/2014, 08h55
TiranusKBX

mais de rien :mrgreen: