LES ALGORITHMES ARITHMETIQUES

I- Introduction

nombres et des opérations entre eux.

II- Calcul du PGCD (Solution récursive) :

1. Activité 1:

PGCD (Le Plus Grand Commun Diviseur) de deux entiers positifs non nuls a et b, en utilisant la méthode des différences.

2. Méthode 1

n > m n = n m n < m m = m n n = m PGCD = m (ou n) m = m n

Exemple 1 : M = 35 ; n = 20

M 35 15 15 10 5

N 20 20 5 5 5

PGCD = 5

Exemple 2 : M = 8 ; n = 8 PGCD(8,8) = 8 a. Solution itérative

Analyse de la fonction PGCD :

Résultat = PGCD

Traitement : PGCD Å a

Tant que Faire

Si a > b alors a Å a b

Sinon b Å b - a

ªla plus grande valeur sera remplacée par la différence

Algorithme de la fonction PGCD :

0- Début fonction PGCD (a, b : entier) : entier

1- Tant que Faire

Si a > b alors a Å a b

Sinon b Å b - a

Fin Si

Fin Tant que

2- PGCD Å a

3- Fin PGCD

Chap 5 : Les algorithmes Arithmétiques Classe : 4ème SI Profs: MSEKNI Dalila, SFAR Hayet & BAFFOUN Rim page-2/9- b. Solution récursive

Algorithme Récursif de la fonction PGCD :

0- Début fonction PGCD (a, b : entier) : entier

1- Si a = b alors PGCD Å a

Sinon

Si a > b Alors

PGCD Å FN PGCD (a-b, b)

Sinon

PGCD Å FN PGCD (a, b-a)

Fin Si

2- Fin PGCD

3. Méthode 2

PGCD (m, n) = PGCD (n, m mod n

Exemple 1:

M = 35 ; n = 20 PGCD (35, 20) = PGCD (20, 15) = PGCD (15, 5) = PGCD (5, 0) = 5

Exemple 2 :

M = 8 ; n = 8 PGCD (8, 8) = PGCD (8, 0) = 8 a. Solution itérative : b. Solution récursive

0. Début fonction Calcul_PGCD (m, n: entier) :

entier

1. Répéter

R Å M mod N

M Å N

N Å R

(N = 0)

2. Calcul_PGCDÅ M

3. Fin Calcul_PGCD

function pgcd(m, n: integer): Integer; begin if (n=0) then pgcd := m else pgcd := pgcd (n, m mod n) ; end;

Image2

1. Présentation

Arrangement de P éléments parmi N :

ordonnées possibles de P éléments parmi N.

Exemple avec {a, b, c} : A(2,3) = 6

{a, b}, {b, a}, {a, c}, {c, a}, {b, c}, {c, b} Chap 5 : Les algorithmes Arithmétiques Classe : 4ème SI Profs: MSEKNI Dalila, SFAR Hayet & BAFFOUN Rim page-3/9-

Combinaison de P éléments parmi N :

nombre de permutations sans ordre possibles de P éléments parmi N.

Exemple avec {a, b, c} : C(2,3) = 3

{a, b}, {a, c}, {b, c}

2. Calcul de

ªUn arrangement de P N éléments est un p-uplet

éléments distincts de E.

ª P

notation suivante :

Image1

ª N et P sont des entiers qui vérifient la condition suivante P N

Activité :

Proposez une analyse, puis déduisez les algorithmes correspondants au problème permettant de

Analyse du PP

Résultat = Ecrire (" A ( ", n, ",", p, ")=",

FN Arrange (n, p))

Traitement :

ª La fonction arrange permet de

ª La saisie de n et p sera la tache de la

procédure saisie.

Analyse de la fonction Arrange:

Résultat =Arrange

Traitement : Arrange Å a

[a Å 1]

Pour i de n à (n-p+1) (pas = -1) faire

a Å a * i

Fin pour

Algorithme du PP

0- Début arrangement

1- Proc saisie (n, p)

2- Ecrire (" A ( ", n,",", p,")=", FN Arrange (n, p));

3- Fin Arrangement

Algorithme de la fonction Arrange :

0- Début fonction arrange (n, p : entier) : entier

1- a Å 1

Pour I de n à (n-p+1) (pas = -1) faire

a Å a * i

Fin Pour

2- Arrange Å a

3- Fin arrange

Chap 5 : Les algorithmes Arithmétiques Classe : 4ème SI Profs: MSEKNI Dalila, SFAR Hayet & BAFFOUN Rim page-4/9-

3. Calcul de la combinaison

ª Une combinaison de P e E de N éléments est une partie de E formée par P éléments.

ª Le nombre de combinaison de P

notation suivante : image3 ª N et P sont des entiers qui vérifient la condition suivante : P N

Activité :

Proposez une analyse, puis déduisez les algorithmes correspondants au problème permettant a combinaison de deux entiers donnés n et p P N).

Solution Itérative

Analyse du PP

Résultat = Ecrire (" C ( ", n,",", p,")=",

FN Comb (n, p))

Traitement :

ª La fonction Comb permet de

rechercher la combinaison de n et p.

ª La saisie de n et p sera la tache de la

procédure saisie.

Analyse de la fonction Comb:

Résultat = Comb

Traitement :

Comb Å FN Fact(n) / (FN Fact(p) * FN Fact(n-p))

Algorithme du PP

0- Début Combinaison

1- Proc saisie (n, p)

2- Ecrire (" C ( ", n,",", p,")=", FN Comb (n, p));

3- Fin Combinaison

Algorithme de la fonction Comb :

0- Début fonction Comb (n, p : entier) : réel

1- Comb Å FN Fact(n) / (FN Fact(p) * FN Fact(n-p))

2- Fin Comb

Solution Récursive

Image4

Analyse de la fonction Comb:

Résultat = Comb

Traitement :

Si (p=0) ou (p = n) alors Comb Å1

Sinon

Comb Å Fn Comb (n-1, p) + Fn Comb (n-1, p)

Algorithme de la fonction Comb :

0- Début fonction Comb (n, p : entier) : réel

1- Si (p=0) ou (p = n) alors Comb Å1

Sinon

Comb Å Fn Comb (n-1, p) + Fn Comb (n-1, p)

Finsi

2- Fin Comb

Chap 5 : Les algorithmes Arithmétiques Classe : 4ème SI Profs: MSEKNI Dalila, SFAR Hayet & BAFFOUN Rim page-5/9-

IV- Quelques règles de divisibilité :

1. Définition:

Un entier n est divisible par un entier m, si le reste de la division euclidienne de n par m est nul.

Une règle de divisibilité

Ces règles sont généralement appliquées à des grands nombres.

2. Divisibilité par 3 :

Règle : Un entier est divisible par 3 si la somme des chiffres qui le composent est divisible par 3.

Activité : Ecrire une analyse modulaire permettant de vérifier si un entier n est divisible par 3 et

déduire les algorithmes correspondants.

Analyse du PP

Résultat = Ecrire (n, FN Div_3(n))

Traitement :

ª La fonction Div_3 permet de savoir si

un entier n est divisible par 3.

ª La saisie de n sera faite dans le PP.

Analyse de la fonction Div_3:

Résultat = Div_3

Traitement : Parcourir la chaîne qui contient le nombre n et rechercher la somme des chiffres qui le compose puis tester si cette somme est divisible par 3

Algorithme du PP

0. Début Divisibilite_3

1. Ecrire ("Entrer n :")

Lire (n)

2. Ecrire ("L'entier ",n,Div_3(n))

3. Fin Divisibilite_3

Algorithme de la fonction Div_3 :

0. Début fonction Div_3 (n : entier) : Chaine

1. Convch (n, ch);

2. Répéter

S Å 0

Pour i de 1 à long (ch) faire

Valeur (ch[i], nb, e)

S Å S + nb

Fin pour

Convch(s, ch)

long (ch)=1

Si S dans [3, 6, 9] Alors

div_3 Å " est divisible par 3" Sinon div_3 Å " nest pas divisible par 3"

Fin si

3- Fin Div_3

3. Divisibilité par 4 :

Un entier est divisible par 4 si le nombre composé des deux derniers chiffres est divisible par 4.

Exemple : 5243 43

7224 est divisible par 4 car 24 est divisible par 4.

Chap 5 : Les algorithmes Arithmétiques Classe : 4ème SI Profs: MSEKNI Dalila, SFAR Hayet & BAFFOUN Rim page-6/9-

Activité : Ecrire une analyse modulaire permettant de vérifier si un entier n est divisible par 4

en utilisant la règle de divisibilité précédente et déduire les algorithmes correspondants.

Analyse du PP

Résultat = Ecrire (n, FN Div_4(n))

Traitement :

ª La fonction Div_4 permet de déterminer

si un entier n est divisible par 4.

ª La saisie de n sera faite dans le PP.

Analyse de la fonction Div_4:

Résultat = Div_4

Traitement : Si d mod 4 = 0 Alors

div_4Å"est divisible par 4" Sinon div_4Å" n'est pas divisible par 4"

Fin si

Valeur (ch1, d, er)

ch1 Å sous chaine (ch, long (ch)-1,2)

Convch(n,ch);

Algorithme du PP

0. Début Divpar4

1. Ecrire ("Entrer n :")

Lire (n)

2. Ecrire ("L'entier ", n, Div_4(n))

3. Fin Divpar4

Algorithme de la fonction Div_4 :

0. Début fonction Div_4 (n : entier) : Chaine

1. Convch(n,ch);

2. ch1 Å sous chaine (ch, long (ch)-1,2)

3. Valeur (ch1, d, er)

4. Si d mod 4 = 0 Alors

div_4Å"est divisible par 4" Sinon div_4Å" n'est pas divisible par 4"

Fin si

5. Fin Div_4

4. Divisibilité par 5:

Un entier est divisible par 5 si son chiffre des unités est égal à 0 ou à 5.

Exemple : 5243 3 ȯ {0,5}

Activité : Ecrire une analyse modulaire permettant de vérifier si un entier n est divisible par 5

en utilisant la règle de divisibilité précédente et déduire les algorithmes.

Algorithme de la fonction Div_5

0. Début Fonction div_5 (n : entier) : chaîne

1. Convch(n,ch)

2. ch1Å "''

3. Ch1Å sous chaine (ch,long(ch),1)

4. Valeur (ch1, u, er)

5. Si u dans [0,5] Alors

div_5 Å " est divisible par 5" Sinon div_5Å" n'est pas divisible par 5"

Fin si

6. Fin Div_5

Chap 5 : Les algorithmes Arithmétiques Classe : 4ème SI Profs: MSEKNI Dalila, SFAR Hayet & BAFFOUN Rim page-7/9-

5. Autre règles de divisibilité :

ªUn entier est divisible par 2 si son chiffre des unités est divisible par 2.quotesdbs_dbs11.pdfusesText_17

[PDF] LES ALGORITHMES ARITHMETIQUES