Algorithmique impérative/PGCD

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche
Algorithmique impérative
PyQt
Sommaire
Théorie de l'algorithmique impérative
  1. Qu'est ce qu'un algorithme impératif Fait à environ 50 %
  2. Les types, les opérateurs et les expressions Fait à environ 50 %
  3. Les constantes, les variables Fait à environ 50 %
  4. Les instructions, les blocs d'instructions Fait à environ 50 %
  5. L'assignation Fait à environ 50 %
  6. Les exécutions conditionnelles Fait à environ 50 %
  7. Les structures itératives Fait à environ 50 %
  8. Les tableaux Fait à environ 50 %
  9. Les procédures et les fonctions Ébauche
  10. Le type enregistrement Fait à environ 50 %
  11. L'algorithme au final : vue d'ensemble En cours
  12. Exercices En cours
Outils de travail
Problèmes posés, analysés, résolus et commentés
Annexes
Modifier ce modèle ce sommaire

Problèmatique[modifier | modifier le wikicode]

Écrire un algorithme donnant le Plus Grand Commun Diviseur (PGCD) de deux nombres donnés par l'utilisateur. On supposera que l'utilisateur ne donne que des entiers strictement supérieurs à zéro.

Il faudra écrire une fonction, prenant en entrée deux entiers strictement positifs et renvoyant leur PGCD. L'algorithme principal y fera appel.

Question subsidiaire : on considérera que l'utilisateur peut entrer n'importe quels entiers. Tenez-en compte pour que l'algorithme ne commette pas d'erreur et qu'il informe l'utilisateur.

Aide[modifier | modifier le wikicode]

Il faut avoir étudié ce problème d'algèbre pour avoir la solution. Elle consiste à appliquer l'algorithme d'Euclide.

Solution[modifier | modifier le wikicode]

 1 Algorithme pgcd
 2 
 3 Fonction euclide( u : entier
 4                    v : entier ) : entier
 5 Variables
 6   r : entier (* le reste d'une division entière *)
 7 Début
 8   Tant que v <> 0 faire
 9     r := u mod v
10     u := v
11     v := r
12   FTQ
13   retourner u
14 Fin
15 
16 Variables
17   u,v : entier (* les deux entiers donnés par l'utilisateur *)
18 Début
19   Écrire("Donner les deux nombres : ")
20   Lire(u,v)
21   (* Début question subsidiaire *)
22   si u=0 et v=0 alors Écrire("Le PGCD n'existe pas")
23   sinon début
24     si u < 0 alors u := -u
25     si v < 0 alors v := -v
26     (* Fin Question subsidiaire *)
27     Écrire(euclide(u,v))
28   fin
29 Fin

Pas vraiment de difficulté pour l'algorithme principal. La difficulté étant la fonction implémentant l'algorithme d'Euclide. Le jeu d'assignation à répéter jusqu'à obtenir un reste nul est difficile à visualiser.

Question subsidiaire : il y a trois événements à contrôler :

  • Le cas où u=v=0 et où le PGCD n'existe pas et il faut arrêter le programme (ligne 22)
  • Le cas où u ou v (ou les deux) est négatif est il faut prendre son opposé (lignes 24 et 25)

Pour la solution sans la question subsidiaire : ôter les lignes 21 à 26 et la 28 de la solution proposée.