Algorithmique et structure des

données
Elaboré par Mme Elkamel Hager
[email protected]

FSM de Monastir 2020-2021

1ière année Licence en Sciences d’Informatique
Semestre 13
H. Jamoussi Elkamel , FSM 1
ASD1 – 2020 – S1

Plan du cours
• Chapitre 1 : Introduction à l’algorithmique
• Chapitre 2 : Types de données, constantes, Variables
• Chapitre 3 : Structures conditionnelles
• Chapitre 4 : Structures itératives
• Chapitre 5 : Procédures et fonctions
• Chapitre 6 : Les tableaux
• Chapitre 7 : La Récursivité
• Chapitre 8 : Les algorithmes de recherche
• Chapitre 9 : Les algorithmes de Tri
• Chapitre 10 : Les enregistrements
• Chapitre 11 : Les pointeurs

ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 2

1
 Chapitre 4 : Structures de
contrôle itératives

ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM

sommaire
1. Introduction
2. Les structures de contrôles itératives
3. Enumération des éléments d’une séquence
4. Le forme des structures de contrôle itératives
5. La structure de contrôle itérative complète
5.1 pour .. Faire
5.2 le parcours descendant
5.3 Cas général
6. Les itérations complètes récurrentes
7. La structure de contrôle itérative à condition d’arrêt répéter ..
Jusqu’à
8. La structure de contrôle itérative à condition d’arrêt tantque ..
faire
ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 4

2
 Introduction
Le langage algorithmique est un langage qui reprend les
concepts des langages impératifs ils offrent
– des entités typées possédant des identifiants
– une suite d’actions (instruction) modifiant l’état
d’un algorithme, on trouve les structures
• Séquentielles
• Conditionnelles
• Itératives
 déterministes
 indéterministes

H. Jamoussi Elkamel , FSM 5

ASD1 – 2020 – S1

Les structures de contrôle itératives

Répéter un traitement = boucle

• En informatique, on peut être amené à répéter un traitement plusieurs

fois.
• La structure itérative ou boucle, est utilisée lorsque l’on doit
effectuer le même traitement plusieurs fois.
• On utilise la structure itérative quand on doit réaliser le même
traitement sur un même objet, ou sur plusieurs objets de même
nature. Mais son réel intérêt réside dans le fait que l’on peut modifier,
à chaque répétition (itération), les objets sur lesquels s’exerce l’action
répétée.

ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 6

3
 Les structures de contrôle itératives
• On raisonne donc sur une séquence d’éléments, c’est-à-dire une
suite d’éléments de même type, et de valeurs différentes
• Exemples de séquences d’éléments:
– chaines de caractères,
– fichiers,
– tableaux,
– suite mathématique,
– suite des valeurs etc.
• Un algorithme itératif consiste à énumérer les éléments d’une
séquence en utilisant une boucle.

H. Jamoussi Elkamel , FSM 7

ASD1 – 2020 – S1

Enumération des éléments d’une séquence

Il y a en fait deux grandes raisons pour énumérer les éléments d’une

séquence :

1. Appliquer un même traitement à tous les éléments de la séquence =

parcours séquentiel
2. Rechercher dans la séquence un élément vérifiant une propriété
donnée = recherche séquentielle

Tous les algorithmes itératifs consistent

◦ soit en un parcours d’une séquence d’éléments
◦ soit en une recherche dans une séquence
◦ soit en une combinaison de parcours et de recherche

ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 8

4
 Les formes de structures de contrôle itératives

Les structures de contrôle itératives sont de deux forme:

• La structure itérative complète (déterministe): utiliser
pour exprimer une répétition d’un traitement un nombre
fini de fois
• La structure itérative à condition d’arrêt
(indéterministe) : exprime une répétition dont on ne
connait pas le nombre. L’arrêt est géré par une condition
d’arrêt. Il existe deux formulations pour exprimer cette
structure
 La structure répéter … jusqu’à
 La structure Tant que …. Faire

H. Jamoussi Elkamel , FSM 9

ASD1 – 2020 – S1

La structure de contrôle itérative complète:

Pour … faire
Une structure de contrôle itérative complète exprime la répétition d’un
traitement un nombre de fois connu d’avance.
séquence d’instruction A
Pour compteur De 1 à n
Faire
séquence d’instructions B
FinPour
séquence d’instruction C
• Compteur : est de type scalaire (entier, caractère) , il est appelé indice de parcours
de l’itération.
• On effectue l’action A, puis n fois l’action B, puis C
• A: est l’initialisation, elle comporte des objets, indépendants du compteur de
l’itération.
• Le compteur est incrémenté automatiquement et il passe au successeur de la
valeur courante
ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 10

5
 La structure de contrôle itérative complète :
Pour … faire
Exemple
écrire un algorithme qui lit à partir du clavier n entiers et affiche les
entiers pairs strictement positifs.

Spécification

Problème NombrePair
entrées : - n : entier : nombre des entiers à lire
- une séquence des entiers xi à lire à partir du clavier
sortie : affichage des entiers pairs et strictement positifs

H. Jamoussi Elkamel , FSM 11

ASD1 – 2020 – S1

La structure de contrôle itérative complète:

Pour … faire
Algorithme nombrePair
Variable n, x, i : entier
Debut
Ecrire("donner un entier n > = 0 ")
Lire(n)
pour i de 1 à n faire
ecrire("donner un entier x ")
Lire(x)
Si (x >= 0) et (x mod 2 = 0)
alors Ecrire( x, " " ).
Finsi
Finpour
Fin

ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 12

6
 La structure de contrôle itérative complète
Le parcours descendant
séquence d’instruction A
Pour compteur De n à 1 pas -1
Faire
séquence d’instructions B
FinPour
séquence d’instruction C

• La décrémentation est automatique, le compteur passe au prédécesseur de sa

valeur en cours.
• Généralement, cette exigence provient du fait que la séquence d’instruction B à
répéter utilise les valeurs du compteur

H. Jamoussi Elkamel , FSM 13

ASD1 – 2020 – S1

La structure de contrôle itérative complète

Le parcours descendant
Exemple
écrire un algorithme qui lit une chaine des caractères et l’affiche dans le
sens inverse.
Spécification

Problème IverserChaine
entrées : - ch : une chaine des caractères
sortie : affichage de ch dans l’ordre inverse.

ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 14

7
 La structure de contrôle itérative complète
Le parcours descendant
Algorithme inverserChaine Algorithme inverserChaine
Variable i, L : entier Variable i, L : entier
ch: chaine ch: chaine
Debut & ch1
Ecrire("donner chaine ") Debut &
Lire(ch) Ecrire("donner chaine ")
L ← longueur(ch) Lire(ch)
pour i de L à 1 pas -1 ch1 ←""
faire L ← longueur(ch)
ecrire( ch[i] ). pour i de L à 1 pas -1
Finpour faire
Fin ch1 ← ch1 & ch[i]
Finpour
ecrire(ch1).
ASD1 – 2020 – S1
Fin , FSM
H. Jamoussi Elkamel 15

La structure itérative complète : Cas général

séquence d’instruction A
Pour compteur De valInitiale à valFinale
Faire
séquence d’instructions B
FinPour
séquence d’instruction C
• Compteur est défini entre valInitiale et valFinale +1.
• On effectue l’action A, puis (valFinale–valInitiale+1) fois l’action B, puis C
• Le compteur est automatiquement incrémenté de 1
• La première fois que B est exécutée, compteur vaut valInitiale, la seconde
fois valInitiale +1, etc., la dernière fois compteur vaut valFinale.
• Lorsque on sort de la boucle le compteur vaut (valFinale +1)
• Si (valFinale < valInitiale ) l’action B n’est jamais exécutée.

ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 16

8
La structure itérative complète : Cas général
séquence d’instruction A
Pour compteur De valInitiale à valFinale pas p
Faire
séquence d’instructions B
FinPour
séquence d’instruction C
• Si p est positif, le parcours est ascendant , si p est négatif le parcours est
descendant.
• Le compteur de parcours de l’itération est automatiquement incrémenté (resp.
décrémenté) de la valeur p à chaque itération
• Le nombre de répétition est n = E ( (valFinale–valInitiale+1) /p)
• l’action B n’est jamais exécutée si l’indice de fin est atteint dès le départ :
 si p >0 et valInitiale > valFinale
 Si p < 0 et valInitiale < valFinale
H. Jamoussi Elkamel , FSM 17
ASD1 – 2020 – S1

La structure itérative complète : Cas général

Exemple
écrire un algorithme qui lit une chaine des caractères et affiche la
chaine après avoir remplacé les caractères se trouvant dans les positions
multiple de trois par ‘*’

Spécification

Problème transformerChaine
entrées : - ch : une chaine des caractères
sortie : affichage de la chaine ch après transformation

ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 18

9
 La structure itérative complète : Cas général
Algorithme transformerChaine
Variable i, L : entier
ch: chaine
Debut &
Ecrire("donner chaine ")
Lire(ch)
L ← longueur(ch)

pour i de 3 à L pas 3
faire
ch[i] ← ‘*’
Finpour
ecrire(ch)
Fin
H. Jamoussi Elkamel , FSM 19
ASD1 – 2020 – S1

Les itérations complètes récurrentes

• une itération est dite récurrente si le traitement à
l’étape i dépend des étapes qui le précèdent (i-1 .. )
• Les résultats intermédiaires sont générés par une relation
de récurrence.
• On s’intéresse au résultat final de l’itération.
• Si la relation de récurrence lie deux éléments successifs,
on dit que la récurrence est d’ordre 1, Ui = f (Ui-1 )
• si elle lie trois éléments, on dit qu’elle est d’ordre 2,
Ui = f (Ui-1 , Ui-2) ect.

ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 20

10
 Les itérations complètes récurrentes
Exemple :
suite récurrente d’ordre 1 : Un = f (Un-1 )
U0 =0
Un = 5Un-1 + 10 pour (n > 0)

suite récurrente d’ordre 2 : Un = f (Un-1 , Un-2)

U0 = 1
U1 = 1
Un = Un-1 + Un-2 pour (n > 1)

H. Jamoussi Elkamel , FSM 21

ASD1 – 2020 – S1

Les itérations complètes récurrentes

Exemple : calculer et afficher la somme des n entiers consécutifs à
partir d’une 1.

Spécification
Problème somme
Entrées : n est un entier à lire à partir du clavier
une séquence de n entiers à lire du clavier
préconditions : ( n ≥ 0) n

Sortie : S : la somme de n entiers =  i 1

i  (1  2  3  ...  n)

ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 22

11
 Les itérations complètes récurrentes
Analyse S= (1+2+3+..+n)
• L’addition étant associative on peut écrire S=((..(((1+2)+3)+4)+…)+n)
On a (n-1) additions à faire
• On change rien en ajoutant 0 à l’expression S=((..((((0+1)+2)+3)+4)+…)+n)
on a maintenant n additions à faire
Le calcul de la somme est défini par récurrence
S0=0 La valeur initiale S0 est égale à 0
S1=S0 + 1
S2=S1 + 2
..
Si=Si-1 + i Récurrence linéaire d’ordre 1
la somme à l’étape i Si = la somme à l’étape (i-1)
S(i-1) en lui ajoutant i
..
Sn=Sn-1 + n La valeur finale Sn est égale à S

– Le calcul de S peut s’exprimer à l’aide d’une boucle qui se répète n fois,

– à une itération i on calcul une somme partielle S ←S +i
H. Jamoussi Elkamel , FSM 23
ASD1 – 2020 – S1

Les itérations complètes récurrentes

Algorithme Somme
Variable n, S , i : entier
Debut
repeter
Ecrire ("donner un entier n :")
Lire(n)
jusqu’à ( n >= 0 )
S←0
pour i de 1 à n faire
S←S+i
Finpour
ecrire(S)
Fin
ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 24

12
 La structure itérative à condition d’arrêt

• Plusieurs problèmes nécessitent les répétitions d’un

traitement dont on ne connait pas le nombre de
répétitions.
• C’est une condition qui doit gérer l’arrêt des
répétitions.
• Il existe deux formulations pour traduire une structure
itérative à condition d’arrêt:
 La structure répéter …. Jusqu’à
 La structure tant que …. Faire

H. Jamoussi Elkamel , FSM 25

ASD1 – 2020 – S1

La structure itérative à condition d’arrêt

Répeter .. Jusqu’à
séquence d’instruction A
Repeter
séquence d’instructions B
jusqu’à condition d’arrêt
séquence d’instruction C
• La condition est une expression logique, appelée condition d’arrêt de l’itération.
• On effectue l’action A, puis une ou plusieurs fois l’action B, puis C.
• L’action B est effectuée au-moins une fois et jusqu’à ce que la condition ait la valeur
vrai
• Si la condition a la valeur vrai dès le départ, on effectue une seule fois B
• Si au départ la condition a la valeur faux, et si l’action B ne modifie pas la condition
on a une itération sans fin : on dit que l’algorithme «boucle» ou « boucle infinie ».
• La boucle repeter commence par une initialisation éventuelle.
ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 26

13
 La structure itérative à condition d’arrêt
Répeter .. Jusqu’à

• Exemple
Calculer la moyenne arithmétique d’une suite de réels strictement
positifs qui se termine par la valeur -1
Spécification

Problème multiplication
Entrées : une suite des réels

Sortie : moy = S / nb

H. Jamoussi Elkamel , FSM 27

ASD1 – 2020 – S1

La structure itérative à condition d’arrêt

Répeter .. Jusqu’à

Analyse
S = somme de la séquence
Nb = nombre des élément de la séquence
condition d’arrêt x= 0
Initialisation
Nb0 = 0
S0 = 0
Itération
Lire(xi)
Si (xi > = 0)
Si = Si-1 + xi pour (xi > 0)
Nbi = Nbi-1 + 1

À la fin de la boucle
Moy
ASD1 = –SS1/ Nb si Nb <> 0H. Jamoussi Elkamel , FSM
– 2020 28

14
 La structure itérative à condition d’arrêt
Répeter .. Jusqu’à
Algorithme multiplication
si ( NB > 0)
Variable NB : entier
Alors Moy ← S / NB Sinon
x, S : réel
Moy ← 0
Debut
FinSi
S←0
NB ← 0
Ecrire (" moyenne = ", moy )
repeter
Fin
Ecrire ("x = ")
Lire(x )
si ( x > 0)
alors
S← S + x
Nb ← Nb + 1
Finsi
jusqu’à ( x = -1 )

H. Jamoussi Elkamel , FSM 29

ASD1 – 2020 – S1

La structure itérative à condition d’arrêt

Répeter .. Jusqu’à

• Exemple
multiplier deux entiers positifs a et b, le deuxième n’étant pas nul, en
utilisant uniquement les additions.
Spécification

Problème multiplication
Entrées : a et b entiers positifs
précondition : (a ≥ 0) et (b> 0)
Sortie : affichage de P = a * b

ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 30

15
 La structure itérative à condition d’arrêt
Répeter .. Jusqu’à
Filtrage des données ou lecture conditionnée
Il s’agit d’obliger l’utilisateur de l’algorithme à fournir des données
vérifiant certaines contraintes du domaine.
On peut utiliser la primitive répéter, puisqu’on sait qu’au moins
une valeur sera donnée.
Dans notre cas on a (a ≥ 0) et (b> 0) condition d’arrêt

repeter
Ecrire ("donner deux entiers a ≥ 0 et b> 0 :")
Lire(a , b )
jusqu’à ( a > = 0) et (b> 0)

H. Jamoussi Elkamel , FSM 31

ASD1 – 2020 – S1

La structure itérative à condition d’arrêt

Répeter .. Jusqu’à

Analyse
a*b = a + a + a + .. + a
b fois
a*b =(..(( (0+a)+a ) + a )+ ..+a)

S0 = 0 i= 0
Si = Si-1 + a pour (i > 0)

on s’arrête lorsque i = b condition d’arrêt

La condition d’arrêt peut être exprimée à l’aide du compteur i

qui permet de compter combien de fois on doit exécuter
l’instruction pour obtenir le résultat.

ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 32

16
 La structure itérative à condition d’arrêt
Répeter .. Jusqu’à
Algorithme multiplication
Variable a, b , i : entier

Debut
repeter
Ecrire ("donner deux entiers a ≥ 0 et b> 0 :")
Lire(a , b )
jusqu’à ( ( a > = 0) et (b> 0) )
S←0
i ←0
repeter
S← S + a
i ←i+1
jusqu’à ( i = b )
Ecrire (S)
Fin

H. Jamoussi Elkamel , FSM 33

ASD1 – 2020 – S1

La structure itérative à condition d’arrêt

Tant que
séquence d’instruction A
tantque non( condition d’arrêt )
Faire
séquence d’instructions B
Fintantque
séquence d’instruction C
• On effectue l’action A, puis zéro, une ou plusieurs fois l’action B, puis C.
• condition = non( condition d’arrêt )
• Si la condition d’arrêt est vérifiée dès le départ, donc non(condition d’arrêt)
a la valeur faux et on n’effectue jamais B.
• L’action B est effectuée jusqu’à ce que la condition d’arrêt devient vrai, c-a-d
non(condition d’arrêt) ait la valeur faux
• Que se passe-t-il si l’action B ne modifie pas la condition ?
• La condition est supervisée directement ou indirectement par le la séquence
de traitement B pour la faire passer à l’état vrai.
ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 34

17
 La structure itérative à condition d’arrêt
Tant que .. Faire

• Exemple
multiplier deux entiers a et b positifs ou nuls, en utilisant uniquement
des additions. (maintenant b peut être nul )
Spécification
Problème multiplication
Entrées : a et b entiers positifs
précondition : (a ≥ 0) et (b ≥ 0)
Sortie : affichage de S = a * b
Analyse
L’utilisation de répéter .. Jusqu’à tombe alors en défaut puisque
(S← S + a) est exécuté au moins une fois on ne pourra avoir le résultat 0
dans S lorsque (a ≥ 0) et (b = 0)
H. Jamoussi Elkamel , FSM 35
ASD1 – 2020 – S1

La structure itérative à condition d’arrêt

Tant que ..faire
Algorithme multiplication2
Variable a, b , i : entier

Debut
repeter
Ecrire ("donner deux entiers a ≥ 0 et b> = 0 :")
Lire(a , b )
jusqu’à ( ( a > = 0) et (b > = 0) )
S←0
i ←0
Tantque (i <> b) faire
S← S + a
i ←i+1
fintantque
Ecrire (S)
Fin
Si b = 0 on n’entre pas dans la boucle et S = 0

ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 36

18
 La structure itérative à condition d’arrêt
Tant que .. Faire

• Exemple
Calculer le Plus Grand Diviseur Commun PGCD de deux entiers
naturels a et b.

Spécification
Problème multiplication
Entrées : a et b entiers positifs
précondition : (a ≥ 0) et (b ≥ 0) et (a + b <> 0)
Sortie: un entier le pgcd(a, b)

H. Jamoussi Elkamel , FSM 37

ASD1 – 2020 – S1

La structure itérative à condition d’arrêt

Tant que .. Faire
Analyse : (a ≥ 0) et (b ≥ 0) et (a + b <>)
Théorème
• Pgcd(a, 0) = a
• Pgcd(a, b ) = pgcd( b, a mod b) si (0 < b =< a )
• Pgcd(a,b) = pgcd(b , a) si (a < b )
(0 < b =< a )
a b R = a mod b
24 9 6
9 6 3
6 3 0
3 0 arrêt
Pgcd = 3 condition d’arrêt (b = 0)
si (a < b )
a b R = a mod b
9 24 9
H. Jamoussi Elkamel , FSM 38
ASD1 – 2020 – S1
24 9 6

19
 La structure itérative à condition d’arrêt
Tant que ..faire
Algorithme pgcd
Variable a, b , R : entier

Debut
repeter
Ecrire ("donner deux entiers a ≥ 0 , b ≥ 0 et (a + b) <> 0:")
Lire(a , b )
jusqu’à ( ( a > = 0) et (b > = 0) et (a + b) <> 0)
Tantque (b <> 0) faire
R ← a mod b
a ←b
b← R
fintantque
Ecrire ( a )
Fin
Remarque: on peut accepter (a < b) , dans ce cas, il y’ a échange automatique de
deux valeurs sans qu’il soit nécessaire de le prévoir en plus dans l’algorithme .

H. Jamoussi Elkamel , FSM 39

ASD1 – 2020 – S1

Exercice : Suite récurrentes d’ordre 2

Exemple : calculer et afficher les n premiers termes de la suite U

définie par
U1 = 1
U2 = 1
Un = Un-1 + Un-2 pour (n > 2)
Récurrence linéaire d’ordre 2
Spécification
Problème termeSuite
Entrées : n est un entier à lire à partir du clavier
préconditions : ( n ≥ 1)
Sortie : affichage de n premiers termes de la suite Un

ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 40

20
 Exercice : Suite récurrentes d’ordre 2
Analyse
• U1 = 1 et U2 = 1 sont donnés, et on calcul (n-2) termes à l’aide de la formule
récurrente Un = Un-1 + Un-2 pour (n > 2)
• Récurrence linéaire d’ordre 2 : il faut deux termes précédents pour calculer Un
• pour calculer U à une itération i , nous avons besoin de 2 valeurs: la précédente (à
l’itération i-1 ) et la pré-précédente (à l’itération i-2).
• On manipule deux variables: Uc et Up
• À un instant donné, une variable ne peut avoir qu’une valeur
• Dans une itération, il faut sauvegarder la valeur calculée dans une variable
intermédiaire aux
• Initialement
Up= U1 = 1 et Uc = U2 = 1
• À une itération i
aux ←Uc + Up
Up ←Uc
Uc ← aux H. Jamoussi Elkamel , FSM 41
ASD1 – 2020 – S1

Exercice Suite récurrentes d’ordre 2

Algorithme termeSuite
Variable n,Uc, Up, aux : entier
Debut
repeter
Ecrire ("donner un entier n > = 1 :")
Lire(n)
jusqu’à ( n > = 1)
Ecrire( "U" , 1 , " = ", 1)
si (n > = 2)
alors
Up ← 1
Uc ← 1
Ecrire("U" , 2 , " = " , Uc)
pour i de 3 à n faire
aux ← Uc + Up
Up ← Uc
Uc ← aux
ecrire("U" , i , " = " , Uc)
Finpour
Finsi
ASD1 – Fin
2020 – S1 H. Jamoussi Elkamel , FSM 42

21
 Exercice : Suite
calculer et afficher racine de a, a est un réel strictement positif par la
méthode de Newton avec une précision esp.
Méthode de Newton : on calcul les éléments de la suite U1
a
U0 
2
1 a
U i  (U i 1  ) si (i  0)
2 U i 1
U i  U i 1
tantt que  eps
U i 1
Problème racine
Entrées : a: un réel
eps : un réel : la précision
préconditions : ( a > 0) et (eps > 0)
Sortie : U = racine de a
H. Jamoussi Elkamel , FSM 43
ASD1 – 2020 – S1

Exercice Suite
Algorithme racine
Variable a , eps : réel
U, T , aux : entier
Debut
repeter
Ecrire ("donner deux réels a > 0 et eps > 0")
Lire(a, eps )
jusqu’à (( a > 0) et (eps > 0))
U←a/2
T←1
tant que ( T > eps ) faire
aux ← U
U ← 1/2 ( U + a / U)
T ← abs( U – aux )/ aux
Fintantque
ecrire(U)
ASD1 – Fin
2020 – S1 H. Jamoussi Elkamel , FSM 44

22
 Exercice : Série entière
Il s’agit de dégager une méthode pour calculer la valeur d’une fonction
grâce à son expression en série entière. Ce calcul devant minimiser le
nombre d’opérations à effectuer.

x x 2 x3 xn
Exemple : calculer la somme S n ( x)  1     .. si (n > 0)
1! 2! 3! n!

Spécification
Problème suiteEntière
Entrées : n est un entier à lire à partir du clavier
x est un réel à lire à partir du clavier
précondition : (n > = 0)
Sortie : affichage de S = Sn(x)

H. Jamoussi Elkamel , FSM 45

ASD1 – 2020 – S1

Les itérations complètes récurrentes

Série entière
Analyse x x 2 x3 xn
S n ( x)  1     .. (pour n ≥ 0)
1! 2! 3! n!
• On utilise le principe de calcul d’une somme
Si = Si-1 + xi / i! pour i > 1 Si est une suite récurrente d’ordre 1
Sn = S
xi x ( i 1) x x
Ti   *  Ti 1 * Ti est une suite récurrente d’ordre 1
i! (i  1)! i i
On remarque que on passe de (i-1) ième terme au ième terme par une multiplication

T0 = 1
Ti = Ti-1 * x / i Les itérations T S
donc S0 = 1 Initialisation 1 1
Si = Si-1 + Ti 1 x 1+x
• À une itération i on calcul 2 x2 / 2 1 + x + x2 /2
T← T * x / i 3 x3 / (2*3) 1 + x + x2 /2 +x2/3!
S← S + T H. Jamoussi Elkamel , FSM 46
ASD1 – 2020 – S1

23
 Les itérations complètes récurrentes
Série entière
Algorithme suiteEntiere
Variable n : entier
S, T , x : réel
Debut
Ecrire ("donner un entier n :")
Lire(n)
Ecrire ("donner un réel x :")
Lire(x)
si ( n > = 0)
alors S←1
T ←1
pour i de 1 à n faire
T ←T* x/i
S← S + T
Finpour
Ecrire (S)
Finsi
Fin
H. Jamoussi Elkamel , FSM 47
ASD1 – 2020 – S1

Les itérations complètes récurrentes

Série entière
Analyse x x 2 x3 xn
S n ( x)  1     ..
1! 2! 3! n! (pour n >0)
• On utilise le principe de calcul d’une somme
S0 = 0
Si = Si-1 + xi / i! pour i > 1
xi x (i 1) x
Ti   * (pour i >0)
i! (i  1)! i
• On remarque qu’on passe de (i-1)ème terme au ième terme par une multiplication
S0 = 0 (n+1 additions à faire)
T0 = 1 Les itérations S T
Si = Si-1 + Ti-1 Initialisation 0 1
Ti = Ti-1 * x / i
1 1 x
Sn+ 1 = S
2 1+x x2 / 2
• À une itération i on calcul
3 1 + x + x2 /2 x3 / (2*3)
S← S + T
T← T * x/ i
ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 48

24
 Les itérations complètes récurrentes
Série entière
Algorithme suiteEntiere
Variable n : entier
S, T , x : réel
Debut
Ecrire ("donner un entier n :")
Lire(n)
Ecrire ("donner un réel x :")
Lire(x)
si ( n > = 1)
alors S←0
T ←1
pour i de 1 à (n+1) faire
S← S + T
T ←T* x/i
Finpour
Ecrire (S)
Finsi
Fin
H. Jamoussi Elkamel , FSM 49
ASD1 – 2020 – S1

La structure itérative à condition d’arrêt

Tant que
Exemple : Calculer et afficher ex (exponentielle de x ) grâce à la série entière

x x 2 x3 xi
ex  1    ..   ...
1! 2! 3! i!

En négligeant les termes inférieurs en valeur absolue à ℰ (ℰ > 0)

Spécification
Problème exponentielle
Entrées : ℰ est un réel (la précision)
x est un réel à lire à partir du clavier
précondition : (ℰ > 0)
Sortie : affichage de E = ex l’exponentielle de x à ℰ près

ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 50

25
 La structure itérative à condition d’arrêt
Tant que
2 3 i
Analyse : calculons la somme e x  1  x  x  x  ..  x  ... (i > 0)
1! 2! 3! i!
Et on s’arrête lorsque |Ti | = | xi/ i!| ≤ ℰ (condition d’arrêt)
S0  0
Si  S (i 1)  Ti

T0  1
xi x (i 1) x x Les itérations S i T
Ti   *  T( i 1) *
i! (i  1)! i i
Initialisation 0 0 1
• À une itération i on calcul 1 1 1 x
S← S + T 2 1+x 2 x2 / 2
3 1 + x + x2 /2 3 x3 / (2*3)
i← i + 1
T← T * x/ i
La condition d’arrêt |Ti | = ≤ ℰ risque d’être vérifier de T0
H. Jamoussi Elkamel , FSM 51
ASD1 – 2020 – S1

Les itérations complètes récurrentes

Série entière
Algorithme exponentielle
Variable i : entier
S, T , x, eps : réel
Debut
Ecrire ("donner un réel x :")
Lire(x)
Ecrire ("donner la précision epsilon :")
Lire(eps )
S←0
i← 0
T ←1
tantque ( abs(T) > eps ) faire
S← S + T
i← i +1
T ←T * x/i
FinTantque
Ecrire (S)
Fin
ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 52

26
 La structure itérative à condition d’arrêt
Série entière généralisation
Soit une fonction, d’images f(x) qui accepte un développement en
série entière dont la somme des i premiers est Si et le terme de rang i
est noté Ti.
Supposons que cette série vérifie les relations de récurrences suivantes
Si  Si 1  Ti i0
Ti  Ti 1 * g ( x, i )

G(x,i) étant un facteur à déterminer pour chaque série, ainsi que S0 et

T0
• l’exemple précédent S0 =0 T0 = 1 , g(x,i)= x/ i
• Le calcul de f(x) se fait d’une manière analogue à celle pour ex

H. Jamoussi Elkamel , FSM 53

ASD1 – 2020 – S1

Exercices

Exercice1
Etant donnée un nombre entier plus grand que 1. tester s’il est parfait.
Un nombre parfait est un entier positif égal à la somme des ses
diviseurs excepte lui-même.
Exemple 6 est parfait 6= 1+2+3
Exercice 2 multiplication égyptienne
Multiplier deux entiers positifs par la multiplication égyptienne.
X*y = x*(y-1) + x si y est impair
X*y = (x*2) * (y/2) si y est pair et y <>0

ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 54

27