Exercice corrigé Ancien programme

programmer le calcul du pgcd de deux entiers à la calculatrice

On propose le programme suivant, décrit en langage naturel :

R, a et b sont trois nombres

Entrer la valeur de a

Entrer la valeur de b

R vaut 1.

Tant que

– R prend la valeur a − b × (partie entière de a /b)

– b prend la valeur R

Afficher le message “Le PGCD cherché vaut”

Afficher la valeur de a

1. Pourquoi est-il indispensable d'initialiser la valeur de R ( par exemple, ici :
R = 1) ?

2. Expliquer pourquoi on a la formule R = ab ×

Cette formule permet de réaliser le programme, même sur des logiciels ou des calculatrices qui ne proposent pas la fonction “reste de la division euclidienne”.

3. Expliquer en détail ce qui se passe lors de la première boucle si a b.

4. Pourquoi fait-on afficher la valeur de a comme étant le PGCD, et non pas R ?

5. Réaliser ce programme sur votre calculatrice, et déterminer :

a. le PGCD de 12 et de 9 

b. le PGCD de 68 et de 48 

c. le PGCD de 347 et de 222.

1. Afin que l'algorithme ne s'arrête pas, il faut initialiser la valeur de R pour être sûr que soit non nul au démarrage de la boucle.

2. La division euclidienne de a par b s'écrit : il existe un unique couple d'entiers q et R, avec tel que soit. De plus, q est le quotient de a par b, c'est-à-dire le plus grand entier inférieur ou égal à , donc q est la partie entière de . Finalement .

3. Si, donc . D'où à la première étape de la boucle. Puis on remplace a par b, et b par, ce qui a pour effet d'échanger a et b. Et comme, la boucle reprend ensuite, avec cette fois .

4. Le programme s'arrête lorsque , ce qui n'est pas le PGCD, donc il faut rechercher le dernier reste non nul.

Au tour de boucle précédent, R prend la valeur
c'est à partir de là que R vaut 0. a prend la valeur b b prend la valeur R, c'est-à-dire 0.

Il faut regarder le tour encore précédent :

R prend la valeur c'est le dernier reste non nul cherché a prend la valeur b b prend la valeur R, c'est le PGCD.

Ainsi, lorsqu'au dernier tour, a prend la valeur b, c'est bien le PGCD.

5. a. Le PGCD de 12 et de 9 vaut 3. b. Le PGCD de 68 et de 48 vaut 4 . c. Le PGCD de 347 et de 222 vaut 1.

Accéder à tous les contenus
dès 6,79€/mois

  • Les dernières annales corrigées et expliquées
  • Des fiches de cours et cours vidéo/audio
  • Des conseils et méthodes pour réussir ses examens
  • Pas de publicités
S'abonner