Les algorithmes arithmétiques
1) Calcul du PGCD :
Activité1 :
Pour calculer le PGCD de deux entiers positifs a et b on utilise la méthode de la division
euclidienne exprimée comme suivant :
a si b=0
PGCD(a,b) =
PGCD(b,a mod b) sinon
a) Calculer manuellement le PGCD(15,27) en utilisant la méthode donnée ci-dessus :
b) Ecrire de deux façons l’algorithme d’un module intitulé Pgcd_Euc qui permet de
calculer le PGCD de deux entiers positifs a et b en utilisant la méthode de la division
euclidienne
Activité2 :
Pour calculer le PGCD de deux entiers positifs a et b on utilise la méthode de la différence
exprimée comme suivant :
a ( ou b) si a=b
PGCD(a,b) = PGCD(a-b,b) si a>b
PGCD(a,b-a) sinon
a) Calculer manuellement le PGCD(130,40) en utilisant la méthode donnée ci-dessus
b) Ecrire de deux façons l’algorithme d’un module intitulé Pgcd_Dif qui permet de
calculer le PGCD de deux entiers positifs a et b en utilisant la méthode de la différence
Application :
a) Ecrire l’algorithme d’un module intitulé Pgcd_3 qui permet de calculer le PGCD de
trois entiers positifs a, b et c.
b) Ecrire l’algorithme d’un module intitulé PPCM qui permet de calculer le
PPCM de deux entiers positifs a et b
2) Calcul de Anp :
Activité1 :
Ecrire dans chaque cas ci-dessous l’algorithme d’un module qui calcule le Anp de deux
entiers n et p ( 1≤p≤n)
a. Anp = n(n-1)(n-2)….........*(n-p+1)
b. Anp = n !/ (n-p) !
3) Calcul de Cnp :
Activité1 :
Ecrire dans chaque cas ci-dessous l’algorithme d’un module qui calcule le Cnp de deux
entiers n et p ( 0≤p≤n)
p
a. Cnp = An / p !
b. Cnp = n !/ (p !(n-p) !)
c.
{ {
p
cn =
1 si ( n= p ) ou ( p=0)
p−1
c n−1 p
+c n−1 sinon }
4) Quelques règles de divisibilité :
4-1) Définitions :
Un entier n est divisible par un entier m, si n mod m =0
Une règle de divisibilité est une suite d’opérations simples qui permet de
reconnaître rapidement si un entier n est divisible par un entier m sans effectuer la
division. Ces règles sont généralement applicables pour les grands nombres
4-2) Divisibilité par 3 :
Règle de divisibilité : un entier n est divisible par 3, si la somme des chiffres qui
le composent est divisible par 3
Application : écrire l’algorithme du module intitulé Div_3 qui permet de vérifier si un entier
positif n composé au moins de 8 chiffres est divisible par 3
4-3) Divisibilité par 4 :
Règle de divisibilité : un entier n est divisible par 4, si le nombre composé de deux
derniers chiffres est divisible par 4
Application : écrire l’algorithme du module intitulé Div_4 qui permet de vérifier si
un entier positif n composé au moins de 8 chiffres est divisible par 4
4-5) Divisibilité par 7 :
Règle de divisibilité : Un nombre N est divisible par 7 si, en soustrayant et en
additionnant alternativement chaque tranche de trois chiffres en partant de la
droite, le résultat est divisible par 7
Exemples
1) L’entier 65465802 n’est pas divisible par 7 car 802-465+65 = 411 n’est pas divisible par
7
2) L’entier 67456802 est divisible par 7 car 802-456+67=413 est divisible par 7
Application : écrire l’algorithme du module intitulé Div_7 qui permet de vérifier si
un n composé au moins de 8 chiffres est divisible par 7
2) Conversions entre les bases de numération :
5-1) Définition:
Un système de numération est une méthode de comptage fondée sur une base de
numération qui est un entier supérieur ou égal à 2. Un nombre écrit en une base b est un
nombre formé des chiffres allant de 0 à b-1. (Exemples : un nombre écrit en base 2 est un
nombre formé des chiffres allant de 0 à 1, un nombre écrit en base 8 est un nombre formé
des chiffres allant de 0 à 7, …)
5-2) Conversion d’un nombre décimal en une base b :
Activité1 :
Ecrire de deux façons le module qui permet de convertir un nombre décimal strictement
positif X en binaire
Activité2 :
Ecrire de deux façons le module qui permet de convertir un nombre décimal strictement
positif X en une b donnée (b ≥ 2)
5-3) Conversion d’un nombre d’une base b en base décimale :
Activité1 :
Ecrire de deux façons le module qui permet de convertir un nombre octal X déjà saisie sous la forme
d’une chaîne des caractères en base décimale
Activité2 :
Ecrire l’algorithme modulaire qui permet de saisir un entier X en une base b ( b ≥ 2 et
≠ 10) et de le convertir en base décimale
5-4) Conversion d’un nombre hexadécimal en binaire :
Activité :
Ecrire l’algorithme du module qui permet de convertir un nombre hexadécimal X en
base binaire en respectant la démarche utilisée dans l’exemple ci-dessous :
Exemple :
Prenons X = 29AF, nous allons procéder comme suivant :
2 9 A F
0010 1001 1010 1111
Chaque chiffre de X sera représenté sur 4 bits.
(29AF)16 = (10100110101111)2 le nombre binaire obtenu est le résultat de la concaténation
de 4 nombres binaires ci-dessus ( les zéros à l’extrême gauche sont non significatifs)
5-5) Conversion d’un nombre binaire en octal :
Activité :
Ecrire l’algorithme du module qui permet de convertir un nombre binaire X en base
octale en respectant la démarche utilisée dans l’exemple ci-dessous :
Exemple :
Prenons X = 1110101, nous allons procéder comme suivant :
001 110 101
1 6 5
Ajouter autant des zéros à gauche du nombre initial X pour que sa longueur sera multiple de
3, convertir chaque tranche de 3 bits en son équivalent décimal ( 5= 1*20+0*21+1*22), le
nombre résultat de la concaténation des chiffres décimaux obtenus est le nombre octal à
chercher.
(1110101)2 = (165)8
