1

Contents
Chapitre 1 Notions d’algorithmes .............................................................................................. 5
I. Généralités ...................................................................................................................... 5
II. Résolution de problème et structure d’un algorithme .......................................... 6
III. Le LDA (langage de description algorithmique) ................................................... 8
a. Définition ....................................................................................................................... 8
b. Syntaxe .......................................................................................................................... 8
c. Description des Ressources Données .......................................................................... 9
d. Quelques types .............................................................................................................. 9
e. Quelques primitives.................................................................................................... 11
f. Les structures de contrôles fondamentales .............................................................. 13
Chapitre 2 : Procédure et Fonction ........................................................................................... 19
I. Généralités .................................................................................................................. 19
II. Procédures ............................................................................................................... 19
a. Procédure sans paramètre ......................................................................................... 19
b. Procédure avec paramètres ....................................................................................... 20
III. Fonctions ................................................................................................................. 20
Chapitre 3 Types complémentaires ......................................................................................... 22
I. Le type simple construit par énumération ............................................................... 22
II. Les types simples construits par intervalle .......................................................... 22
I. Le type ensemble ........................................................................................................ 22
II. Le type string .......................................................................................................... 23
III. Le type Fichier ........................................................................................................ 24
Chapitre 4 Introduction à la récursivité et à la programmation récursive ................................ 26
I. Notion de récursivité .................................................................................................. 26
II. Récursivité des actions ........................................................................................... 28
1. Réalisation algorithmique ........................................................................................ 28
2. Visibilité des objets d’une procédure (ou fonction) ................................................. 29
3. Exemple de procédures récursives ........................................................................... 29
4. Programmation récursive ......................................................................................... 29
Chapitre 5 Initiation au langage et à la programmation en C ................................................... 32
I. Introduction ................................................................................................................ 32
I. Structure générale d’un programme ............................................................................. 33
II. Variables et identificateurs ........................................................................................... 33
III. Variable global, variable locale ................................................................................ 34
IV. Affectation, saisie, affichage .................................................................................... 34
VI. Les types classiques ................................................................................................. 35

2
VII. Type enregistrement ................................................................................................. 37
VIII. Procédures et fonction en C ..................................................................................... 37

3
 Partie 1 : Initiation à la programmation

4
Chapitre 1 Notions d’algorithmes
I. Généralités
L’informatique a pour objet le traitement automatique de l’information considérée comme
support des connaissances du monde réel. Le traitement dont il est question ici se fait par un
ordinateur1 ou calculateur. Ce dernier ne peut effectuer des traitements sur des données que
parce qu’il reçoit de la part du (des) programmeur (s) des instructions (liste des actions à
exécuter) lui indiquant comment effectuer ces traitements. Ces instructions écrient en langage
machine (Pascal, langage C, etc.) sont d’abord décrites de façon claire (sans ambiguïtés) à l’aide
d’algorithmes. L’algorithme sert donc au (x) programmeur (s) à décomposer un problème en
sous-problèmes (problèmes plus simples) afin d’en faciliter la résolution. On pourrait le définir
comme l’énoncé d’une suite d’opérations permettant de donner la réponse à un problème. Voici
une autre définition est la suivante : « un algorithme est une procédure de calcul bien définie,
qui prend en entrée une valeur, ou un ensemble de valeurs, et qui produit en sortie, une valeur
ou un ensemble de valeurs ». Un algorithme est donc une séquence d’étapes de calcul
permettant de passer de la valeur d’entrée à la valeur de sortie.
Plus formellement, un algorithme A est une multi-application de l’ensemble des données en
entrées vers l’ensemble des données résultats tel que pour tout E données d’entrée et R résultat
d’un problème, 𝐴(𝐸) = 𝑅
La programmation consiste à se donner un E et un R et à fournir A (éventuellement exploitable
sur une machine donnée).
L’algorithme A est spécifié sur la base d’une décomposition en un nombre fini d’opérations
𝑂𝑘 , 𝑘 = 1, … , 𝑛 avec 𝐴 = 𝑂𝑛 ∘ 𝑂𝑛−1 ∘ … ∘ 𝑂1
𝐸1 = 𝐸
𝑂𝑘−1 (𝐸𝑘−1 ) = 𝐸𝑘 , 𝑘 = 2, … , 𝑛 − 1
𝑂𝑛 (𝐸𝑛 ) = 𝑅
L’état de sortie (ou prédicat de sortie) d’une opération est l’état d’entrée (prédicat d’entrée) de
l’opération suivante.
Une fois un algorithme d’un problème trouvé, il faut le transcrire dans un langage de
programmation (plus simple que le français dans sa syntaxe). L’algorithme transcrit en langage
de programmation est appelé code. Celui-ci est compiler (pour le rendre compréhensible par la

1
Machine automatique qui permet d’effectuer dans le cadre de la programmation des ensembles d’opérations
arithmétiques et logiques à des fins scientifiques, administratives ou comptable

5
machine) et exécuté par un compilateur (celui du langage : compilateur Pascal, compilateur C,
etc.) pour donner la réponse au problème.
Apprendre l’algorithmique, c’est apprendre à manier la structure logique des programmes.

II. Résolution de problème et structure d’un algorithme

1. Différentes étapes de déduction d’un programme à partir d’un problème

Un algorithme peut être vu comme un outil de résolution d’un problème calculatoire bien défini.
L’énoncé du problème spécifie en termes généraux la relation désirée entre l’entrée et la sortie.
L’algorithme décrit une procédure de calcul spécifique permettant d’établir cette relation.
La résolution automatique d'un problème passe par trois des étapes décrites par l’organigramme
suivant.
Énoncé du problème
(statique)
Niveau de
l’homme Algorithme

Langage assembleur Langage évolué

Niveau de Assembleur Compilateur ou interpréteur

machine

Programme en langage binaire (langage machine)

Dans ce chapitre nous avons fait le tour de toutes les étapes importantes à la résolution d’un
problème avec un ordinateur. La figure suivante résume ces différentes étapes.

Figure 5.1 Principales étapes de la résolution d’un problème avec l’ordinateur

6
L’Enoncé du problème ou cahier des charges doit préciser les données en entrées au
problème, les besoins en traitement et les résultats souhaités. Ainsi, l’étape Enoncé-
programme va se décomposer en deux :
• Enoncé- algorithme : à ce niveau la question de l’analyse et de la conception d’une
solution informatique du problème spécifié par son énoncé est posée. Ce travail devra
aboutir à une description algorithmique de ce traitement que l’on appelle algorithme.
• Algorithme-programme : la question de l’obtention d’un programme (avec toutes les
préoccupations techniques qui sont légitimes) est ramenée à une phase de production
par traduction en un langage cible choisi
2. Moyen à mettre en œuvre pour passer d’une étape à l’autre
• Passage de l’algorithme au programme : C’est la transition qui doit être la plus facile
dans la mesure où l’algorithme est un automate décrivant rigoureusement la suite finie
des opérations permettant de faire passer les données d’un état d’entré à un état de
résultat : solution du problème demandé. Il s’agira essentiellement d’une réécriture de
l’algorithme dans un langage cible de programmation sur une machine cible. C’est une
phase qui doit être indépendante de toute l’activité d’analyse et de conception.
• Passage de l’énoncé à l’énoncé explicite : l’énoncé fournit une propriété générale du
résultat et ne permet pas toujours d’obtenir la solution algorithmique. En revanche
l’énoncé explicite doit spécifier le procédée de calcul permettant d’obtenir
l’algorithme. Il s’agit essentiellement d’une analyse de l’énoncé de manière à :
o Identifier les informations fondamentales manipulées (reconnaissance)
o Classer ces informations en entrée (hypothèse du problème), sortir (résultat ou
conclusion du problème) et de définir leur organisation (compréhension)
o Proposer une solution explicite des procédés de calcul et de mise en œuvre qui
permettent d’obtenir ces résultats (modélisation)
Les outils utilisés dans cette description dépendent évidemment de la nature du
problème. Ils peuvent être graphique, de type texte, algébrique, etc.
• Passage de l’énoncé explicite à l’algorithme : l’algorithme sera obtenu par réécriture
de l’énoncé explicite en incluant un ordre dans le procédé de traitement. Cela nécessite
un langage adapté à la reformulation que l’on appelle Langage de Description (ou
notation) Algorithmique ou LDA. Comme tout langage, ce langage se définit au mois
par deux ensembles : Un ensemble formé du vocabulaire général du lange et un autre
décrivant sa grammaire.

7
Nous allons développer ce dernier point.

III. Le LDA (langage de description algorithmique)

a. Définition

- Un texte du LDA est la concaténation de mots de 𝑉𝑡 séparé par un ou plusieurs espaces

et respectant rigoureusement les règles grammaticales correspondantes et édictées
dans G.
- Pour des raisons de lisibilité et de clarté de l’écriture les verbes du langage seront
soulignés pour les mettre en évidence par rapport aux objets du programmeur.
- Un texte du LDA représente un algorithme et a impérativement la structure générale
suivante :
ALGORITHME identificateur
Description des Ressources de l’algorithme
{
Description de la séquence des opérations à effectuer.
}

b. Syntaxe

- Ce texte algorithmique commence nécessairement par le mot clef ALGORITHME et

se termine par un point (fin de l’algorithme).
- Le corps du texte est formé de deux parties : une première qui sert à décrire toutes les
ressources (données ou actions) utilisées dans le procédé opératoire de l’algorithme
qui sera décrit dans la deuxième partie. D’où découle la conséquence syntaxique
suivante : il ne peut y avoir de ressources utilisées dans le traitement qui n’aient été
décrites
- Règle syntaxique de construction d’un identificateur : un identificateur est le nom
donné par le programmeur à tout objet manipulé dans l’algorithme. La règle de
construction est : un identificateur est une suite de caractère commençant par un
caractère alphabétique. Exemple : somme, impôt, salaire_de_base. Tous les caractères
ont le même niveau d’écriture : pas d’indice ni d’exposant. Il n’y’a pas de limitation
du nombre de caractères à utiliser, cependant le bon sens nous amène à profiter de
cette souplesse de manière à créer les identificateurs s’approchant le plus possible de
la signification de l’objet qu’ils désignent sans peut-être exagérer par sa longueur.

8
Pour construire des identificateurs pertinents, on pourra se référer aux indications suivantes :
• Choisir des identificateurs facilement prononçables
• Eviter les abréviations non courantes
• Choisir des constructions de préférences courtes et dans le cas des compositions de
mots utiliser un caractère de concaténation (comme le sous tiret _) pour marquer la
suite des sens véhiculés par l’identificateur. Exemple : bourse_etudiant_inphb
• Identifier distinctement les informations, chaque fois que cela est possible.
L’identificateur bourse_etudiant_inphb est plus évocateur que bourse.
Par ailleurs, le texte algorithmique est constitué de phrases logiques séparées par le point
virgule. Par conséquent, il n’y’a pas forcément une phrase par ligne (de notre feuille), seules
des considérations de lisibilité et de clarté peuvent nous amener à ne pas effectivement trop la
surcharger. Comme exemple, la première phrase de notre LDA présenté ci-dessus sous sa
forme générale est ALGORITHME identificateur ;

c. Description des Ressources Données

Toute données, quelle soit d’entrée ou de sortie ou intermédiaire de calcul, manipulée dans la
partie description des ressources d’un algorithme est caractérisée par la double indication de

Contenu
Contenan
t
son contenant, représenté par le nom de la donnée ou identificateur et son contenu, valeur de
la constante prise par la donnée.
Remarque
- Le contenu d’une donnée peut varier d’un instant à l’autre mais seul le dernier est
évidemment conservé et le contenant lui à priori ne change jamais.
- Une donnée est souvent appelée variable, ce qu’il faut accepter avec la description ci-
dessus (seules les contenus peuvent varier …)

d. Quelques types

Concernant les types, certains sont bien sûr prédéfinis, ce sont ceux qui seront considérés
comme de base et permettront par construction d’obtenir des types plus sophistiqués.
Dans la classification simplifiée des types on distingue les types simples dont les constantes
atomiques (constituées d’un seul tenant ou indécomposable) et les types organisés dont les
constantes sont composées d’autres constantes.

9
 - Quelques types simples : les entiers relatifs, les nombres réels, les constantes logiques
et l’ensemble de tous les caractères du LDA sont désignés respectivement par les mots
clés ENTIER, REEL, LOGIQUE et CARACTERE.
Type Description Exemple
ENTIER est décrit en décimal signée, le On a les exemples suivants. 1969,
signe + pouvant être omis s’il est -56.
positif.
REEL Est aussi écrit en décimale signée 651.48, -5,07.
avec le point (ou la virgule) pour
séparer la partie entière de la partie
réelle
LOGIQUE est formé des deux constantes
VRAI et FAUX.
CARACTERES Représente l’ensemble de tous les On a les exemples suivants. ‘a’,
caractères (en d’autres termes son ‘A’, ‘1’
alphabet). Les constantes caractères
sont mises entre quotte.
- Le type organisé : On dit qu’une information est organisée ou structurée si elle est une
collection finie et dénombrable d’autres informations. Elle est alors dite composite et
chacune des informations qui la composent (ou composantes) peut être aussi structurée
de la même manière. Il apparait une ‘’récursivité’’ au niveau de la définition de l’objet
structuré du fait qu’il se définit par lui-même, la condition d’arrêt de reproduction de la
définition est qu’au dernier niveau les objets soient de types simples : entier, réel,
logique, etc.).
Le type TABLEAU est un cas particulier ou l’objet est une collection d’objets de même
type et en nombre fixe. Chaque élément du tableau est appelé composante et le domaine
de valeurs est le produit cartésien des domaines de valeurs de chaque composante.
La syntaxe de désignation du type est : TABLEAU[indice de début .. indice de fin] DE
type d’une composante. Indice de début et indice de fin sont des constantes d’un type
simple quelconque mais ordonné totalement. Ils permettront de fixer le nombre de
composantes et de pouvoir identifier chaque composante par un indice dont le contenu
est compris dans l’intervalle [indice de début ; indice de fin].
La syntaxe d’une description de ressources données est la suivante :

Liste d’identificateurs : type

Liste d’identificateurs est soit un identificateur soient plusieurs identificateurs (ayant le
même type) séparés par une virgule. Par exemple, on a :
sal1, sal2 : REEL ;
Etat : LOGIQUE ;

10
 i, j : ENTIER ;
catégorie : CARACTERE ;

Dans le cadre de notre LDA, nous avons la possibilité d’identifier des types. Un intérêt
possible est le cas où une description de types est utilisée à plusieurs endroits de l’algorithme
(nous y reviendrons) mais aussi pour apporter de la clarté dans les descriptions de type
organisés :
Identificateur d’un type=type
Identificateur de type est le nom donné au type et type est la description du type. Comme
exemple, on a :
occupe=LOGIQUE ;
siege=occupe ;
compartiment=TABLEAU[1..6] DE siège ;
wagon=TABLEAU[1 .. 12] DE compartiment ;
train=TABLEAU[1 .. 10] DE wagon ;
untrain : train

Occupe, siège, compartiment, wagon et train sont des noms de type. Ils doivent servir de
descripteurs de données. Dans notre cas seul la donnée untrain est créée (instanciation) et
décrite comme de type train. L’accès à une composante se fait par l’intermédiaire d’une
variable de type simple correspondant au type de l’intervalle.
Ainsi si i, j, k : ENTIER ; est une déclaration alors untrain[i,j,k] est un logique indiquant l’état
d’occupation du siège k du compartiment J du wagon i du train.

e. Quelques primitives

Ce sont des facilités d’écriture qui permettent une action spécifique comme l’affectation, les
expressions arithmétiques et logiques et les entrées-sortie.
- L’affectation : le symbole utilisé est la flèche renversée ⟵. On a donc la syntaxe
suivante :
identificateur⟵ expression du même type.

La constante provenant de l’évaluation de l’expression est transférée comme contenu

de l’identificateur, ce qui impose qu’elle soit du même type que celui de
l’identificateur. Une expression garde le sens habituel d’une formule comportant des

11
 opérateurs et des opérandes. Elle est évaluée de la gauche vers la droite en respectant
les ordres de priorité prédéfinis.
- Les expressions arithmétiques : les opérandes sont des données de type ENTIER ou
REEL, et les opérateurs concernés sont :
Opérateurs Noms
+ Addition
- Soustraction
* Multiplication
/ Division réelle
DIV Division entière
MOD Reste de la division
entière
L’ordre de priorité est le même qu’habituellement, c'est-à-dire dans décroissant :
Règle de priorité
() Le parenthésage pour forcer la priorité
∗ / mod div Même priorité
+- Même priorité

- Les expressions logiques : celles prédéfinies sont : la négation ( NON ) , la

conjonction ET et la disjonction OU.
Les opérateurs relationnels sont applicables aux données de types simples ordonnées.
Ce sont :
Opérateurs relationnel Nom
< Strictement inférieur
<= Inférieur ou égal
> Strictement supérieur
>= Supérieur ou égal
= Egalité
<> Différent

Comme exemple on a :

x1, x2 : ENTIER
I : LOGIQUE
L’action suivante est correcte L⟵ x1=x2
- Les ENTREE/SORTIE : les primitives d’entrée/sortie vont permettre d’assurer le
transfert de constantes entre l’algorithme et une unité périphérique quelconque. Pour

12
 l’instant nous nous limiterons au cas où l’unité périphérique est l’écran-clavier.
En entrée le verbe utilisé est LIRE. Sa syntaxe est
LIRE(liste d’expression de type simple)

f. Les structures de contrôles fondamentales

On distingue trois structures de contrôle fondamentale : la séquence, l’alternative et

l’itérative.
- La séquence : elle a pour effet de séquencer dans le temps deux actions.
Syntaxiquement on utilise le point-virgule (;) comme séparateur d’actions (action1 ;
action2, exprime que action 1 s’exécute avant action 2). En guise d’illustration
considérons l’algorithme suivant.
ALGORITHME identificateur ;
A, B, C, D : ENTIER;
{A⟵1 ; B⟵ 3 ;
C⟵A+B ; D⟵A-B ;
A⟵C+2*B ; B⟵C+B ;
C⟵A*B ; D⟵ B+D; A⟵ D*C
}.
Dans l’algorithme précédent la dernière action n’est pas suivie de point-virgule
puisqu’aucune action ne vient en séquence. Par ailleurs on a pris la précaution de
n’utiliser aucune donnée dans une expression qui n’ait un contenu au préalable (soit
par initialisation soit par calcul). Pour voir la séquence des opérations on construit le
tableau de simulation qui permet de suivre le déroulement successif des états des
données de l’algorithme (le dernier état sera état des résultats).
A B C D
1 3
4
-2
10 7
70
5
350
On voit bien que l’algorithme calcule effectivement les contenus de A, B, C, D à
partir de A et B, mais ne donne aucun moyen de s’en apercevoir. Il est judicieux, de
terminer le traitement par une instruction ECRIRE. De même les calculs étant toujours

13
 réalisés pour les mêmes contenus, il peut être intéressant de rendre l’algorithme plus
général en remplaçant les instructions d’initialisations par une instruction LIRE. Soit :
ALGORITHME identificateur ;
A, B, C, D : ENTIER;
{
LIRE(A,B) ;
C⟵A+B ; D⟵A-B ;
A⟵C+2*B ; B⟵C+B ;
C⟵A*B ; D⟵ B+D;
A⟵ D*C
ECRIRE(A,B,C,D)
}.

Cette organisation des traitements est une bonne structure de calcul : en effet chaque
fois qu’il est possible de rassembler toutes les initialisations au début, de terminer par
toutes les opérations d’affichage et entre les deux la partie calcul vous créez une
disposition qui peut apporter de la clarté et de la lisibilité à votre algorithme.
- L’alternative : Supposons qu’on ait deux actions : action1 et action2. On voudrait à
partir de l’évaluation d’une expression logique condition exécuter exclusivement l’une
ou l’autre. La syntaxe est :
SI (condition) ALORS action1 SINON action2
Une illustration est donnée par l’exemple qui suit.
SI (𝑥 <= 𝑦) ALORS
𝑥 ⟵𝑥+𝑦
SINON
𝑥 ⟵𝑥−𝑦

Une variante alternative au cas où action2 est vide, en d’autres termes, on voudrait juste
exécuter une action si une condition était réalisée. La syntaxe suivante est admise et
s’appelle la conditionnelle :
SI (condition) ALORS action1

Remarquons que, dans le cas où action1 ou action 2 est composé de plusieurs actions,
un problème de syntaxe peut se poser. Cependant, si nous avons besoin de faire
considérer syntaxiquement un groupe d’action comme une seule, cela peut être réalisée

14
 par la primitive dite de blocage d’actions (on met toutes les actions concernées entre
accolade) :

SI (condition) ALORS
{ action11 ;
action12 ;
action13
}
SINON
{ action21 ;
action22
}

- L’itérative : comme son nom l’indique, on dispose d’une action (élémentaire ou

bloquée) : action et d’une expression logique : condition. La phrase suivante :
TANT QUE (condition) FAIRE action

A pour effet d’exécuter action autant de fois que nécessaire et de ne s’arrêter que si
condition bascule à FAUX. Action peut n’être exécuté aucune fois (si dès le départ
condition est FAUX) ou plusieurs fois, ce qui implique que dans action des opérations
sont prévues pour faire basculer à un moment donné condition à FAUX sinon on aurait
un traitement infini ce qui n’est pas algorithmique. Une variante de l’itérative : LA
REPETITIVE : supposons qu’on veuille que action soit faite au moins une fois avant de
rentrer dans une itérative, situation qui est courante. On peut écrire :
Action ;
TANTQUE (condition) FAIRE action
Une syntaxe est prévue pour ce cas
REPETER
action
JUSQUA (condition)

Action est exécutée au moins une fois ensuite condition est évaluée. Si condition est
VRAI le processus est arrêté sinon l’itération est reprise. On remarquera que le sens
du test d’arrêt est contraire à celui de l’itérative et par construction action est faite au
moins une fois. Si action est composée de plusieurs il n’est pas utile de le bloquer
puisque REPETER JUSQUA joue déjà ce rôle : formellement il n’y’a pas

15
 d’ambiguïté. Une caractéristique de ces deux ordres d’itération est qu’on ne connait
pas à priori le nombre de fois qu’i faut exécuter action. Lorsque ce nombre est connu,
on utilise la variante : BOUCLE :
POUR identificateur←expression initiale JUSQUA expression finale FAIRE action
Identificateur va jouer le rôle de compteur, il doit donc être d’un type simple énumérable
et ordonné, d’où pour le moment ENTIER, CARACTERES, et LOGIQUE ; traduisons
cette variante en utilisant TANT QUE avec la convention suivante succ(identificateur)
dépend du type de identificateur est la constante successeur dans l’ordre correspondant
au type de l’identificateur.
identificateur←expression initiale ;
TANTQUE (identificateur→expression finale) FAIRE
{ action ;
identificateur←succ(identificateur)
}

Exemple d’écriture d’algorithme sous forme d’organigramme

Organigramme

Début

a, b, c

𝐷 = 𝑏 2 − 4𝑎𝑐

NON
𝐷
>0
OUI
NON
𝐷
−𝑏 + ξ𝐷
=0 𝑥1 =
2𝑎
OUI

−𝑏
affiché pas solution 𝑥0 = −𝑏 − ξ𝐷
2𝑎 𝑥2 =
2𝑎

Affiché 𝑥0
Affiché 𝑥1 et 𝑥2

Fin

16
Application
Ecrire l’algorithme (en utilisant un organigramme) de la résolution d’un système linéaire de
deux équations à deux inconnues par la méthode de Cramer (ou des déterminant)

Pseudo-code
Notre pseudo-code pour la résolution de l’équation du second degré se présente sous la forme
d’une procédure appelé POLY2-SOLVE. Elle prend comme paramètre un tableau ….qui
contient les coefficients d’une équation du second degré à résoudre
- Analyse des données en entrées et sortie, méthode de résolution, écriture de
l’algorithme
- Traduction dans pseudo-code ou langage de description des algorithmique (LDA)
IV. Les langages de programmation

1. Le langage machine

Un ordinateur ne ‘’comprend’’ qu’un seul langage dit langage machine (de première
génération) que son unité de contrôle est capable d’analyser et d’exécuter. C’est le langage
qui se situe au niveau le plus bas et ses caractéristiques sont celles vue précédemment.
2. Le langage d’assemblage

Vue la complexité des langages machines, les constructeurs ont développé un autre type de
langage dit langage d’assemblage (deuxième génération) moins ésotérique et plus facile à
utiliser. Il est constitué de la manière suivante :

• Toute instruction machine est représentée par une et une seule instruction en langage
d’assemblage.
• Les codes opérations qui étaient binaires dans le langage machine deviennent
mnémonique, exemple : ADD au lieu du code binaire de l’addition
• Les adresse des opérandes ne sont plus gérer par leur valeur numérique mais par des
symboles qui les représentent qu’on appelle identificateurs.

Par exemple pour réaliser l’instruction 𝑋 = 𝐴 + 𝐵 on pourrait avoir : 𝐴𝐷𝐷 𝐴, 𝐵, 𝑋 ce qui est
plus parlant. Ce programme ne sera pas directement exécutable car il nécessite une phase de
traduction en langage machine. L’utilitaire chargé de cette traduction est appelé assembleur.

Programme Programme
en ASSEMBLEUR en
langage langage
d’assemblage d’assemblage

3. Les langages évolués

• Les langages de troisième génération : ces langages se rapprochent des langages
naturels mais sont définis par des règles de grammaires précises. Elles ont facilité la
conception et la programmation et ont permis un développement fulgurant de la science
informatique (en se détachant de la machine par leur universalité) et de la facilité
d’utilisation des ordinateurs. L’informatique devient d’un accès beaucoup plus aisé et
tous les domaines des sciences humaines sont touchés.

17
• Les langages de quatrième génération : environnement logiciel offrant des outils prêt à
l’emploi que l’on peut aisément utiliser pour concevoir une application, un projet, etc.
La programmation reste bien sûr algorithmique mais elle s’élève à des niveaux
d’abstraction plus proches des méthodes naturelles de résolution qu’un utilisateur
adopte face à un problème. Un programme n’est plus uniquement un processus
(composition d’instruction) permettant de faire passer les données (manipulées par ces
instructions) d’un état d’hypothèse (entrée) à un état de conclusion (résultat) mais plutôt
abstrait à être une collection d’objets (entité représentant une catégorie quelconque
d’informations caractérisé par son état (ses données) et son comportement (les
traitements spécifiques qu’elle peut réaliser) s’envoyant des messages (demande
d’informations) en vue d’amener le système à un état désiré.
EXERCICES
1. Calculer le salaire d’un fonctionnaire ou auxiliaire, sachant que s’il est fonctionnaire
il cotise 6% de son salaire de base pour sa retraite 2.75 % du salaire de base pour sa
protection sociale si son salaire est plus petit que le plafond fixé par l’organisme de
gestion de la protection sociale, dans le cas contraire il cotise pour 2.75% du même
plafond.
S’il est auxiliaire il ne cotise pas pour la retraite, par contre il cotise pour la
protection sociale au taux de 5% de son salaire de base si ce dernier est inférieur ou
égal au plafond sinon il cotise pour 6.75% du plafond augmenté de 1.5% de la
différence entre le salaire de base et le plafond.
2. Résoudre dans R une équation du second degré
3. Afficher dans l’ordre trois nombres entiers et distincts.
4. On considère un texte formé de caractères et terminé par un caractère unique : ‘#’, on
voudrait connaitre :
a. Le nombre de ‘a’
b. Le nombre de voyelle
c. Le nombre de ‘le’
d. Le nombre de mots
5. On considère la suite de FIBONACCI :
𝑢0 = 𝑢1 = 1
𝑢𝑛 = 𝑢𝑛−1 + 𝑢𝑛−2
Calculer la somme des q premiers termes.
La structure d’un algorithme comporte 3 étapes : la présentation du traitement, le
traitement et l’édition des résultats.
6. Ecrire un algorithme qui détermine tous les couples (𝑚; 𝑛) avec 1 ≤ 𝑚, 𝑛 ≤ 2014 et
vérifiant la relation (𝑛2 + 𝑚𝑛 − 𝑚2 )2 = 1

18
Chapitre 2 : Procédure et Fonction
I. Généralités
Si un problème apparait difficile, il faut éviter la recherche directe de la solution ce qui
amènerait à penser à plusieurs choses à la fois et à rentrer trop vite dans le détail des actions.
Bien au contraire il s’agit :
1. D’apprécier le problème dans sa totalité ensuite de le morceler (… de le décomposer,
de le factoriser ou de le raffiner) en des sous-problèmes maitrisables (représentent une
fonction du problème analysé) et indépendants (chacun doit représenter une difficulté
dans la résolution du problème de départ) dans leurs fonctions liées dans l’ordre de leur
exécution.
2. De spécifier les sous problèmes identifiés, de décrire leur utilisation dans la solution du
problème et de procéder à une validation à cette étape.
3. Reprendre chacun de ces sous problèmes spécifiés par un énoncé en leur appliquant le
même principe.

Quoique les sous problèmes soient indépendants ils doivent être liés par un enchaînement
particulier : la solution du problème. Par exemple, si le problème posé est la résolution d’un
système linéaire par la méthode de Gauss, on peut le factoriser en les sous-problèmes suivants :
- Lecture de la matrice
- Lecture du second membre
- Triangularisation de la matrice
- Résolution d’un système linéaire
- Affichage des solutions

Au concept de sous-programme point de départ d’une étape de factorisation nous allons faire
correspondre celui de ressources actions. Syntaxiquement une ressource action va avoir la
même structure qu’un algorithme. Elle contient ses propres ressources (données et actions) et
son traitement mais sera activé dans la partie action de la ressource père. Comme toute
ressource, les ressources actions sont décrites formellement dans la partie description des
ressources et sont utilisées dans la partie description des actions.
II. Procédures
Elles ont plusieurs formes : les procédures sans paramètre et les procédures avec paramètres.
a. Procédure sans paramètre
La syntaxe d’une procédure (ressource action) est la suivante.

PROCEDURE identificateur de la
ressource ;
corps d’un algorithme

Ainsi, une ressource action est nommée par un identificateur et la structure d’un
algorithme devient :

19
 ALGORITHME identificateur ;
Liste des identificateurs : type
PROCEDURE identificateur ;
Description des ressources propres (données et actions)
{ description du processus opératoire de la ressource action
};
{ description du processus opératoire de l’algorithme
}.

L’algorithme utilisant les procédures est appelé algorithme principal, la partie

description des actions est appelée partie principale. De la même manière toute
procédure pouvant contenir des procédures comme ressources propres a aussi une partie
principale. Une partie principale comprend un ou plusieurs appels de procédure qui se
font en nommant la procédure concernée. Tout se passe comme si la partie principale
de la procédure nommée s’insère à l’endroit de l’appel : on dit qu’elle est activée.
Pour faciliter la lecture d’un algorithme, le LDA nous permet de décrire une procédure
à l’extérieur de l’algorithme principal mais en indiquant dans les parties description des
ressources correspondantes les entêtes de leur description suivi du bloc de description
des actions vide : ce que l’on appelle prototype. Par exemple on peut avoir :
ALGORITHME pp
PROCEDURE p1 ; {}
PROCEDURE p2 ; {}
{ partie principale de l’algorithme
}.
b. Procédure avec paramètres
Dans la partie description des ressources on utilise la syntaxe
PROCEDURE (description des ressources paramètres
formels) ;
corps d’un algorithme ;

Où paramètres formels désigne les données identifiées dans la description des

paramètres lors de la description de la procédure. Une description de paramètres formels
est une séquence de description d’une liste de paramètres formels d’un même type. Les
paramètres réels (ou effectifs) sont les données passées lors de l’activation de la
procédure, ils peuvent varier d’un appel à l’autre. Les paramètres réels se substituent
aux paramètres formels en respectant l’ordre par lequel ils ont été décrits.
III. Fonctions
- Les fonctions : la fonction est une procédure particulière pour laquelle on privilégie un
résultat spécifique à condition qu’il soit unique et de type simple. Ce résultat unique
sera constitué par le nom de la fonction au lieu de figurer dans la liste des paramètres
formels. La syntaxe d’une fonction est la suivante :
FONCTION identificateur : type simple ;
Corps d’un algorithme

FONCTION identificateur (déclaration des paramètres formels) : type

simple ;

20
 Corps d’un algorithme
Ainsi, on assimile le résultat de la fonction à son nom. Par conséquent dans la
description formelle de la fonction il doit y avoir au moins une action lui donnant le
contenu résultat du traitement. L’appel d’une fonction se fait en invoquant directement
son nom dans une expression utilisant le résultat de manière correcte et en passant
éventuellement tous les paramètres réels. En d’autres termes la fonction rendra une
valeur qui peut être utilisée pour initialiser une autre variable ou dans une expression de
même type.
EXERCICES
1. Ecrire une fonction qui donne le maximum de trois nombres réels
2. Ecrire une fonction qui prend un tableau de 5 entiers, puis retourne la valeur Vraie ou
Faux selon que le tableau est trié par ordre croissant ou non
3. Ecrire une fonction qui calcule le nombre de combinaison
4. Soit 𝑓 une application de l’ensemble des entiers strictement positifs dans l’ensemble
des entiers positifs ou nul, vérifiant les propriétés suivantes :
a. Pour tout (𝑚; 𝑛), 𝑓(𝑚 + 𝑛) − 𝑓(𝑚) − 𝑓(𝑛) l’une des valeurs 0 ou 1
b. 𝑓(2) = 0 ; 𝑓(3) 𝑒𝑡 𝑓(999) = 3333
Déterminer 𝑓(2014)
5. L’ensemble des entiers naturels strictement positifs est la réunion de deux sous
ensemble disjoints
{𝑓(1), 𝑓(2), ⋯ , 𝑓(𝑛), ⋯ } 𝑒𝑡 {𝑔(1), 𝑔(2), ⋯ , 𝑔(𝑛), ⋯ }
Vérifiant les conditions :
a. Les suites 𝑓 et 𝑔 sont croissantes
b. 𝑔(𝑛) = 𝑓(𝑓(𝑛)) + 1 pour tout 𝑛 ≥ 1
Déterminer 𝑓(2014)

4. Ecrire un algorithme qui

– Lit un entier positif n puis
– Affiche tous les nombres impairs inférieurs à n

5. Reprendre l’algorithme de tri et le développer cette fois-ci en utilisant des fonctions

et des procédures
6. Procédure de saisie du tableau
7. Fonction qui retourne l’indice de la valeur max dans une partie du tableau
8. Procédure qui échange les valeurs de deux cases
9. Procédure qui fait le tri en utilisant la fonction et les 2 procédures ci-dessus

21
Chapitre 3 Types complémentaires
I. Le type simple construit par énumération
En plus des quatre types simples déjà vu, nous avons la possibilité de construire des types
simples propres en énumérant les différentes constantes créées dites constantes scalaires par la
syntaxe suivante

,
Constante
( scalaire )

Exemple

JOUR={LUNDI, MARDI, MERCREDI, JEUDI, VENDREDI, SAMEDI, DIMANCHE}

SEXE=(FEMININ, MASCULIN)
Si J1 et J2 sont de type JOUR, on peut utiliser toutes les opérations habituelles sur les types
simples.

J1 :=J2 ;

If (J1<J2) then …… : l’ordre est celui de l’énumération

etc.
II. Les types simples construits par intervalle
Dans ce cas l’ensemble des valeurs du type est défini comme partie d’un autre ensemble de
type simple et énumérable. Ainsi, l’intervalle est une partie fermée d’un type simple et
énumérable de base.

Exemple
Type
INT=-10..15 ;
JOUROUVRABLE=
LUNDI..VENDREDI ;
Var
I : INT ;
Jour : JOUROUVRABLE
I. Le type ensemble

A partir d’un type simple de base on peut définir une structure d’ensemble comme étant un
ensemble un ensemble au sens mathématique d’objets de ce type.
Une déclaration (instanciation) d’une variable de type ensemble a donc une structure
d’ensemble.

22
 SET OF
Type de base
Exemple
S : SET OF JOUR
Les opérations suivantes sont possibles :
Opération Syntaxe Exemple
L’affectation := S :=[lundi, mercredi,
jeudi] ;
s :=[] (…)
L’intersection * [1..56]*[34..76] vaut
[34..56]
L’union + [11..34]+[1..34] vaut [1 ..
34]
La différence -
L’égalité = S1=s2
L’inclusion < S1<s2
<= s1<=s2
L’appartenance IN IF (reponse IN [‘o’, ‘n’])
THEN ..

II. Le type string

C’est une variante du type tableau pour nous permettre de travailler sur les chaînes de
caractères, c’est donc l’équivalent d’une description en tableau de caractères

Exemple :

A : STRING [30] ;
Déclare une chaîne A de 30 caractères commençant à partir de 1.
o A peut être manipulé comme un tableau, mais en outre il peut être traité
globalement : toutes les opérations relationnelles deviennent valables. (l’ordre
considéré est l’ordre lexicographique induit à partir de l’ordre des codes ASCII
des caractères).
o Pour déterminer la longueur de la chaine contenue dans une variable de type
string, le principe suivant est adopté : la position 0 de la variable string codé sur
un octet contiendra la longueur de la chaîne courante de caractères contenue
dans A. La longueur maximale d’une chaîne de caractères est donc de 255.
Plusieurs fonctions et procédure prédéfinies sur les chaînes de caractères existent dans
turbo Pascal.
- Le type enregistrement: Le type enregistrement correspond à une collection d’objets
de types différents qu’on appelle champs

RECOR
D Liste des champs EN
D

23
Exemple 1

Type
Datenaiss=RECORD
Jour : 1..31 ;
Mois : 1..12 ;
Annee : 1950..200
END ;
Employe=RECORD
Nom : STRING[30] ;
sexe: (MASCULIN, FEMININ);
Date : datenais ;

Référencer un champ consiste en un parcours de la racine jusqu’au nœud du champ en

indiquant les nœuds intermédiaires séparés par des points.

d :date ;
Les champs jour, mois et année seront référencés par d.jour, d.mois et d.annee.

Remarque : on peut utiliser l’accès avec WITH s’il n’y’a pas d’ambigüité ce qui évite de
répéter le nom de l’enregistrement :

Syntaxe
,

Identificateur O Identificateur
WIT
F
H

Exemple :

WITH d DO
BEGIN
Jour :=12 ;
mois:=1;
annee:=2O14
END
III. Le type Fichier

Un fichier est un objet de type FILE est définie comme une suite d’objets de même type sauf
le type fichier et en nombre indéterminé

syntaxe

FILE
OF Def de type

24
Si les composantes d’une variable de type fichier sont traitées de manière séquentielle on dit
que le fichier est à accès séquentiel.

Cependant si nous accédons à n’importe quelle composante par l’intermédiaire de son rang le
fichier est à accès direct.

En Turbo Pascal, à la création du fichier un index (file pointer) automatique (transparent au

programmeur) prend la valeur zéro (rang de la première composante). A chaque lecture ou
écriture dans la variable de type fichier cet index est incrémenté.

Exemple

Femploye=FILE OF employé
Fich : femploye ;

Opérations fondamentales sur les fichiers

Pour pouvoir travailler avec les fichiers il faut obligatoirement passer par les trois phases
suivantes :

- Etablir la liaison entre la variable interne de type fichier et son nom externe tel qu’il
est connu par le système d’exploitation.
- Ouvrir ce fichier soit en lecture soit en écriture
- Après les traitements sur ce fichier réaliser une fermeture logique.

Des procédures prédéfinies ont été écrites et permettent de réaliser ces trois objectifs.

Procédures Syntaxe Commentaires

Assignation ASSIGN (fich, ‘’c : employe.dat) fich nom interne
c: employe.dat nom externe
Ouverture en lecture RESET(fich) Fich : identificateur d’1
variable de type fichier. Le file
pointe vaut 0 (il pointe sur la
1ère composante)
Ouverture en écriture REWRITE(fich)
Fermeture CLOSE(fich)

Opérations de traitements de fichier

Procédure ou fonction Syntaxe Commentaires

Lecture d’une composante READ (fich, ident) Ident : type composante de fich
Ecriture d’une composante WRITE (fich, ident) Ecrit dans fich à l’emplacement
pointeur par le file pointer puis
s’incrémente
Accès direct SEEK (fich, 𝑛) Fait pointer le file pointer au
rang 𝑛
Taille du fichier FILISIZE (fich)
Test de fin de fichier EOF (fich) true si fin de fichier pointé
false sinon

25
Chapitre 4 Introduction à la récursivité et à la programmation
récursive
I. Notion de récursivité
Bien que tous les chapitres précédents soient axés principalement sur les techniques de
programmation (dite itératives), nous avons été confrontés à plusieurs reprises à la récursivité
surtout dans les tentatives de décrire formellement la syntaxe d’un langage
Dans le cadre de ce chapitre, charnière entre cette première partie et la deuxième relative aux
techniques d’analyse des algorithmes et des structures de données.
Les objectifs sont :
• Illustrer la récursivité en apportant des précisions sur sa définition, sa représentation
algorithmique et son mode de fonctionnement
• Donner des indications sur son utilisation dans la conception des algorithmes dans le
cadre de ce qu’il est souvent convenu d’appeler la programmation récursive.
• Le chapitre suivant nous donnera l’occasion de porter quelques réflexions sur d’une
part les possibilités de passer d’une version récursive à une version itérative
(dérécursivation) et d’autre part sur la portée des deux techniques de programmation.
1. Définition générale
Une notion est récursive si elle se contient elle-même en partie ou si elle est partiellement
définie à partir d’elle-même. Elle est dite auto-référencée.
Pour retourner l’écran : ALT+ ↑
Quelques commentaires sur cette définition
1. La récursivité est un concept que l’on rencontre fréquemment :
a. Dans la vie courante (des histoires à l’intérieur d’histoires, des représentations
à l’intérieur de représentation, des objets à l’intérieur d’objets, …)
b. En mathématiques : les suites récurrentes, méthodes itératives ; etc.
c. En théorie des langages etc.
2. Ce processus d’auto-référencement doit être fini ! en effet il ne s’agit pas d’une
référence à l’exacte elle-même ce qui serait circulaire mais à une copie de la version
précédente. La terminaison est assurée par le fait que cette suite de versions doit
converger vers un état connu
3. Une fois cet état atteint, il faut retourner à la version précédente afin de la terminer
pour reprendre la version encore précédente, la terminer etc.

Ce mécanisme de fonctionnement impose de garder la trace de toute la chaîne des versions et

dans l’ordre de leur création puisqu’on doit les reprendre dans le sens contraire (ordre LIFO :
last in first out)
Exemple de notions récursives :
1. Calcul de la somme des premiers termes d’une suite
𝑛

𝑆 = ∑ 𝑢𝑘
𝑘=0
Règle i/ 𝑆(0) = 𝑢0
Règle ii/ 𝑆(𝑛) = 𝑢𝑛 + 𝑆(𝑛 − 1)

26
 2. Factorielle 𝑛!
a. Règle i/ 0! = 1
b. Règle ii/ 𝑛! = 𝑛. (𝑛 − 1)!
- PGCD de deux nombre entiers u et v
a. 𝑝𝑔𝑐𝑑(𝑢, 0) = 𝑢
b. 𝑝𝑔𝑐𝑑(𝑢, 𝑣) = 𝑝𝑔𝑐𝑑(𝑢, 𝑢 𝑚𝑜𝑑𝑢𝑙𝑜 𝑣)
- Les informations relevées sur chaque individu sont :
a. Son nom
b. Sa date de naissance
c. Et celle de son père (qui est un individu) etc.

L’analyse de ces quelques exemples fait ressortir les remarques suivantes :

1- Pour assurer une terminaison à l’application des règles de définition d’une notion
récursive :
a. Une première condition nécessaire est que la partie faisant appel à la redéfinition
récursive soit conditionnelle et doit être fausse au moins une fois.
De ce fait, la définition d’une notion récursive doit prévoir une sortie qui
intervient quand la condition d’application de la partie récursive devient fausse.
2- La récursivité peut se présenter de deux manières :
a. Elle est dite directe si la règle de redéfinition récursive utilise directement la
notion sinon elle est indirecte, c'est-à-dire qu’elle passe par une ou plusieurs
autres règles avant de faire appel à la notion en définition
3- La récursivité s’illustre en algorithmique aussi bien au niveau des actions qu’au niveau
des objets. On parlera
a. De récursivité des actions si l’énoncé du problème fait appel directement ou
indirectement à lui-même et
b. De récursivité des structures de données si un objet est défini comme une
collection d’objets dont certains ont la même structure que l’objet en définition
La récursivité des structures de données est un concept extrêmement puissant pour
représenter les modèles fondamentaux d’organisation des données. Elle sera utilisée
pratiquement dans toute la deuxième partie de ce cours, néanmoins dans le chapitre 2
nous avons vu un moyen classique de représentation algorithmique en passant par les
pointeurs. En effet, si l’objet a un type T on ne peut décrire sa composante par T ce qui
provoquerait une définition circulaire. On passe alors par les pointeurs qui font référence
aux objets de type T pour définir le type de la composante et l’arrêt de la chaîne des
définitions se faisant par une constante spéciale pointeur indiquant le fait de ne pointer
sur rien (nil). L’exemple 4 pourrait se décrire par :

PPERS=↑ PERSONNE ;
PERSONNE= RECORD
Nom : STRING[30]
Date_naiss : RECORD jour : 1 ..31 MOIS/ 1..12 ;
année : 2000..2013 END ;
Père : PPERS
END

27
 Et une instanciation par individu : PPERS ; donnerait :

Vers le père de
nom date pere l’individu

indivudu

II. Récursivité des actions

1. Réalisation algorithmique
Pour exprimer un énoncé récursif, il nous faut un moyen de le nommer ce que nous avons par
l’appel de procédure ou de fonction. Ainsi, une procédure P (ou fonction F) contient un ou
plusieurs appels explicite à elle-même on dit qu’elle est directement récursive autrement si P
(ou F) contient un appel à P (ou F) nous dirons que P (ou F) est indirectement récursive ou
encore que P (ou F) et Q (ou G) sont des récursivités croisées.
Récursivité directe
PROCEDURE P(D : TD) ; FONCTION Q( D : TD) : RD ;

{ {
P(B(D)) ; F(B(D)) ;
} }

Récursivité directe
PROCEDURE P(D : TD) ; FONCTION Q( D : TD) : RD ;

{ {
Q(B(D)) ; P(C(D)) ;
} }

Nous parlerons aussi de procédure (ou fonction) récursive primitive si les paramètres ne
s’expriment pas par appel de la procédure (ou de la fonction) autrement elle est dite générale.
Exemple de fonction générale (non primitive) :
FONCTION ack (m,n : ENTIER) : ENTIER ;

{ SI (m=0) ALORS ack⟵ 1

SINON
SI (n=0) ALORS ack⟵ack(m-1,1)
SINON ack⟵ ack (m-1, ack(m,n-1)
}

Dans tout ce qui suit, nous parlerons généralement des procédures, l’adaptation aux fonctions
sera laissée aux soins du lecteur, sauf dans le cas contraire ou une différenciation s’impose.

28
 2. Visibilité des objets d’une procédure (ou fonction)
i. Récursivité et mécanisme de fonctionnement
A chaque procédure est associée un ensemble d’objets accessibles qui sont :
- Ses objets locaux
- Ses objets paramètres
- Ses objets plus globaux

L’ensemble des objets propres (locaux et paramètres passés par valeur) a une certaine existence
(durée de vie) pendant l’exécution de la procédure.
Nous dirons qu’un appel de la procédure entraine la création d’un environnement formé d’un
exemplaire particulier de cet ensemble d’objets qui ne cesse d’exister que quand cet appel se
termine (cette existence continuant au-delà pour les objets plus globaux ou les objets paramètres
passés par adresse) en d’autres termes, Si une procédure est appelée récursivement, cela signifie
qu’un nouvel environnement va naître sous celui du précédent (celui qui l’a appelé). Il va donc
exister plusieurs environnements différents pour la même procédure et par conséquent plusieurs
incarnations différentes pour un même objet dans chaque environnement sans qu’il n’y ait
aucun rapport ni aucune communication entre ces différents environnements et la désignation
d’un objet local à une procédure n’est pas ambiguë puisqu’elle se réfère toujours au dernier
environnement créé et encore en cours d’existence. Quand un appel récursif se termine, les
objets de l’environnement correspondant à l’appel précédent redeviennent accessibles parce
qu’ils n’ont pas cessé d’exister entre temps
3. Exemple de procédures récursives
i. Calcul de n !
FONCTION fact (n : ENTIER) : ENTIER

{ SI (n=0) ALORS fact⟵1

SINON fact⟵ 𝑓𝑎𝑐𝑡(𝑛 − 1) × 𝑛
}

Simulation pour n=3

𝑖 ⟵ 𝑓𝑎𝑐𝑡(3)
𝑓𝑎𝑐𝑡 ⟵ 𝑓𝑎𝑐𝑡(2) × 3

𝑓𝑎𝑐𝑡 ⟵ 𝑓𝑎𝑐𝑡(1) × 2

𝑓𝑎𝑐𝑡 ⟵ 𝑓𝑎𝑐𝑡(0)
×1
𝑓𝑎𝑐𝑡 ⟵ 1

4. Programmation récursive
Les exemples traités permettent de mettre en évidence les idées fortes dans la conception en
programmation récursive.

29
La première est de transformer (de manière équivalente) l’énoncé du problème en un autre
dont les spécifications sont récursives
Exemple 1
On considère deux chaînes de caractères w1 et w2 et on désire savoir si w1 est anagramme de
w2, c'est-à-dire que w1 est égale à w2 à une permutation près de caractères
Eléments d’analyse
1- Sur quelles données faut-il porter la récursivité ?
2- Toute définition récursive doit avoir un état connu (point de sortie) qui permet de ne
plus appliquer la règle récursive

30
 Partie 2 : Langage C et programmation

31
Chapitre 5 Initiation au langage et à la programmation en C
I. Introduction

Le langage Pascal est un langage procédural2 qui a été crée en 1975 par Niklaus Wirth.
L’ancêtre du langage Pascal, comme d’ailleurs tous les langages de sa catégorie est le Fortran
(voir figure suivante).

Figure 5.1 Hiérarchie des langages procéduraux comme Pascal

Dans la liste de la figure, seuls Algol et Pascal sont des langages qui ont été conçus dans le but
d’enseignement ou de recherche. Les autres langages sont élaborés par des firmes dans le but
de commercialisation, de rationalisation des coûts de gestion (DOD) etc.
L’apprentissage du langage PASCAL constitue une approche saine de la programmation,
surtout dans l’enseignement car il est important d’acquérir dès le départ une méthodologie de
conception des programmes et un bon style. Ce langage permet justement d’éviter les mauvaises
habitudes qui une fois instaurées, sont difficiles à corriger.
Le langage Pascal est un langage compilé, c'est-à-dire qu'il faut :
• Entrer un texte dans l'ordinateur (à l'aide d'un programme appelé éditeur);

2
Dans un langage procédural, l’affectation (transfert d’une valeur dans une mémoire) est la base des actions.

32
• Le traduire en langage machine (c'est-à-dire en codes binaires compréhensibles par
l'ordinateur) : c'est la compilation et éventuellement l'édition de liens (Link);
• L'exécuter.
I. Structure générale d’un programme
#include <stdio.h>
#include <conio.h>

main()
{ <déclaration de variable>
<instruction à exécuter>
}

Exemple
Ouvrons notre éditeur de texte préféré et saisissons le programme suivant
# include<stdio.h
#include<conio.h

int main()
{
print(‘’Salut le Monde\n’’ ;
getch()
return 0 ;
}

Sauvegardez ce fichier sous le nom salutMonde. Dans le menu Exécuter, cliquez sur
Compiler. Remarquez que la compilation a produit un fichier salutMonde.exe. Vous avez
deux façons de l’exécuter :
- Double-cliquez directement sur salutMonde.exe
- Dans le menu exécuter, cliquez sur exécuter

II. Variables et identificateurs

- Une variable est un emplacement de la mémoire dans lequel est stockée une valeur.
Chaque variable porte un nom et c’est ce nom qui sert à identifier l’emplacement de la
mémoire représenté par cette variable. Pour utiliser une variable, la première étape est
la déclaration

- Identificateur : Les identificateurs, de variables, de fonctions, obéissent à la règle

habituelle ‘’suite de caractères alphanumériques, l’initiale devant être une lettre’’. Le
caractère de soulignement _ est autorisé. L’utilisation d’autres caractères non
alphanumériques est à éviter dans la mesure du possible. La taille maximale d’un
identificateur était limité à 6 caractères en C-K&R. Aujourd’hui tous les compilateurs
Ansi acceptent un minimum de 31 caractères. L’utilisation de noms assez longs a
l’avantage de mieux documenter un programme :

float constante_ de_planck

est plus explicite que
float h

33
 Il faudra éviter l’’utilisation de caractère de soulignement _ en début ou fin d’un
identificateur, cette notation est habituellement réservée aux mécanismes internes des
compilateurs.
III. Variable global, variable locale
- On appelle déclaration globale toute déclaration effectuée à l’extérieur des corps de
fonction, donc au niveau 0 du code source. Un identificateur global est valide (on dit
aussi ‘’visible’’) pour tous les modules fonctions d’un même fichier source. De même
la définition d’une fonction a valeur de déclaration globale
- On appelle déclaration locale, toute déclaration effectuée dans un corps de fonction.
Un identificateur local n’est utilisable que dans le corps de fonction auquel il
appartient
Remarque
- Les déclarations des arguments d’appel d’une fonction sont des identificateurs locaux
- En cas d’homonymie, c’est la déclaration locale qui est prioritaire
IV. Affectation, saisie, affichage
Syntaxe Commentaire

Affectation 𝑛𝑜𝑚𝑑𝑒𝑣𝑎𝑟 = 𝑣𝑎𝑙𝑒𝑢𝑟 Si on souhaite affecter à la variable v une valeur, on utilise

l'opérateur =
Saisie scanf(‘’%d,〈𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒〉) ; Permet à l’utilisateur d’affecter une valeur à 〈𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒〉

Affichage Printf(‘’%d,〈𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒〉) ; Affiche la valeur de 〈𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒〉

V. Affichage du contenu d’une variable
Structure conditionnelle Syntaxe C

While
(tant que)

do ..While

for

34
 VI. Les types classiques
- Entiers non signés entiers signés : Par défaut ; les entiers permettent de stocker des
valeurs de signe quelconque. Si on préfixe un type entier par unsigned, on le restreint à
des valeurs uniquement positives.

Entier
nom Taille Nombre de Plus petite Plus grande
valeurs valeur valeur
Unsigned 1 octet 28 0 28 − 1
short 2 octets 216 0 216 − 1
Unsigned int 4 octets 232 0 232 − 1
Unsigned
long
Entiers signés
nom Taille Nombre de Plus petite Plus grande
valeurs valeur valeur
Unsigned 1 octet 28 −27 27 − 1
short 2 octets 216 −215 215 − 1
Unsigned int 4 octets 232 −231 231 − 1
Unsigned
long

La plage de valeur d’un unsigned short, encodée en binaire, est

{0000 0000; 0000 0001; 0000 0010, … , 1111 1110, 1111 1111}
- Les flottants : Les flottants servent à représenter les réels. Leur nom vient du fait qu'on
les représente de façon scientifique : un nombre décimal (à virgule) muni d'un exposant
(un décalage de la virgule). Trois types d base servent à représenter les flottants :

Il est conventionnel d'écrire des littéraux flottants avec un point, par exemple
l'approximation à 10−2 près de 𝜋 s'écrit 3.14. Il est aussi possible d'utiliser la notation
scientifique, par exemple le décimal 1 000 s'écrit 1e3, à savoir 1.10−3.Nous nous
limiterons à la description du type float, les autres types obéissent à des règles similaires.
Le codage d’un nombre de type float (32 bits) est découpé en trois parties :
Bit de signe L’exposant La mantisse
Taille 1 8 23
Le nombre est positif si le bit de signe est 0, négatif si le bit de signe est 1. La
mantisse et l’exposant.
Les connecteurs logiques
Connecteur Syntaxe en C Commentaires
logique
𝑒𝑡 && A et B vérifié simultanément
𝑜𝑢 ∥ L’un au moins de A ou B est
réalisé

35
 - Un tableau est regroupement de variables de même type, il est identifié par un nom.
Chacune des variables du tableau est numérotée, ce numéro s’appelle un indice.
Chaque variable du tableau est donc caractérisée par le nom du tableau et son indice.

Déclaration Initialisation Accès aux éléments

Synt 〈𝑡𝑦𝑝𝑒〉〈𝑛𝑜𝑚〉[〈𝑡𝑎𝑖𝑙𝑙𝑒〉] 〈𝑡𝑦𝑝𝑒〉〈𝑛𝑜𝑚〉[〈𝑡𝑎𝑖𝑙𝑙𝑒〉] 𝑇[0], … , 𝑇[𝑖], ⋯ , 𝑇[𝑛]
= {𝑣1, ⋯ , 𝑣(𝑛 − 1)}
Exemple 𝑖𝑛𝑡 𝑇[2] 𝑖𝑛𝑡 𝑇[2] = {−2,0,2} 𝑝𝑟𝑖𝑛𝑡(𝑇[0])
Com Déclare T comme un Les éléments de T sont : -2, 0, 2 Afficher le 1er élément
tableau de taille 3 de T i.e. -2

- Chaînes de caractères : une chaîne de caractères est un tableau de char contenant le

caractère nul. Le caractère nul a 0 pour code ASCII et s’écrit ‘\0’. Les valeurs
significatives de la chaîne de caractères sont toutes celles placées avant le caractère nul.
On remarque donc que si le caractère nul est en première position, on a une chaîne de
caractères vide.
Par exemple le mot « gagamou » sera codée de la sorte :
‘g’ ‘a’ ‘g’ ‘a’ ‘m’ ‘o’ ‘u’ ‘0’ …

Déclaration Initialisation Accès aux éléments

Synt 𝒄𝒉𝒂𝒓 〈𝑛𝑜𝑚〉[〈𝑡𝑎𝑖𝑙𝑙𝑒〉] 𝑐ℎ𝑎𝑟 〈𝑛𝑜𝑚〉[〈𝑡𝑎𝑖𝑙𝑙𝑒〉] 𝑡𝑒𝑥𝑡[𝑖]
= {𝑣1, ⋯ , 𝑣(𝑛 − 1)}
Exemple 𝑐ℎ𝑎𝑟 𝑡𝑒𝑥𝑡[300] 𝑐ℎ𝑎𝑟 𝑡𝑒𝑥𝑡 [300] =′′ 𝑔𝑎𝑔𝑎𝑚𝑜𝑢′′ 𝑝𝑟𝑖𝑛𝑡(𝑡𝑒𝑥𝑡[𝑖])
Com Déclare une chaîne Les éléments de T sont : -2, 0, 2 Affiche le 𝑖 + 1
text de 300 élément de la chaîne
text
- L’affichage
Syntaxe Commentaire
Affichage 𝑝𝑟𝑖𝑛𝑡𝑓(‘’mon texte :% 𝑛’’,c) Affiche le contenu de la variable c après le texte entre
cote
Saisie 𝑓𝑔𝑒𝑡𝑠(〈𝑐ℎ𝑎𝑖𝑛𝑒〉, 〈𝑡𝑎𝑖𝑙𝑙𝑒〉, 𝑠𝑡𝑑𝑖𝑛) Place les taille du 1er terme saisi par l’utilisateur dans
〈𝑐ℎ𝑎𝑖𝑛𝑒〉

Ecrire en C un programme qui affiche la position du nombre saisit par l’utilisateur dans la
liste.
Applications 1

36
Application 2
Etant donné le programme dont l’exécution est tracée ci-dessous :
Saisissez une phrase : Il y’ a l’internet à l’école.
Vous avez saisi :
Il y’ a l’internet à l’école.
Cette phrase commence par une majuscule.
Cette phrase se termine par une majuscule.
Cette phrase se termine par un point.

Comment faire pour saisir et manier des séquences de caractères de la sorte ?

Ecrire en C un programme qui affiche la position du nombre saisit par l’utilisateur dans la
liste.
VII. Type enregistrement
Nous avons utilisé des tableaux pour désigner, avec un nom unique, un ensemble de variables.
Par exemple, un tableau T _a n éléments est un ensemble n de variables désignées par la lettre
T. Dans un tableau, les variables doivent être de type homogène, cela signifiant qu'il n'est pas
possible de juxtaposer des char et des int dans un tableau. Lorsque l'on souhaite faire cohabiter
dans une variable non scalaire des types hétérogènes, on utilise des structures.
Une structure, appelée enregistrement dans d'autres langages, est une variable contenant
plusieurs variables, appelées champs. Si une structure t contient un char et un int, chacun de ces
champs portera un nom, par exemple i et c. Dans ce cas, 𝑡: 𝑐 désignera le char de t et 𝑡: 𝑖 l'int de
t.
Syntaxe Exemple Commentaire
Déclaration struct point p ; Ce type permet de représenter un
{ point dans ℝ2 , avec une abscisse et
double abs ; une ordonnée. Struct point est
double ord ; maintenant un type, il devient
} possible de déclarer un point p
comme tout autre variable

Accès au champ main () Ainsi, le champ ord de notre

{ variable p sera accessible avec p:ord
struct point p ; et le champ abs de notre variable p
p.ord=2 ; sera accessible avec p:abs. Voici un
p.abs=p.ord+1 ; exemple de programme illustrant ce
print(‘’p=(%f, %f)\n’’, p.abs, principe :
p.ord);
}
main () Point est donc le nom de ce type
{ structuré
point p ;
p.ord=2 ;
p.abs=p.ord+1 ;
print(‘’p=(%f, %f)\n’’, p.abs,
p.ord);
}

VIII. Procédures et fonction en C

- Procédure : Une procédure est un ensemble d’instructions portant un nom. Pour définir
une procédure, on utilise la syntaxe :

37
 Void nomprocedure ()
{
/∗
Instruction
/∗
}
Une procédure est une nouvelle instruction, il suffit pour l’exécuter d’utiliser son nom.
Par exemple pour exécuter (on dit aussi appeler ou invoquer) une procédure appelé pr,
il suffit d’écrire pr(). L’exemple suivant en donne une illustration

- Fonction : On définit une fonction avec la syntaxe suivante

typeValeurValeurDe Retour nomFonction (listeParametres)
{
}
La fonction carre sera donc définie comme suit :
Int carré (int i)
{
/∗
Instructions
∗/
}
Une fonction ressemble beaucoup à une procédure. Vous remarquerez que void est
remplacé par int, void signifie aucun type de retour. Une procédure est une fonction
qui ne retourne rien. Un exemple nous est donné comme suit.
Int soustraction(int u, int v)
{
/∗
Instructions
∗/
}

38
 L’instruction servant à retourner une valeur est return. Cette instruction interrompt
l’exécution de la fonction et retourne la valeur placée immédiatement après.

N.B : Problème d’affichage de certains caractères dans l’éditeur C

Il est fort possible, malgré le passage avec succès du clavier en AZERTY, que vous ne puissiez
produire aucun des caractères accessibles par combinaison avec la touche Alt Gr. Pour
contourner ce problème gênant, on utilise les codes ASCII des caractères, que l’on tape après
avoir enfoncé la touche Alt.
Codes ASCII
Caractères Codes
# Alt-35
@ Alt-64
\ Alt-92
[ et ] Alt-91 et 93
^ Alt-94
{ et } Alt-123 et Alt-125
I Alt-124
tilde Alt-126
Exercice
Réécrire tous les programmes des exercices précédents en langage C

39
INP-HB Yamoussoukro Année académique 2012-2013
GMP1
TP : Algo et programmation
Du problème posé à la solution informatique (programme) par l’exemple
Activité 1
1. Ecrire les algorithmes qui permettent de calculer le minimum de 2 entiers : on
commencera par une analyse du problème (variables d’entrée, de sortie, etc.)
2. Ajouter des instructions à l’algorithme précédent de sorte :
1. A demander à l’utilisateur d’entrer les valeurs de a et b
2. A lire les valeurs de a et b entrées par l’utilisateur
3. A afficher à l’écran la solution.
3. Traduire en Pascal l’algorithme final
Application : Même question avec le maximum
Programme, procédure
Activité 2
Ecrire l’algorithme des procédures suivantes :
1. Min de 2 entiers
2. Max de 2 entiers
Puis l’algorithme du programme qui lit 2 entiers, appelle les procédures Min et Max et affiche
les résultats.
Traduire en Pascal l’algorithme du programme.
Application : utiliser les procédures Min et Max pour déterminer le minimum de 3 entiers.
Activité 3

Fonction
Activité 4
Ecrire une fonction ayant en paramètre un entier représentant une année et retournant un 1 si
l’année est bissextile et 0 sinon.
Prototype : bissextile(annee : integer) : integer;

Activité 5
Ecrire une fonction qui retourne le plus grand commun diviseur (pgcd) de deux nombres
entiers positifs.

Prototype: pgcd(a, b : integer) : integer ;

40
INP-HB Yamoussoukro Année académique 2012-2013

TP : Algo et programmation

Programme, procédure

Exercice 1
Ecrire les procédures suivantes :
1. Min de 2 entiers
2. Max de 2 entiers
Puis le programme qui lit 2 entiers, appelle les procédures Min et Max et affiche les résultats.
Exercice 2 (trier des entiers n )
Procédure Echange2 sur 2 réels a et b qui échange éventuellement a et b pour que l’état de
sortie soit 𝑎 ≤ 𝑏. Ecrire un programme d’appel.

Exercice 3

Fonction
Exercice 4 (calendrier)

Exercice 5
Ecrire une fonction ayant en paramètre un entier représentant une année et retournant un 1 si
l’année est bissextile et 0 sinon.

Exercice 6
Ecrire une fonction ayant en paramètre trois entiers représentant un jour, un mois et une année
et retournant un 1 si l’année est bissextile et 0 sinon.

Exercice 7
Ecrire une fonction qui retourne le plus grand commun diviseur (pgcd) de deux nombres
entiers positifs.

41
 Les caractères, type enregistrement

Exercice 8(Compter des caractères)

Faire une fonction qui lit au clavier une suite de caractères terminée par ‘.’ Et qui renvoie le
nombre de caractères lu avanr ‘.’.
Ne pas les laisser chercher trop longtemps, mais leur expliquer l’algorithme

Exercice 9 (Compter les L)

Faire une fonction qui lit au clavier une suite de caractères terminée par ‘.’ et qui renvoie le
nombre d’occurrences du caractères L.

Exercice 10 (

Exercice 11
Ecrire une fonction calc_ns(t) qui renvoie le nombre de secondes ns écoulées depuis 0 :0 :0
Exercice 12

Exercice 13

Exercice 14 (début avec des ‘a’)

42
Exercice 9 (caractère minuscule)

Exercice 10 (Ligne minuscule)

Ecrire la procédure MinusLig (var s : ligne_t) qui met tous les caractères de s en minuscule
Exercice 11 (ouverture, fermeture)
On considère que l’on dispose de la procédure CasseFi (var f1, fé : text). Ecrire une procédure
CasseNom(nom1, nom2 : ligne_t) qui ouvre en lecture f1 : text ; ouvre en écriture f2 : text,
appelle CasseFi (f1, f2) puis ferme ces fichiers
Fichier, recherche de mots
Dans tous les exercices on suppose que l’on a en entrée un fichier texte, résultat du
programme c'est-à-dire exactement un mot par ligne, en minuscule et sans espacement (sauf à
la fin ou il peut y avoir une ligne vide).
Exercice 12 (nombre de mots)
Ecrire la fonction NombreMots(nomf : ligne_t) : integer ; qui renvoie le nombre de mots
présents dans le fichier nomf .

Exercice 13 (recherche d’un mot)

Ecrire la fonction RechercheMot (nomf, m : ligne_t) : boolean ; qui renvoie TRUE si le mot
m (reçu en minuscule) est présent dans le fichier nomf

Exercice 14 (compter un mot)

Ecrire la fonction CompterMot (nomf, m : ligne_t) : boolean ; qui renvoie le nombre
d’occurrence du mot m (reçu en minuscules) dans le fichier nomf.

Exercice 15 (compter dans un fichier trié)

Ecrire la fonction CompterMot(nomf, m : ligne_t) : integer ; qui envoie le nombre
d’occurrences du mot m (reçu en minuscules) dans le fichier nomf.

Exercice 16 (Programme principal)

En TP, écrire un programme principal et un fichier texte d’exemple (trié à la main si besoin),
de façon à tester les procédures et fonctions de l’exercice.

43
 INPHB DE YAMOUSSOKRO
1ème ANNEE GMP 2011-2012
TD N° 2 INFO. GENE.

Exercice 1
Résoudre dans R une équation du second degré
Exercice 2
Calculer le salaire d’un fonctionnaire ou auxiliaire,
sachant que s’il est fonctionnaire il cotise
6% de son salaire de base pour sa retraite
2.75 % du salaire de base pour sa protection sociale si son salaire est plus petit que le plafond
fixé par l’organisme de gestion de la protection sociale, dans le cas contraire il cotise pour
2.75% du même plafond.
S’il est auxiliaire il ne cotise pas pour la retraite, par contre il cotise pour la protection sociale
au taux de 5% de son salaire de base si ce dernier est inférieur ou égal au plafond sinon il
cotise pour 6.75% du plafond augmenté de 1.5% de la différence entre le salaire de base et le
plafond.
Exercice 3
1. Afficher dans l’ordre trois nombres entiers et distincts.
2. Afficher le maximum de trois entiers
Exercice 4
On considère un texte formé de caractères et terminé par un caractère unique : ‘#’, on voudrait
connaitre :
a. Le nombre de ‘a’
b. Le nombre de voyelle
c. Le nombre de ‘le’
d. Le nombre de mots
Exercice 5
On considère la suite de FIBONACCI :
𝑢0 = 𝑢1 = 1
𝑢𝑛 = 𝑢𝑛−1 + 𝑢𝑛−2
1. Ecrire un algorithme qui calcul le nième terme de la suite Fibonacci
2. Calculer la somme des q premiers termes.

44
Exercice 6
ALGORITHME algo;
X, MY: REEL;
I: ENTIER;
MY=0;
{
POUR I⟵1 JUSQUA 10 FAIRE
{ LIRE(X);
MY⟵MY+X/10 ;
}
ECRIRE (MY)
}.

1. Que fait algo ?

2. Ecrire le programme turbo pascal correspondant
3.
a. Tapez ce programme
b. Faire l’exécution pour les valeurs de X suivantes

Exercice 7
ALGORITHME algo1 ;
X, Y, S : ENTIER ;
{ LIRE(X, Y) ;
SI (X>0) ALORS S⟵1
SINON
{SI (Y<0) ALORS S⟵1
SINON S⟵O
}
ECRIRE (S) ;
}.

45
 1. Que fait algo1 ?
2. Ecrire le programme turbo pascal correspondant
3. Remplir le tableau suivant
X Y Z

Exercice 8
ANGUI donne l’algorithme suivant
ALGORITHME Angui_algo ;
X, Y, Z, SAUVER : ENTIER ;
{ LIRE(X, Y, Z) ;
SAUVE⟵X ;
X⟵Z ;
Z⟵Y ;
Y⟵SAUVE ;
ECRIRE(X, Y, Z)
}.

1. Que fait le programme d’Angui

2. Ecrire le programme turbo pascal correspondant
3. Faire l’exécution pour X=10, Y=9, Z=8

Exercice 9
1. Ecrire un algorithme qui permet de calculer la moyenne d’une série de 6 entiers
2. Ecrire le programme turbo pascal correspondant
3. Faire l’exécution pour la série suivante : 19 524 1291 2301 99 201

46