1. Méthodologie de conception d’un programme.............................................................................................................

2
1.1. Phase 1 : Conception fondamentale ou analyse des besoins :.................................................................................2
1.2. Phase 2 : Conception détaillée ou Spécification:.....................................................................................................2
1.3. Phase 3 : Codage......................................................................................................................................................4
1.4. Phase 4 : Intégration.................................................................................................................................................4
1.5. Phase 5 : Validation - Tests.....................................................................................................................................4
1.6. Phase 6: Exploitation..............................................................................................................................................4
2. ALGORITHMES..........................................................................................................................................................5
2.1. Définition.................................................................................................................................................................5
2.2. Exemple : Calcul d’interêt.......................................................................................................................................5
2.3. Méthodologie...........................................................................................................................................................6
2.4. Formalisation de l’algorithme..................................................................................................................................6
2.5. Langage de description............................................................................................................................................7
2.6. Exemple : Addition..................................................................................................................................................8
2.7. Exemple : Robot......................................................................................................................................................8
2.8. Exercice a faire : Raffinement.................................................................................................................................9
3. LA SEQUENCE............................................................................................................................................................9
3.1. Instructions...............................................................................................................................................................9
3.2. les instructions de lecture (d'entrée) notées:............................................................................................................9
3.4. les instructions d'assignation (d'affectation) représentées par...............................................................................10
3.5. Exemples................................................................................................................................................................10
3.6. Déclaratives............................................................................................................................................................10
3.7. Exo a faire ……………….....................................................................................................................................11
4. LES STRUCTURES REPETITIVES.........................................................................................................................11
4.1. Introduction............................................................................................................................................................11
4.2. La boucle « tant que »............................................................................................................................................11
4.3. Exemple de calcul de PGCD..................................................................................................................................12
4.5. La boucle " pour"...................................................................................................................................................14
4.7. La boucle " répéter ... jusqu'à "..............................................................................................................................16
4.8. Exercices................................................................................................................................................................16
4.9. Le choix multiple...................................................................................................................................................16
4.10. Exercices...........................................................................................................................................................17
5. LES TABLEAUX.......................................................................................................................................................17
5.1. Notion de tableau...................................................................................................................................................17
5.2. Exemple.................................................................................................................................................................18
5.3. Parcours partiel d'un tableau..................................................................................................................................19
5.4. Exemple.................................................................................................................................................................19
5.5. Parcours imbriqués.................................................................................................................................................20
5.6. Exemple.................................................................................................................................................................20
5.7. Tableaux multidimensionnels................................................................................................................................20
5.8. Tableaux à deux dimensions..................................................................................................................................21
5.9. Exemple : calcul de la somme...............................................................................................................................21
5.10. Recherche dichotomique..................................................................................................................................22
5.11. Exemple............................................................................................................................................................22
5.12. Une technique de tri d’un tableau....................................................................................................................22
5.13. Exercices...........................................................................................................................................................24
5.14. Exercices...........................................................................................................................................................25
5.15. Travaux dirigés.................................................................................................................................................27
5.16......................................................................................................................................................................................... 34
6. Fonctions et procédures............................................................................................................................................41
6.1. Définition...............................................................................................................................................................41
6.2. Exemple : Pseudo-code – Tri Bull.........................................................................................................................42
7. Les structures de données............................................................................................................................................43

1
 1. Méthodologie de conception d’un programme
L'absence de cette méthodologie conduit le plus souvent à des défaillances du programme. En effet,
on constate généralement que 60% des erreurs rencontrées lors de la mise en oeuvre d'un
programme sont des erreurs de conception algorithmique, et 40% de ces erreurs ne sont détectées
que pendant ou après les tests de validation.

La méthodologie est composée de 6 phases.

[Link] 1 : Conception fondamentale ou analyse des besoins :

Elle représente le point de départ de la phase de conception, elle permet à partir d'un cahier des
charges, d'élaborer les spécifications fonctionnelles du l'application (programmes) et de définir de
façon fonctionnelle, le comportement de votre application (par quel processus, dans quel domaine
d'application ?). FORMULER LE PROBLEME

CONNAITRE LE PROBLEME A TRAITER,

C'EST DEJA L'AVOIR RESOLU A MOITIE

[Link] 2 : Conception détaillée ou Spécification:

L'objectif de cette phase est de définir, de façon aussi précise que possible la spécification des
données et actions sur ces données intervenant dans votre application (programmes)

La spécification : c'est la description d'une action en terme d'état initial et d'état final.
Action spécifiée : abstraction sur laquelle on peut raisonner.

Les notions d'état initial et final ne pouvant s'exprimer qu'en termes d'état des objets manipulés par
les programmes (algorithmes).

Après avoir spécifié les données et vérifié qu'elles correspondent globalement au cahier des charges
défini dans la phase 1, on peut entreprendre la construction d'une solution.
La figure présentée ci-dessous illustre les étapes nécessaires à la mise en oeuvre d'une solution

2
La phase de conception détaillée est répartie en trois étapes :

¨ Une étape initiale de modélisation, où le problème à résoudre est représenté par un modèle
formel.

¨ Une étape de raisonnement rigoureux, où les règles de raisonnements sont surtout utilisées pour
construire une suite de modèles (modèles intermédiaires). Chaque modèle caractérise un élément de
solution.

¨ Une étape d'adaptation au problème initial, où une solution de ce problème est dérivée de la
solution formelle trouvée au niveau du modèle.

Il faut noter que ces étapes illustrent la démarche scientifique de conception quel que soit le
domaine d'application.

Comment s'applique la démarche de modélisation sur les méthodes de conception de programme.

La figure présentée ci-dessous illustre la démarche scientifique à suivre pour la conception de

programmes.

1.3. Phase 3 : Codage

Le codage est l'écriture d'un module dans un langage de programmation afin de le rendre
exécutable.

[Link] 4 : Intégration

Le rôle de la phase d'intégration est de traduire les spécifications du cahier des charges définitif en
instructions exécutables. L'intégration doit être réalisée module par module: la mise en oeuvre
progressive des unités de traitement (module ou programme) facilite la mise au point en isolant les
erreurs.

3
La construction doit être structurée pour permettre le test des modules en adoptant une approche
descendante. Les programmes sont ainsi testés individuellement, puis intégrés dans le contexte de
l'application, et toute erreur reste donc facilement localisable jusqu'au dernier programme intégré.

[Link] 5 : Validation - Tests

Elle concerne chaque phase de conception. Elle a aussi pour but de :

- Faciliter la rédaction du manuel d'utilisation

- Confirmer les performances du programme à partir de jeux de tests

[Link] 6: Exploitation

Elle constituent le moyen de vérification et de contrôle de l'ensemble de l'application.

Cette phase permet aussi de constater que l'application réalisée correspond bien aux spécifications
définies dans le cahier des charges. Elle doit fournir la preuve que l'application développée (logiciel
ou système) atteint bien tous les objectifs fixés dans le cahier des charges.

Toutefois il faut remarquer que cette preuve ne pourra être apportée qu'après un certain temps
d'utilisation.

2. ALGORITHMES.
2.1.Définition.

Certains voient, à tort, dans l'ordinateur une machine pensante et intelligente, capable de
résoudre bien des problèmes. En fait l’ordinateur est stupide mais très rapide, et ne serait
capable de rien si quelqu'un (le programmeur en l'occurence) ne lui avait fourni la liste des
actions à exécuter. Cette description doit être faite de manière non ambigüe car il ne faut pas
s'attendre à la moindre interprétation des ordres fournis. Ils seront exécutés de manière
purement mécanique.

De plus, les opérations élémentaires que peut exécuter un ordinateur sont en nombre restreint
et doivent être communiquées de façon précise dans un langage qu'il comprendra. Le
problème principal de l'utilisateur est donc de lui décrire la suite des actions élémentaires
permettant d'obtenir, à partir des données fournies, les résultats escomptés. Cette description
doit être précise, envisager le moindre détail et prévoir les diverses possibilités de données.
Cette marche à suivre porte le nom d'algorithme dont l'Encyclopaedia Universalis donne la
définition suivante:

" Un algorithme est une suite finie de règles à appliquer dans un ordre déterminé à un
nombre fini de données pour arriver, en un nombre fini d'étapes, à un certain résultat, et cela
indépendamment des données. "

4
Le mot algorithme provient du nom d'un célèbre mathématicien arabe de la première moitié
du IXe siècle: Muhammad ibn Musa al Khwarizmi.

Né vers 780 à Bagdad et mort vers 850. Il fut un de premier à trouver l’algorithme d'équation
de second degré et commença par écrire des faits mathématiques logiques et nouveaux, qui
furent soit admirés, soit critiqués et arrangés.

Le rôle de l'algorithme est fondamental. En effet, sans algorithme, il n'y aurait pas de
programme (qui n'est jamais que sa traduction dans un langage compréhensible par
l'ordinateur). De plus, les algorithmes sont fondamentaux en un autre sens: ils sont
indépendants à la fois de l'ordinateur qui les exécute, des langages dans lequel ils sont
énoncés et traduits.

[Link] : Calcul d’interêt

Calcul de l'intérêt et de la valeur acquise par une somme placée pendant un an à intérêt
simple.

L'énoncé du problème indique

les données fournies: deux nombres représentant les valeurs de la somme placée et du taux
d'intérêt. les résultats désirés: deux nombres représentant l'intérêt fourni par la somme placée
ainsi que la valeur obtenue après placement d'un an. Il nous faut maintenant décrire les
différentes étapes permettant de passer des donnés aux résultats. Nos connaissances
générales nous permettent d'exprimer cette règle:

"Pour obtenir l'intérêt fourni par la somme, il suffit de multiplier la somme par le taux
d'intérêt divisé par cent; la valeur acquise s'obtient en additionnant ce dernier montant et la
somme initiale."

2.3.Méthodologie

Dans cet exemple simple apparaissent les trois étapes qui caractérisent la résolution d'un
problème sur ordinateur:

comprendre la nature du problème posé et préciser les données fournies ("entrées"

ou "input" en anglais)

préciser les résultats que l'on désire obtenir ("sorties" ou "output" en anglais)

déterminer le processus de transformation des données en résultats.

Le but final d'une méthodologie de programmation est de rédiger un programme particulier dans
un langage de programmation précis pour un type d'ordinateur. Mais il se trouve que cette
démarche devienne étroitement liée à l'informatique est en fait un cas particulier d'une
méthodologie générale : celle de description d'un algorithme.

Ces trois étapes ne sont pas indépendantes et leur ordre peut être modifié.

5
Si les résultats fournis par l'ordinateur ne sont pas corrects, c'est qu'une erreur s'est glissée soit
dans l'analyse du problème, soit dans la mise au point de l'algorithme, soit dans sa traduction
en langage de programmation car l'ordinateur ne fait qu'exécuter scrupuleusement les
opérations demandées.

[Link] de l’algorithme

L'exemple décrit ci-dessus deviendrait:

1. Prendre connaissance de la somme initiale et du taux d'intérêt

2. Multiplier la somme par le taux; diviser ce produit par 100; le quotient obtenu est
l'intérêt de la somme
3. Additionner ce montant et la somme initiale; cette somme est la valeur acquise
4. Afficher les valeurs de l'intérêt et de la valeur acquise.

Il est évident, même sur cet exemple simple, qu'une telle formalisation risque de produire un
texte long, difficile à comprendre et ne mettant pas clairement en évidence les différentes
étapes du traitement.

[Link] de description

Dans un langage de description, les actions sont généralement décrites par un symbole ou un
verbe à l'infinitif choisi pour éviter les confusions. Ce langage est appelé soit pseudocode soit
langage de description d'algorithme (LDA).

Notre exemple devient:

écrire " Introduisez la somme initiale (en francs): "

lire somme_initiale
écrire " Introduisez le taux d'intérêt (ex: 3 pour 3%): "
lire taux
intérêt <-- somme_initiale * taux / 100
valeur_acquise <-- somme_initiale + intérêt
écrire " L'intérêt fourni est de " , intérêt , "francs "
écrire " La somme après un an sera de " , valeur_acquise , "francs "

lire correspond à la saisie, à l'introduction des données;

écrire correspond l'affichage à l'écran ou l'impression des résultats.

Ces verbes sont soulignés pour indiquer qu'ils ont un sens particulier, qu'il est interdit de les
utiliser dans un autre sens et qu'il seront traduits pour être rendus compréhensibles par la
machine.

Les valeurs manipulées dans cet algorithme sont des constantes (100) et des variables
(somme_initiale, taux, intérêt, valeur_acquise). Il est pratique de choisir le nom des variables
de manière à rappeler la signification de la valeur qu'elles représentent.

Ce nom est souvent appelé identificateur de la variable. Les variables jouent le rôle de
"tiroirs" dans lesquels on place une valeur durant l'exécution de l'algorithme.

6
Ainsi, lire somme_initiale signifie que l'on introduit dans le tiroir baptisé somme_initiale la
valeur numérique entrée au clavier lors de l'exécution du programme.

Le contenu d'un de ces tiroirs peut être modifié en y plaçant le résultat d'un calcul. Cette
instruction porte le nom d'assignation ou affectation et se représente par une flèche (<--).
Ainsi,

intérêt <-- somme_initiale * taux /100 : signifie que l'on place dans le tiroir intérêt le résultat
de l'opération figurant à droite de la flèche. Cette instruction se lit: assigner à la variable
intérêt la valeur de l'expression de droite.

Les expressions symbolisant les calculs à effectuer sont représentées par des formules
algébriques faisant intervenir les noms des variables, des symboles mathématiques ("+" pour
l'addition, "-" pour la soustraction, "*" pour la multiplication, "/" pour la division, ...) et des
constantes numériques.

La description d'une action et des objets qui y participent porte le nom d'instruction. L'ordre
dans lequel les différentes opérations seront écrites indique l'ordre dans lequel elles seront
exécutées: de haut en bas et de droite à gauche. Il s'agit d'une exécution séquentielle.

[Link] : Addition
1. écrire les deux nombres l'un en dessous de l'autre bien alignés
2. tirer un trait sous le deuxième le nombre
3. écrire dans la colonne unité sous le trait le nombre d'unités de la somme
4. écrire dans la colonne des dizaines au dessus du premier chiffre, la retenue c'est à
dire le nombre de dizaines de la somme (1 ou 0)
5. ajouter les chiffres des dizaines de la retenue
6. écrire dans la colonne des dizaines sous le trait du nombre de dizaines de la
somme
7. écrire dans la colonne centaine sous le trait la retenue, c'est à dire le nombre des
centaines de la somme
[Link] : Robot

Imaginons un robot domestique à qui nous devons fournir un algorithme lui permettant de
préparer une tasse de café soluble. Une première version de l'algorithme pourrait être:

1. Faire bouillir de l'eau

2. Mettre le café dans la tasse
3. Ajouter l'eau dans la tasse

Les étapes de cet algorithme ne sont probablement pas assez détaillées pour que le robot
puisse les interpréter.

Chaque étape doit donc être affinée en une suite d'étapes plus élémentaires, chacune étant
spécifiée d'une manière plus détaillée que dans la première version. Ainsi l'étape

7
1. faire bouillir l'eau peut être affinée en
1.1. Remplir la bouilloire d'eau
1.2. Brancher la bouilloire sur le secteur
1.3. Attendre l'ébullition
1.4. Débrancher la bouilloire

De même,

2. Mettre le café dans la tasse pourrait être affiné en

2.1. ouvrir le pot à café
2.2. prendre une cuiller à café
2.3. plonger la cuiller dans le pot
2.4. verser le contenu de la cuiller dans la tasse
2.5. fermer le pot à café

3. ajouter de l'eau dans la tasse pourrait être affinée en

3.1. verser de l'eau dans la tasse jusqu'à ce que celle-ci soit pleine

Certaines étapes étant encore trop complexes et sans doute incompréhensibles pour notre
robot, il faut les affiner davantage. Ainsi l'étape

1.1 Remplir la bouilloire d'eau : peut nécessiter les affinements suivants:

1.1.1 Mettre la bouilloire sous le robinet
1.1.2 Ouvrir le robinet
1.1.3 Attendre que la bouilloire soit pleine
1.1.4 Fermer le robinet

Quand il procède à des affinements des différentes étapes, le concepteur d'un algorithme doit
naturellement savoir où s'arrêter. Autrement dit, il doit savoir quand une étape constitue une
primitive adéquate au point de ne pas avoir besoin d'affinement supplémentaire. Cela signifie
évidemment qu'il doit connaître quelle sorte d'étape le processeur peut interpréter. Par
exemple, le concepteur de l'algorithme précédent doit savoir que le robot peut interpréter
"brancher la bouilloire" ce qui de ce fait n'exige pas d'affinement, mais qu'en revanche, il ne
peut pas interpréter "remplir la bouilloire" et que dès lors un affinement devient nécessaire.

[Link] a faire : Raffinement

Le premier algorithme comportera quatre lignes

1. enduire la viande de poivre blanc concassé,

2. poêler le steak,
3. flamber au cognac,
4. déglacer à la crème fraîche.

8
3. LA SEQUENCE.
[Link].

Dans les algorithmes décrivant des calculs sur les quantités numériques, seront utilisées
essentiellement les instructions que nous avons déjà étudiées.

[Link] instructions de lecture (d'entrée) notées:

lire variables
indiquant la saisie des données

exemples:
lire somme_initiale
lire taux

3.3. les instructions d'écriture (de sortie) de la forme:

écrire expression

exemple:

écrire " Introduisez la somme initiale (en francs): "

écrire " L'intérêt fourni est de " , intérêt
écrire intérêt
écrire a, b, (a+b)/2

[Link] instructions d'assignation (d'affectation) représentées par

variable <-- expression

intérêt <-- somme-initiale * taux / 100

a <-- 0
i <-- i + 1

[Link]

Exprimer un nombre de secondes sous forme d'heures, minutes, secondes. La seule donnée est
le nombre total de secondes que nous appellerons nsec; les résultats consistent en 3 nombres
h, m, s.

écrire " Introduisez le nombre de secondes"

lire nsec
s <-- nsec mod 60
m <-- (nsec \ 60) mod 60
h <-- nsec \ 3600
écrire nsec, "valent: ", h, "heure(s) ", m, "minute(s) et", s, "seconde(s)"

9
 3.6.Déclaratives

Il est aussi nécessaire de préciser ce que les variables utilisées contiendront comme type de
données. Il peut s'agir de nombres entiers, de nombres réels, de chaînes de caractères, ... Il
faut faire précéder la description de l'algorithme par une partie dite déclarative où l'on
regroupe les caractéristiques des variables manipulées.

La partie déclarative est placée en tête de l'algorithme et regroupe une ou plusieurs indications
de la forme:

entier variables ou réel variables

L'algorithme complété de l'exemple 1 devient:

entier nsec, h, m, s
écrire "Introduisez le nombre de secondes:"
lire nsec
s <-- nsec mod 60
m <-- (nsec \ 60) mod 60
h <-- nsec \ 3600
écrire nsec, "valent: ", h, "heure(s)", m, "minute(s) et", s,
"seconde(s)"

[Link] a faire ………………

4. LES STRUCTURES REPETITIVES.

[Link].

L'intérêt d'utiliser un ordinateur n'apparaît clairement que lors de la manipulation de données

nombreuses ou traitées de manière répétitive.

Exemple 1: Chercher dans une liste de noms et d'adresses, l'adresse d'une personne à partir
de son nom. Le nombre de fois qu'il faudra comparer le nom donné aux noms de la liste est
dans ce cas inconnu.

Exemple 2 : Calculer la N ème puissance entière d'un nombre x par multiplications

successives du nombre par lui-même. Ici, le nombre de répétition (N) de l'instruction de
multiplication est connu.
S'il est théoriquement possible de se contenter d'une seule structure de répétition, bien choisie,
pour exprimer tous les algorithmes, l'expérience a montré l'utilité d'en définir plusieurs,
chacune bien adaptée à des circonstances particulières. Ce sont les boucles tant que,
répéter ... jusqu'à et pour.

4.2. La boucle « tant que ».

10
 Résolvons l'exemple 1:
...
lire nom_donné
lire nom1
si nom1 = nom_donné alors écrire adresse1
sinon lire nom2
si nom2 = nom_donné alors écrire adresse2
sinon lire nom3
si nom3 = nom_donné alors ...
…..
L'inconvénient de cet algorithme (en dehors de l'empiètement inévitable sur la marge de
droite) tient au fait que l'auteur ne sait pas quand il doit s'arrêter d'écrire. Plus précisément, il
lui est impossible de savoir combien de fois il doit écrire l'instruction de comparaison au
nom_donné.

Un problème identique surgit dans l'écriture d'un algorithme qui décrit comment calculer le
premier nombre premier qui soit plus grand qu'un nombre entier positif donné N.

lire N
i <-- N+1
si i est premier alors écrire i
sinon i <-- i+1
si i est premier alors écrire i
sinon i <-- i+1
si i est premier alors écrire i
sinon i <-- i+1
si ...
Le test "si i est premier alors" ne sera exécuté qu'une fois si N=4, il le sera quatre fois si
N=13, mais combien de fois faudra-t-il réécrire le test si N=7394485?
Ces exemples montrent que la séquence et l'alternative ne sont pas en elles-mêmes suffisantes
pour exprimer des algorithmes dont la longueur peut varier selon les circonstances. Il est donc
nécessaire d'introduire le moyen de répéter certaines instructions d'un algorithme un nombre
quelconque de fois. La structure qui permet cela est appelée structure répétitive.

En utilisant la boucle "tant que", l'exemple 1 (avec la liste) s'écrit:

lire nom_donné
i <-- 1
lire nomi
tant que NOT ((nomi = nom_donné) ou (fin de liste)) faire
i <-- i+1
lire nomi
fin tant
si nomi = nom_donné alors écrire adressei
sinon écrire "Le nom demandé ne se trouve pas dans la liste."
Fin si

L'exemple avec le nombre premier s'écrira:

lire N

11
i <-- N+1
tant que NOT (i est premier) faire
i <-- i+1
ftant
écrire i

Notons qu'il faudra exprimer autrement les conditions " (fin de liste) " et " (i est premier) ",
ces formes n'étant pas compréhensibles par les compilateurs/interpréteurs.

[Link] de calcul de PGCD

Considérons aussi l'exemple suivant: étant donnés deux nombres entiers m et n positifs ou
nuls, on demande d'en calculer le PGCD. L'algorithme d'Euclide permet de résoudre ce
problème en prenant d'abord le reste de la division de m par n, puis le reste de la division de n
par ce premier reste, etc jusqu'à ce qu'on trouve un reste nul. Le dernier diviseur utilisé est le

PGCD de m et n. Pour m=1386 et n=140, on a successivement:

1386 = 140 * 9 + 126 140 = 126 * 1 + 14 126 = 14 * 9 + 0 et le PGCD de 1386 et 126 est
bien 14.

Remarquons que par définition, si un des nombres est nul, l'autre nombre est le PGCD .
Si nous avions pris m=140 et n=1386, nous aurions obtenu la suite de calculs suivants:

140 = 1386 * 0 + 140 1386 = 140 * 9 + 126

140 = 126 * 1 + 14 126 = 14 * 9 + 0 et le PGCD est le même. L'ordre de m et n n'a

donc pas d'importance.

Dans cet exemple, nous devons répéter le calcul du reste de la division d'un nombre par un
autre. Pour fixer les idées, appelons a le dividende, b le diviseur et r le reste. Le calcul du reste
de la division de a par b se fait simplement au moyen de l'instruction :

r <-- a mod b

L'algorithme s'écrit donc:

entier m,n,a,b,r,PGCD
lire m, n
a <-- m
b <-- n
tant que NOT(b = 0) faire
r <-- a mod b
a <-- b
b <-- r
ftant

PGCD <-- a
écrire "Le PGCD de",m,"et",n,"est",PGCD

12
 4.4. Commentaires

1) Les mots faire et ftant (abréviation de "fin de tant que") encadrent les instructions qui
doivent être exécutées plusieurs fois. On indique entre tant que et faire les conditions dans
lesquelles on doit exécuter le corps de la boucle.

2) Une boucle "tant que" se présente donc comme suit:

tant que expression logique faire

séquence d'instructions
ftant

En premier lieu, l'expression logique est évaluée (il faut donc veiller à sa valeur lors de
l'entrée dans la boucle): si sa valeur est vrai, le corps de la boucle est exécuté puis
l'expression logique est réévaluée (il faut donc qu'elle puisse changer de valeur pour sortir de
la boucle) et si elle a la valeur faux, on exécute l'instruction qui suit ftant.

3) Il est à noter qu'il est préférable d'exprimer l'expression logique sous la forme NOT
(condition(s) d'arrêt). Il est en effet plus simple de déterminer les raisons d'arrêter le
processus répétitif que celles de continuer.

La forme de ce type de boucle devient donc:

tant que NOT condition(s) d'arrêt faire

séquence d'instructions
ftant

[Link] boucle " pour".

Reprenons l'exemple 2 de l'introduction. Une boucle "tant que" permet de le résoudre:

entier N, i
réel x, puiss
lire N, x
puiss <-- 1
i <-- 1
tant que NOT(i > N) faire
puiss <-- puiss * x
i <-- i + 1
ftant
écrire "La puissance",N,"ème de",x,"est",puiss

Cependant, le nombre d' exécutions du corps de la boucle étant connu à l'avance, une boucle
"pour" est d'un emploi plus simple:
entier N, i
réel x, puiss
lire N, x
puiss <-- 1
pour i de 1 à N faire
puiss <-- puiss * x
fpour
écrire "La puissance",N,"ème de",x,"est",puiss
13
 4.6. Commentaires

1° Les mots faire et fpour (abréviation de "fin du pour") encadrent les instructions qui
doivent être exécutées plusieurs fois. On précise entre pour et faire comment seront
contrôlées les répétitions. On y définit une variable appelée variable de contrôle (i dans
l'exemple) et les valeurs que prendra cette variable: une première valeur ou valeur initiale
indiquée après le mot de, une dernière valeur ou valeur finale indiquée après le mot à. La
variable de contrôle est initialisée à la première valeur. Avant chaque exécution du corps
de la boucle, la valeur de la variable de contrôle est comparée à la valeur finale. Si la
variable de contrôle ne dépasse pas cette valeur, on exécute le corps de la boucle, sinon on
passe à l'instruction qui suit le mot fpour. Après chaque exécution du corps de la boucle,
la variable de contrôle est augmentée d'une unité.

2° Dans l'exemple ci-dessus, la variable de contrôle sert uniquement de compteur du

nombre d'exécutions du corps de la boucle. Si on le souhaite, on peut utiliser cette valeur
dans le corps de la boucle, entre autres pour faire un calcul fondé sur cette valeur. Dans
tous les cas, il faut éviter de modifier la valeur de cette variable.

3° Il est parfois utile de faire varier la variable de contrôle par valeurs décroissantes, ou
par incréments différents de l'unité. Dans ce cas, il faut utiliser la forme la plus générale
de la boucle "pour":

pour v.c. de [Link]. à [Link]. par incr faire

séquence d'instructions
fpour

où
v.c. est le nom de la variable de contrôle
[Link]. est la première valeur (ou valeur initiale)
[Link]. est la dernière valeur (ou valeur finale)
incr. est l'incrément, c'est-à-dire la quantité non nulle ajoutée à la variable de
contrôle à la fin de chaque exécution du corps de la boucle.

Il est important de noter ici l'impossibilité de traduire en Pascal les boucles avec des
incréments différents de 1 et -1.

Avant chaque exécution du corps de la boucle, la valeur de la variable de contrôle est

comparée à la dernière valeur. L'exécution s'arrête
lorsque la variable de contrôle a une valeur supérieure (strictement) à la dernière valeur si
l'incrément est positif

lorsque la variable de contrôle a une valeur inférieure (strictement) à la dernière valeur si

l'incrément est négatif.
Par convention, lorsque l'incrément est égal à 1, il n'est pas indiqué.

14
4° La première valeur, la dernière valeur et l'incrément peuvent être des expressions
numériques. Les instructions du corps de la boucle ne peuvent en aucun cas modifier ces
valeurs.

5° En fin de boucle, la valeur de la variable de contrôle n'est pas toujours égale à la valeur
finale (à vérifier avec votre compilateur). Il est donc dangereux d'utiliser celle-ci.

6° Il est théoriquement possible de modifier la valeur de la variable de contrôle à l'intérieur de

la boucle mais cette technique est à proscrire et ne masque pas un manque de réflexion lors de
l'analyse du problème. Cette manière de faire revient en fait à transformer artificiellement une
boucle pour en boucle tant que.

[Link] boucle " répéter ... jusqu'à ".

Comme la boucle "tant que", ce type de répétitive est utilisé lorsque le nombre de fois que la
séquence d'instructions à répéter est inconnu au moment où cette séquence est abordée pour la
premiè fois mais le corps de la boucle est toujours exécuté au moins une fois.
Sa formulation générale est:

répéter
séquence d'instructions
jusqu'à (expression logique)

L'expression logique est évaluée aprés l'exécution du corps de la boucle: si sa valeur est faux,
le corps de la boucle est exécuté à nouveau puis l'expression logique est réévaluée (il faut
donc qu'elle puisse changer de valeur pour sortir de la boucle) et si elle a la valeur vrai, on
exécute l'instruction qui suit jusqu'à. Attention, si ceci correspond tout à fait à l'usage
familier que nous faisons de l'expression répéter ... jusqu'à, le test effectué est la négation de
celui utilisé dans la boucle "tant que" et ceci peut parfois prêter à confusion.
Il faut en effet remarquer que dans

tant que expression logique faire

séquence d'instructions
ftant
expression logique exprime les raisons de continuer et dans
répéter
séquence d'instructions
jusqu'à (expression logique)

expression logique : exprime les raisons d'arrêter.

[Link].

1- Lire un nombre entier et déterminer s'il est premier.

2- Lire un nombre entier et déterminer tous ses diviseurs.

15
3- L'ordinateur "choisit" un nombre entier compris entre 0 et 100. Un joueur essaie de le
deviner. Lors de chaque essai, l'ordinateur affiche la "fourchette" dans laquelle se trouve le
nombre qu'il a choisi.

[Link] choix multiple.

Supposons que l'on veuille demander à l'utilisateur de choisir dans un menu une des 3
possibilités offertes. Le choix présenté ne se limite pas à une alternative (soit - soit).

Nous nous trouvons en présence d'un choix multiple qui s'écrit en LDA:

entier i
lire i
selon que
i=1 : instruction 1
i=2 : instruction 2
i=3 : instruction 3
autrement écrire "Mauvais choix"
fselon

La première forme généralise le si ... alors ... sinon ... fsi, la seconde le si ... alors ... fsi.

Si la i ème expression logique a la valeur vrai, la i ème séquence d'instructions est exécutée
puis il y a passage aux instructions qui suivent le mot fselon. Si toutes les expressions
logiques ont la valeur faux, on exécute dans le premier cas la séquence d'instructions qui suit
le mot autrement , dans le deuxième cas on passe directement à ce qui suit fselon.

Afin d'éviter toute ambiguïté, on exige que les différentes expressions logiques soient
mutuellement exclusives.

4.10. Exercices.

1) Lire 3 nombres a, b et c. Déterminer si l'équation ax+by+c=0 représente l'équation d'une

droite parallèle à l'un des axes (et si oui, lequel) ou une droite oblique par rapport aux axes.
Tenir compte du fait qu'on pourrait avoir a=b=0.

2) Lire 3 nombres a, b et c où a est différent de 0. Déterminer si la parabole d'équation

y=ax²+bx+c coupe l'axe des x en 0, 1 ou 2 points.

3) Demander et lire les valeurs de R en Ohm, I en Ampère et t en seconde. Déterminer un

algorithme qui proposerait de calculer la différence de potentiel, la puissance et l'énergie.

5. LES TABLEAUX
[Link] de tableau

16
Les tableaux servent à désigner une suite finie d'éléments de même type au moyen d'une
unique variable. Ces éléments peuvent être des entiers, des chaînes, ... Ils sont stockés dans les
différentes cases du tableau, habituellement numérotées de 0 à n-1, n représentant la taille du
tableau (le nombre de cases dans le tableau).

Le type d'un tableau précise l'intervalle de définition et le type (commun) des éléments.
tableau type_des_éléments[borne_inférieure .. borne_supérieure]

En général, nous choisirons toujours la valeur 0 pour la borne inférieure dans le but de
faciliter la traduction de l'algorithme vers les autres langages (C, Java, ...). Par exemple, pour
un tableau de 10 entiers, on pourra écrire :
t : tableau entier[0..9]

Un tel tableau peut par exemple contenir les éléments suivants :

0 1 2 3 4 5 6 7 8 9
45 54 1 -56 22 134 49 12 90 -27

Pour accéder à un élément du tableau, il suffit de préciser entre crochets l'indice de la case
contenant cet élément. Par exemple, pour accéder au septième élément (49) du tableau
d'entiers ci-dessus, on écrit : t[6]. L'instruction suivante affecte à la variable x la valeur du
premier élément du tableau, c'est à dire 45 :
x <- t[0]

L'élément désigné du tableau peut être utilisé comme n'importe quelle variable : t[6] <- 43

Cette instruction a modifié le tableau t :

0 1 2 3 4 5 6 7 8 9
45 54 1 -56 22 134 43 12 90 -27

Parcours complet d'un tableau

La plupart des algorithmes basés sur les tableaux utilisent des itérations permettant de faire un
parcours complet ou partiel des différents éléments du tableau. De tels algorithmes établissent
le résultat recherché par récurrence en fonction des éléments successivement rencontrés.

Les répétitions inconditionnelles sont le moyen le plus simple de parcourir complètement un

tableau.

[Link]

Dans l'exemple suivant, le sous programme « procédure » affiche un à un tous les

éléments d'un tableau de n éléments :

17
procedure écrireTableau(n : entier, tab : tableau entier[0..n-1])

début
pour i de 0 à n-1 faire
écrire(tab[i])
fpour
fin

Algorithme

début Lexique :
n <- lire() - n : entier, taille du tableau
Pour i de 0 à n-1 faire - tab : tableau entier[0..n-1]
tab[i] <- lire()
fpour
écrireTableau(n, tab) // appel de la procédure
fin

Exemple 2

La fonction suivante multiplie par 2 tous les éléments d'un tableau.

fonction doublerTableau(n : entier, t InOut : tableau entier[0..n-1])

début
Lexique :
Pour i de 0 à n-1 faire
- n : entier, taille du tableau
t[i] <- t[i]*2 - t : tableau entier[0..n-1], tableau
fpour modifiable
fin

[Link] partiel d'un tableau

Certains algorithmes sur les tableaux se contentent de parcourir successivement les

différents éléments du tableau jusqu'à rencontrer un élément satisfaisant une certaine
condition. Un tel parcours partiel est le plus souvent basé sur une répétition
conditionnelle.

[Link]

On cherche ici à savoir si un tableau saisi au clavier n'est constitué que d'entiers positifs :

18
 Algorithme
début
tab <- lire()
i <- 0
positif <- vrai
tant que positif et i < n faire Lexique :
si tab[i] < 0 - i : entier, indice d'itération
alors positif <- faux - n : entier, taille du tableau
- tab : tableau entier[O..n-1]
fsi - positif : booléen, vrai si aucun entier
i <- i+1 négatif n'a été détecté
ftant
si positif
alors écrire("tableau d'entiers naturels")
sinon écrire("tableau d'entiers relatifs")
fsi
fin

[Link] imbriqués

Certains algorithmes sur les tableaux font appel à des boucles imbriquées : la boucle
principale sert généralement à parcourir les cases une à une, tandis que le traitement de
chaque case dépend du parcours simple d'une partie du tableau (par exemple toutes les cases
restantes), ce qui correspond à la boucle interne.

[Link]

La fonction suivante calcule, pour chaque case d'un tableau, le nombre de cases suivantes qui
contiennent un élément strictement supérieur. Les résultats sont placés dans un tableau.

fonction NbSuccesseurSup(n:entier, t:tableau entier[0..n-1]):

tableau entier[0..n-1]
début Lexique :
Pour i de 0 à n-2 faire - n : entier, taille du tableau
- t : tableau entier[0..n-1]
tres[i] <- 0 - tres : tableau entier[0..n-1], tableau résultat (case i contient le nombre de cases
fpour de t indice strictement supérieur à i qui contiennent un élément supérieur à t[i]
- i : entier, indice d'itération de la boucle principale (parcours pour remplir tres)
- j : entier, indice d'itération de la boucle interne (parcours des cases restantes de t)
Pour i de0 à n-2 faire
Pour j de i+1 à n-1 aire
si t[i] < tres[i]+1
alors tres[i] <- tres[i]+1
fsi
fpour
fpour
retourne tres
fin

[Link] multidimensionnels

19
 Les cases d'un tableau à une dimension sont indicées de manière consécutive (cases
"alignées"). Il est possible de disposer ces cases selon des grilles (tableaux à deux
dimensions), des cubes (tableaux à trois dimensions),

Les algorithmes les plus simples sur ces tableaux utilisent néanmoins en général des boucles
imbriquées : chaque niveau de boucle correspond au parcours selon une dimension.

Le type d'un tableau précise l'intervalle de définition selon chaque dimension.

tableau type_des_éléments[borne_inf_dim1 .. borne_sup_dim1, borne_inf_dim2.. borne_sup_dim2, ...]

[Link] à deux dimensions

Ces tableaux sont faciles à se représenter comme une grille (ou matrice) ayant un certain
nombre de lignes (première dimension) et un certain nombre de colonnes (seconde
dimension).

tableau type_des_éléments[0..nb_lignes-1, 0..nb_colonnes-1]

Un tel tableau, avec 5 colonnes et 3 lignes, peut par exemple contenir les éléments suivants :

0 1 2 3 4
0 45 54 1 -56 22
1 64 8 54 34 2
2 56 23 -47 0 12

Pour accéder à un élément du tableau, il suffit de préciser entre crochets l'indice de la case
contenant cet élément, et ce pour chacune des dimensions. Par exemple, pour accéder à
l'élément 23 du tableau d'entiers ci-dessus, on écrit : t[2,1]. L'instruction suivante affecte à la
variable x la valeur du premier élément du tableau, c'est à dire 45.

x <- t[0,0]
L'élément désigné du tableau peut alors être utilisé comme n'importe quelle variable :

t[2,1] <- 43
Cette instruction a modifié le tableau :

0 1 2 3 4
0 45 54 1 -56 22
1 64 8 54 34 2
2 56 43 -47 0 12

[Link] : calcul de la somme

20
fonction somme(li:entier,co:entier,t:tableau entier[0..li-1, 0..co-1]):entier
début
s <- 0
Pour i de 0 à li-1 faire
Lexique :
Pour j de 0 à co-1 faire - li : entier, nombre de lignes du tableau
s <- s + t[i,j] - co : entier, nombre de colonnes du tableau
fpour - t : tableau entier[0..li-1, 0..co-1], tableau dont on cherche
fpour l'élément maximal
- s : entier, somme des éléments déjà parcourus
- i : entier, indice d'itération sur les lignes
retourne s - j : entier, indice d'itération sur les colonnes

fin

5.10. Recherche dichotomique

La fonction rechercheDicho recherche un élément dans un tableau trié et retourne l'indice

d'une occurrence de cet élément (ou -1 en cas d'échec). Une telle recherche peut être réalisée
de manière séquentielle ou dichotomique. Nous développons ici la version dichotomique qui
est la plus efficace en temps d'exécution.

On compare l'élément cherché à celui qui se trouve au milieu du tableau. Si l'élément cherché
est plus petit, on continue la recherche dans la première moitié du tableau sinon dans la
seconde. On recommence ce processus sur la moitié. On s'arrête lorsqu'on a trouvé ou lorsque
l'intervalle de recherche est nul.

5.11. Exemple

Exemple de recherche dans le tableau d'entiers suivant défini sur l'intervalle [3..10] :
5 13 18 23 46 53 89 97
3 4 5 6 7 8 9 10

Recherche de 46 :

Etape 1 : comparaison de 46 avec t[6] (6=(10+3)÷2), t[6]<46 => recherche dans [7..10]
Etape 2 : comparaison de 46 avec t[8], t[8]>46 => recherche dans [7..7]
Etape 3 : comparaison de 46 avec t[7], t[7]=46 => élément cherché trouvé à l'indice 7

Recherche de 10 :

Etape 1 : comparaison de 10 avec t[6], t[6]<10 => recherche dans [3..5]

Etape 2 : comparaison de 10 avec t[4], t[4]<10 => recherche dans [3..3]
Etape 3 : comparaison de 10 avec t[3], t[3]>10 => recherche dans [4..3], Borne inférieure
supérieure à la borne supérieure donc on met fin à l'algorithme et l'élément cherché n'a pas été
trouvé

5.12. Une technique de tri d’un tableau

21
 Ce qui suit est incontournable. Combien de fois au cours d’une carrière (brillante) de
développeur a-t-on besoin de ranger des valeurs dans un ordre donné ? C’est incalculable.
Aussi, plutôt qu’avoir à réinventer à chaque fois la roue, le fusil à tirer dans les coins, le fil à
couper le roquefort et la poudre à maquiller, vaut-il mieux avoir assimiler quelques techniques
solidement éprouvées, même si elles paraissent un peu ardues au départ.

Il existe plusieurs stratégies possibles pour trier les éléments d’un tableau ; nous en verrons
une : le tri par sélection.

Admettons que le but de la manœuvre soit de trier un tableau de 12 éléments dans l’ordre
croissant.

45 122 12 3 21 78 64 53 89 28 84 46

On commence par rechercher le plus petit élément. On l’identifie en quatrième position, et on

l’échange alors avec l’élément numéro 1.

3 122 12 45 21 78 64 53 89 28 84 46

On recommence à rechercher le plus petit élément, mais cette fois à partir du deuxième
élément. On le trouve en 3e position, on échange donc le deuxième avec le troisième :

3 12 122 45 21 78 64 53 89 28 84 46

On recommence à partir du troisième, ce qui donnera in fine :

3 12 21 45 122 78 64 53 89 28 84 46

Et cetera, et cetera , jusqu’à l’avant dernier.

L’algorithme permettant d’effectuer cette tâche est le suivant :

Pour i  1 à 11
mini = t(i)
posmini = i
Pour j  i + 1 à 12
Si t(j) < mini alors
mini  t(j)
posmini  j
Finsi
j suivant
t(posmini)  t(i)
t(i)  mini
i suivant

fonction rechercheDicho(e : entier, n : entier, t : tableau

entier[0..n-1]):entier

22
début
debut <- 0
fin <- n-1
trouve <- faux
tant que debut <= fin et non trouve faire
i <- (debut+fin)÷2
si t[i] = e
alors trouve <- vrai
sinon si t[i] > e Lexique :
alors fin <- i-1 - e : entier, élément recherché
sinon debut <- i+1 - n : entier, taille du tableau
- t : tableau entier[0..n-1], tableau trié par ordre croissant
fsi - debut : entier, début de la zone de recherche
fsi - fin : entier, fin de la zone de recherche
ftant - trouve : booléen, faux tant que l'élément cherché n'est pas trouvé
- i : entier, indice de la case du milieu de la zone de recherche
si trouve - indice : entier, indice de l'élément recherché ou -1 s'il n'est pas trouvé
alors indice <- i
sinon indice <- -1
fsi
retourne indice
fin

5.13. Exercices.
1. Etant donné un vecteur de nombres triés par ordre croissant, chercher si un nombre donné x
figure parmi les composantes. Si oui, indiquer la valeur de l'indice correspondant.

2. Bonhomme pendu. L'algorithme lit un mot proposé par un premier joueur. L'algorithme
affiche ensuite le mot où toutes les lettres sauf la première et la dernière sont remplacées par
un tiret. Un deuxième joueur propose des lettres une à une. Chaque fois que la lettre se trouve
dans le mot, l'algorithme remplace les tirets qui remplaçaient cette lettre et réaffiche le mot.
Le second joueur a droit à un maximum de 6 essais infructueux (lettre ne se trouvant pas dans
le mot).

3. Carrés magiques d'ordre impair. Un carré magique d'ordre n est un tableau carré à n lignes
et n colonnes, donc de n² cases, dans lesquelles on écrit une et une seule fois les nombres
entiers de 1 à n², de telle sorte que la somme des n nombres de chaque ligne, de chaque
colonne et de chaque diagonale soit toujours la même. On dispose pour les carrés magiques
d'ordre impair de l'algorithme suivant:

En désignant par (i,j) la case de la ligne i et de la colonne j:

(a) on place 1 en ( n , (n+1)/2 )

(b) ayant placé le nombre k dans la case (i,j) on place le nombre k+1 dans la case (i+1,j+1),
toutefois si cette case est occupée on place le nombre k+1 dans la case (i-1,j).

Lorsque les indices calculés sont supérieurs à n, on prend 1 comme indice. Ces opérations se
font pour 1<=k<=n²-1.

4. Jeu de Marienbad. On place des allumettes sur 4 rangées: 1 allumette sur la première,
sur la seconde, 5 sur la troisième et 7 sur la dernière. Deux joueurs peuvent

23
 alternativement ôter, sur une seule rangée à la fois, autant d'allumettes qu'ils le
souhaitent mais au moins une. Le joueur qui enlève la dernière allumette a perdu.

5. Lire un texte d'au moins 120 caractères. Compter et afficher le nombre d'occurences
(d'apparition) de chacune des lettres de l'alphabet.

6. Nous désignerons par a1, a2, ..., an les éléments d'un tableau à trier par ordre croissant.
On commence par chercher l'indice du plus petit des éléments, soit j cet indice. On
permute alors les valeurs de a 1 et aj .On cherche ensuite l'indice du plus petit des
éléments a2, a3, ..., an et on permute avec a2, etc.
5.14. Exercices.

1. Calculer la racine carrée de a grâce à la formule récurrente x = 1/2 (x + a/x). Les calculs
commenceront avec 1 comme valeur initiale de x et stopperont quand la valeur absolue de
la différence entre les deux dernières valeurs calculées sera inférieure à 10 -6.

2. Lire deux polynômes et en calculer la somme et le produit.

3. Lire un polynôme et en calculer la valeur pour x = a (a est lu au clavier).

4. Lire un nombre entier, la base dans lequel il est exprimé et celle dans lequel il doit être
exprimé. Effectuer la conversion et afficher le résultat.
5. Lire une chaîne de caractères et la mettre en majuscules.

6. Lire une chaîne de caractères et en déterminer le nombre de mots.

7. Lire une chaîne de caractères et en déterminer le nombre de caractères différents.

8. Lire deux nombres entiers N1 et N2. Si un des nombres est nul, l'autre est le PGCD sinon
il faut soustraitre le plus petit du plus grand et laisser le plus petit inchangé. Puis,
recommencer ainsi avec la nouvelle paire jusqu'à ce que un des deux nombres soit nul.
Dans ce cas, l'autre nombre est le PGCD

9. Lire deux nombres entiers N1 et N2. Assigner à N1 la valeur de N2 et à N2 la valeur du

reste de la division de N1 par N2. Puis recommencer jusqu'à ce que le reste de la division
soit nul. A ce moment, N1 contient le PGCD.

10. Calculer ab avec a réel et b entier par multiplications successives.

11. Rédigez en LDA (langage de description d’algorithme) un algorothme qui réalise le jeu suivant :

(a) A tour de rôle, l'ordinateur et le joueur choisissent un nombre qui ne peut prendre que 3
valeurs: 0, 1 ou 2.

Note: l'instruction
N <-- Random(3)
réalise le choix de l'ordinateur. (voir l’instruction case )

24
(b) Si la différence entre les nombres choisis vaut 2, le joueur qui a proposé le plus grand
nombre gagne un point 1, le joueur qui a proposé le plus petit nombre gagne un point
0, aucun point n'est marqué.

(c) Le jeu se termine quand un des deux joueurs (l'ordinateur ou le joueur humain) totalise 10
points ou quand l'être humain introduit un nombre négatif qui indique sa volonté d'arrêter de
jouer.

5.15. Travaux dirigés

Exercice 6.1

25
Ecrire un algorithme qui déclare et remplisse un tableau de 7
valeurs numériques en les mettant toutes à zéro.

Exercice 6.2
Ecrire un algorithme qui déclare et remplisse un tableau
contenant les six voyelles de l’alphabet latin.

Exercice 6.3
Ecrire un algorithme qui déclare un tableau de 9 notes, dont
on fait ensuite saisir les valeurs par l’utilisateur.

Exercice 6.4
Que produit l’algorithme suivant ?

Tableau Nb(5) en Entier

Variable i en Entier

Début
Pour i ← 0 à 5
Nb(i) ← i * i
i Suivant

Pour i ← 0 à 5
Ecrire Nb(i)
i Suivant
Fin

Peut-on simplifier cet algorithme avec le même résultat ?

Exercice 6.5
Que produit l’algorithme suivant ?

Tableau N(6) en Entier

Variables i, k en Entier
Début
N(0) ← 1
Pour k ← 1 à 6
N(k) ← N(k-1) + 2
k Suivant

Pour i ← 0 à 6
Ecrire N(i)
i Suivant

Fin

Peut-on simplifier cet algorithme avec le même résultat ?

Exercice 6.6
Que produit l’algorithme suivant ?

26
Tableau Suite(7) en Entier
Variable i en Entier
Début
Suite(0) ← 1
Suite(1) ← 1
Pour i ← 2 à 7
Suite(i) ← Suite(i-1) + Suite(i-2)
i suivant

Pour i ← 0 à 7
Ecrire Suite(i)
i suivant
Fin

Exercice 6.7
Ecrivez la fin de l’algorithme 6.3 afin que le calcul de la
moyenne des notes soit effectué et affiché à l’écran.

Exercice 6.8
Ecrivez un algorithme permettant à l’utilisateur de saisir un
nombre quelconque de valeurs, qui devront être stockées dans un
tableau. L’utilisateur doit donc commencer par entrer le nombre
de valeurs qu’il compte saisir. Il effectuera ensuite cette
saisie. Enfin, une fois la saisie terminée, le programme
affichera le nombre de valeurs négatives et le nombre de
valeurs positives.

Exercice 6.9
Ecrivez un algorithme calculant la somme des valeurs d’un
tableau (on suppose que le tableau a été préalablement saisi).

Exercice 6.10
Ecrivez un algorithme constituant un tableau, à partir de deux
tableaux de même longueur préalablement saisis. Le nouveau
tableau sera la somme des éléments des deux tableaux de départ.

Exemple :
Tableau 1 : 4 – 8 – 7 – 9 – 1 – 5 – 4 – 6
Tableau 2 : 7 – 6 – 5 – 2 – 1 – 3 – 7 – 4
Tableau à constituer : 11 – 14 – 12 – 11 – 2 – 8 – 11 - 10

Exercice 6.11
Toujours à partir de deux tableaux précédemment saisis, écrivez
un algorithme qui calcule le schtroumpf des deux tableaux. Pour
calculer le schtroumpf, il faut multiplier chaque élément du
tableau 1 par chaque élément du tableau 2, et additionner le
tout.

Exemple :

27
Tableau 1 : 4 – 8 – 7 - 12
Tableau 2 : 3 – 6

Le Schtroumpf :

3*4 + 3*8 + 3*7 + 3*12 + 6*4 + 6*8 + 6*7 + 6*12 = 279

Exercice 6.12
Ecrivez un algorithme qui permette la saisie d’un nombre
quelconque de valeurs, sur le principe de l’ex 6.8. Toutes les
valeurs doivent être ensuite augmentées de 1, et le nouveau
tableau sera affiché à l’écran.

Exercice 6.13
Ecrivez un algorithme permettant, toujours sur le même
principe, à l’utilisateur de saisir un nombre déterminé de
valeurs. Le programme, une fois la saisie terminée, renvoie la
plus grande valeur en précisant quelle position elle occupe
dans le tableau. On prendra soin d’effectuer la saisie dans un
premier temps, et la recherche de la plus grande valeur du
tableau dans un second temps.

Exercice 6.14
Toujours et encore sur le même principe, écrivez un algorithme
permettant, à l’utilisateur de saisir les notes d'une classe.
Le programme, une fois la saisie terminée, renvoie le nombre de
ces notes supérieures à la moyenne de la classe.

Exercice 6.14
Avec les éléments vus dans cette première partie, voici
quelques exercices simples à réaliser:

1) "Calculer le volume d'un pavé"

2) "Calculer le nombre de secondes écoulées depuis le début de

la journée à partir d'une heure donnée"

3) "Calculer l'heure courante à partir du nombre de secondes

écoulées depuis le début de la journée"
Pour ce dernier exercice, on pourra utiliser l'opérateur "\"
qui effectue une division entière (ne retourne pas de partie
décimale).

Corrigés des Exercices

28
Exercice 6.1
Tableau Truc(6) en Entier
Variable i en Entier
Debut
Pour i ← 0 à 6
Truc(i) ← 0
i Suivant

Fin

Exercice 6.2
Tableau Truc(5) en Caractère

Debut
Truc(0) ← ”a“
Truc(1) ← ”e“
Truc(2) ← ”i“
Truc(3) ← ”o“
Truc(4) ← ”u“
Truc(5) ← ”y“
Fin

Exercice 6.3
Tableau Notes(8) en Entier
Variable i en Entier
Début
Pour i ← 0 à 8
Ecrire "Entrez la note numéro ", i + 1

Lire Notes(i)
i Suivant
Fin

Exercice 6.4
Cet algorithme remplit un tableau avec six valeurs : 0, 1, 4,
9, 16, 25. Il les écrit ensuite à l’écran. Simplification :

Tableau Nb(5) en Entier

Variable i en Entier

Début
Pour i ← 0 à 5
Nb(i) ← i * i
Ecrire Nb(i)
i Suivant

Fin
Exercice 6.5 :
Cet algorithme remplit un tableau avec les sept valeurs : 1, 3, 5, 7, 9, 11,
13. Il les affiche ensuite :

29
Tableau N(6) en Entier
Variables i, k en Entier
Début
N(0) ← 1
Ecrire N(0)
Pour k ← 1 à 6
N(k) ← N(k-1) + 2
Ecrire N(k)
k Suivant
Fin

Exercice 6.6
Cet algorithme remplit un tableau de 8 valeurs : 1, 1, 2, 3, 5, 8, 13, 21

Exercice 6.7
Variable S en Entier
Tableau Notes(8) en Entier
Debut
s ← 0
Pour i ← 0 à 8
Ecrire “Entrez la note n° “, i + 1
Lire Notes(i)
s ← s + Notes(i)
i Suivant
Ecrire “Moyenne : “, s/9
Fin

Exercice 6.8
Variables Nb, Nbpos, Nbneg en Entier
Tableau T() en Entier
Debut
Ecrire “Entrez le nombre de valeurs :“
Lire Nb
Redim T(Nb - 1)
Nbpos ← 0
Nbneg ← 0
Pour i ← 0 à Nb – 1
Ecrire “Entrez le nombre n° “, i + 1
Lire T(i)
Si T(i) > 0 alors
Nbpos ← Nbpos + 1
Sinon
Nbneg ← Nbneg + 1
Finsi
i Suivant
Ecrire “Nombre de valeurs positives : “, Nbpos
Ecrire “Nombre de valeurs négatives : “, Nbneg
Fin

Exercice 6.9

30
Variables i, Som, N en EntierTableau T() en Entier
Debut
… (on ne programme pas la saisie du tableau, dont on suppose
qu’il compte N éléments)

Redim T(N - 1)
…
Som ← 0
Pour i ← 0 à N – 1
Som ← Som + T(i)
i Suivant

Ecrire “Somme des éléments du tableau : “, Som

Fin

Exercice 6.10

Variables i, N en Entier
Tableaux T1(), T2(), T3() en Entier
Debut
… (on suppose que T1 et T2 comptent N éléments, et qu’ils sont
déjà saisis)
Redim T3(N - 1)
…
Pour i ← 0 à N – 1
T3(i) ← T1(i) + T2(i)
i Suivant
Fin

Exercice 6.11
Variables i, j, N1, N2, S en Entier
Tableaux T1(), T2() en Entier
Debut
… On ne programme pas la saisie des tableaux T1 et T2.
On suppose que T1 possède N1 éléments, et que T2 en possède T2)
…
S ← 0
Pour i ← 0 à N1 – 1
Pour j ← 0 à N2 – 1
S ← S + T1(i) * T2(j)
j Suivant
i Suivant

Ecrire "Le schtroumpf est : ", S

Fin

Exercice 6.12

31
Variables Nb, i en Entier
Tableau T() en Entier
Debut
Ecrire “Entrez le nombre de valeurs :“
Lire Nb
Redim T(Nb - 1)
Pour i ← 0 à Nb – 1
Ecrire “Entrez le nombre n° “, i + 1
Lire T(i)
i Suivant
Ecrire "Nouveau tableau :"

Pour i ← 0 à Nb – 1
T(i) ← T(i) + 1
Ecrire T(i)
i Suivant
Fin

Exercice 6.13

Variables Nb, Posmaxi en Entier

Tableau T() en Entier
Ecrire “Entrez le nombre de valeurs :“
Lire Nb
Redim T(Nb - 1)
Pour i ← 0 à Nb – 1
Ecrire “Entrez le nombre n° “, i + 1
Lire T(i)
i Suivant

Posmaxi ← 0

Pour i ← 0 à Nb – 1
Si T(i) > T(Posmaxi) alors
Posmaxi ← i
Finsi

i Suivant

Ecrire “Element le plus grand : “, T(Posmaxi)

Ecrire “Position de cet élément : “, Posmaxi
Fin

Exercice 6.14

32
Il n'y a pas de correction unique, celles qui sont proposées
ici représentent juste une manière de faire.
1) "Calculer le volume d'un pavé"
Similaire à l'exemple du calcul de la surface d'un carré.
On se contente de lire les valeurs, de faire le calcul et
d'afficher le résultat.
LIRE longueur
LIRE largeur
LIRE hauteur
volume = longueur x largeur x hauteur
ECRIRE volume

2) "Calculer le nombre de secondes écoulées depuis le début de

la journée à partir d'une heure donnée"

Puisque l'on ne connait pas d'autre manière pour le moment, on

va demander l'heure sous sa forme décomposée.

LIRE heure
LIRE minutes
LIRE secondes
total_secondes = (heure x 3600) + (minutes x 60) + secondes
ECRIRE total_secondes

3) "Calculer l'heure courante à partir du nombre de secondes

écoulées depuis le début de la journée"

Peut-être un peu plus de réflexion pour ce dernier exercice. Il

faut s'aider de l'opérateur qui permet de faire une division
entière, et savoir manipuler les calculs horaires.
LIRE secondes_ecoulees
heures = secondes \ 3600
minutes = (secondes_ecoulees - (heures x 3600)) \ 60
secondes = secondes_ecoulees - (minutes x 60) - (heures x 3600)
ECRIRE heures
ECRIRE minutes

Exercices corrigés

33
Exercice 1 : Lire 2 nombres a et b. Les écrire dans l'ordre croissant.
réel a, b
écrire "Introduisez a:"
lire a
écrire "Introduisez b:"
lire b
si a>b alors écrire b, a
sinon écrire a, b
fsi

Exercice 2 : Lire 3 nombres a, b et c. Les écrire dans l'ordre croissant.

réel a, b, c
écrire "Introduisez a:"
lire a
écrire "Introduisez b:"
lire b
écrire "Introduisez c:"
lire c
si a>b alors Min <-- b
Max <-- a
sinon Min <-- a
Max <-- b
fsi
si c<Min alors Moy <-- Min
Min <-- c
sinon si c>Max alors Moy <-- Max
Max <-- c
sinon Moy <-- c
fsi
fsi
écrire "Dans l'ordre croissant:", Min, Moy, Max
écrire "Dans l'ordre décroissant:", Max, Moy, Min

Exercice 3 : Déterminer si l'année A est bissextile. Note: Si A n'est pas divisible par
4, l'année n'est pas bissextile. Si A est divisible par 4, l'année est bissextile sauf si A est
divisible par 100 et pas par 400.
entier A
écrire "Introduisez l'année:"
lire A
si NOT (A mod 4=0) alors écrire "L'année ", A, "n'est pas
bissextile."
sinon si NOT (A mod 100=0) alors écrire "L'année ", A, "est
bissextile."
sinon si NOT (A mod 400=0) alors écrire "L'année ", A, "n'est pas
bissextile."
sinon écrire "L'année ", A, "est bissextile."
fsi
fsi
fsi

L’exercice 3 peut aussi s’écrire de la façon suivante :

34
entier A
écrire "Introduisez l'année:"
lire A
si (A mod 4=0) et ((A mod 100>0) ou (A mod 400=0)) alors
écrire "L'année ", A, "est bissextile."
sinon écrire "L'année ", A, "n'est pas bissextile."
fsi

Exercice 14: Déterminer la valeur absolue d'un nombre réel x à partir de la définition
de la valeur absolue.
réel x
écrire "Introduisez x:"
lire x
si x>0 alors écrire "Valeur absolue =", x
sinon si x=0 alors écrire "Valeur absolue =", 0
sinon écrire "Valeur absolue =", -x
fsi
fsi

5) Résoudre l'équation du premier degré: a * x + b = 0

réel a, b
écrire "Résolution de ax + b = 0"
écrire "Introduisez a:"
lire a
écrire "Introduisez b:"
lire b
si a=0 alors si b=0 alors écrire "Equation indéterminée."
sinon écrire "Equation impossible."
fsi
sinon écrire "x = ", -b/a
fsi

Exercice 6 : La transformation de coordonnées cartésiennes (x,y) en coordonnées

polaires (r,t) se fait par les formules :
r2 = x2+y2
t = arctg (y/x) auquel il faut ajouter pi si x < 0
sauf si x = 0, t = pi/2 si y > 0
t = - pi/2 si y < 0
t n'existe pas si y = 0
réel x, y, r, t
écrire "Introduisez l'abscisse x:"
lire x

écrire "Introduisez l'ordonnée y:"

lire y
r <-- (x2+y2)1/2
si x=0 alors si y>0 alors écrire "r=", r ," et t= ", pi/2
sinon si y<0 alors écrire "r=", r ," et t= ", -pi/2

35
 sinon écrire "r=", r ," et t n'existe pas."
fsi
fsi

sinon t <-- arctg (y/x)

si x<0 alors t <-- t + pi
fsi
écrire "r=", r ," et t= ", t
fsi

Exercice 7 : Lire une date (j/m/a) et déterminer le jour de la semaine. L'algorithme

est valable pour les dates postérieures à 1582.

Pour janvier et février, il faut augmenter m de 12 et diminuer a de 1.

Calculer s qui vaut la partie entière de a divisé par 100
JD = 1720996,5 - s + s \ 4 + [365,25*a] + [30,6001*(M+1)] + j
JD = JD - [JD/7]*7
JS = [JD] MOD 7
si JS = 0, le jour est mardi,
si JS = 1, le jour est mercredi,
....
si JS = 7, le jour est lundi.
entier j, m, a, s, JD, JS
écrire "Introduisez le jour (1-31)"
lire j
écrire "Introduisez le mois (1-12)"
lire m
écrire "Introduisez l'année (xxxx)"
lire a
si m<3 alors m <-- m + 12
a <-- a - 1
fsi

s <-- a \ 100
JD <-- 1720996,5 - s + s \ 4 + [365,25*a] + [30,6001*(M+1)] + j
JD <-- JD - [JD/7]*7
JS <-- [JD] mod 7
selon que
JS = 0 : Dat <-- "mardi";
JS = 1 : Dat <-- "mercredi";
JS = 2 : Dat <-- "jeudi";
JS = 3 : Dat <-- "vendredi";
JS = 4 : Dat <-- "samedi";
JS = 5 : Dat <-- "dimanche";
JS = 6 : Dat <-- "lundi";
fselon

écrire "Le ", j, "/", m, "/", a, "est un ", Dat

Exercice 8 : Calcul du sinus d'un angle exprimé en radians

Lire un angle Rad exprimé en radians

36
 Mettre +1 dans Sign
"Enlever" un nombre entier de tours grâce à:
- Rad = Rad - 2 * pi * [Rad / (2*pi)] si rad<0
- Rad = Rad + 2 * pi * [-Rad / (2*pi)] + 2*pi
si rad>=0
Si Rad>pi, le ramener entre 0 et pi en soustrayant pi et s'en
souvenir en
mettant -1 dans Sign
Si Rad>pi/2, faire Rad = pi - Rad
Si Rad>pi/4, * faire Rad = pi/2 - Rad
- Sinus vaut 1 - Rad*Rad/2 + Rad*Rad*Rad*Rad/24
Si Rad<=pi/4,
Sinus = Rad - Rad*Rad*Rad/6 +Rad*Rad*Rad*Rad*Rad/120

Multiplier Sinus par Sign et afficher la réponse

réel x, Rad, pi, Sinus

entier Sign
écrire "Introduisez l'angle (en radians):"
lire x
pi <-- 3.1416;
Rad <-- x
Sign <-- +1
si Rad>0 alors Rad <-- Rad - 2*pi * [Rad / (2*pi)]
sinon Rad <-- Rad + 2*pi * [-Rad / (2*pi)] + 2*pi
fsi
si Rad > pi alors Rad <-- Rad - pi
Sign <-- -1
fsi
si Rad > pi/2 alors Rad <-- pi - Rad
fsi
si Rad > pi/4 alors Rad <-- pi/2 - Rad
Sinus <-- 1 - Rad*Rad/2 +
Rad*Rad*Rad*Rad/24
sinon Sinus <-- Rad - Rad*Rad*Rad/6 + Rad*Rad*Rad*Rad*Rad/120
fsi
Sinus <-- Sinus * Sign
écrire "sin(",x,")=",Sinus

Exercice 9 : L'algorithme CalculMiMaree calcule l'heure et la

hauteur d'eau à mi-marée après avoir demandé à l'utilisateur
les heures et hauteurs de la basse mer et de la pleine mer. La
mi-marée est définie comme le temps au milieu entre les heures
de basse mer et pleine mer ; la hauteur d'eau est alors la
moyenne des hauteurs à basse mer et à pleine mer.

Pour représenter, un temps, par exemple 10H24, on peut utiliser

2 nombres entiers, un pour le nombre d'heures, l'autre pour le
nombre de minutes. L'algorithme demande à l'utilisateur 2
entiers pour chacun des temps de marée basse et haute et doit

37
 calculer les 2 entiers caractérisant l'heure de mi-marée. Il
calcule de plus avec des nombres réels la hauteur d'eau.

Voici un exemple d'exécution possible pour cet algorithme (sont

notées en gras les données fournies par l'utilisateur) :

Heure de la maree basse ? Heure : 10, Minute : 24

Hauteur d eau a maree basse ? 1.10 , Heure de la maree
haute ? Heure : 18 , Minute : 52
Hauteur d eau a maree haute ? 5.40
La mi-maree est a : 14H38 , avec la hauteur d eau : 3.25 m

Algorithme CalculMiMaree
{ Calcule le temps et la hauteur de la mi-marée, en fonction
des temps et hauteurs des marées haute et basse. Pour calculer
le temps de la mi-marée convertit les temps en minutes pour
faire la moyenne, et convertit le resultat en heures et minutes
}

identificateur type Rôle

HBas entier Heure de la marée basse
MnBas entier Minute de la marée basse
HHaut entier Heure de la marée haute
MnHaut entier Minute de la marée haute
HMi entier Heure de la mi-marée
MnMi entier Minute de la mi-marée
TempsBas entier Temps compté en mn depuis 0h00 de la marée basse
TempsHaut entier Temps compté en mn depuis 0h00 de la marée haute
TempsMi entier Temps compté en mn depuis 0h00 de la mi-marée
HauteurHaut reel Hauteur d'eau à marée haute
HauteurBas reel Hauteur d'eau à marée basse
HauteurMi reel Hauteur d'eau à mi-marée

début

ecrire ('Heure de la maree basse ? Heure :')

lire (HBas)
ecrire ('Minute :')
lire(MnBas)
ecrire ('Hauteur d eau a maree basse ?')
lire (HauteurBas)
ecrire ('Heure de la maree haute ? Heure :')
lire (HHaut)
ecrire ('Minute :')
lire(MnHaut)
ecrire ('Hauteur d eau a maree haute ?')

38
 lire (HauteurHaut)
TempsBas <-- 60 * HBas + MnBas { conversion des
heures/minutes }
TempsHaut <-- 60 * HHaut + MnHaut { en nombre de minutes
depuis 0H00 }
HauteurMi <-- (HauteurBas + HauteurHaut)/2 { moyenne des
hauteurs }
TempsMi <-- (TempsBas + TempsHaut) div 2 { division
entière par 2 }
HMi <-- TempsMi div 60 { division
entière par 60 }
MnMi <-- TempsMi mod 60 { reste de la
division par 60 }
ecrire ('La mi-maree est a : ', HMi, 'H', MnMi)
ecrire ('avec la hauteur d eau : ', HauteurMi ,
'm')
fin

Exemple d'algorithme

L'algorithme suivant, écrit de façon informelle, décrit une

version simplifiée du calcul des impôts dus par un
contribuable :

debut
demander a l'utilisateur son revenu annuel
memoriser sa reponse sous le nom: revenu
demander a l'utilisateur son nombre de part
memoriser sa reponse sous le nom: nbparts
SI revenu/nbparts < 25460
ALORS afficher : Vous n'avez pas d'impots a payer
SINON afficher : Le montant de votre impot est:
(revenu*0,25)-(nbparts*5260)
fin

6. Fonctions et procédures

39
 6.1.Définition

Une procédure représente un bloc d'instructions combinées, le cas échéant, avec des structures
de contrôle. une fois définie, elle peut être utilisée dans le programme comme si elle était
native du langage.

Exemple

Entrée Sortie

Tableau de points 1/2  P0Pi  P0Pi+1 ints Surface

L'entête d'une fonction spécifie son nom, le type de son résultat, et les paramètres (avec leurs
types). Ces paramètres sont considérés comme les données transmises à la fonction, c'est à
dire l'entrée de la fonction. Il peut arriver que la fonction modifie ces paramètres lors de
l'exécution de son algorithme. On parle alors de paramètre modifiable : il s'agit à la fois d'une
entrée et d'une sortie de l'algorithme. La déclaration d'un tel paramètre dans la liste des
paramètres se fait de la manière suivante :

fonction nom(nom_param InOut : type_param):type_résultat

Exemple :

echanger(tableau T, entier i, entier j)

debut
entier M
M<-T(i)
T(i)<-T(j)
T(j)<-M
fin

Une fonction est basée sur le même principe qu'une procédure. Seulement la procédure ne se
contente que d'exécuter les instructions qui la composent alors que la fonction renvoie une
valeur : la procédure est utilisée comme une primitive alors que la fonction est utilisée par
affectation ou en paramètre d'un autre bloc.

(Les paramètres sont des variables qui permettent d'utiliser plusieurs fois les procédures et
fonctions avec des valeurs différentes.)

[Link] : Pseudo-code – Tri Bull

40
 tri_bulle(tableau T) tri_bulle_optimise(tableau T)
debut debut
entier longueur, i entier longueur, i
booleen inversion booleen inversion

longueur<-taille(T) longueur<-taille(T)

faire faire
inversion=faux inversion<-faux
pour i=0 à (longueur-1) pour i=0 à (longueur-1)
si T(i)>T(i+1) si T(i)>T(i+1)
echanger(T,i,i+1) echanger(T,i,i+1)
inversion<-vrai inversion<-vrai
fin si fin si
fin pour longueur<-longueur-1
tantque inversion fin pour
fin tantque inversion
fin

public static void triBulle(int tableau[]) public static void

{ triBulleOptimise(int tableau[])
int longueur=[Link]; {
boolean inversion; int longueur=[Link];
boolean inversion;
do
{ do
inversion=false; {
inversion=false;
for(int i=0;i<longueur-1;i++)
{ for(int i=0;i<longueur-1;i++)
if(tableau[i]>tableau[i+1]) {
{ if(tableau[i]>tableau[i+1])
echanger(tableau,i,i+1); {
inversion=true; echanger(tableau,i,i+1);
} inversion=true;
} }
} }
while(inversion); longueur--;
} }
while(inversion);
}

41
7. Les structures de données

On ne verra pas la conception objet qui est vue plus tard.

Nous avons vu les variables, les tableaux, mais il existe des structures de données plus
complexes.

3.1 Motivation

Les structures de données vues jusqu'à présent sont statiques. Une variable correspond à un
espace mémoire défini et figé. De même pour un tableau : le nombre de cases est fixé une fois
pour toutes. Explication : le programme réserve de la mémoire lors de la déclaration de
variables; on ne sait pas ce qu'il y a dans la mémoire autour de l'espace réservé; on ne peut
donc pas augmenter l'espace réservé de façon contiguë.
D'où l'idée de faire des structures de données dynamiques. On se rend bien compte qu'on a
très souvent besoin de rajouter/enlever des données de façon dynamique (Carnet d'adresse,
liste de notes, etc...).

3.2 Listes chaînées

``Une liste chaînée est une structure de données dans laquelle les objets sont arrangés
linéairement. Toutefois, contrairement au tableau, pour lequel l'ordre linéaire est déterminé
par les indices, l'ordre d'une liste chaînée est déterminé par un pointeur dans chaque objet.''

[Link] exemple:

contenu(Liste) = 9
contenu(suivant(Liste) = 3
contenu(suivant(suivant(Liste)) = 5
contenu(suivant(suivant(suivant(Liste))) = 2

Liste est une variable (un espace mémoire) dans laquelle il y a un pointeur (une flèche) vers la
première cellule (premier maillon de la chaîne). Chaque cellule (ou maillon) est constitué,
dans notre exemple, de deux cases mémoire :

42
  une case où il y une valeur entière appelée contenu
 une case où il y a un pointeur appelée suivant

Pour chaîner les éléments, il faut mettre dans suivant le pointeur vers la cellule suivante.

On peut voir les listes chaînées un peu comme une course au trésor. Au début, on vous
indique où est le premier trésor (sous le chêne par exemple). Vous allez chercher le premier
élément (trésor) et avec il y a un papier qui vous dit où est le second élément (sous la
balançoire), et ainsi de suite...
Vous ne savez pas au début où sont les éléments. Vous devez accèder à un élément pour
savoir où trouver le suivant.

[Link] exemple: programme qui affiche les éléments d'une liste

AFFICHER_LISTE(Liste)
curseur <- Liste
tant que (curseur <> NIL)
faire afficher(contenu(curseur))
curseur <- suivant(curseur)

Bien entendu, on peut mettre plusieurs informations dans chaque cellule de la liste chaînée,
c'est à dire qu'on peut faire des cellules ``plus grosses'' avec plus de cases mémoires. On
conservera tout de même la case suivant qui permet de chaîner les éléments (si on ne conserve
pas cette case, comment chaîner les éléments entre eux ???).

[Link] exemple: cellule plus complexe

Dans cette cellule, il y a les cases téléphone, portable, bureau et anniversaire dans lesquelles
ont met des chiffres et les cases Nom, Prénom et Adresse dans lesquelles ont met du texte. La
case suivant est toujours une case contenant un pointeur.

En quoi une liste chaînée est dynamique ? On crée une cellule, et on l'accroche dans la liste en
mettant à jour les champs suivant.

3.2.1 Exercice : Ajout de cellule à la fin / au début

43
Ecrire un algorithme Ajout_fin(cellule, liste) qui ajoute une cellule pointée par cellule à la fin
de la liste liste.

Première façon FAUSSE d'écrire l'algorithme:

Ajout_fin(cellule, liste)
curseur <- liste
tant que (curseur <> NIL)
faire curseur <- suivant(curseur)
curseur <- cellule

Pourquoi cette solution est fausse ?

curseur est une variable de type pointeur (c'est une case mémoire avec un pointeur à
l'intérieur). A la fin du programme, on sort de la boucle tant que lorsque la variable curseur
vaut NIL. On fait ensuite pointer le pointeur contenu dans la case curseur vers la cellule que
l'on souhaite ajouter. Nulle part dans cet algorithme on a mis un pointeur sur la cellule cellule
dans une case mémoire suivant de la liste chaînée.

Je vous propose cette solution:

Ajout_fin(cellule, liste)
si (liste = NIL)
alors
liste <- cellule
sinon
curseur <- liste
tant que (suivant(curseur) <> NIL)
faire curseur <- suivant(curseur)
suivant(curseur) <- cellule
ou alors avec une variable cellule_précédente
Ajout_fin(cellule, liste)
curseur <- liste
cellule_précédente <- NIL
tant que (curseur <> NIL)
faire cellule_précédente <- curseur
curseur <- suivant(curseur)
si (cellule_précédente = NIL)
alors
liste <- cellule
sinon
suivant(cellule_précédente) <- cellule

Une solution pour ajouter au début de la liste:

Ajout_début(cellule, liste)
si (liste = NIL)
alors
liste = cellule
sinon
suivant(cellule) <- liste

44
 liste <- cellule

3.2.2 Exercice : Ajout de cellule dans une liste triée

On suppose que la liste liste est triée dans l'ordre croissant. Ecrire un algorithme
Ajout_triée(cellule, liste) qui ajoute une cellule pointée par cellule à sa place dans la liste.

Comme énoncé précédemment, il faut gérer tous les cas de figures. Ici, il a 4 cas:

1. la liste est vide on met la cellule toute seule dans la liste

2. la liste n'est pas vide et le premier élément a un contenu supérieur au contenu de la
cellule on insère la cellule au début
3. la liste n'est pas vide et toutes les cellules ont des contenus inférieurs au contenu de la
cellule on insère la cellule à la fin
4. la liste n'est pas vide et il y des cellules avec des contenus plus grands et des contenus
plus petits que le contenu de la cellule on insère la cellule au milieu d'autres
cellules

Ajout_triée(cellule, liste)
si liste <> NIL
alors
curseur <- liste
cellule_précédente <- NIL
tant que (curseur <> NIL) ET (contenu(curseur) < contenu(cellule))
faire cellule_précédente <- curseur
curseur <- cuivant(curseur)
si (cellule_précédente = NIL)
alors
liste <- cellule
suivant(cellule) <- curseur
sinon
suivant(cellule_précédente) <- cellule
suivant(cellule) <- curseur
sinon
liste <- cellule

3.2.3 Exercice : Suppression de cellule

Ecrire un algorithme Supprimer(nombre, liste) qui supprime la cellule de contenu nombre de

la liste liste.
Supprimer(nombre, liste)
si (liste <> NIL)
alors
curseur <- liste
cellule_précédente <- NIL
tant que (curseur <> NIL) ET (contenu(curseur) <> nombre)

45
 faire cellule_précédente <- curseur
curseur <- suivant(curseur)
si (curseur <> NIL)
alors
suivant(cellule_précédente) <- suivant(curseur)

Que devient la cellule supprimée ? Soit il y a un garbage collector, soit on la supprime à la

main.

3.2.4 Exercice: Mise à jour de champs

On suppose que chaque cellule de la liste liste contient les champs nom, prénom et note.
Ecrire un algorithme Mise_a_jour(liste, nom_recherché, prénom_recherché, note_à_mettre)
qui met la note note_à_mettre à l'étudiant de nom nom_recherché et de prénom
prénom_recherché dans la liste.
Mise_a_jour(liste, nom_recherché, prénom_recherché, note_à_mettre)
si (liste <> NIL)
alors
curseur <- liste
tant que (curseur <> NIL)
ET ((nom(curseur) <> nom_recherché) OU
(prenom(curseur) <> prenom_recherché))
faire curseur <- suivant(curseur)
si (curseur <> NIL)
alors
note(curseur) <- note_à_mettre
Quelques mots sur les conditions:
 le contraire de (a OU b) est ((NON a) ET (NON b))
 le contraire de (a ET b) est ((NON a) ET (NON b))

Rappel:
 (NON VRAI) = FAUX
 (NON FAUX) = VRAI

Dans l'algorithme précedent, on souhaite arrêter de parcourir la liste

quand on est arrivé à la fin de la liste

OU
quand on a trouvé une cellule avec le champ Nom égal à nom_recherché
ET le champ Prénom égal à prénom_recherché
c'est à dire
quand curseur = NIL

OU
quand nom(curseur) = nom_recherché ET prenom(curseur) = prenom_recherché
On arrête de parcourir la liste quand la condition précédent est vraie, autrement dit, on
parcourt la liste tant que la condition précédente est fausse, ce qui donne
tant que
(NON
((curseur = NIL)

46
OU
((nom(curseur) = nom_recherché) ET (prenom(curseur)=prenom_recherché))
ce qui donne avec les règles énoncées plus haut
tant que
((curseur <> NIL)
ET
((nom(curseur) <> nom_recherché) OU (prenom(curseur)<>prenom_recherché))

3.2.5 Exercice : Fusion de listes

On suppose que l'on dispose de deux listes liste1 et liste2 triées dans l'ordre croissant. Ecrire
un programme qui réalise la fusion des ces listes en une liste elle même triée.

Plusieurs façons de faire:

 mettre deux curseurs sur liste1 et liste2 et toujours comparer le contenu des deux
curseurs en avançant d'un cran à la fois
 mettre deux curseurs sur liste1 et liste2 et avancer un curseur tant que les contenus
sont inférieurs au contenu de l'autre curseur
 copier la liste1 et insérer un par un les éléments de la liste2

. Spécification fonctionnelle d'une Liste

1.1 Opérations
Soient LISTE le type liste et ELEMENT le type des éléments de la liste.
Type d'opérations Profil et définition de l'opération
construction liste_vide : LISTE
constante désignant une liste vide
consultation longueur : LISTE ENTIER
fournit la longueur d'une liste L
ieme : LISTE x ENTIER ELEMENT
fournit l'élément de rang k d'une liste L
modification insérer : LISTE x ENTIER x
ELEMENT LISTE
modifie l'élément de rang k d'une liste L
par un élément e
supprimer : LISTE x ENTIER LISTE
suppression de l'élément de rang k d'une
liste L

Exemple : Supprimer
// supprimer l'élément de rang k d'une liste L
SI la liste L n'est pas vide ALORS
SI le rang k de suppression est valide ALORS

47
décaler les éléments e(k+1), …, e(n) vers la gauche;
SINON
afficher le message d'erreur "rang non valide";
FIN SI;
SINON
afficher le message d'erreur "liste vide";
FIN SI;

Dans un pseudo langage de programmation, on écrira :

// supprimer l'élément de rang K d'une liste L
PROCEDURE supprimer (MISE A JOUR L, ENTREE K)
GLOSSAIRE
L : enregistrement composé de 2 champs :
un tableau VALEURS et une variable NB_VALEURS;
K : rang de l'élément à supprimer;
I : variable de parcours du tableau [Link] pour les décalages;
DEBUT
SI L.NB_VALEURS != 0 ALORS
SI K >=1 ET K <= L.NB_VALEURS ALORS
// décaler les éléments e(k+1), …, e(n) vers la gauche
I K;
TANT QUE I < L.NB_VALEURS FAIRE
[Link][I] [Link][I+1];
I I + 1;
FIN TANT QUE;
// décrémenter le nombre d'éléments de la liste L
L.NB_VALEURS L.NB_VALEURS - 1;
SINON
ERREUR("rang non valide");
FIN SI;

Algorithmie Les listes chaînées

SINON
ERREUR("liste vide");
FIN SI;
FIN

2.2 Représentation dynamique

En représentation dynamique, on représente chaque élément de la liste par une cellule en
mémoire :
Une cellule = un enregistrement composé de 2 champs :
- 1 champ VALEUR
- 1 champ SUIVANT : adresse (pointeur) de la cellule suivante
La liste en elle-même sera représentée par un pointeur sur la première cellule.
e1Le2eien......
On déclarera :
Pointeur Liste sur enregistrement CELLULE;
Enregistrement CELLULE composé de 2 champs
VALEUR (de type ELEMENT) et
SUIVANT (de type pointeur sur enregistrement CELLULE);

48
 Nous avons ici un cas de structure de données récursive (SUIVANT étant un pointeur sur
enregistrement de même type)
Remarque
- Pour accéder à l'élément ei il faudra balayer séquentiellement les i-1 éléments qui
précédent (s'ils existent)
- Le passage d'une cellule à la cellule suivante, si L désigne l'adresse de la cellule
courante, s'écrira :
L L^.SUIVANT
Algorithme de l'opération supprimer
// supprimer l'élément de rang k d'une liste L
SI la liste L n'est pas vide ALORS
SI le rang k est égal à 1 ALORS
supprimer la première cellule;
SINON
rechercher séquentiellement la cellule k;
SI cette cellule k existe ALORS
supprimer la cellule;
SINON
afficher le message d'erreur "rang incorrect";

Algorithmie Les listes chaînées

FIN SI;
FIN SI;
SINON
afficher le message d'erreur "liste vide";
FIN SI;

Pour traduire cette algorithme en pseudo langage de programmation, il est nécessaire de

déclarer 2 pointeurs pour parcourir la liste :
PTR_PRECEDENT
PTR_COURANT
Deux cas de figure se présentent :
• Suppression en tête de liste :
e1Le2eien......
L L^.SUIVANT;
• Suppression dans la liste :
eke1Leken......ek-1
PTR_PRECEDENT^.SUIVANT PTR_COURANT^.SUIVANT;
D'où l'écriture de la fonction supprimer :
// supprimer l'élément de rang K d'une liste L
PROCEDURE supprimer (MISE A JOUR L, ENTREE K)
GLOSSAIRE
L : pointeur sur un enregistrement CELLULE composé de 2 champs
VALEUR et SUIVANT;
K : rang de l'élément à supprimer;
I : compteur de cellules pour la recherche séquentielle de la cellule K;
PTR_COURANT : pointeur sur la cellule courante;
PTR_PRECEDENT : pointeur sur la cellule précédente vérifiant
PTR_COURANT = PTR_PRECEDENT^.SUIVANT;
DEBUT

49
SI L != NULL ALORS
SI K = 1 ALORS
// suppression en tête de liste
L L^.SUIVANT;
SINON
// suppression dans la liste

Algorithmie Les listes chaînées

// rechercher l'élément de rang K de la liste
I 1;
PTR_COURANT L;
TANT QUE (I <= K) ET (PTR_COURANT != NULL) FAIRE
I I + 1;
PTR_PRECEDENT PTR_COURANT;
PTR_COURANT PTR_COURANT^.SUIVANT;
FIN TANT QUE;
SI PTR_COURANT != NULL ALORS
// la cellule de rang K existe, la supprimer
PTR_PRECEDENT^.SUIVANT PTR_COURANT^.SUIVANT;
SINON
ERREUR("Rang invalide");
FIN SI;
FIN SI;
SINON
ERREUR("Liste vide");
FIN SI;
FIN

50