Devoir pratique n°9 : PGCD et PPCM, tri à bulles et PGCD d'un tableau

Exercice 1 : PGCD et PPCM (8 pts)

Pour deux entiers a et b strictement positifs (saisies contrôlées), PPCM(a, b) = a × b / PGCD(a, b).

• 1) Créer un programme Python et l'enregistrer sous le nom PgcdPpcm.py (1 pt).
• 2) Écrire la fonction PGCD(a, b) qui renvoie le PGCD de a et b par l'algorithme d'Euclide (2 pts).
• 3) Écrire la fonction PPCM(a, b) qui renvoie le PPCM de a et b en utilisant PGCD (2 pts).
• 4) Écrire le programme principal en Python qui lit a et b puis affiche leur PGCD et leur PPCM sous la forme de l'exemple (3 pts).

Exemple : pour a = 24 et b = 36, le programme affiche :

PGCD = 12
PPCM = 72

Exercice 2 : trier un tableau et chercher son PGCD (12 pts)

On veut lire un tableau T de n entiers strictement positifs (2 ≤ n ≤ 20, saisies contrôlées), le trier dans l'ordre croissant par la méthode du tri à bulles, l'afficher, puis afficher le PGCD de tous ses éléments, calculé avec la fonction PGCD de l'exercice 1 (recopiée dans ce programme) : PGCD(a, b, c) = PGCD(PGCD(a, b), c).

• 1) Créer un programme Python et l'enregistrer sous le nom TriPgcd.py (1 pt).
• 2) Écrire la procédure Remplir(T, n) qui lit les n éléments de T, chacun strictement positif (2 pts).
• 3) Écrire la procédure TriBulles(T, n) qui trie T dans l'ordre croissant : on parcourt le tableau en échangeant deux voisins mal rangés, et on recommence tant qu'un passage a fait au moins un échange (4 pts).
• 4) Écrire la fonction PgcdTableau(T, n) qui renvoie le PGCD de tous les éléments de T, en appelant PGCD (2 pts).
• 5) Écrire la procédure Afficher(T, n) qui affiche les éléments de T sur une ligne, séparés par un espace (1 pt).
• 6) Écrire le programme principal en Python qui lit n, remplit, trie et affiche T, puis affiche son PGCD (2 pts).

Exemple : pour n = 4 et les valeurs 36, 24, 60, 12, le programme affiche :

12 24 36 60
PGCD du tableau : 12