LISTE 4 D'EXERCICES D'ALGORITHME Novembre 2011
Algorithme 4
Arithmétique Division PGCD
EXERCICE 1. DIVISION PAR SOUSTRACTIONS SUCCESSIVES
Soit A et B deux entiers naturels non nuls avec A > B.
Ecrire, avec Algobox, un algorithme qui permet de diviser A par B
par des soustractions successives.
Il faudra qu'à l'écran apparaisse le quotient q et le reste r de la division
entière de A par B.
AIDE : • Tant que A ≥ B mettre A - B dans A
et ajouter 1 au compteur.
• FIN_ TANT _QUE
Faire afficher "le quotient entier q est = " compteur
et " le reste r = " A
( on rappelle que q = int( A / B ) et r = A - B × int( A / B ) mais on ne l'utilise pas ici )
-----------------------------------------------------------------------------------------
EXERCICE 2
Soit A et B deux entiers naturels non tous les deux nuls.
On note D leur PGCD.
Ecrire un algorithme avec Algobox qui donne PGCD( A ; B ).
On peut utiliser l'algorithme d'EUCLIDE :
CET ALGORITHME D'EUCLIDE EST:
• SI A = B ALORS A = B × 1 + 0
PGCD( A , B ) = PGCD( B , 0 ) = B = A
Les diviseurs communs de A et B sont ceux communs de B et 0.
Le plus grand est donc B .
• SI A > B ALORS ON DIVISE A PAR B.
Il existe un unique entier naturel Q1 et
un unique entier naturel R1 tels que
A = B × Q1 +R1 AVEC 0 ≤ R1 < B
On a: PGCD( A , B ) = PGCD( B , R1 )
Les diviseurs commun de A et B sont les diviceurs communs de B et R1 .
• • Si R1 = 0 alors PGCD( A , B ) = PGCD( B , 0 ) = B
• • Si 0 < R1 < B alors on recommence en divisant B par R1.
Il existe un unique entier naturel Q2 et
un unique entier naturel R2 tels que
B = R1 × Q2 + R2 AVEC 0 ≤ R2 < R1
On a : PGCD( A , B ) = PGCD( B , R1 ) = PGCD( R1 , R2 )
• • Si R2 = 0
alors PGCD( A , B ) = PGCD( B , R1 ) = PGCD( R1 , R2 ) = PGCD( R1 , 0 ) = R1
• • Si 0 < R2 < R1 alors on recommence en divisant R1 par R2.
Le processus continue ainsi ......
Comme B , R1 , R2 , .... constitue les termes d'une suite décroissante
strictement d'entiers naturels le processus s'arrête à un dernier reste nul.
La dernière etape comporte donc un reste nul . R n+1 =0 .
On a Rn - 1 = Rn × Qn+1 + 0
PGCD( A , B ) = PGCD( B , R1 ) = PGCD( R1 , R2 ) = .... = PGCD( R n , R n+1 ) = PGCD( R n , 0 ) = Rn
Le dernier reste non nul est bien PGCD(A , B )
--------------------------------------------------------------------------------