Algorithmique Et Programmation-4SI

Algorithmique et Programmation
4ème Année Sciences Informatique

Préface
Ce manuel a été préparé aux élèves de la quatrième année secondaire de la
filière sciences Informatique. Son contenu obéit aux programmes officiels de
l’enseignement de la matière algorithmique et programmation pour l’année
scolaire 2011-2012. Il a été préparé pour servir du compilateur Turbo Pascal pour
Windows 1.5 de Borland International, Inc. Ce manuel peut être utilisé, modifié,
retransmis avec ou sans autorisation de l’auteur. Toute réclamation ou
interrogation peut être adressé à l’auteur :
Haiethem Elguediri1
21751811
[email protected]
http://www.haiethem.co.cc
Vous êtes vivement remerciés pour l’intérêt apporté à ce manuel.
1 Copyright © Haiethem Elguediri 2010
ii
Remerciement
Je tiens à remercier vivement tous ceux qui m’ont aidé à réaliser ce document.
Merci infiniment
Haiethem
iii
Premier Chapitre : Enregistrement et Fichiers
iv
1. Enregistrements
1.1 Définition
Un enregistrement est une structure de données qui peut regrouper des objets
éventuellement de types différents.
champ_1 champ_2 champ_3 ... champ_n
Structure d’un enregistrement

1.2 Déclaration
* En algorithmique :
Type
Nom_enregistrement = enregistrement
Objet1 : type
Objet2 : type
...
Objetn : type
fin
Objet Type/nature Rôle

Nom_variable Nom_enregistrement Rôle
* En Pascal :
Type
Nom_enregistrement = record
Objet1 : type ;
Objet2 : type ;
...
Objetn : type ;
end ;
var
Nom_variable : Nom_enregistrement ;
Exemple :
5
* en algorithmique :
Type
eleve = enregistrement
nom : chaîne de caractères
age : entier
moy : réel
fin

e eleve Enregistrement eleve
* en Pascal :
type
eleve = record
nom : string ;
age : integer ;
moy : real ;
end ;
var
e : eleve ;
1.3 Utilisation des Enregistrements

1.3.1 Affectation :
L’affectation des Valeurs aux différents champs se fait comme suit :
En algorithmique En Pascal
Variable.champ valeur Variable.champ :=valeur
Exemple :
e.nom ← « Mohamed » e.nom := ‘Mohamed’ ;
e.age ← 25 e.age := 25 ;
e.moy ← 12.36 e.moy := 12.36 ;
6
Remarque :
Le champ d’une variable Enregistrement peut être lui-même un
enregistrement.
Exemple :
Type
Date_nais = enregistrement
jour : entier
mois : chaîne de caractères
année : entier
fin date_nais
eleve = enregistrement
nom : chaîne de caractères
date : date_nais
moy : réel
fin eleve

e eleve Enregistrement eleve
d Date_nais Enregistrement date de naissance
1.3.2 Lecture :
La lecture des valeurs des différents champs d’une variable
enregistrement se fait comme suit :
Au niveau de
l’analyse
Variable.champ=donnée Lire (variable.champ) Readln(variable.champ) ;
* Exemple :
En analyse En algorithmique En Pascal
e.nom = donnée Lire (e.nom) Read (e.nom ) ;
e.age = donnée Lire (e.age) Read (e.age ) ;
e.moy = donnée Lire (e.moy) Read (e.moy ) ;
7
1.3.3 L’écriture :
L’écriture des valeurs des différents champs d’une variable
enregistrement se fait comme suit :
En algorithmique et analyse En Pascal

Ecrire (Variable.champ) Write(Variable.champ) ;
* Exemple :
En analyse et algorithmique En Pascal
Ecrire (e.nom) Write (e.nom ) ;
Ecrire (e.age) Write (e.age ) ;
Ecrire (e.moy) Write (e.moy ) ;
1.3.4 Structure Avec ….. Faire

La structure avec ... faire (with ... do) permet de simplifier l’utilisation des
enregistrements en évitant d’écrire chaque fois le nom de l’enregistrement.
En algorithmique et analyse En Pascal

With enregistrement do
Avec enregistrement faire
Begin
...
...
Fin avec
End ;
* Exemple :
With e do
Avec e faire
begin
Ecrire (nom)
Write (nom ) ;
Ecrire (age)
Write (age ) ;
Ecrire (moy)
Write (moy ) ;
Finavec
End ;
Remarque :
En Pascal, il est nécessaire d’utiliser begin et end ; pour englober plusieurs
instructions dans la structure with ... do.
8
1.3.5 Vecteur d’enregistrements
Pour utiliser le même enregistrement plusieurs fois, on utilise un tableau
d’enregistrements (vecteur d’enregistrements).
* En algorithmique :
Type
Nom_enregistrement = enregistrement
Objet1 : type
Objet2 : type
...
Objetn : type
Fin
Nom_Vecteur = tableau de n Nom_enregistrement

Nom_variable Nom-Vecteur Rôle
* En Pascal :
Type
Nom_enregistrement = record
Objet1 : type ;
Objet2 : type ;
...
Objetn : type ;
end ;
Nom_Vecteur = array [1..n] of Nom_enregistrement ;
var
Nom_variable : Nom_Vecteur ;
9
2. Fichiers
2.1 Introduction
Les informations utilisées dans tous les programmes que nous avons déjà écris
ne pouvaient provenir que de deux manières : soit introduite par le programme
lui-même (affectation ou boucle pour par exemple) soit manuellement par
l’utilisateur pendant l’exécution et le test de ses programmes.
Ces informations sont perdues à la fin du programme et l’utilisateur devra les
réintroduire à chaque test ou exécution. La raison est que ces informations
résident toutes dans la mémoire principale de l’ordinateur.
Cependant, il est parfois nécessaire de conserver ou sauvegarder certaines
informations afin de les consulter ou utiliser ultérieurement. Pour cela nous
allons utiliser une structure de données qui est stocké sur un support de stockage
et non pas dans la mémoire centrale. C’est la notion de FICHIER.
2.2 Définition
Un fichier est un ensemble structuré de données de même type identifié

par un nom et enregistré sur un support de stockage.
blocs
Structure d’un fichier
2.3 Organisation des fichiers
Un fichier est composé d’un ensemble de blocs enregistrés les uns après
les autres de façon linéaire. Comment peut on parcourir ces blocs de
données? C’est l’organisation interne du fichier qui détermine la façon de
parcourir ces blocs.
Parmi les types d’organisation des fichiers on peut citer :
10
L’organisation séquentielle dans laquelle on ne peut accéder à un
élément q’après avoir parcouru tous les éléments précédents.
L’organisation directe dans laquelle les éléments sont identifiés par un
numéro d’ordre.
Remarque : le dernier bloc de données est suivi d’un caractère de fin de
fichier (EOF).
2.4 Types d’accès
D’après les manières d’organisation des fichiers, on peut déduire les

deux types d’accès suivants :
Accès séquentiel : pour lire une information on doit lire tous les blocs
qui la précèdent.
fins des blocs

bloc 0
bloc 1 blocs
bloc 2
...
bloc n Fin de fichier
Fichier à accès séquentiel
Accès direct : on peut directement accéder au bloc désiré juste en

précisent son numéro d’ordre.
fins des blocs

0
bloc 0
1 bloc 1 blocs
2
bloc 2
.
. ...
n–1 bloc n Fin de fichier
Fichier à accès direct
11
Pour exercer ces accès, le système d’exploitation dispose d’un pointeur.
Ce pointeur pointe le bloc en cours.
fins des blocs

bloc 0
bloc 1 blocs
bloc 2
Pointeur
...
bloc n Fin de fichier
Accès au fichier par le pointeur
Remarque:
Les objets ordinaires nécessitent un seul nom de variable (nom de
l'emplacement mémoire) alors que les fichiers nécessitent deux noms. Le
premier désigne l'emplacement mémoire et le deuxième désigne
l'emplacement sur le support de stockage. On appelle le premier nom
logique et le deuxième nom physique. L'instance du fichier située dans la
mémoire vive est de même appelée fichier logique et celle située sur le
support de stockage est appelée fichier physique.
R.A.M. Support de stockage
Fichier logique
Fichier physique
Fichier logique et fichier physique
2.4.1 Les fichiers à accès séquentiel :

Présentation :
Les éléments d’un fichier séquentiel sont disposés les uns à la suite des
autres de façon qu’on ne peut accéder à un élément qu’après avoir passé
par tous les éléments qui le précèdent.
12
Déclaration :
En algorithmique
Tableau de déclaration de nouveaux types
Type
Nom_fichier = Fichier de type_elements
Tableau de déclaration des objets :
Nom_logique Nom_fichier Fichier pour …
Remarque :
Nom_logique désigne la variable utilisée seulement dans le
programme c’est donc le nom interne du fichier.
A la suite, nous allons voir qu’on doit déclarer une autre variable
appelée Nom_physique ; c’est le nom externe c’est à dire le nom du fichier
sur le support externe de stockage (disque dur, disquette,…)
En Pascal
Type
Nom_fichier = File of type_elements ;
Var
Nom_logique : Nom_fichier ;
* Exemple :
Tableau de déclaration de nouveaux types
Type
Eleve = enregistrement
Nom : chaîne de caractères
Age : entier
Moy : reél
Fin eleve
fiche = Fichier de eleve
13
e eleve Enregistrement de élève
f fiche Fichier de élèves
Traitements sur les fichiers :

• Association : cette opération permet de faire la correspondance entre le nom
physique du fichier (fichier sur un support de stockage) et son nom logique
(variable dans la mémoire centrale). Elle est assurée par la procédure
prédéfinie « associer » (assign).
* Syntaxe :
Associer ( nom_logique, Assign (nom_logique,
nom_physique) nom_physique) ;
* Exemple :
Associer (f, « c:\bac\eleves.don ») Assign (f, ‘ c:\bac\eleves.don ’);
Remarque :
La procédure associer (assign) ne crée pas un fichier mais elle relie les deux
noms, logique et physique, d’un fichier.
• Ouverture : cette opération permet d’ouvrir un fichier. Un fichier
quelconque peut être ouvert soit en lecture seule, soit en lecture et écriture.
Ces deux modes d’ouvertures sont assurées chacune par une procédure
prédéfinie « recréer » (rewrite) pour l’ouverture en lecture et écriture et
« ouvrir » (reset) pour l’ouverture en lecture seule.
* Syntaxe :
recréer ( nom_logique) Rewrite (nom_logique) ;
ouvrir ( nom_logique) Reset (nom_logique) ;
* Exemple :
14
recréer ( f) Rewrite (f) ;
ouvrir ( f) Reset (f) ;
Remarque :
La procédure recréer (rewrite) efface le contenu du fichier s’il existe
précédemment, sinon il sera créé.
• Écriture : cette opération permet d’introduire des informations dans un
fichier. Les informations introduites doivent être compatibles avec le type
du fichier. Elle est assurée par la procédure prédéfinie « écrire » (write).
* Syntaxe :
écrire ( nom_logique, variable) write (nom_logique, variable) ;
* Exemple :
écrire (f, e) write (f, e) ;
Remarque :
La procédure writeln n'est pas utilisable.
• Lecture : cette opération réalise la lecture d’une donnée à partir d’un
fichier. Elle est assurée par la procédure prédéfinie « lire » (read).
* Syntaxe :
lire ( nom_logique, variable) read (nom_logique, variable) ;
* Exemple :
lire (f, e) read (f, e) ;
Remarque :
La procédure readln n'est pas permise.
• Fermeture : cette opération ferme un fichier. Elle transfère le contenu du
fichier logique (variable fichier dans la mémoire centrale) vers le fichier
15
physique (sur le support de stockage). Elle est assurée par la procédure
prédéfinie « fermer » (close).
* Syntaxe :
fermer ( nom_logique) close (nom_logique) ;
* Exemple :
fermer (f) close (f) ;
• Test de fin de fichier : cette opération vérifie si la fin de fichier est atteinte.
Si le pointeur pointe le caractère fin de fichier (eof) alors la fin de fichier est
atteinte. Elle est réalisée par la fonction prédéfinie fin_fichier (eof).
* Syntaxe :
Variable ← Fin_fichier ( nom_logique) Variable := eof (nom_logique) ;
* Exemple :
Test ← Fin_fichier (f) Test := eof (f) ;
2.4.2 Les fichiers à accès direct :

Présentation :
Les éléments d’un fichier à accès direct sont identifiés par des numéros
(indices). Pour accéder à un bloc, on utilise son numéro d’indice. Le premier
bloc est indiqué par le numéro zéro. Donc le nième bloc est indiqué par le
numéro n-1.
Traitements sur les fichiers à accès direct :
• Pointer un élément : cette opération permet d’accéder directement à un
élément quelconque dans le fichier. Elle est réalisée par la procédure
prédéfinie « pointer » (seek).
Syntaxe :
16
Pointer ( nom_logique, numéro) Seek (nom_logique, numéro) ;
* Exemple :
Pointer ( f, 3) Seek (f, 3) ;
Remarque :
Il faut faire attention à ne pas pointer un numéro de bloc après la fin du
fichier. Pour cela on utilise la fonction « taille_fichier » (filesize).
• Taille de fichier : cette fonction retourne un entier qui permet de savoir le
nombre de blocs dans le fichier fourni en paramètres.
Syntaxe :
N ← taille_fichier ( nom_logique) N := filesize(nom_logique) ;
* Exemple :
N ← taille_fichier ( f ) N := filesize ( f ) ;
Autres procédures et fonctions :

Les fonctions et procédures vues jusqu’à maintenant sont gérées par l’unité
système. Il y a d’autres modules gérés par l’unité « windos ». Parmi ces modules:
• Position dans un fichier : cette opération retourne un entier qui désigne le
numéro de bloc actuel (position du pointeur) dans le fichier fourni en
paramètres. Elle est réalisée par la fonction « Position_fichier » (filepos).
Syntaxe :
N ← position_fichier ( nom_logique) N := filepos(nom_logique) ;
* Exemple :
N ← position_fichier ( f ) N := filepos ( f ) ;
17
• Effacer un fichier : cette opération permet d’effacer le contenu du fichier
fourni en paramètres. Elle est réalisée par la procédure « effacer » (erase).
Syntaxe :
Effacer ( nom_logique) Erase (nom_logique) ;
* Exemple :
Effacer ( f ) Erase ( f ) ;
• Renommer un fichier : cette opération permet de renommer le fichier fourni

en paramètres. Elle est réalisée par la procédure « renommer » (rename).
Syntaxe :
Renommer ( ancien_nom_logique, Rename (ancien_nom_logique,
nouveau_nom_logique) nouveau_nom_logique) ;
* Exemple :
Rename ( f, g ) Rename ( f, g ) ;
• Tronquer un fichier : cette opération permet d’effacer tous les blocs situés
après la position courante de pointeur (tronquer). Elle est réalisée par la
procédure « tronquer » (truncate).
Syntaxe :
Tronquer ( nom_logique) Truncate (nom_logique) ;
* Exemple :
Tronquer ( f ) Truncate ( f ) ;
Remarque : pour utiliser l’unité « windos » en Pascal : uses wincrt,windos ;
18
2.4.3 Les fichiers textes :
Présentation :
Un fichier texte est un fichier composé d’une suite de caractères (lettres,
chiffres, signes de ponctuation, symboles, caractères de contrôle (CR, LF ou
tabulation par exemple)). Ces fichiers sont déclarés par le type texte (text). Les
opérations standard pour les fichiers restent valables pour les fichiers textes.
Mais il y a quelques traitements spécifiques pour ce type de fichiers.
Déclaration :
En algorithmique
Nom_logique texte Fichier texte pour …
En Pascal
Var
Nom_logique : text ;
* Exemple :
En algorithmique
f texte Fichier texte pour …
En Pascal
Var
f : text ;
Traitements sur les fichiers textes :
• Test de fin de ligne : cette opération permet de savoir si le pointeur a arrivé
à la fin de la ligne courante ou non. Elle est réalisée par la fonction
prédéfinie « fin_ligne » (eoln).
Syntaxe :
Variable ← Fin_ligne ( nom_logique) Variable := eoln (nom_logique) ;
19
* Exemple :
Test ← fin_ligne ( f) Test := eoln (f) ;
• Chercher la fin de ligne : cette opération permet de savoir si le pointeur a

arrivé à la fin de la ligne courante ou non tout en supprimant les espaces et
les tabulations avant d’exécuter ce test. Elle est réalisée par la fonction
prédéfinie « chercher_fin_ligne » (seekeoln).
Syntaxe :
Variable ← chercehr_fin_ligne ( nom_logique) Variable := seekeoln (nom_logique) ;
* Exemple :
Test ← chercher_fin_ligne ( f) Test := seekeoln (f) ;
• Chercher la fin du fichier : cette opération permet de savoir si le pointeur a

arrivé à la fin du fichier ou non tout en supprimant les espaces et les
tabulations avant d’exécuter ce test. Elle est réalisée par la fonction
prédéfinie « chercher_fin_fichier » (seekeof).
Syntaxe :
Variable ← chercehr_fin_fichier ( nom_logique) Variable := seekeof (nom_logique) ;
* Exemple :
Test ← chercher_fin_fichier ( f) Test := seekeof (f) ;
• Ajouter : cette opération permet de positionner le pointeur à la fin du

fichier. Elle est réalisée par la procédure prédéfinie « ajouter » (append).
Syntaxe :
20
Ajouter ( nom_logique) Append (nom_logique) ;
* Exemple :
Ajouter ( f) Append (f) ;
• Lecture ligne par ligne : cette opération permet de lire une ligne du fichier
fourni en paramètres. Elle est réalisée par la procédure prédéfinie
« lire_nl » (readln).
Syntaxe :
Lire_nl ( nom_logique, variable) Readln (nom_logique, variable) ;
* Exemple :
Lire_nl ( f , ch) Readln (f , ch) ;
Remarque : la variable doit être de type chaîne de caractères. Mais si on

n’introduit pas de variable, seul le pointeur sera déplacé au début de la ligne
suivante.
• Écriture ligne par ligne : cette opération permet d’écrire une ligne dans le
fichier fourni en paramètres. Elle est réalisée par la procédure prédéfinie
« écrire_nl » (writeln).
Syntaxe :
Écrire_nl ( nom_logique, variable) Writeln (nom_logique, variable) ;
* Exemple :
Écrire_nl ( f , ch) Writeln ( f , ch) ;
Remarque : la variable doit être de type chaîne de caractères. Mais si on

n’introduit pas une variable, seul le pointeur sera déplacé au début de la ligne
suivante (écriture d’une ligne vide).
21
Deuxième Chapitre : Récursivité
xxii
1. Définition
La récursivité est une méthode algorithmique dans laquelle un module est
appelé dans son propre corps (s’appelle lui même). Cet appel est fait en
changeant les valeurs des paramètres d’appel.
2. Principe
Le principe de récursivité repose sur deux traitements :
• traiter un ou plusieurs cas généraux qui représentent les appels récursifs.
• traiter un ou plusieurs cas particuliers qui représentent les conditions
d’arrêt.
module () module () module ()

inst 1 inst 1 inst 1
module () module () module ()
fin fin fin
Appels récursifs
3. Application
Soit une fonction fact qui retourne le factoriel d’un entier n. On veut écrire
cette fonction d’une façon récursive.
3.1 analyse
DEF FN fact (n : entier) :entier long
résultat = fact ← f
f=[ ]
si n = 1 alors f←1
sinon
f ← n * fact (n-1)
finsi
23
3.2 algorithme
0) DEF FN fact (n : entier) :entier long
1) si n = 1 alors f ← 1
sinon
f ← n * fact (n-1)
finsi
2) fact ← f
3) fin fact
3.3 Programme
function fact (n :integer) :longint ;
begin
if n = 1 then f := 1
else
f := n * fact (n-1) ;
fact := f ;
end ;
24
Troisième chapitre : Algorithmes de Tri
xxv
1. Tri par Insertion
1.1 Principe
Le tri par insertion assure, à la nième itération, l’insertion du nième élément à sa
bonne place parmi les n-1 éléments précédents.
1.2 Analyse
Analyse de la procédure tri_ins :
DEF PROC tri_ins (var t :tab ; n : entier)
résultat = t_trié
t_trié = [ ] pour i de 2 à n faire
si t[i-1] > t[i] alors
aux ← t[i]
PROC decaler (t,i-1,p)
t[p + 1] ← aux
fin si
fin pour
Analyse de la procédure decaler :
DEF PROC decaler (t :tab ; deb : entier ; var fin : entier)
résultat = fin
fin = [fin ← deb ] tantque (fin>=1) et (t[fin] > aux) faire
t[fin+1] ← t[fin]
fin ← fin -1
fin tantque
1.3 Algorithme
Algorithme de la procédure tri_ins :
0) DEF PROC tri_ins (var t :tab ; n : entier)
1) pour i de 2 à n faire
si t[i-1] > t[i] alors
aux ← t[i]
PROC decaler (t,i-1,p)
26
t[p + 1] ← aux
fin si
fin pour
3) fin tri_ins
Algorithme de la procédure decaler :
0) DEF PROC decaler (t :tab ; deb : entier ; var fin : entier)
1) fin ← deb
2) tantque (fin>=1) et (t[fin] > aux) faire
t[fin+1] ← t[fin]
fin ← fin -1
fin tantque
3) fin decaler
1.4 Programme
procedure tri_ins (var t:tab;n:integer); end;
var c,p:integer; begin
aux:real; for i:=2 to n do
procedure decaler(var begin
t:tab;deb:integer; var fin:integer); if t[i-1] > t[i] then
begin begin
fin:=deb; tmp:=t[i];
while (fin>=1) and(t[fin]>aux) do decaler(t,i-1,p);
begin t[p+1]:=aux;
t[fin+1]:= t[fin]; end;
fin:=fin-1; end;
end; end;
1.5 Interprétation
Cette méthode de tri déplace les éléments par position, donc elle est efficace
dans les cas ou le tableau est presque trié. Pour remédier cela on va utiliser le tri
Shell.
27
2. Tri Shell
Cette méthode est proposée par Donald Shell. Elle représente une version
améliorée de tri par insertion.
2.1 Principe
Cette méthode de tri propose de diviser le tableau en sous – tableaux formés
par des éléments éloignés de p positions. On définit donc la notion de pas (p). On
commence par le plus grand pas inférieur à la longueur du tableau à trier. On
applique aux sous tableaux le tri par insertion. On diminue chaque fois le pas
jusqu’à arriver au pas égal à un et dans ce cas le tri devient par insertion simple.
Pour calculer le pas, D. Shell a prouvé que la suite pn+1 = 3 * pn +1 est la
meilleure pour définir le plus grand pas inférieur ou égal à la longueur du
tableau.
2.2 Analyse
Analyse de la procédure tri_shell :
DEF PROC Tri_shell (var t : tab ; n : integer)
résultat = t_trié
t_trié = [ ] tantque pas >0 faire
pas ← pas div 3
pour i de pas +1 à n faire
aux ← t[i]
j←i
tantque (j>pas ) et (t[j-pas]>aux) faire
t[j] ← t[j-pas]
j ← j – pas
fin tantque
t[j] ← aux
fin pour
fin tantque
pas = [pas ← 0] tantque pas < n faire
pas ← 3 * pas +1
fin tantque
28
2.3 Algorithme
Algorithme de la procédure tri_shell :
0) DEF PROC Tri_shell (var t : tab ; n : integer)
1) pas ← 0
2) tantque pas < n faire
pas ← 3 * pas +1
fin tantque
2) tantque pas >0 faire
pas ← pas div 3
pour i de pas +1 à n faire
aux ← t[i]
j←i
tantque (j>pas ) et (t[j-pas]>aux) faire
t[j] ← t[j-pas]
j ← j – pas
fin tantque
t[j] ← aux
fin pour
fin tantque
3) fin tri_shell
2.4 Programme
procedure tri_shell(var t:tab; n:integer); aux:=t[i]; j:=i;
var pas,aux:integer; while (j>pas) and (t[j - pas] >aux ) do
begin begin
pas:=0; t[j]:=t[j - pas];
while pas<n do pas:=3*pas + 1; j:=j-pas;
while pas>0 do end;
begin t[j]:=aux
pas:=pas div 3; end;
for i:= pas+1 to n do end;
begin end;
29
2.5 Interprétation
Le tri Shell commence par déplacer les grandes valeurs vers la fin et les petites
vers le début du tableau pour faciliter le traitement de tri par insertion (si le pas
est égal à un). Ce qui permet d’éliminer le grand désordre dans le tableau à trier.
30
3. Tri par fusion
3.1 Principe
Le principe de tri par fusion se base sur la division du tableau à trier en deux
sous tableaux. Ensuite, on trie séparément les deux sous tableaux. Enfin, il reste
à rassembler les deux sous tableaux pour reconstruire le tableau trié. Dans notre
cas nous allons forcer la saisie triée des deux sous tableaux (pendant la saisie
chaque élément doit être supérieur ou égal à son précédant).
3.2 Analyse
Analyse de la procédure fusionner :
DEF PROC fusionner (var t : tab ; t1,t2 : tab ; n1,n2 :entier)
résultat = t
i ← 0 
t =  j1 ← 1  répéter
 j 2 ← 1
i ← i+1
si t1[j1] < t2[j2] alors
t[i] ← t1[j1]
j1 ← j1 + 1
sinon
t[i] ← t2[j2]
j2 ← j2 + 1
finsi
jusqu’à (j1> n1) ou (j2 > n2)
si j1 > n1 alors
pour j de j2 à n2 faire
i ← i+1
t[i] ← t2 [j]
finpour
sinon
31
i←i+1
t[i] ← t1[j]
finpour
finsi
3.3 Algorithme
0) DEF PROC fusionner (var t : tab ; t1,t2 : tab ; n1,n2 :entier)
1) i ← 0 , j1 ← 1 , j2 ← 1
2) répéter
i ← i+1
si t1[j1] < t2[j2] alors
t[i] ← t1[j1]
j1 ← j1 + 1
sinon
t[i] ← t2[j2]
j2 ← j2 + 1
finsi
jusqu’à (j1> n1) ou (j2 > n2)
3) si j1 > n1 alors
i ← i+1
t[i] ← t2 [j]
finpour
sinon
i←i+1
t[i] ← t1[j]
finpour
finsi
4) fin
32
3.4 Programme
procedure fusionner(var t,t1,t2:tab;n1,n2:integer); if j1 > n1 then
begin for j:= j2 to n2 do
i:=0; begin
j1:=1;j2:=1; i := i+1;
repeat t[i]:= t2 [j];
i:=i+1; end
if t1[j1] < t2[j2] then else
begin for j := j1 to n1 do
t[i] := t1[j1]; begin
j1 := j1 + 1; i :=i + 1 ;
end t[i] := t1[j];
else end;
begin end;
t[i] := t2[j2];
j2 := j2 + 1 ;
end;
until (j1>n1) or (j2>n2);
3.5 Interprétation
En effet, cette méthode n’est pas une méthode principalement de tri, mais de
fusion de deux tableaux triés. Elle reste utile pour les tableaux de grandes tailles.
33
Quatrième chapitre : Algorithmes Récurrents
34
1. Introduction
1.1 Définition
Un algorithme récurrent utilise un ou plusieurs résultats précédents. L’ordre
de récurrence dépend du nombre de résultats antérieurs utilisés.
Exemple : Un algorithme récurrent d’ordre 1 utilise un résultat précédent. Un
algorithme récurrent d’ordre p utilise p résultats antérieurs.
2. Calcul de somme
On désire calculer la somme des éléments d’une matrice mat de m lignes et n
colonnes.
2.1 Analyse
Analyse de la fonction calcul :
DEF FN calcul (mat : matrice ; m,n : entier) : entier
résultat = calcul ← s
s = [s ← 0] pour ligne de 1 à m faire
pour colonne de 1 à n faire
s ← s + mat [ligne , colonne]
finpour
finpour
2.2 Algorithme
0) DEF FN calcul (mat : matrice ; m,n : entier) : entier
1) s ← 0
2) pour ligne de 1 à m faire
pour colonne de 1 à n faire
s ← s + mat [ligne , colonne]
finpour
finpour
3) calcul ← s
4) fin
35
2.3 Programme
function calcul (mat :matrice ; m,n :integer) :integer ;
var ligne,colonne,s :integer ;
begin
s :=0 ;
for ligne := 1 to n do
for colonne :=1 to m do
s := s + mat[ligne,colonne] ;
calcul :=s ;
end ;
3. Suite de Thue Morse

La suite de Thue Morse est une suite qui traite des chaînes de caractères
comme suit :
U0 = « 0 »
Ensuite, à chaque itération on insère « 1 » après chaque « 0 » et « 0 » après
chaque « 1 ».
Exemple : On cherche U3. A chaque fois les
U0 = « 0 » caractères ajoutés sont
U1 = « 01 » formatés en gars italique.
U2 = « 0110 »
U3 = « 01101001 »
On demande d’analyser un module qui retourne le nème terme de la suite de
Thue Morse.
3.1 Analyse
Analyse de la fonction Thue_Morse :
DEF FN thue_Morse (n :entier) :chaîne de caractères
résultat = thue_morse ← ch
ch = [ch ← "0"] pour i de 1 à n faire
j←1
répéter
si ch[j] = « 0 » alors insère (« 1 »,ch,j+1)
sinon insère (« 0 »,ch,j+1)
36
finsi
j ← j+2
jusqu’à j > long(ch)
finpour
Remarque :
La longueur du nème terme de cette suite est 2n caractères. En Pascal la
longueur maximale d’une chaîne de caractères est 255 caractères. Donc cette
solution est valable pour les termes : U1 à U7. Pour pouvoir déterminer les
autres termes on utilise les fichiers plus tôt que les chaînes de caractères.
2ème solution :
Analyse de la procédure thue_morse :
DEF PROC thue_morse(var t,f : texte ; n :entier)
résultat = f
recréer( f ) 
f = écrire( f , "0" ) pour i de 1 à n faire
 fermer ( f ) 
PROC remplir (f,t,n)

PROC permut (f,t)
finpour
Analyse de la procédure remplir :
DEF PROC remplir (var f,t:texte ; n:entier)
résultat = f
ouvrir (t ) 
f=   tantque non fin_fichier(t) faire
recréer( f )
lire (t,c)
écrire (f,c)
si c = « 0 » alors écrire (f, «1»)
sinon écrire (f, « 0 »)
finsi
fin tantque
fermer(f) , fermer(t)
Analyse de la procédure permut :
37
DEF PROC permut (var t,f : texte)
résultat = t
ouvrir ( f ) 
t=   tantque non fin_fichier (f) faire
recréer(t )
lire (f,c)
écrire (t,c)
fintantque
fermer (t) , fermer (f)
3.2 Algorithme
1ère solution :
0) DEF FN thue_Morse (n : entier) :chaîne de caractères
1) ch ← « 0 »
j←1
répéter
si ch[j] = « 0 » alors insère (« 1 »,ch,j+1)
sinon insère (« 0 »,ch,j+1)
finsi
j ← j+2
jusqu’à j > long(ch)
finpour
3) thue_morse ← ch
4) fin
2ème solution :
0) DEF PROC thue_morse(var t,f : texte ; n :entier)
1) recréer (f)
2) écrire (f, « 0 »)
3) fermer(f)
PROC remplir (f,t,n)
PROC permut (f,t)
38
finpour
5) fin
Algorithme de la procédure remplir :
0) DEF PROC remplir (var f,t:texte ; n:entier)
1) ouvrir (t) , recréer (f)
2) tantque non fin_fichier(t) faire
lire (t,c)
écrire (f,c)
si c = « 0 » alors écrire (f, «1»)
sinon écrire (f, « 0 »)
finsi
fin tantque
3) fermer(f) , fermer(t)
4) fin
Algorithme de la procédure permut :
0) DEF PROC permut (var t,f : texte)
1) ouvrir (f) , recréer (t)
2) tantque non fin_fichier (f) faire
lire (f,c)
écrire (t,c)
fintantque
3) fermer (t) , fermer (f)
4) fin
3.3 Programme
2ème solution :
program thue_m; begin
uses wincrt; writeln('Donner un entier positif');
var readln(n);
f,t:text; if n <=0 then saisir(n);
j,k,i,n:integer; end;
x:real; procedure remplir(var f,t:text;
c:char; n:integer);
procedure saisir(var n:integer); begin
39
reset(t); read(f,c);
rewrite(f); write(c);
while not(eof(t)) do end;
begin close(f);
read(t,c); end;
write(f,c); procedure thue_morse (var f,t : text ; n :
if c='0' then write(f,'1') integer)
else write(f,'0'); begin
end; for i:=1 to n do
close(t);close(f); begin
end; remplir( f,t,n);
procedure permut(var t,f:text); permut(t,f);
begin end;
reset(f);rewrite(t); end ;
while not eof(f) do begin
begin assign(t,'c:\bac2011\thuemorse.txt');
read(f,c); assign(f,'c:\bac2011\thuemorse.res');
write(t,c); rewrite(t);
end; write(t,'0');
close(t);close(f); close(t);
end; saisir(n);
procedure affiche (var f:text); remplir(f,t,n);
begin thue_morse (f,t ,n)
reset(f); affiche (f);
while not eof (f) do end.
begin
40
4. Triangle de Pascal
On se propose d’afficher les n premiers lignes du triangle de Pascal. On
rappelle que les éléments de la première colonne sont tous égaux à 1 et les
éléments de la diagonale (ligne = colonne) sont tous aussi égaux à 1. Pour les
autres éléments :
mat [ligne , colonne] = mat [ligne – 1 , colonne – 1] + mat [ligne – 1 , colonne]
Exemple pour n = 5 on a :
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
On demande d’analyser un module qui remplit les n premiers lignes d’une
matrice correspondante au triangle de Pascal.
4.1 Analyse
Analyse de la procédure triangle :
DEF FN triangle (var mat : matrice ; n : entier)
résultat = mat
mat = [] pour ligne de 1 à n faire
pour colonne de 1 à ligne faire
si (ligne = colonne) ou (colonne = 1) alors
mat [ligne,colonne] ← 1
sinon
mat[ligne,colonne] ← mat [ligne – 1,colonne – 1] + mat [ligne – 1, colonne]
finsi
finpour
finpour
4.2 Algorithme
Algorithme de la procédure triangle :
0) DEF FN triangle (var mat : matrice ; n : entier)
41
1) pour ligne de 1 à n faire
pour colonne de 1 à ligne faire
si (ligne = colonne) ou (colonne = 1) alors
mat [ligne,colonne] ← 1
sinon
mat[ligne,colonne] ← mat [ligne – 1,colonne – 1] + mat [ligne – 1, colonne]
finsi
finpour
finpour
2) fin
4.3 Programme
procedure triangle (var mat : matrice ; n : integer) ;
begin
for ligne :=1 to n do
for colonne :=1 to ligne do
begin
if (ligne=colonne) or (colonne=1) then
mat[ligne,colonne] :=1
else
mat[ligne,colonne] := mat [ligne – 1,colonne – 1] + mat [ligne – 1, colonne] ;
end ;
end ;
42
5. Suite de Fibonacci
La suite de Fibonacci est définie comme suit :
U0 = 1
U1 = 1
pour tout n≥2 Un = Un-1+Un-2
Analyser un module qui évalue le nème terme de cette suite.
5.1 Analyse
Analyse de la fonction fibonacci :
DEF FN fibonacci (n : entier) : entier
résultat = fibonacci ← s
u 0 ← 1
s= u1 ← 1  pour i de 1 à n faire
 s ← 0 
s ← u0 + u1
u0 ← u1
u1 ← s
finpour
5.2 Algorithme
Algorithme de la fonction fibonacci :
0) DEF FN fibonacci (n : entier) : entier
1) u0 ← 1, u1 ← 1, s ← 0
s ← u0 + u1
u0 ← u1
u1 ← s
finpour
3) fibonacci ← s
4) fin
43
5.3 Programme
function fibonacci (n :integer) :integer ;
var u0,u1,i :integer ;
begin
u0 := 1 ; u1 := 1 ; s := 0 ;
for i :=1 to n do
begin
s := u0 + u1 ;
u0 := u1 ;
u1 := s ;
end ;
fibonacci : = s ;
end ;
44
6. Nombre d’or
Le nombre d’or est le solution positive de l’équation : x2-x-1=0, il est égal à
1+ 5
. Ce nombre est historiquement rencontré dans plusieurs cas (voir manuel
2
scolaire page 149). On peut définir ce nombre en utilisant la suite de Fibonacci
par le rapport du terme Un+1 divisé par le terme précédant Un.
U n +1
λ=
Un
Analyser un module qui calcule le nombre d’or à une précision e donnée.
6.1 Analyse
Analyse de la fonction nbr_or :
DEF FN nbr_or (e : réel) : réel
résultat = nbr_or ← s
u1 ← 1 
s=   répéter
u 2 ← 1
U ← U1 + U2
s1 ← U2 / U1
s ← U/U2
U1 ← U2
U2 ← U
jusqu’à abs(s-s1)<e
6.2 Algorithme
Algorithme de la fonction nbr_or :
0) DEF FN nbr_or (e : réel) : réel
1) u1 ← 1 , u2 ←1
2) répéter
U ← U1 + U2
s1 ← U2 / U1
s ← U/U2
U1 ← U2
45
U2 ← U
jusqu’à abs(s-s1)<e
3) nbr_or ← s
4) fin
6.3 Programme
function nbr_or(e:real):real;
begin
u1:=1; u2:=1;
repeat
u:=u1+u2;
s1:=u2/u1;
s:=u/u2;
u1:=u2;
u2:=u;
until abs(s-s1)<e;
nbr_or:= s;
end;
46
Cinquième chapitre : Algorithmes Arithmétiques
xlvii
1. Introduction
L’arithmétique est une branche mathématique qui s’intéresse aux relations
entre les nombres. Dans ce chapitre nous allons étudier quelques algorithmes
arithmétiques tels que le calcul du PGCD, et les règles de divisibilité.
2. Calcul du PGCD
On veut calculer le P.G.C.D de deux entiers naturels non nuls en utilisant la
méthode de différence. Proposez une solution récursive.
2.1 Analyse
DEF FN pgcd (a,b : entier) : entier
résultat = pgcd ← p
p = [] si a = b alors p ← a
sinon si a > b alors p ← FN pgcd (a-b,b)
sinon p ← FN pgcd (a,b-a)
finsi
finsi
2.2 Algorithme
0) DEF FN pgcd (a,b : entier) : entier
1) si a = b alors p ← a
sinon si a > b alors p ← FN pgcd (a-b,b)
sinon p ← FN pgcd (a,b-a)
finsi
finsi
2) pgcd ← p
3) fin
2.3 Programme
function pgcd (a,b : integer) :integer ; else if a > b then p := pgcd(a-b,b)
var p : integer ; else p := pgcd (a,b-a) ;
begin pgcd := p ;
if a = b then p := a end ;
48
3. Calcul de Apn
On veut calculer l’arrangement de p parmi n éléments ( Apn ).
3.1 Analyse
DEF FN a(n,p :entier) : réel
résultat = a ← FN fact(n) / FN fact (n-p)
DEF FN fact (x :entier) : entier
résultat = fact ← f
f = [f ← 1] pour i de 1 à x faire
f←f*i
finpour
3.2 Algorithme
Fonction a :
0) DEF FN a(n,p :entier) : réel
1) a ← FN fact(n) / FN fact (n-p)
2) fin
Fonction fact :
0) DEF FN fact (x :entier) : entier
1) f ← 1
2) pour i de 1 à x faire
f←f*i
finpour
3) fin
3.3 Programme
function a(n,p :integer) : real ; f := f * i ;
var i,f :integer ; fact := f ;
function fact(x :integer) :integer ; end ;
begin begin
f :=1 ; a :=fact(n)/fact(n-p) ;
for i :=1 to x do end ;
49
4. Calcul de C pn
On veut calculer la combinaison de p parmi n éléments ( C pn ).
4.1 Analyse
DEF FN c(n,p :entier) : réel
résultat = c ← FN a (n,p) / FN fact(p)
4.2 Algorithme
0) DEF FN c(n,p :entier) : réel
1) c ← FN a (n,p) / FN fact(p)
2) fin
4.3 Programme
function c (n,p :integer) : real ;
begin
c := a(n,p) / fact(p) ;
end ;
5. Règles de divisibilité
Nous allons vérifier la divisibilité des grands nombres par quelques nombres
(3, 5, 7, 11 etc.) sans utiliser les opérateurs div et mod. Parce que les grands
nombres (nombre de chiffres > 12) ne peuvent pas être définies comme des
entiers ou entiers longs.
Par exemple un nombre est divisible par 3 si la somme de ses chiffres est
divisible par 3.
5.1 Analyse
DEF FN div3 ( ch : string ) : booléen
résultat = div3 ← test
test = [test ← faux] si somme mod 3 = 0 alors
test ← vrai
finsi
somme = [somme ← 0] pour i de 1 à long(ch) faire
50
valeur (ch[i],n ,e)
somme ← somme + n
finpour
5.2 Algorithme
0) DEF FN div3 ( ch : string ) : booléen
1) somme ← 0
2) pour i de 1 à long(ch) faire
valeur (ch[i],n ,e)
somme ← somme + n
finpour
3) test ← faux
4) si somme mod 3 = 0 alors
test ← vrai
finsi
5) div3 ← test
6) fin
5.3 Programme
function div3 (ch : strng) :boolean ; val(ch[i],n,e) ;
var somme,i,n,e :integer ; somme := somme + n ;
test : boolean ; end ;
begin test := false ;
somme := 0 ; if somme mod 3 = 0 then test := true ;
for i :=1 to length(ch) do div3 := test ;
begin end ;
6. Conversion entre les bases de numération

Dans ce paragraphe nous allons convertir un nombre d’une base b1 en une
base b2. Avec 2≤ b1 ≤ 16 et 2 ≤ b2 ≤16.
6.1 Analyse
Analyse de la fonction conv_b1b2 :
DEF FN conv_b1b2 (ch_b1 : chaîne ; b1,b2 entier ) : chaîne de caractères
51
résultat = conv_b1b2 ← ch_b2
ch_b2 = []
ch_b2 ← FN conv_b2 (N_b10,b2)
N_b10 ← FN conv_10 (ch_b1,b1)
Analyse de la fonction conv_10 :
DEF FN conv_10 (ch_b1 :chaîne ; b1 :entier) : entierlong
résultat = conv_10 ← N_b10
N_b10 = [N_b10 ← 0] pour ide long(ch) à 1 (pas = -1) faire
si majus(ch[i]) dans [« A ».. « F »] alors
n ← ord(majus(ch[i]))-55
sinon valeur(ch[i],n,e)
finsi
N_b10 ← N_b10 +n * FN puissance(long(ch)-i,b1)
finpour
Analyse de la fonction conv_b2 :
DEF FN conv_b2 (n_10 : entierlong ; b2 : entier) : chaîne
résultat = conv_b2 ← ch_b2
ch_b2 = [ch_b2 ← « »] répéter
r ← n_10 mod b2
si r ≥ 10 alors ch_r ← majus(chr(55+r))
sinon convch(r,ch_r)
finsi
ch_b2 ← ch_r+ch_b2
n_10 ← n_10 div b2
jusqu’à (n_10 = 0)
6.2 Algorithme
Algorithme de la fonction conv_b1b2 :
0) DEF FN conv_b1b2 (ch_b1 : chaîne ; b1,b2 entier ) : chaîne de caractères
1) N_b10 ← FN conv_10 (ch_b1,b1)
2) ch_b2 ← FN conv_b2 (N_b10,b2)
3) conv_b1b2 ← ch_b2
52
4) fin
Algorithme de la fonction conv_10 :
0) DEF FN conv_10 (ch_b1 :chaîne ; b1 :entier) : entierlong
1) N_b10 ← 0
2) pour ide long(ch) à 1 (pas = -1) faire
si majus(ch[i]) dans [« A ».. « F »] alors
n ← ord(majus(ch[i]))-55
sinon valeur(ch[i],n,e)
finsi
N_b10 ← N_b10 +n * FN puissance(long(ch)-i,b1)
finpour
3) conv_10 ← N_b10
4) fin
Algorithme de la fonction conv_b2 :
0) DEF FN conv_b2 (n_10 : entierlong ; b2 : entier) : chaîne
1) ch_b2 ← « »
2) répéter
r ← n_10 mod b2
si r ≥ 10 alors ch_r ← majus(chr(55+r))
sinon convch(r,ch_r)
finsi
ch_b2 ← ch_r+ch_b2
n_10 ← n_10 div b2
jusqu’à (n_10 = 0)
3) conv_b2 ← ch_b2
4) fin
6.3 Programme
program conversion;
uses wincrt; procedure saisir;
var begin
i,j,e,x,n10,b1,b2:integer; repeat
chb1,chb2:string; writeln(' Donner les bases b1 et b2: ');
53
readln(b1,b2);
until (b1 in [2..16]) and( b2 in [2..16]); function conv_10b2(n10,b2:integer):string;
writeln(' Donner un nombre dans la base ', b1); var ch_r:string;
readln(chb1); r:integer;
end; begin
chb2:='';
function puiss(a,b1:integer):integer; repeat
var z:integer; r:= n10 mod b2;
begin if r>=10 then ch_r :=upcase(chr(55+r))
z:=1; else str(r,ch_r);;
for j:=1 to a do chb2:=ch_r+chb2;
z:= z*b1; n10:= n10 div b2;
puiss:=z; until n10=0;
end; conv_10b2:=chb2;
end;
function
conv_b110(b1:integer;chb1:string):longint; function conv_b1b2(b1,b2:integer;
begin chb1:string):string;
n10:=0; begin
for i:= length(chb1) downto 1 do N10:= conv_b110(b1,chb1);
begin chb2:= conv_10b2(n10,b2);
if upcase(chb1[i]) in ['A'..'F'] then conv_b1b2:=chb2;
x:=ord(upcase(chb1[i])) - 55 end;
else begin
val(chb1[i],x,e); saisir;
n10:=n10+x* puiss(length(chb1)-i,b1); writeln('(',chb1,')',b1,'=(',conv_b1b2(b1,b2,chb1),')',b2)
end; ;
conv_b110:=n10; end.
end;
54
Sixième chapitre : Algorithmes d’approximation
lv
1. Introduction
L’approximation est l’évaluation d’une grandeur à une valeur approchée à une
précision donnée. Dans ce chapitre nous allons voir quelques cas d’approximation
tels que le calcul d’aire, et la recherche d’un point fixe d’une fonction...
2. Calcul de quelques constantes

Parmi ces constantes on trouve le nombre Π et le nombre de Neper e.
2.1 ConstanteΠ
2.1.1 Méthode de Wallis
La constante Π peut être calculée par la formule de Wallis :
π 2 2 4 4
= * * * * ...
2 1 3 3 5
2.1.2 Méthode d’Euler
La constante Π peut être calculée par la formule d’Euler :
π2 1 1
= 1+ + + ...
6 2 2 32
2.2 Constante e (nombre de Neper)

Le nombre de Neper (e) peut être calculé par la formule suivante :
1 2
e = 1 + + + ...
1! 2!
56
3. Point fixe d’une fonction
3.1 Principe
Le point fixe d’une fonction f est défini par : f(x) = x . C’est l’intersection de la
courbe de f avec la première bissectrice ( y = x ).
Courbe d’une fonction

n’admettant pas un point Première bissectrice (y=x)
fixe
Courbe de f
→
j
o →
i Point fixe
Remarquons bien qu’il y a des fonctions qui n’admettent pas de point fixe. Pour
savoir si une fonction f admet un point fixe, on définit une suite récurrente
Un+1=f(Un), si cette suite est convergente, alors la fonction f admet un point fixe.
Pour chercher ce point fixe, on choisit un point de départ et on suit la courbe de
f jusqu’à arriver à un point fixe.
3.2 Analyse
DEF FN point_fixe (x0,eps : réel): réel
Résultat = point_fixe ← x1
x1 = [ x1 ← x0 ] répéter
x0 ← x1
x1 ← FN f(x1)
jusqu'à (abs(x0 – x1)< eps)
3.3 Algorithme
0) DEF FN point_fixe (x0,eps : réel): réel
1) x1 ← x0
57
2) répéter
x0 ← x1
x1 ← FN f(x1)
jusqu'à (abs(x0 – x1)< eps)
3) point_fixe ← x1
4) fin
3.1 Programme
function point_fixe (x0,eps: real):real;
var x1:real;
begin
x1:=x0;
repeat
x0 := x1;
x1 := f(x1);
until (abs(x1 – x0)< eps);
point_fixe := x1;
end;
58
4. Calcul d’aire
Le calcul d’une surface limitée par une courbe d’une fonction f quelconque et
l’axe des abscisses entre deux points a et b ne peut pas être réalisé directement
puisque cette surface ne forme pas une forme géométrique régulière. On doit donc
calculer une valeur approchée de cette surface en utilisant une méthode comme :
4.1 Méthode des rectangles

4.1.1 Principe
On veut calculer la surface S limitée par l’axe des abscisses et la courbe de f
entre deux points a et b.
f(a) f(x)
f(b)
a b
Pour cela on divise l’intervalle [a,b] en n rectangles. Il suffit ensuite de calculer

la somme de ces rectangles pour trouver une valeur approchée de la surface S
recherchée.
La surface d’un rectangle n° i est : S i = f ( xi ) * h ,
h b−a
avec xi = ai + , ai = a + i * h et h = .
2 n
4.1.2 Analyse
DEF FN rect (a,b:réel ; n:entier):réel
Résultat = rect ← somme
59
 
 somme ← 0
 
b−a 
somme= h ← pour i de 1 à n faire
 n 
 h 
x ← a + 
 2 
somme ← somme + f(x) * h
x←x+h
fin pour
4.1.3 Algorithme
0) DEF FN rect(a,b:réel;n:entier):réel
1) somme ← 0
2) h ← (b – a) / n
3) x ← a + h / 2
somme ← somme + f(x) *h
x←x+h
finpour
5) rect ← somme
6) fin
4.1.4 Programme
function rect(a,b :real ; n : integer) :real ; begin
var x,h,somme :real ; somme :=somme + (f(x)*h ;
begin x :=x+h ;
somme :=0 ; end ;
h := (b – a ) / n; rect :=somme ;
x :=(a+h)/2 ; end ;
for i :=1 to n do
60
4.2 Méthode des trapèzes
4.1.1 Principe
On veut calculer la surface S limitée par l’axe des abscisses et la courbe de f
entre deux points a et b.
f(a) f(x)
f(b)
a b
Pour cela on divise l’intervalle [a,b] en n trapèzes. Il suffit ensuite de calculer

la somme de ces trapèzes pour trouver une valeur approchée de la surface S
recherchée.
f(
f ( ai ) + f ( ai + h )
La surface d’un trapèze n° i est : S i = *h ,
2
b−a
avec ai = a + i * h et h = .
n
4.1.2 Analyse
DEF FN trap (a,b:réel ; n:entier):réel
Résultat = trap ← somme
 somme ← 0
 b − a 
somme= h ← pour i de 1 à n faire
 n 
x ← a 
 
61
f ( x) + f ( x + h)
somme ← somme + *h
2
x←x+h
fin pour
4.1.3 Algorithme
0) DEF FN trap (a,b:réel ; n:entier):réel
1) somme ← 0
2) h ← (b – a ) / n
3) x ← a
somme ← somme + f ( x) + f ( x + h) / 2 * h
x←x+h
fin pour
5) trap ← somme
6) fin
4.1.4 Programme
function trap(a,b :real ; n : integer) :real ;
var x,h,somme :real ;
begin
somme :=0 ;
h := (b – a ) / n;
x :=a ;
for i :=1 to n do
begin
somme :=somme + (f(x)+f(x+h))/2*h ;
x :=x+h ;
end ;
trap :=somme ;
end ;
62
Septième chapitre : Algorithmes Avancés
lxiii
1. Algorithme de tri rapide
1.1 Principe
Le tri rapide consiste à choisir un pivot (élément du tableau) et le mettre à sa
place définitive (tous les éléments inférieurs ou égaux seront à sa gauche, et tous
ceux qui sont supérieurs seront à sa droite). Ensuite nous recommençons
récursivement le traitement de deux sous tableaux (à gauche et à droite du
pivot).
Choix du pivot : le choix du pivot est très important. Le choix optimal est de
telle sorte que les deux sous tableaux contiennent le même nombre d’éléments.
Mais c’est impossible de savoir d’avance la valeur médiane du tableau. On peut
choisir le premier élément, ou bien le dernier.
Exemple : soit un tableau t :
10 7 14 8 19 2 1 33 4 12
Soit le pivot l’élément n°1 : 10
1ère étape :
10 7 14 8 19 2 1 33 4 12
t[2] ≤ pivot, on passe à t[3], t[3] ≥ pivot
2ème étape :
10 7 14 8 19 2 1 33 4 12
t[d] ≥ pivot, on passe à t[d – 1], t[d – 1] ≤ pivot donc on permute t[2] et t[d – 1].
10 7 4 8 19 2 1 33 14 12
On continue à partir de la 4ème position :
3ème étape :
10 7 4 8 19 2 1 33 14 12
t[4] ≤ pivot, on passe à t[5], t[5] ≥ pivot
4ème étape :
10 7 4 8 19 2 1 33 14 12
t[d – 2] ≥ pivot, on passe à t[ d – 3], t[ d – 3] ≤ pivot donc on permute t[d – 3] et
t[5].
10 7 4 8 1 2 19 33 14 12
On continue à partir de la 6ème position :
64
5ème étape :
10 7 4 8 1 2 19 33 14 12
t[6] ≤ pivot, et d – 4 = 6 (les deux compteurs de gauche et de droite se
rencontrent). Donc on permute t[6] et pivot.
2 7 4 8 1 10 19 33 14 12
Ainsi le pivot est à sa place définitive (tous les éléments à sa gauche sont
inférieurs ou égaux et tous ceux de droite sont supérieurs).
On recommence ce même traitement pour les deux sous tableaux séparées par
l’ancien pivot. Pour chaque sous tableau, on prend le premier élément comme
pivot.
2 7 4 8 1 10 19 33 14 12
65
1.2. Analyse
Analyse de la procédure tri_rapide :
DEF PROC tri_rapide (var t :tab ; deb,fin : entier)
Résultat = t_trié
t_trié = [] Si deb < fin alors
i ← deb
j ← fin
[ ] tantque i ≤ j faire
[ ] tantque (i ≤ fin) et (t[deb]>t[i]) faire
i ← i +1
fin tantque
[ ] tantque (deb+1 ≤ j) et (t[deb] ≤t[j]) faire
j←j–1
fin tantque
[ ] si j > i alors
Proc permut (t[i],t[j])
i←i+1
j←j–1
finsi
fin tantque
Proc permut(t[deb],t[j])
Proc tri_rapide (t, deb , j – 1)
Proc tri_rapide (t, j + 1, fin)
Finsi
66
1.3 Algorithme
0) DEF PROC tri_rapide (var t :tab ; d,g :entier )
1) Si deb < fin alors
i ← deb
j ← fin
tantque i ≤ j faire
tantque (i <= fin) et (t[deb]>t[i]) faire
i ← i +1
fin tantque
tantque (deb+1 <= j) et (t[deb] <=t[j]) faire
j←j–1
fin tantque
si j > i alors
Proc permut (t[i],t[j])
i←i+1
j←j–1
finsi
fin tantque
Proc permut(t[deb],t[j])
Proc tri_rapide (t, deb , j – 1)
Proc tri_rapide (t, j + 1, fin)
Finsi
2) fin
67
2. Tours de Hanoi
2.1 Définition et principe

Le problème des tours de Hanoï consiste à déplacer n disques de diamètres
différents deux à deux d’un premier piquet vers un deuxième en utilisant un
troisième piquet intermédiaire. Ce déplacement est exercé en respectant les
règles suivantes :
♣ Ne déplacer q’un disque à la fois
♣ Ne déplacer que le disque situé en haut
♣ Ne déposer un disque que sur un autre de diamètre inférieur
Piquet A Piquet B Piquet C
Disques
On veut déplacer les disques situés autour du piquet A vers le piquet B en

utilisant le piquet C comme piquet intermédiaire en faisant le minimum de
déplacements.
2.2 Analyse
Analyse de la procédure hanoi :
DEF PROC hanoi (n, a, b, c : entier)
Résultat = affichage des déplacements
[ ] si n > 0 alors
PROC hanoi (n – 1,a,c,b)
Écrire (« disque autour du piquet »,a, « vers le piquet »,c)
PROC hanoi (n – 1,b,a,c)
finsi
68
2.3 Algorithme
Algorithme de la procédure hanoi :
0) DEF PROC hanoi (n, a, b, c : entier)
1) si n > 0 alors
PROC hanoi (n – 1,a,c,b)
Écrire (« disque autour du piquet »,a, « vers le piquet »,c)
PROC hanoi (n – 1,b,a,c)
finsi
3) fin
69
3. Problème de huit dames

Le problème de huit dames (reines) consiste à placer huit dames d’un jeu
d’échec sur un échiquier de 8 x 8 cases sans que deux reines ne puissent se
menacer. Sachant qu’une reine menace une autre si elles sont sur la même ligne,
la même colonne ou la même diagonale.
: Reine
En général on veut placer n reines sur un échiquier de n x n cases. Bien sur
sans qu’une reine menace l’autre.
Exemple : (1ère solution)
70
(2ème solution)
Pour 8 reines sur un échiquier 8 x 8 cases, il y en a 92 solutions possibles.

Nous allons représenter la position d’une reine par le caractère « X », et une case
libre par le caractère « 0 ». De plus, nous allons utiliser un fichier texte pour y
sauvegarder toutes les solutions. Nous allons définir un tableau de 8 cases pour
stocker les positions (i représente le numéro de la ligne et t[i] le numéro de la
colonne). On définit une procédure place_reine qui place les reines une à une.
Bien sur chaque reine sera placée sur une ligne différente, donc la première reine
sera placée dans la première case et ainsi de suite (donc la case de la première
reine sera (1, t[1]), la deuxième (2,t[2]) etc.). La procédure place_reine est
récursive qui une fois place la reine n°i est appelée pour placer la reine n°i+1.
71
3.2 Analyse
Analyse de la procédure place_reine :
DEF PROC place_reine (var f : texte ; t : tab ; nr : entier)
Résultat = Proc remplir (f, t, n)
(t,n) = [ ] pour i de 1 à n faire
[ ] pour j de 1 à nr faire
[ ] si ((t[j] = i) ou (abs(t[j] – i ) = abs (j – nr))) alors
aller à suivant
finsi
finpour
t[nr] ← i
Proc place_reine (f, t, nr + 1)
suivant :
finpour
[ ] si nr = n + 1 alors
Proc remplir (f, t, n) { afficher cette solution }
s←s+1 { nombre de solutions }
finsi
n = constante { nombre de reines }
DEF PROC remplir (var f : texte ; t : tab ; n : entier)
Résultat = f
f = [ ] pour i de 1 à n faire
[ ] pour j de 1 à n faire
[ ] si (t[i] = j) alors
Écrire (f, « X »)
sinon Écrire (f, « 0 »)
finsi
Écrire_nl (f)
finpour
72
3.3 Algorithme
Algorithme de la procédure place_reine :
0) DEF PROC place_reine (var f : texte ; t : tab ; nr : entier)
1) si nr = n + 1 alors
Proc remplir (f, t, n)
s←s+1
finsi
pour j de 1 à nr faire
si ((t[j] = i) ou (abs(t[j] – i ) = abs (j – nr))) alors
aller à suivant
finsi
finpour
t[nr] ← i
Proc place_reine (f, t, nr + 1)
suivant :
finpour
3) fin
Tableau de déclaration des objets locaux :
Objet Type / Nature Rôle
i entier Compteur
j entier Compteur
suivant étiquette Étiquette pour sauter un bloc d’instructions
remplir procédure Remplir le fichier texte

0) DEF PROC remplir (var f : texte ; t : tab ; n : entier)
pour j de 1 à n faire
si (t[i] = j) alors
Écrire (f, « X »)
sinon Écrire (f, « 0 »)
73
finsi
Écrire_nl (f)
finpour
2) fin
Tableau de déclaration des objets locaux :
Objet Type / Nature Rôle
i entier compteur
j entier compteur
74
4. Problème de voyageur de commerce

Le problème de voyageur de commerce est issu du faite qu’un voyageur de
commerce, doit visiter n villes. Il doit passer par chaque ville une seule fois. Ce
voyageur commence par une ville quelconque et termine par retourner à cette
même ville. Le but est de minimiser la distance parcourue par ce voyageur. Pour
cela, on définit un tableau pour les noms des villes, une matrice carrée pour les
distances entre les villes, un tableau pour vérifier si une ville est visitée ou non,
et un tableau pour les villes visitées en ordre de visite.
4.2 Analyse
Résultat = PROC affiche (vi_visitées , n , nom_villes)
(n , nom_villes) = PROC saisir (n , nom_villes)
vi_visitées = PROC trajet (vi_visitées , distances , vi_dep , vis_test , n)
distances = PROC remplir (distances , n )
(vi_dep , vis_test ) = PROC init ( vi_dep , vis_test)
Analyse de la procédure affiche :
DEF PROC affiche (vi_visitées : tab_vis ; n : entier ; nom_villes : tab_nom)
Résultat = affichage
[ ] pour i de 1 à n faire
Écrire (nom_villes[vi_visitées[i]])
fin pour
Écrire (nom_villes[vi_visitées[1]])
Analyse de la procédure saisir :
DEF PROC saisir (var n : entier ; var nom_villes : tab_nom)
Résultat = (n , nom_villes)
n= [ ] répéter
n = donnée (« donner le nombre de villes à visiter »)
jusqu’ à n dans [1 .. man_nb_villes]
nom_villes = [ ] pour i de 1 à n faire
nom_villes [i] = donnée (« donner le nom de la ville N°»,i)
75
fin pour
Analyse de la procédure trajet :
DEF PROC trajet (var vi_visitées : tab_vis , distances : mat_dist , vi_dep :
entier , vis_test : tab_test_vis , n : entier)
Résultat = vi_visitées
vi _ visitées[1] ← vi _ dep 
vi_visitées =   pour i de 2 à n faire
vis _ test[vi _ dep] ← vrai 
j ← FN vil_pro_non_visi (i , distances , vis_test , n)
finpour
vi_visitées[i] ← j
vis_test[j] ← vrai
76
4.3 Algorithme
0) début
1) PROC saisir (n , nom_villes)
2) PROC remplir (distances , n )
3) PROC init ( vi_dep , vis_test)
4) PROC trajet (vi_visitées , distances , vi_dep , vis_test , n)
5) PROC affiche (vi_visitées , n , nom_villes)
6) fin
Algorithme de la procédure saisir :
0) DEF PROC saisir (var n : entier ; var nom_villes : tab_nom)
1) répéter
écrire (« donner le nombre de villes à visiter »)
lire (n)
jusqu’ à n dans [1 .. man_nb_villes]
écrire (« donner le nom de la ville N°»,i)
lire (nom_villes [i])
fin pour
3) fin
0)
Algorithme de la procédure init :
0)
Algorithme de la procédure trajet :
0) DEF PROC trajet (var vi_visitées : tab_vis , distances : mat_dist , vi_dep :
entier , vis_test : tab_test_vis , n : entier)
1) vi_visitées [1]← vi_dep
2) vis_test [vi_dep] ← vrai
j ← FN vil_pro_non_visi (i , distances , vis_test , n)
finpour
77
4) vi_visitées[i] ← j
5) vis_test[j] ← vrai
6) fin
Algorithme de la procédure affiche :
0) DEF PROC affiche (vi_visitées : tab_vis ; n : entier ; nom_villes : tab_nom)
Écrire (nom_villes[vi_visitées[i]])
fin pour
2) Écrire (nom_villes[vi_visitées[1]])
3) fin
78
Table de Matières
Préface ________________________________________________________________________________ii
Remerciement_________________________________________________________________________ iii
Premier Chapitre : Enregistrement et Fichiers___________________________________________ iv
1. Enregistrements ___________________________________________________________________ 5
1.1 Définition _____________________________________________________________________ 5
1.2 Déclaration ____________________________________________________________________ 5
1.3 Utilisation des Enregistrements _________________________________________________ 6
2. Fichiers __________________________________________________________________________ 10
2.1 Introduction __________________________________________________________________ 10
2.2 Définition ____________________________________________________________________ 10
2.3 Organisation des fichiers ______________________________________________________ 10
2.4 Types d’accès _________________________________________________________________ 11
Deuxième Chapitre : Récursivité_______________________________________________________xxii
1. Définition ________________________________________________________________________ 23
2. Principe__________________________________________________________________________ 23
3. Application _______________________________________________________________________ 23
3.1 analyse _______________________________________________________________________ 23
3.2 algorithme ____________________________________________________________________ 24
3.3 Programme ___________________________________________________________________ 24
Troisième chapitre : Algorithmes de Tri ________________________________________________xxv
1. Tri par Insertion __________________________________________________________________ 26
1.1 Principe ______________________________________________________________________ 26
1.2 Analyse ______________________________________________________________________ 26
1.3 Algorithme ___________________________________________________________________ 26
1.4 Programme ___________________________________________________________________ 27
1.5 Interprétation ________________________________________________________________ 27
2. Tri Shell _________________________________________________________________________ 28
2.1 Principe ______________________________________________________________________ 28
2.2 Analyse ______________________________________________________________________ 28
2.3 Algorithme ___________________________________________________________________ 29
2.4 Programme ___________________________________________________________________ 29
2.5 Interprétation ________________________________________________________________ 30
3. Tri par fusion_____________________________________________________________________ 31
3.1 Principe ______________________________________________________________________ 31
3.2 Analyse ______________________________________________________________________ 31
3.3 Algorithme ___________________________________________________________________ 32
lxxix
3.4 Programme ___________________________________________________________________ 33
3.5 Interprétation ________________________________________________________________ 33
Quatrième chapitre : Algorithmes Récurrents____________________________________________ 34
1. Introduction ______________________________________________________________________ 35
1.1 Définition ____________________________________________________________________ 35
2. Calcul de somme__________________________________________________________________ 35
2.1 Analyse ______________________________________________________________________ 35
2.2 Algorithme ___________________________________________________________________ 35
2.3 Programme ___________________________________________________________________ 36
3. Suite de Thue Morse ______________________________________________________________ 36
3.1 Analyse ______________________________________________________________________ 36
3.2 Algorithme ___________________________________________________________________ 38
3.3 Programme ___________________________________________________________________ 39
4. Triangle de Pascal ________________________________________________________________ 41
4.1 Analyse ______________________________________________________________________ 41
4.2 Algorithme ___________________________________________________________________ 41
4.3 Programme ___________________________________________________________________ 42
5. Suite de Fibonacci ________________________________________________________________ 43
5.1 Analyse ______________________________________________________________________ 43
5.2 Algorithme ___________________________________________________________________ 43
5.3 Programme ___________________________________________________________________ 44
6. Nombre d’or ______________________________________________________________________ 45
6.1 Analyse ______________________________________________________________________ 45
6.2 Algorithme ___________________________________________________________________ 45
6.3 Programme ___________________________________________________________________ 46
Cinquième chapitre : Algorithmes Arithmétiques ______________________________________ xlvii
1. Introduction ______________________________________________________________________ 48
2. Calcul du PGCD __________________________________________________________________ 48
2.1 Analyse ______________________________________________________________________ 48
2.2 Algorithme ___________________________________________________________________ 48
2.3 Programme ___________________________________________________________________ 48
3. Calcul de Apn _____________________________________________________________________ 49

3.1 Analyse ______________________________________________________________________ 49
3.2 Algorithme ___________________________________________________________________ 49
3.3 Programme ___________________________________________________________________ 49
4. Calcul de C pn _____________________________________________________________________ 50
4.1 Analyse ______________________________________________________________________ 50
4.2 Algorithme ___________________________________________________________________ 50
lxxx
4.3 Programme ___________________________________________________________________ 50
5. Règles de divisibilité ______________________________________________________________ 50
5.1 Analyse ______________________________________________________________________ 50
5.2 Algorithme ___________________________________________________________________ 51
5.3 Programme ___________________________________________________________________ 51
6. Conversion entre les bases de numération __________________________________________ 51
6.1 Analyse ______________________________________________________________________ 51
6.2 Algorithme ___________________________________________________________________ 52
6.3 Programme ___________________________________________________________________ 53
Sixième chapitre : Algorithmes d’approximation _________________________________________ lv
1. Introduction ______________________________________________________________________ 56
2. Calcul de quelques constantes _____________________________________________________ 56
2.1 ConstanteΠ___________________________________________________________________ 56
2.2 Constante e (nombre de Neper)_________________________________________________ 56
3. Point fixe d’une fonction ___________________________________________________________ 57
3.1 Principe ______________________________________________________________________ 57
3.2 Analyse ______________________________________________________________________ 57
3.3 Algorithme ___________________________________________________________________ 57
3.1 Programme ___________________________________________________________________ 58
4. Calcul d’aire______________________________________________________________________ 59
4.1 Méthode des rectangles ________________________________________________________ 59
4.2 Méthode des trapèzes__________________________________________________________ 61
Septième chapitre : Algorithmes Avancés______________________________________________ lxiii
1. Algorithme de tri rapide___________________________________________________________ 64
1.1 Principe ______________________________________________________________________ 64
1.2. Analyse ______________________________________________________________________ 66
1.3 Algorithme ___________________________________________________________________ 67
2. Tours de Hanoi ___________________________________________________________________ 68
2.1 Définition et principe __________________________________________________________ 68
2.2 Analyse ______________________________________________________________________ 68
2.3 Algorithme ___________________________________________________________________ 69
3. Problème de huit dames ___________________________________________________________ 70
3.2 Analyse ______________________________________________________________________ 72
3.3 Algorithme ___________________________________________________________________ 73
4. Problème de voyageur de commerce ________________________________________________ 75
4.2 Analyse ______________________________________________________________________ 75
4.3 Algorithme ___________________________________________________________________ 77
lxxxi
Table de Matières __________________________________________________________________ lxxix
Annexes __________________________________________________________________________ lxxxiii
Annexe 1. Fonctions et procédures prédéfinies_____________________________________ lxxxiii
Annexe2. Table des codes ASCII _________________________________________________lxxxvii
Index _____________________________________________________________________________ lxxxix
lxxxii
Annexes
Annexe 1. Fonctions et procédures prédéfinies
MODULE SYNTAXE DESCRIPTION
ABS ABS(r):Real; renvoie la valeur absolue de r.
ARCTAN ARCTAN(r):Real; renvoie l'arc tangent de r.
COS COS(r):REAL; renvoie le cosinus de r.
EXP EXP(r):Real; renvoie l'exponentielle de r.
FRAC FRAC(r):Real; renvoie la partie fractionnaire de r.
INT INT(r):Real; renvoie la partie entière de r.
LN LN(r):Real; renvoie le logarithme népérien de r.
PI PI; renvoie la valeur du nombre pi.
SIN SIN(r):Real; renvoie le sinus de r.
SQR SQR(r):Real; renvoie le carré de r.
SQRT SQRT(r):Real; renvoie la racine carrée de r.
lxxxiii
CHR CHR(n):Char; renvoie le caractère de code ASCII n.
renvoie la position de ident dans son type;

ORD ORD(ident):LongInt; par exemple, ord ('A') renvoie 65 car A est le 65ème
caractère de la table ASCII.
renvoie le caractère successeur du caractère c dans la

SUCC SUCC(c) :Char ;
table des codes ASCII.
renvoie le caractère précédent du caractère c dans la

PRED PRED(c) :Char ;
table des codes ASCII.
UPCASE UPCASE(c):Char; renvoie la majuscule du caractère c.
ROUND ROUND(r) : LongInt; renvoie la valeur arrondie du réel r.
écrit nombre (entier ou réel) dans chaîne de type String

STR STR (nombre[:i[:j]], chaîne); avec éventuellement un total de i caractères dont j après
la virgule.
TRUNC TRUNC(r):LongInt; renvoie la partie entière du réel r.
transforme chaîne de type String en nombre (entier ou

VAL Val (chaîne,nombre,coderreur); réel) et place un code dans la variable coderreur de type
Integer; coderreur = 0 lorsque l'interprétation a réussi.
lxxxiv
CONCAT CONCAT (chaine1,chaine2,[,...]):String; équivalente à l'addition des chaînes de caractères.
renvoie une chaîne formée par les nombrecar caractères

COPY COPY (chaîne,position,nombrecar):String;
situés à partir de position dans chaîne.
supprime dans chaîne nombrecar caractères situés à

DELETE DELETE(chaîne,position,nombrecar);
partir de position.
INSERT INSERT (chaine1,chaine2,position); insère chaine1 dans chaine2 à partir de position.
LENGTH LENGTH (chaîne):Byte; renvoie la longueur de chaîne.
renvoie la position de la première occurrence de chaine1

POS POS (chaine1,chaine2):Byte;
dans chaine2 et 0 si chaine1 n'a pas été trouvée.
exécute nomb1:=nomb1-nomb2 où nomb1 et nomb2 sont

DEC DEC (nomb1[,nomb2]);
des entiers; la valeur par défaut de nomb2 est 1.
exécute nomb1:=nomb1+nomb2 où nomb1 et nomb2 sont

INC INC (nomb1[,nomb2]);
des entiers; la valeur par défaut de nomb2 est 1.
renvoie le nombre de paramètres spécifiés à l'appel du

PARAMCOUNT PARAMCOUNT:Word;
programme.
renvoie le paramètre numéro nomb spécifié à l'appel du

PARAMSTR PARAMSTR (nomb):String;
programme.
lxxxv
permet de sortir d'une procédure ou d'une fonction avant
EXIT EXIT;
sa fin.
permet de quitter le programme en envoyant un

HALT HALT (n);
ErrorLevel égal à n au DOS.
renvoie un nombre aléatoire entier entre 0 et nomb; si

RANDOM RANDOM [(nomb)]:Integer ou Real; nomb n'est pas précisé on obtient un nombre aléatoire
décimal entre 0 et 1.
RANDOMIZE RANDOMIZE; initialise le générateur de nombres aléatoires.
lxxxvi
Annexe2. Table des codes ASCII
Code Caractère Code Caractère Code Caractère Code Caractère Code Caractère
0 NUL 51 3 102 f 153 ™ 204 Ì
1 SQH 52 4 103 g 154 š 205 Í
2 STX 53 5 104 h 155 › 206 Î
3 ETX 54 6 105 i 156 œ 207 Ï
4 EOT 55 7 106 j 157 208 Ð
5 ENQ 56 8 107 k 158 ž 209 Ñ
6 ACK 57 9 108 l 159 Ÿ 210 Ò
7 BEL 58 : 109 m 160 211 Ó
8 BS 59 ; 110 n 161 ¡ 212 Ô
9 HT 60 < 111 o 162 ¢ 213 Õ
10 LF 61 = 112 p 163 £ 214 Ö
11 VT 62 > 113 q 164 ¤ 215 ×
12 FF 63 ? 114 r 165 ¥ 216 Ø
13 CR 64 @ 115 s 166 ¦ 217 Ù
14 SO 65 A 116 t 167 § 218 Ú
15 SI 66 B 117 u 168 ¨ 219 Û
16 DLE 67 C 118 v 169 © 220 Ü
17 DC1 68 D 119 w 170 ª 221 Ý
18 DC2 69 E 120 x 171 « 222 Þ
19 DC3 70 F 121 y 172 ¬ 223 ß
20 DC4 71 G 122 z 173 224 à
21 NAK 72 H 123 { 174 ® 225 á
22 SYN 73 I 124 | 175 ¯ 226 â
23 ETB 74 J 125 } 176 ° 227 ã
24 CAN 75 K 126 ~ 177 ± 228 ä
lxxxvii
25 EM 76 L 127 178 ² 229 å
26 SUB 77 M 128 € 179 ³ 230 æ
27 ESC 78 N 129 180 ´ 231 ç
28 FS 79 O 130 ‚ 181 µ 232 è
29 GS 80 P 131 ƒ 182 ¶ 233 é
30 RS 81 Q 132 „ 183 · 234 ê
31 US 82 R 133 … 184 ¸ 235 ë
32 83 S 134 † 185 ¹ 236 ì
33 ! 84 T 135 ‡ 186 º 237 í
34 " 85 U 136 ˆ 187 » 238 î
35 # 86 V 137 ‰ 188 ¼ 239 ï
36 $ 87 W 138 Š 189 ½ 240 ð
37 % 88 X 139 ‹ 190 ¾ 241 ñ
38 & 89 Y 140 Œ 191 ¿ 242 ò
39 ' 90 Z 141 192 À 243 ó
40 ( 91 [ 142 Ž 193 Á 244 ô
41 ) 92 \ 143 194 Â 245 õ
42 * 93 ] 144 195 Ã 246 ö
43 + 94 ^ 145 ‘ 196 Ä 247 ÷
44 , 95 _ 146 ’ 197 Å 248 ø
45 - 96 ` 147 “ 198 Æ 249 ù
46 . 97 a 148 ” 199 Ç 250 ú
47 / 98 b 149 • 200 È 251 û
48 0 99 c 150 – 201 É 252 ü
49 1 100 d 151 — 202 Ê 253 ý
50 2 101 e 152 ˜ 203 Ë 254 þ
255 ÿ
lxxxviii
Index
algorithme ..................................................... 24, 35 Nom_physique ..................................................... 13
Algorithme ..............................26, 29, 32, 69, 73, 77 objet........................................................................ 5
Algorithmique........................................................ 1 Objet....................................5, 6, 7, 9, 13, 19, 73, 74
alors ................16, 23, 24, 26, 31, 32, 36, 37, 38, 39 Ouverture..................................................14, 17, 18
Analyse26, 28, 31, 35, 36, 37, 41, 43, 45, 66, 68, pourii, 8, 10, 11, 13, 14, 18, 19, 26, 27, 28, 29, 30,
72, 75 31, 32, 33, 35, 36, 37, 38, 41
Association....................................14, 16, 19, 20, 21 Présentation...........................................12, 16, 19
Avancés .........................................................lv, lxiii Principe...............................................26, 28, 31, 64
bulles.................................................................... 66 PROC26, 27, 28, 29, 31, 32, 37, 38, 39, 68, 69, 72,
change.................................................................... 5 73, 75, 76, 77, 78
compteur .............................................................. 74 procédure14, 15, 16, 18, 20, 21, 26, 27, 28, 29, 31,
Conditionnelles...................................................xxv 37, 39, 41, 66, 68, 69, 71, 72, 73, 75, 76, lxxxvi
d’entrée................................................................. 23 Programmation ..................................................... 1
Déclaration ................................................... 5, 13 Programme ...............................................27, 29, 33
DEF...................................................................... 68 Programmes ..................................................... xlvii
DEF FN23, 24, 35, 36, 38, 41, 43, 45, 48, 49, 50, récurrent .............................................................. 35
51, 52, 53, 59, 60, 61, 62 récursivité ............................................................ 23
DEF PROC .............................................. 66, 67, 69 répéter .................................................31, 32, 36, 38
Définition............................................. 5, 10, 23, 35 résultats ............................................................... 35
Données................................................................. iv Rôle .....................................5, 6, 7, 9, 13, 19, 73, 74
Ecriture................................................................ 15 saisir .......................................39, 40, 53, 54, 75, 77
entier6, 7, 13, 17, 23, 24, 26, 27, 31, 32, 35, 36, 37, séquentielle ...............................................68, 70, 75
38, 39, 41, 43, 48, 49, 50, 51, 52, 53, 59, 60, 61, 62, si16, 19, 20, 21, 23, 24, 26, 27, 30, 31, 32, 36, 37,
66, 67, 68, 69, 72, 73, 74, 75, 76, 77, 78, lxxxiv, 38, 39, 41, 42, 48, 50, 51, 52, 53, 57, 68, 69, 70, 72,
lxxxvi 73, 75, lxxxv, lxxxvi
Expressions .......................................................... 10 Simples .............................................................. xxii
faire8, 14, 17, 26, 27, 28, 29, 31, 32, 35, 36, 37, 38, sinon .....................15, 23, 24, 31, 32, 36, 37, 38, 39
39, 41, 42, 43, 49, 50, 51, 52, 53, 60, 61, 62, 72, 73, sortie .................................................................... 23
75, 76, 77, 78 Tableau.......................................................... 13, 19
Fermeture ............................................................ 15 tantque..............................26, 27, 28, 29, 37, 38, 39
fin de fichier......................................................... 16 tri ..................................................64, 66, 67, 68, 69
finsi23, 24, 31, 32, 37, 38, 39, 41, 42, 48, 50, 51, Tri par fusion ...................................................... 31
52, 53, 68, 69, 72, 73, 74 Tri par Insertion.................................................. 26
fonction ................. 16, 17, 19, 20, 23, 35, 36, lxxxvi Tri Shell............................................................... 28
insertion............................................................... 67 Type ....................................5, 6, 7, 9, 13, 19, 73, 74
Interprétation .......................................... 27, 30, 33 Type/nature ...................................5, 6, 7, 9, 13, 19
itératives .............................................................. 34 types ......................................................5, 10, 11, 13
jusqu’à.....................................17, 28, 31, 32, 37, 38 valeur..................................................................... 5
Lecture ............................................................. 7, 15
Nature............................................................ 73, 74
Nom_logique............................................ 13, 14, 19
lxxxix

Algorithmique Et Programmation-4SI

Transféré par

Droits d'auteur :

Formats disponibles

Algorithmique Et Programmation-4SI

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Algorithmique Et Programmation-4SI

Transféré par

Droits d'auteur :

Formats disponibles

Algorithmique et Programmation

4ème Année Sciences Informatique

1 Copyright © Haiethem Elguediri 2010

champ_1 champ_2 champ_3 ... champ_n

Structure d’un enregistrement

Objet Type/nature Rôle

Objet Type/nature Rôle

1.3 Utilisation des Enregistrements

Objet Type/nature Rôle

En algorithmique et analyse En Pascal

1.3.4 Structure Avec ….. Faire

En algorithmique et analyse En Pascal

Objet Type/nature Rôle

Un fichier est un ensemble structuré de données de même type identifié

Structure d’un fichier

2.3 Organisation des fichiers

2.4 Types d’accès

D’après les manières d’organisation des fichiers, on peut déduire les

fins des blocs

Fichier à accès séquentiel

Accès direct : on peut directement accéder au bloc désiré juste en

fins des blocs

Fichier à accès direct

fins des blocs

Accès au fichier par le pointeur

R.A.M. Support de stockage

Fichier logique et fichier physique

2.4.1 Les fichiers à accès séquentiel :

Traitements sur les fichiers :

2.4.2 Les fichiers à accès direct :

Autres procédures et fonctions :

• Renommer un fichier : cette opération permet de renommer le fichier fourni

Remarque : pour utiliser l’unité « windos » en Pascal : uses wincrt,windos ;

• Chercher la fin de ligne : cette opération permet de savoir si le pointeur a

• Chercher la fin du fichier : cette opération permet de savoir si le pointeur a

• Ajouter : cette opération permet de positionner le pointeur à la fin du

Remarque : la variable doit être de type chaîne de caractères. Mais si on

Remarque : la variable doit être de type chaîne de caractères. Mais si on

module () module () module ()

3. Suite de Thue Morse

PROC remplir (f,t,n)

Analyser un module qui calcule le nombre d’or à une précision e donnée.

On veut calculer l’arrangement de p parmi n éléments ( Apn ).

On veut calculer la combinaison de p parmi n éléments ( C pn ).

6. Conversion entre les bases de numération

2. Calcul de quelques constantes

2.2 Constante e (nombre de Neper)

courbe de f avec la première bissectrice ( y = x ).

Courbe d’une fonction

4.1 Méthode des rectangles

Pour cela on divise l’intervalle [a,b] en n rectangles. Il suffit ensuite de calculer

La surface d’un rectangle n° i est : S i = f ( xi ) * h ,

Pour cela on divise l’intervalle [a,b] en n trapèzes. Il suffit ensuite de calculer

2.1 Définition et principe

Piquet A Piquet B Piquet C

On veut déplacer les disques situés autour du piquet A vers le piquet B en

3.1 Définition et principe

Pour 8 reines sur un échiquier 8 x 8 cases, il y en a 92 solutions possibles.

Algorithme de la procédure remplir :

4.1 Définition et principe