60 .pdf


À propos / Télécharger Aperçu
Nom original: 60.pdf

Ce document au format PDF 1.4 a été envoyé sur fichier-pdf.fr le 03/04/2015 à 02:48, depuis l'adresse IP 105.104.x.x. La présente page de téléchargement du fichier a été vue 891 fois.
Taille du document: 333 Ko (14 pages).
Confidentialité: fichier public


Aperçu du document


Les Algorithmes Arithmétiques 

Classe : 3 ième  SI 

Chapitre VI 

Les Algorithmes Arithmétiques 
I. Introduction 
Dans ce chapitre, on présentera les algorithmes arithmétiques les plus connus : calculs du PGCD e 
du PPCM, recherche des nombres premiers et décomposition en produits des facteurs premiers, la 
conversion d’un nombre en base 10 vers le binaire et en hexadécimal. A la fin, on développera le 
problème qui convertit un nombre en base b1 en son équivalent en base b2. 

II. Le calcul du PGCD 
1. Définition 
PGCD : Plus Grand Commun Diviseur 
Le PGCD de deux entiers m et n noté PGCD(m,n) est le grand entier permettant de diviser m et n. 
2. Application 
Analyser puis déduire l’algorithme d’une fonction qui permet de déterminer le PGCD de deux entiers 
m et n selon les deux méthodes : différence et Euclide. 
Méthode de différence 

a. Principe 
Le principe de cette méthode est : 
Chercher le différence de deux valeurs et la ranger dans la valeur la plus grande jusqu’à obtenir la 
même valeur.
·

Est ce que le nombre de répétitions est connu ?

·

Au moins égale combien ? 

b. Exemples 

c. Spécification de la fonction PGCD_Diff  
Résultat=PGCD_diff 
Traitement = 
En cas d’égalité le PGCD_Diff=m 
Tant que M <> N chercher la valeur la plus grande 
Cette valeur reçoit la différence 
Paramètres da la fonction : m et n
Mourad Bahri  & Naima Bayoudh & Leila Ben Njima  Ikram Nasrallah & Med Ali Farhat 

Page 1 

Les Algorithmes Arithmétiques 

Classe : 3 ième  SI 

d. Algorithme 
0)  Début fonction PGCD_Diff (m,n :entier) :entier 
1)  Tant que m <> n Faire 
Si m > n Alors m ßm­n 
Sinon n ß n­m 
Finsi 
Fin tant que 
2)  PGCD_Diffßm 
3)  Fin PGCD_Diff 
Méthode d’Euclide 

a. Principe 
Le principe de cette méthode est : 
Chercher le différence de deux valeurs et la ranger dans la valeur la plus grande jusqu’à obtenir la 
même valeur.
·

Est ce que le nombre de répétitions est connu ?

·

Au moins égale combien ? 

b. Exemples  

c. Spécification de la fonction PGCD_Euc 
Résultat=PGCD_Euc 
Traitement= 
En cas d’égalité le PGCD_Euc=m 
Tant que (m <> n) et (n <> 0) 
m prend la valeur de n ; n prend le reste de la division de m et n 
Paramètres da la fonction : m et n 
d. Algorithme 
0)  Début fonction PGCD_Euc (m,n :entier) :entier 
1)  Tant que (m <> n) et (n <>0) Faire 
auxßm ; m ßn ; n ßn mod aux 
Fin tant que 
2)  PGCD_Eucßm 
3)  Fin PGCD_Euc
Mourad Bahri  & Naima Bayoudh & Leila Ben Njima  Ikram Nasrallah & Med Ali Farhat 

Page 2 

Classe : 3 ième  SI 

Les Algorithmes Arithmétiques 

e. TDO 
Objet 

Type Nature  Rôle 

aux 

Entier 

Variable auxiliaire 

3. Exercice 
Ecrire un programme pascal qui calcule le PGCD de trois entiers strictement positifs a,b et c. 
N.B. PGCD(a,b,c)=PGCD(PGCD(a,b),c) 

II. Le calcul du PPCM 
1. Définition 
PPCM : Plus Petit Commun Multiple 
Le PPCM de deux entiers m et n noté PPCM(m,n) est le plus petit entier multiple à la fois de m et n. 
2. Application 
Analyser puis déduire l’algorithme d’une fonction qui permet de déterminer le PPCM de deux entiers 
m et n. 

a. Principe 
Le principe de recherche de PPCM est :
·

Chercher le plus multiple de m qui est aussi multiple de n

·

est ce que le nombre de répétitions est connu et au moins égale combien ? 

b. Exemples 

c. Spécification de la fonction PPCM 
Résultat=PPCM 
Traitement= 
Afin de minimiser les itérations il utile de chercher le maximum de m et n 
Le PPCM commence à 0 , on répète l’ajout de m au PPCM jusqu’à avoir PPCM multiple de n (PPCM 
mod n = 0) 
Paramètres da la fonction : m et n
Mourad Bahri  & Naima Bayoudh & Leila Ben Njima  Ikram Nasrallah & Med Ali Farhat 

Page 3 

Classe : 3 ième  SI 

Les Algorithmes Arithmétiques 

d. Algorithme 
0)  Début fonction PPCM (m,n :entier) :entier 
1)  PPCM ß 0 
Répéter 
PPCMßPPCM+m 
Jusqu’à PPCM mod n =0 
2)  Fin PPCM3. Exercice 
Ecrire un programme pascal qui cherche le PPCM de deux entiers m et n en utilisant la formule 
suivante : 
PPCM(m,n)=m*n DIV PGCD(m,n) 

III. Les nombres premiers 
1. Définition 
Un nombre > 1 est dit premier s’il est divisible seulement par 1 et par lui même. 
2. Application 
Analyser puis déduire l’algorithme d’une fonction qui permet vérifier si un entier > 1 est premier ou 
non. 

a. Principe 
pour tester si un nombre > 1 est premier, il suffit de :
·

Chercher le nombre de ses diviseurs

·

Tester si ce nombre=2b. Exemples  

n=10 
les diviseurs de 10, autres que 1 et 10, sont compris entre 2 et 5 (10 div 2) : 
à utilisation de la boucle Pour 
nb commence à 2 
si on trouve un diviseur le nb augmente de 1 

c. Algorithme 
0)  Début premier(n :entier) :booléen 
1)  nb ß 2 
Pour i de 2 à n div 2 faire 
Si n MOD i = 0 Alors nbßnb+1 
Finsi 
Fin pour 
2)  premier ßFaux 
Si  nb = 2 Alors premier ßVrai 
Finsi 
3)  Fin premier 

d. TDO 
Objet 

Type Nature  Rôle 

nb 

Entier 

Nombre de diviseurs de n 



Entier 

Compteur

Mourad Bahri  & Naima Bayoudh & Leila Ben Njima  Ikram Nasrallah & Med Ali Farhat 

Page 4 

Les Algorithmes Arithmétiques 

Classe : 3 ième  SI 

3. Exercices 
1) Ecrire un programme pascal qui détermine si deux entiers non nuls sont premiers entre eux en 
suivant la propriété suivante :; deux entiers non nuls sont premiers entre eux si et seulement si leurs 
PGCD=1 

2) Un nombre est dit primaire s’il est un nombre premier ou s’il un nombre qui a un seul diviseur 
premier autre que 1. 
Un nombre est dit premier s’il est divisible par 1 et par lui même seulement. 
Soit le problème Primaire qui lit un nombre strictement positif et vérifie s’il est primaire. 
Pour vérifier que le nombre est primaire il suffit de vérifier : 
­  Qu’il  est premier . 
­  Ou  s’il possède un seul diviseur premier. 

NB :  
Si x est non premier alors chercher tous diviseurs de x (autre que 1 et x) et les mettre dans un 
tableau  et 
vérifier si parmi ses diviseurs existe un seul nombre premier . 

Exemples :  

Travail à Faire 

1)  Décomposer le problème en modules ; 
2)  Analyser le problème principal et chacun des modules envisagés. 
3)  En déduire les algorithmes relatifs aux modules et au programme principal. 
IV. Décomposition en facteurs premiers 
1. Définition 
Décomposer un entier en facteurs premiers consiste à écrire cet entier sous la forme d’un produit de 
ces diviseurs premiers. 
2. Application 
Analyser puis déduire l’algorithme qui  permet de chercher et d’afficher la décomposition en produit 
de ces diviseurs premiers.
Mourad Bahri  & Naima Bayoudh & Leila Ben Njima  Ikram Nasrallah & Med Ali Farhat 

Page 5 

Les Algorithmes Arithmétiques 

Classe : 3 ième  SI 

a. Principe 
Pour chercher la décomposition d’un entier en produit de facteurs premiers on peut suivre la 
méthode suivante :
·

tant que le nombre est divisible par 2, le remplacer par le quotient

·

refaire le même travail avec 3,4, ….

·

jusqu’à avoir la valeur 1 

b. Exemples 

c. Décomposition modulaire 

d. Analyse de la procédure facteurs  
Résultat = un tableau F qui contiendra les facteurs ; N : nombre des facteurs 
Traitement = 
Répéter si le nombre x est divisible par i alors on augmente le nombre des facteurs (n) et on met le i 
dans le tableau F sinon i s’incrémente Jusqu’à n devient = 1. 
Paramètres de la procédure 
tableau F, n : nombre des facteurs qui passent par variable ; Le nombre x qu’on va le décomposer ne 
facteurs premiers. 

e. Algorithme de la procédure facteurs  
0)  Début procédure facteurs (var F :tab ; var n :entier ; x :entier) 
1)  nß0  , iß2 
Répéter 
si n mod i = 0 alors x ß x div i ; n ß n+1 ; F[n] ßi 
sinon i ß i+1 
Finsi 
Jusqu’à n= 1 
2)  Fin facteurs
Mourad Bahri  & Naima Bayoudh & Leila Ben Njima  Ikram Nasrallah & Med Ali Farhat 

Page 6 

Les Algorithmes Arithmétiques 

Classe : 3 ième  SI 

f. TDO 
Objet 

Type Nature  Rôle 



entier 

Compteur 

3. Exercice 
Un nombre est dit rigolos ou de SMITH s’il est un nombre dont la somme des chiffres est égale à la 
somme de tous les chiffres de ses facteurs premiers 

Exemples  

4 = 2 x 2   => Somme chiffres = 4 
22 = 2 x 11 => Somme chiffres = 4 
27 = 3 x 3 x 3 => Somme chiffres = 9 

Soit le problème SMITH qui lit un nombre N strictement positif et affiche s’il est un nombre de SMITH 
ou non. 
1)  Décomposer le problème SMITH en trois modules au moins. 
2)  Analyser le problème principal et ses modules et en déduire les algorithmes corresponds 

VI. La conversion entre bases de numération 
1. Définition 
Convertir un entier positif n dans une base b ( b >=2) consiste à chercher la représentation de n dans 
la base b. 
Cette représentation s’écrit sous la forme : 
N = anb n  + an­1b n­1  + an­2b n­2  + ... + a1b 1  + a0b 0 . 
Où    0 <= ak  <= b­1 
2. Application 1 
Analyser puis déduire l’algorithme qui  permet de convertir un nombre en base 10 en binaire. 

a. Principe 
pour convertir un nombre en base 10 vers la base 2 consiste à faire
·

des divisions successives par 2 en remplaçant à chaque fois le dividende par le quotient

·

prendre les restes en ordre inverse. 

b. exemple 
convertir 13 en base 10 en binaire

Mourad Bahri  & Naima Bayoudh & Leila Ben Njima  Ikram Nasrallah & Med Ali Farhat 

Page 7 

Classe : 3 ième  SI 

Les Algorithmes Arithmétiques 

3. Décomposition modulaire 

d. Analyse de la procédure Restes  
Résultat= un tableau R qui contiendra les restes des divisions; n : taille du tableau R 
Traitement= 
Répéter chercher le reste de la division de X par 2 ,  mettre le reste dans le tableau R Jusqu’à n 
devient =0. 
Paramètres de la procédure 
tableau R, n : taille du tableau qui passent par variable 
Le nombre x qu’on va le convertir en base 2. 

e. Algorithme de la procédure restes  
0)  Début procédure restes (var R :tab ; var n :entier ; x :entier) 
1)  nß0 
Répéter 
n ß n+1 
R[n] ß x Mod 2 
nßn div 2 
Jusqu’à n= 0 
2)  Fin restes 
3. application 2 
Analyser puis déduire l’algorithme qui  permet de convertir un nombre en base 10 en hexadécimal. 

a. Principe 
pour convertir un nombre en base 10  vers la base 16 consiste à faire 
des divisions successives par 16 en remplaçant à chaque fois le dividende par le quotient 
prendre les restes en ordre inverse tout en codant les restes compris entre 10 et 15 selon la 
manière suivante : 
Reste 

10  11  12  13  14  15 

Code en base 
16 











F

Mourad Bahri  & Naima Bayoudh & Leila Ben Njima  Ikram Nasrallah & Med Ali Farhat 

Page 8 

Les Algorithmes Arithmétiques 

Classe : 3 ième  SI 

b. exemple 
Convertir 152 en base 10 vers l’hexadécimal 

c. Décomposition modulaire 

d. Analyse de la procédure Restes  
Résultat= un tableau R qui contiendra les restes des divisions; N : taille du tableau R 
Traitement= 
Répéter chercher le reste de la division de X par 16 ,  mettre le reste dans le tableau R Jusqu’à n 
devient =0. 
Paramètres de la procédure 
tableau R, n : taille du tableau qui passent par variable 
Le nombre x qu’on va le convertir en base 16. 

e. Algorithme de la procédure restes  
0)  Début procédure restes (var R :tab ; var n :entier ; x :entier) 
1)  nß0 
Répéter 
n ß n+1 
R[n] ß x Mod 16 
nßn div 16 
Jusqu’à n= 0 
2)  Fin restes 

f. Analyse de la procédure afficher  
Résultat= afficher les éléments de tableau R de taille n 
Traitement= afficher les éléments de tableau R de taille n : utiliser boucle pour .. faire 
pour chaque élément de R , vérifier s’il est dans [0,9] alors l’afficher sinon affiche la lettre 
correspondante. 
Le code de 10 en base 16 est ‘A’ 
Ord(‘A’)=65 
On affiche le caractère dont le code = 65+10­10 à ‘A’ 
On affiche le caractère dont le code = 65+11­10 à ‘B’ …
Mourad Bahri  & Naima Bayoudh & Leila Ben Njima  Ikram Nasrallah & Med Ali Farhat 

Page 9 

Classe : 3 ième  SI 

Les Algorithmes Arithmétiques 

Paramètres de cette procédure 
tableau R, n : taille du tableau qui passent par valeur 

e. Algorithme de la procédure restes  
0)  Début procédure restes (R :tab ; n :entier ;) 
1)  Pour i de n à 1 Faire 
Si R[i] dans [1..9] Alors Ecrire(R[i]) 
Sinon Ecrire(chr(ord(‘A’)+R[i]­10) 
Finsi 
2)  Fin afficher 
4. Exercice 
Nous proposons de convertir un nombre binaire en octal (base 8) en suivant la méthode suivante : 
­  Extraire une partie de 3 bits. 
­  Convertir cette partie en octal en utilisant les puissances de 2. 
Répéter ces deux opérations pour toutes les parties du nombre binaire. 
La concaténation des déférents résultats donne le résultat en octal. 
On  ajoute si nécessaire des "0" à gauche du nombre binaire de façon à obtenir une longueur 
multiple de 3. 
Exemples : 
Soit à convertir le nombre 1101 
On suit la méthode suivante : 
La longueur de nombre n’est pas multiple de 3 : 
Ajouter des 0" à gauche de ce nombre de façon à obtenir une longueur multiple de 3 : 
à Le nombre devient 001101 










0*2  +0*2  +1*2  = 1 











1*2  +0*2  +1*2  = 5 

à Le nombre octal est 15 

VII. Problème 
1. Enoncé 
Écrire  un  programme  qui  réalise  la  conversion  d’un  nombre  écrit  en  base  b1  en  son  équivalent  en 
base b2. avec b1 et b2 sont deux entiers supérieurs à 1. 
2. Exemple 
Convertir (15)8  à  (….)2 
(15)8 à (…)10  à  (15)8=1*8 1 + 5*8 0 = (13)10 
(13)10=(1101)2
Mourad Bahri  & Naima Bayoudh & Leila Ben Njima  Ikram Nasrallah & Med Ali Farhat 

Page 10 

Classe : 3 ième  SI 

Les Algorithmes Arithmétiques 

3. Solution  

Principe 
1.  Vérifier que le nombre N est un nombre "valide" dans sa base (b1) : 
à Vérifier si chaque chiffre de N est "acceptable" pour   cette  base. 
2.  Si b1=10 alors La transformation en nouvelle base (b2) se fera par des divisions successives par 
b2. 
3.  Si b2=10 Alors la transformation en base 10 se fait par multiplications successives. 
4.   Sinon  : Ramener N dans la base 10 . 

Transformer le résultat dans b2 

Méthode 1 
Décomposition modulaire 

Algorithme du PP 
0) Début conversion 
1) Répéter 

Proc  Saisie_base(b1) 

Proc  Saisie_base( b2) 
Jusqu’à (b1 ≠ b2) 
2) Proc Saisie_Nombre(N, b1) 
3) Ecrire (N, " dans ", b1," = ", FN Calcul( N, b1, b2)," dans ",b2) 
4) Fin conversion 
Algorithme de la Procedure Saisie_base 
0) Procédure saisie_base (var b : entier) 
1) Répéter 
Ecrire ("introduire une base entre 2 et 16"),  Lire( b ) 
Jusqu’à  (b>1) 
2) Fin Saisie_base

Mourad Bahri  & Naima Bayoudh & Leila Ben Njima  Ikram Nasrallah & Med Ali Farhat 

Page 11 

Classe : 3 ième  SI 

Les Algorithmes Arithmétiques 

Algorithme de la Procédure Saisie_nombre 
0) Procédure Saisie_nombre(var N : Chaîne ; b1 : entier) 
1) Répéter 
écrire ("introduire un nombre dans base",b1), Lire(N) 
Testß  vrai 
Pour i de 1 à long(N) faire 
Si  b1  ≤ 10 alors convch(b1­1, ch) ; cßch[1] 
Si NON (N[i] dans ["0"..c]) alors Test ß faux 
Finsi 
Sinon c ß chr ( b1 + 54 ) 
Si NON (N[i] dans ["0".."9",'"A"..c]) alors Test ß  faux 
Fin si 
Fin Pour 
Jusqu’à  (test) et ( N ≠ "") 
2) Fin Saisie_nombre 
Algorithme de la fonction Calcul 
0) Fonction Calcul (N : chaîne ; b1,b2 : entier) : chaîne 
1) Si (b1 = 10) alors Calcul ß FN conv_10_b(N,b2) 
Sinon 
Si b2= 10 alors  Calcul ßFN conv_b_10(N,b1) 
Sinon  Calcul ß FN conv_10_b(FN conv_b_10(N,b1), b2) 
Fin si 
2) Fin Calcul 
Algorithme de la fonction conv_b_10 
0) Fonction Conv_b_10(N :chaîne;b1: entier) :chaîne 
1) Nr ß0 
Pour  i  de 1  à  long(N)  faire 
Si N[ i ] dans ["0".."9"] Alors  Valeur(N[i], x, e) 
Sinon  x ß ord(N[i]) ­ 55 
Fin si 
Nr ßNr + x* FN puissance (b1, long(N) – i ) 
Fin pour 
2) Convch(Nr,ch) ; 
3) Conv_b_10 ß ch 
4) Fin Conv_b_10

Mourad Bahri  & Naima Bayoudh & Leila Ben Njima  Ikram Nasrallah & Med Ali Farhat 

Page 12 

Classe : 3 ième  SI 

Les Algorithmes Arithmétiques 

Algorithme de la fonction conv_10_b 
0) Fonction Conv_10_b(N :chaîne ;b2: entier) :chaîne 
1) Valeur( N, Nd, e) 
2)  Ch ß "" 
Répéter 
R ß Nd mod  b2 
Si R dans [0..9]  Alors Convch ( R, Ch1) 
Ch  ß Ch1 + Ch 
Sinon  Ch  ß Chr(55+R) + Ch 
Fin Si 
Nd  ß Nd div b2 
Jusqu’à  (Nd = 0) 
3) Conv_10_b ß ch 
4) Fin Conv_10_b 
Algorithme de la Fonction Puissance 
0) Fonction Puissance (b,k : entier) : entier long 
1) P ß 1 
Pour  j  de  1  à  K  faire 
P ß P * b 
Fin pour 
2) Puissance ß P 
3) Fin puissance 
Méthode 2 

Décomposition modulaire 

{Programme Principal} 
0) Début conversion 
1) Ch ß "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" 
2)  répéter 
lire (N ) 
lire (b1) 
jusqu’à Verifie(N,b1) ; 
3) Lire (b2)
Mourad Bahri  & Naima Bayoudh & Leila Ben Njima  Ikram Nasrallah & Med Ali Farhat 

Page 13 

Les Algorithmes Arithmétiques 

Classe : 3 ième  SI 

4) Ecrire (N," en base ",b1, " = ", Base(Base10(N,b1),b2), " en base ",b2) 
5) Fin conversion 
Algorithme de la Fonction Verifie 

{Ch ß"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"} 
0) Fonction Verifie (N :chaîne,b1 :entier) : booléen 
1) test ß vrai 
Pour i de 1 à long(N) faire 
Si Pos(N[i], Ch) > b1 Alors testßfaux 
Finsi 
Finpour 
2) Verifie ß test 
3) Fin verifie 
{Transforme le nombre en base 10} 
0) Fonction Base10(N :chaine, b1 :entier) :entier 
1) b10 ß 0 
Pour i de 1 à long(N) faire 
b10 ß b10 * b1 + Pos(N[i],Ch) – 1 
Finpour 
2) base10ßb103) Fin base10 
{Transforme le nombre de base 10 en Base : b2} 
0) Fonction base(N :entier, b2 :entier) :chaîne 
1) b ß"" 
Tant que  (N <> 0) faire 
i ß N mod b2 
b ß ch[i+1]+ b 
N ßN div b2 
fin tant que 
2) base ß b 
3) fin base

Mourad Bahri  & Naima Bayoudh & Leila Ben Njima  Ikram Nasrallah & Med Ali Farhat 

Page 14 


Aperçu du document 60.pdf - page 1/14

 
60.pdf - page 2/14
60.pdf - page 3/14
60.pdf - page 4/14
60.pdf - page 5/14
60.pdf - page 6/14
 




Télécharger le fichier (PDF)


60.pdf (PDF, 333 Ko)



Sur le même sujet..





Ce fichier a été mis en ligne par un utilisateur du site. Identifiant unique du document: 00317167.
⚠️  Signaler un contenu illicite
Pour plus d'informations sur notre politique de lutte contre la diffusion illicite de contenus protégés par droit d'auteur, consultez notre page dédiée.