Algorithmique impérative/PGCD

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ématiqueModifier

É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.

AideModifier

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

SolutionModifier

Algorithme pgcd

Fonction euclide( u : entier
                   v : entier ) : entier
Variables
  r : entier (* le reste d'une division entière *)
Début
  Tant que v <> 0 faire
    r := u mod v
    u := v
    v := r
  FTQ
  retourner u
Fin

Variables
  u,v : entier (* les deux entiers donnés par l'utilisateur *)
Début
  Écrire("Donner les deux nombres : ")
  Lire(u,v)
  (* Début question subsidiaire *)
  si u=0 et v=0 alors Écrire("Le PGCD n'existe pas")
  sinon début
    si u < 0 alors u := -u
    si v < 0 alors v := -v
    (* Fin Question subsidiaire *)
    Écrire(euclide(u,v))
  fin
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.