INFO LISTE 4 D'EXERCICES D'ALGORITHME Novembre 2011
Algorithme 4
Arithmétique
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. ( c-à-d q = int( A / B ) et r = A - B× int( A / 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
----------------------------------------------------
Réponse : Voici un algorithme possible.
VARIABLES
A EST_DU_TYPE NOMBRE
B EST_DU_TYPE NOMBRE
k EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
LIRE A
LIRE B
AFFICHER " A = "
AFFICHER A
AFFICHER " B = "
AFFICHER B
SI (A<B) ALORS
DEBUT_SI
AFFICHER* " A n'est pas divisible par B."
FIN_SI
k PREND_LA_VALEUR 0
TANT_QUE (A>B) FAIRE
DEBUT_TANT_QUE
A PREND_LA_VALEUR A-B
k PREND_LA_VALEUR k + 1
FIN_TANT_QUE
AFFICHER " Le reste r est : "
AFFICHER A
AFFICHER " Le quotient entier q est : "
AFFICHER k
FIN_ALGORITHME
-----------------------------------------------------------------------------------------
EXERCICE 2
Soit A et B deux entiers naturels non nuls.
On note D leur PGCD.
Ecrire un algorithme avec Algobox qui donne PGCD( A ; B ).
-------------------------------------------------------------
Réponse:
Voici un algorithme possible:
( avec Euclide: Le dernier reste non nul
donne le PGCD voir plus bas les explications)
VARIABLES
A EST_DU_TYPE NOMBRE
B EST_DU_TYPE NOMBRE
R EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
LIRE A
LIRE B
AFFICHER " A = "
AFFICHER A
AFFICHER " B = "
AFFICHER B
R PREND_LA_VALEUR A%B
TANT_QUE (R!=0) FAIRE
DEBUT_TANT_QUE
A PREND_LA_VALEUR B
B PREND_LA_VALEUR R
R PREND_LA_VALEUR A%B
FIN_TANT_QUE
AFFICHER " Le PGCD de A et B est :"
AFFICHER B
FIN_ALGORITHME
-----------------------------------------------------------
LE PRINCIPE DE 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 )
-----------------------------------------------------------------------------------
On peut aussi utiliser la division par soustraction successives.
L'idée de base est la suivante:
Soit A et B deux entiers naturels non tous les deux nuls.
PGCD(A ; 0 ) = A
• Si A = B alors PGCD(A ; B ) = A = B
• SI A > B alors PGCD( A ; B ) = PGCD( A - B ; B )
• SI A < B alors PGCD( A ; B ) = PGCD( A ; B - A )
--------------------------------------------------------------------------------