Forum de mathématiques - Bibm@th.net

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 101

[AlgoBox] PGCD par l'axiome d'Euclide, puis PPCM

Bonjour,

Calcul du PGCD par divisions successives comme on le fait en 3e.

VARIABLES
2       a EST_DU_TYPE NOMBRE
3       b EST_DU_TYPE NOMBRE
4       c EST_DU_TYPE NOMBRE
5       d EST_DU_TYPE NOMBRE
6       pgcd EST_DU_TYPE NOMBRE
7       e EST_DU_TYPE NOMBRE
8     DEBUT_ALGORITHME
9       AFFICHER "Calcul du PGCD de 2 nombres "
10      AFFICHER " - Algorithme d'Euclide -"
11      AFFICHER " "
12      AFFICHER "Entrer le 1er nombre entier : "
13      LIRE a
14      c PREND_LA_VALEUR a
15      AFFICHER a
16      AFFICHER "Entrer le 2e nombre entier : "
17      LIRE b
18      AFFICHER b
19      d PREND_LA_VALEUR b
20      AFFICHER " "
21      TANT_QUE (d>0) FAIRE
22        DEBUT_TANT_QUE
23        e PREND_LA_VALEUR c%d
24        c PREND_LA_VALEUR d
25        d PREND_LA_VALEUR e
26        FIN_TANT_QUE
27      pgcd PREND_LA_VALEUR c
28      AFFICHER " "
29      SI (pgcd==1) ALORS
30        DEBUT_SI
31        AFFICHER "Les nombres "
32        AFFICHER a
33        AFFICHER " et "
34        AFFICHER b
35        AFFICHER " sont premiers entre eux."
36        AFFICHER " "
37        FIN_SI
38        SINON
39          DEBUT_SINON
40          AFFICHER "Le PGCD de "
41          AFFICHER a
42          AFFICHER " et "
43          AFFICHER b
44          AFFICHER " est "
45          AFFICHER pgcd
46          AFFICHER " "
47          FIN_SINON
48    FIN_ALGORITHME

Résultats :
***Algorithme lancé***
Calcul du PGCD de 2 nombres
- Algorithme d'Euclide -

Entrer le 1er nombre entier : 468
Entrer le 2e nombre entier  : 864

Le PGCD de 468 et 864 est 36

***Algorithme terminé***
 

PPCM par calcul préalable du PGCD

VARIABLES
2       a EST_DU_TYPE NOMBRE
3       b EST_DU_TYPE NOMBRE
4       c EST_DU_TYPE NOMBRE
5       d EST_DU_TYPE NOMBRE
6       pgcd EST_DU_TYPE NOMBRE
7       e EST_DU_TYPE NOMBRE
8     DEBUT_ALGORITHME
9       AFFICHER "Calcul du PPCM de 2 nombres "
10      AFFICHER " "
11      AFFICHER "Entrer le 1er nombre entier : "
12      LIRE a
13      c PREND_LA_VALEUR a
14      AFFICHER a
15      AFFICHER "Entrer le 2e nombre entier : "
16      LIRE b
17      AFFICHER b
18      d PREND_LA_VALEUR b
19      AFFICHER " "
20      TANT_QUE (d>0) FAIRE
21        DEBUT_TANT_QUE
22        e PREND_LA_VALEUR c%d
23        c PREND_LA_VALEUR d
24        d PREND_LA_VALEUR e
25        FIN_TANT_QUE
26      pgcd PREND_LA_VALEUR c
27      AFFICHER "Le PPCM de "
28      AFFICHER a
29      AFFICHER " et "
30      AFFICHER b
31      AFFICHER " est "
32      e PREND_LA_VALEUR a*b/pgcd
33      AFFICHER e
34      AFFICHER " "
35    FIN_ALGORITHME

Résultats :
***Algorithme lancé***
Calcul du PPCM de 2 nombres

Entrer le 1er nombre entier : 72
Entrer le 2e nombre entier  : 84

Le PPCM de 72 et 84 est 504
***Algorithme terminé***

Je garde les nombres en double pour pouvoir afficher "proprement" le résultat final...

@+

---

Arx Tarpeia Capitoli proxima...

Credo

Invité

Re : [AlgoBox] PGCD par l'axiome d'Euclide, puis PPCM

Bonjour, puis-je avoir l'exemple de l'écriture d'un algorithme de PPCM?, Merci

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 101

Re : [AlgoBox] PGCD par l'axiome d'Euclide, puis PPCM

Bonjour,

Tu veux un algo de calcul du PPCM seul sans passer par le PGCD ? Combien de nombres ?
Sinon,ci-dessus le programme Algobox utilise 2 nombres (je peux le récrire en Python : le PGCD, existe à l'état natif, plus besoin d'utiliser l'axiome d'Euclide).

Soient deux nombres a et b.
L'algorithme est basé sur cette propriété mathématique :
        PGCD(a,b) * PPCM(a,b) = a * b i)
Donc si je connais le PGCD, le $PPCM =\dfrac{a\times b}{PGCD}$
Autres exemples de calcul :
PGCD(84,98)=14
Donc $PPCM(84,98)=\dfrac{84\times 98}{14}=\dfrac{8232}{14}=588$

PGCD(252,294)=42
Donc $PPCM(252,294)=\dfrac{252\times 294}{42}=\dfrac{74088}{42}=1764$

@+

---

Arx Tarpeia Capitoli proxima...