Portail informatique Année 2018 – 2019

CSC 3101 – Algorithmique et langage de programmation

Le but de cet exercice est d'écrire un programme permettant de calculer le plus grand commun diviseur (pgcd) de deux entiers. Créez un projet nommé pgcd contenant une classe Pgcd, elle-même contenant une méthode main. Affichez les arguments de votre programme après avoir spécifié que ses paramètres sont 243 576. Modifiez votre programme de façon à vérifier que le nombre d'arguments est bien égal à 2. Si ce n'est pas le cas, votre programme doit afficher un message d'erreur et quitter à l'aide de la méthode System.exit(n), où n est le code de retour de votre programme. Si vous vous souvenez de votre cours d'introduction aux systèmes, vous devriez vous rappeler que toute valeur différente de 0 signifie que votre programme quitte avec une erreur. Vérifiez que votre programme se comporte correctement en modifiant les paramètres. Après vos tests, pensez à rétablir les arguments 243 et 576. Les arguments sont donnés sous la forme de chaînes de caractères. Il faut donc les convertir en entier avant de pouvoir calculer leur plus grand commun diviseur. Pour cela, définissez deux variables entières nommées p et q, et utilisez Integer.parseInt(uneChaine) pour convertir la chaîne de caractères uneChaine en entier. Affichez les valeurs de p et q. Un algorithme calculant le plus grand commun diviseur peut reposer sur la propriété suivante :
  • si p=0, alors pgcd(p ,q) = q,
  • si q=0, alors pgcd(p ,q) = p,
  • si p>q, alors pgcd(p ,q) = pgcd(p-q, q),
  • sinon: pgcd(p, q) = pgcd(p, q-p).
Mettez en œuvre un algorithme itératif (par opposition à récursif) utilisant cette propriété pour calculer le plus grand commun diviseur de p et q. Pour cela, utilisez une boucle while. Si vous obtenez pgcd(243, 576) = 9, vous avez gagné, bravo !