Algorithme &

Programmation
Cours Magistral
Licence Informatique & MIO

Dr Edouard Ngor SARR

Enseignant-Chercheur
Université Assane SECK de Ziguinchor (UASZ)
Ziguinchor-Sénégal
edouard-ngor.sarr@univ-zig.sn
2021-2022
 Avant-Propos

Généralités sur le traitement de l’information

2
 Algorithme et programmation 2 Ed.N.SARR

Objectifs
• Connaitre les notions de base de l’algorithme
– Identificateurs
– Variables, Constantes et Types
– Operateurs
– Entrées / sorties
– Instructions conditionnelles et itératives
• Maitriser les notions avancés de l’algorithme
– Programmation modulaire
– Les structures de de données
– Programmation récursif
• Savoir implémenter et compiler les programmes en le langage C
– Compilation
– Implémentation
3
– Exécution
 Algorithme et programmation 2

Sommaire
• Chapitre 1 : Notions de bases de l’algorithme
– Variables, Constantes,Types et les Operateurs
– Instructions conditionnelles et itératives
– Lire et Afficher
• Chapitre 2 : Initiation au Langage C
– TD 1 & TP 1
• Chapitre 3 : Les Tableaux et algorithmes de Tri
– TD 2 & TP 2
• Chapitre 4 : Programmation modulaire et récursivité
– Les procédures
– Les Fonctions
– Appels de fonctions
– TD 3 & TP 3

4
 Chapitre 1
Les fondamentaux de
l’algorithme

2H
Chapitre 1: Les fondamentaux de l’algorithme

Définitions, Objectif et problèmes

• Définitions
– Suite ordonné d’instructions (Ordres) écrite en langage humain (pseudocode)
mais formel (bien codifié) pour résoudre un problème bien défini.
• Objectifs
– Apprendre à l’ordinateur à résoudre un problème
• Cela suppose que nous savons à priori comment résoudre le problème.
• On décrit alors à l’ordinateur étape par étape comment proceder
• Problèmes fondamentaux
1. Complexité
– En combien de temps et avec quelles ressources (CPU & RAM) notre
algorithme va -t-il atteindre le résultat escompté ?
2. Calculabilité:
– Dans ma démarche de résolution, existe-t-il des tâches pour lesquelles il
n'existe aucun solution ?
3. Correction
– Peut-on être sûr que notre algorithme trouvera la solution attendue
6
Chapitre 1: Les fondamentaux de l’algorithme

Ingrédients d’un algorithme

• Un algorithme prend des données en entrée (inputs), exprime un
traitement particulier (Algorithme) et fournit des données en
sortie (outputs).

7
Chapitre 1: Les fondamentaux de l’algorithme

Structure générale d’un algorithme

8
Chapitre 1: Les fondamentaux de l’algorithme

Structure générale d’un algorithme: Exemple

9
Chapitre 1: Les fondamentaux de l’algorithme

Les variables & les constantes

• Définitions
– Des structures utilisées en informatique pour stocker
temporairement en mémoire RAM des données.
– Sont des sortes de « boites » dans lesquelles on met une
valeur (un nombre, un mot…)
– Sont caractérisées par:
• Un nom : son identificateur
• Une valeur : la donnée stockée en mémoire RAM
• Un type: son domaine d’existence
• Différence
– Lors de l’exécution du programme:
• La valeur de la variable peut changer
• La valeur de la Constantes ne peut pas changer
10
Chapitre 1: Les fondamentaux de l’algorithme

Les variables & les constantes: Identificateurs

• Définitions
– Un mot choisi par le programmeur pour identifier de façon
unique un élément du programme : variable, constante,
procédure, type, etc.
• Règles
– composé de lettres seulement ou des lettres et de chiffres
– Il commence toujours par une lettre
• Prenom1 est valide
• 1prenom pas bon
– Pas d’espaces
– Pas de caractères spéciaux tels que -@,/.+?¨*£°ë“‘«Çøø}ë‘‘{¶«
– Le seul caractère accepté est le _
• Est utilisé lorsque la l’identificateur est composé de
plusieurs mots (remplace l’espace) 11
Chapitre 1: Les fondamentaux de l’algorithme

Les variables & les constantes: Types

• Renseigne sur le domaine d’existence d’une valeur (sa famille)
– Permet à l’ordinateur de savoir quel capacité réserver avant la
venue de la donnée.
– Defini la taille de la place occupée en mémoire.
• Les différents types:
– les entiers: Ensemble N (Les nombres entiers ne sont pas
bornés)
– Les réels: Les nombres décimaux (avec virgule)
– Les booléen: Nombre de deux valeurs possibles (Vraie ou
Faux, M ou F etc.)
– Date: Exprime les dates (jour/mois/année)
– les chaînes de caractères: Des séquences obtenues en
concaténant plusieurs caractères. Exemple: 'bonsoir' 'il fait
froid' '254.25' 'j''imagine'
12
Chapitre 1: Les fondamentaux de l’algorithme

Les variables & les constantes: Déclaration

• Consiste à réserver une place en mémoire VIVE
• Comment ?
– Obligatoire
• Attribuer l'identificateur : un nom
• Attribuer un type à cette place
– Optionnel
• Attribuer une valeur (Initialisation)
– Possibilité de faire une déclaration multiple
– Attention: Une constante est toujours initialisée
• Exemple:
– Variables Constantes
X : entier Pays ß’SENEGAL’: Chaines
i , j , k entiers Pie ß 3,14: entier
Min ß 12,5 : Réel Sexe ß’M’ : BOOLEEN
13
Chapitre 1: Les fondamentaux de l’algorithme

Les variables & les constantes: Déclaration

14
Chapitre 1: Les fondamentaux de l’algorithme

Les opérateurs
• les opérateurs arithmétiques
+ (addition) * (multiplication)
% (Modulo) - (soustraction)
/ (division) ^ (exponentiation)
• Les opérateurs logiques
ET OU NON
• Les operateurs de comparaison
= (égal) < (inférieur) <= (inférieur ou égal)
<> (différent) > (supérieur) >= (supérieur ou égal)
• L’opérateur concaténation
+ (réalisant la concaténation de deux chaînes de caractères)
• Operateurs d’incrémentation et de décrémentation
++ -- += -= *= /=
• Affectation (ß) : permet d'affecter, à une variable, une nouvelle valeur.
15
Chapitre 1: Les fondamentaux de l’algorithme

Les opérateurs: Exemples

• Affectation

16
Chapitre 1: Les fondamentaux de l’algorithme

Les operateurs: Pré/Post Incré/décrémentation

• Dans une opération d'affectation qui met en jeu l'opérateur de :
– Pré-incrémentation (pré-décrémentation): la variable est
d'abord incrémentée (décrémentée) de 1. L'affectation est
ensuite effectuée.
– post-incrémentation (post-décrémentation): L'affectation (sans
les ++ (--)) est effectuée avant
• Exemples
i = i + 20; i += 20;
i = i - 20; i -= 20;
i = i * 20; i *= 20;
i = i / 20; i /= 20;

17
Chapitre 1: Les fondamentaux de l’algorithme

Entrées / Sorties
• Au cours de l'exécution d'un programme, il est indispensable que
l’utilisateur puisse communiquer avec l'ordinateur:
– Demander des données (Lecture)
– Rendre des données (Affichage)
• Possible grâce à l'emploi des instructions Afficher et Lire.
• NB:
– Chaines de caractères et dates sont mises entre cotes ' ’ lors
de l’affichage
• Exemples
• afficher ('le plus grand est=' , max)
• afficher ('la racine carrée de ' , x , ' est ' , r)
• Afficher (x+y)
• lire (x)
• Saisir (x , y) lecture de deux valeurs saisies par l’utilisateur
18
Chapitre 1: Les fondamentaux de l’algorithme

Entrées / Sorties: Exemples

19
Chapitre 1: Les fondamentaux de l’algorithme

Instructions conditionnelles: SI
• Structure de contrôle permettant de gérer des cas et de rendre
conditionnelle l'exécution de séquences d'instructions.
• Si la condition est vraie le programme exécute la séquence1
d'instructions puis il se poursuit après l'instruction finsi
• sinon (condition fausse) il exécute la séquence2 d'instructions.

Remarque: Dans
certain cas le SINON
n'existe pas; la syntaxe
et le schéma sont alors
réduits à la forme
suivante à

20
Chapitre 1: Les fondamentaux de l’algorithme

Instructions conditionnelles: SI

21
Chapitre 1: Les fondamentaux de l’algorithme

Instructions conditionnelles: SI

22
Chapitre 1: Les fondamentaux de l’algorithme

Instructions conditionnelles: SELON

• SELON indique le traitement à faire selon la valeur d'une variable.
• Gere aussi des cas possibles d’une variable
• La condition 1 est évaluée
– Si la condition 1 est vraie, alors on exécute l'action correspondante et on quitte la
structure selon-que
– Si la condition 1 est fausse, on évalue la condition 2...et ainsi de
suite.
• Si aucune n'est vraie on effectue l'action sinon ( au cas où l'action
sinon n'existe pas alors aucune action n'est exécutée !).

SELON abréviation
"M" : afficher( " Monsieur " )
"Mme" :afficher( " Madame " )
"Mlle" : afficher( " Mademoiselle " )
autres :afficher( " Monsieur, Madame " )
FIN SELON 23
Chapitre 1: Les fondamentaux de l’algorithme

Instructions conditionnelles: SI vs SELON

On va utiliser le SELON a la place du

SI lorsque chaque cas de notre
condition nécessite un traitement
particulier. 24
Chapitre 1: Les fondamentaux de l’algorithme

Instructions Itératives : POUR

Pour variable allant de expression1 jusqu'à expression2 avec un
pas de expression3 faire

• La variable n est appelée variable de contrôle ou indice de

– A l'origine n = 1
– Si n<=10 alors la séquence d'instructions est exécutée.
• n est incrémenté de la valeur décrite par le PAS (n+1) et est à
nouveau testé avec 10.
– Si n>10 alors on sort de la boucle
Chapitre 1: Les fondamentaux de l’algorithme

Instructions Itératives : TANT QUE

• Le test est fait en début de boucle (on peut donc simuler une
boucle "pour" à l'aide d'une boucle "tant que").

26
Chapitre 1: Les fondamentaux de l’algorithme

Instructions Itératives : FAIRE - TANT QUE

• Le test est fait en fin de boucle (on peut aussi simuler une
boucle "pour" à l'aide d'une boucle »Faire tant que").

• La Condition est évaluée après

chaque itération
• Les instructions entre Répéter
et jusqu’à sont exécutées au
moins une fois
• Leur exécution est répétée
jusqu’à ce que condition soit
vrai (tant qu'elle est fausse)

27
Chapitre 1: Les fondamentaux de l’algorithme

Instructions Itératives : CHOIX

• Si on peut déterminer le nombre d'itérations avant l'exécution de
la boucle, il est plus naturel d'utiliser la boucle POUR
• S'il n'est pas possible de connaitre le nombre d'itérations avant
l'exécution de la boucle, on fera appel à l'une des boucles TANT
QUE ou REPETER TANT QUE
– Si le minimum d’iteration =O alors utiliser TANT QUE
– Si le minimum d’iteration =1 alors utiliser REPETER TANT QUE

28
 Chapitre 2
Les bases du langage C
Définitions
Langage C
Les identificateurs
Les mots clés
Les types
Variables et les constante
Commentaires
Operateurs
Les entrées / Sorties
Instructions conditionnelles
Les boucles
Les fonctions en C
Chapitre 2: les bases du langage C

Définitions
• Programmation = Développement = Codage
• Instruction
– Ordre donné à l’ordinateur pour effectué une tache
– Se termine toujours par un point virgule ( ; )
– Exemple: Int x=5;
• Programme
– Ensemble cohérant d’instructions pour résoudre un problème.
– Chacune de ces instructions permet de faire une tache et la somme
permet de résoudre le problème.
– Exemple: Programme Somme de deux valeurs
– Méthode : Fonction ou procédure
• Applications
– Un ou plusieurs programme
– Permet d’effectuer un travail (resoudre un ensemble de problemes)
30
– Exemple: Application calculatrice
Chapitre 2: les bases du langage C

Le langage C
• Langage de programmation utilisé pour
éditer et exécuter des programmes
• Conçu en 1972 par Dennis Richie et Ken
Thompson
• Langage de Bas Niveau
• A inspiré beaucoup d'autres langages tels
que le JAVA ou C++
• Langage Procédurale c’est-à-dire non
orienté Objet
• Langage compilé (par opposition aux
langages interprétés tels que le JAVA)
• Les fichiers source sont suffixés par .c

31
Chapitre 2: les bases du langage C

Exécution d’un programme en C

• Cycle de vie d’un programme

32
Chapitre 2: les bases du langage C

Structure d’un programme en C

• 04 grandes Parties
– Zone des directives ou déclaration des bibliothèques avec
INCLUDE
– Zone de déclaration des variables et constantes globales
– Zone de déclaration (annonce) des fonctions
– Corps du programme qui lui est composé:
• Méthode principale main
– Cette méthode est la partie du programme qui montre du
point de vue séquentiel tout ce qui sera exécute.
– Contient :
» les variables et constantes locales
» L’appel des autres méthodes du programme
• Autres méthodes :
– Procédure (void)
33
– Ponctions
Chapitre 2: les bases du langage C

Structure d’un programme en C: Exemples

34
Chapitre 2: les bases du langage C

Les identificateurs
• Une suite de caractères parmi : les lettres (minuscules ou majuscules,
mais non accentuées),
• Le rôle d'un identificateur est de donner un nom à une entité du
programme :un nom de variable, constantes ou de fonction
• Règles:
– suite de caractères alphanumériques ou caractère espérés par un _
donc pas d’espace
– premier caractère doit être alphabétique ou caractère surligné _
– Longueur des identificateurs dépendante du compilateur
• Mots réservés
– Un certain nombre de mots, appelés mots-clefs, sont réservés pour le
langage lui-même donc non utilisables

35
Chapitre 2: les bases du langage C

Les types de données

• Un type est un ensemble de valeurs que peut prendre une variable.
• Il y a des types prédéfinis et des types qui peuvent être définis par le
programmeur.

36
Chapitre 2: les bases du langage C

Les commentaires
• Un texte en langage humaine dans un code source
• Permet de donner son opinion ou d’expliciter une partie du
programme
• Débute par /* et se termine par */.
• Par exemple:
main( ) {
printf("bonjour MIO 2"); /* ce programme affiche bonjour*/
}

37
Chapitre 2: les bases du langage C

Les Variables
• Syntaxe de base :
type nomVariable ;
– Exemple:
int i; /* i est une variable de type entier */
float j,k; /* j et k sont des variables de type réel */
char c; /* c est une variable de type caractère */
• Une valeur initiale peut être affectée à une variable dès la déclaration
int i, j=3, k; /* seul j est initialisé à 3*/
float f=1.2344 ; /* f est initialisé à 1,2344*/
• On peut déclarer plusieurs variables d'un même type:
– Exemple:
int a, b, c;
• On peut initialiser une variable lors de sa déclaration:
– Exemple:
float pi = 3.14; 38
Chapitre 2: les bases du langage C

Les Constantes
• Une constante est une donnée dont la valeur ne varie pas lors de
l'exécution du programme.
• Syntaxe :
const Type Identificateur = Valeur ;
• Ou bien en utilisant la directive define avant d’entrer dans le main:
#define Identificateur Valeur

39
Chapitre 2: les bases du langage C

Caractères spéciaux
• Des caractères spéciaux sont représentés à l'aide du méta-caractère \.

40
Chapitre 2: les bases du langage C

Affichage avec printf

• L’instruction printf permet d'obtenir un affichage formaté à l'écran.
Syntaxe :
Printf ("texte et caractères de contrôle", , arg1) ;
• Chaque format d'affichage est introduit par le caractère % suivi d'un
caractère qui indique le type de conversion.
Int x=5;
Printf ("X=%d", x) ;

41
Chapitre 2: les bases du langage C

Affichage avec printf

42
Chapitre 2: les bases du langage C

Lecture de données avec scanf

• L’instruction scanf effectue la lecture des variables.
• Syntaxe :
Scanf ("formats d'affichage", variable1, variable2,…,variablen) ;
• Remarque : Seules les variables scalaires (entiers, réels et caractères)
doivent être précédées de &.

43
Chapitre 2: les bases du langage C

Operateurs
• Operateurs arithmétiques
+ addition x=y+z;
- soustraction x=z-y;
* multiplication t=vs* s;
/ division v=a/u;
% reste de la division entière z=e%b;
• Operateurs de pas
+= -= *= /=

• Exemples
i = i + 20; i += 20;
i = i - 20; i -= 20;
i = i * 20; i *= 20;
i = i / 20; i /= 20;
44
Chapitre 2: les bases du langage C

Operateurs
• Operateurs logiques
• Les opérateurs logiques sont, par ordre décroissant de priorité :
! Non logique
> >= < <= Test de supériorité et d'infériorité
== et != Test d'égalité et d'inégalité
&& et || ET et OU logique

45
Chapitre 2: les bases du langage C

Operateurs
• Post (i++) et pré-incrémentation (++i)
– Ils permettent d'incrémenter ou de décrémenter une variable.
– Dans une opération d'affectation qui met en jeu l'opérateur de :
• pré-incrémentation (pré-décrémentation), la variable est d'abord
incrémentée (décrémentée) de 1. L'affectation est ensuite effectuée.
• post-incrémentation (post-décrémentation), L'affectation (sans les ++ (--
)) est effectuée avant l'incrémentation (décrémentation).

46
Chapitre 2: les bases du langage C

Instructions conditionnelles: IF
• L'instruction if sélectionne le traitement (bloc d'instructions) à faire si une
condition est vérifiée.
• Syntaxe :

• Si le traitement à effectuer est constitué d'une seule instruction, il est

possible d'omettre les accolades.
47
Chapitre 2: les bases du langage C

Instructions conditionnelles: IF
• If ELSEIF ELSE
– En combinant plusieurs structures if - else en une expression
nous obtenons une structure qui est très courante pour
prendre des décisions entre plusieurs alternatives:

48
Chapitre 2: les bases du langage C

Instructions conditionnelles: IF
• If imbriqués
– Il est possible d'imbriquer plusieurs structures if-else, cela
permet de prendre des décisions entre plusieurs alternatives.
– Mais, afin de gagner en lisibilité, on conseille d'adopter une
écriture tabulée.

49
Chapitre 2: les bases du langage C

Instructions conditionnelles: IF
• Exemple avec les IF

50
Chapitre 2: les bases du langage C

Instructions conditionnelles: SWITCH

• SELON en ALGO
• S’il y a plus de deux choix possibles, l’instruction selon permet une
facilité d’écriture

51
Chapitre 2: les bases du langage C

Instructions Itératives: FOR

• Les boucles permettent de répéter une série d'instructions tant
qu'une certaine condition n'est pas vérifiée.

• Exemple

• Explications :
– i = 0 initialise la variable i à 0. Il suppose l’existence préalable de la
variable i (donc sa déclaration en amont).
– i < 10 constitue la condition pour entrer dans la boucle (c’est la
condition qui autorise l’exécution du bloc d’instructions de la boucle).
– i = i + 1 correspond à l’incrémentation (on remplace parfois en i++ à
la fin de chaque boucle).
Chapitre 2: les bases du langage C

Instructions Itératives: WHILE

• Tant que expression est vérifiée (i.e., non nulle)
alors instruction est exécutée.
• Si expression est nulle au départ, instruction ne sera jamais
exécutée.

53
Chapitre 2: les bases du langage C

Instructions Itératives: DO WHILE

• Il peut arriver que l'on ne veuille effectuer le test de continuation
qu'après avoir exécuté l'instruction.
• Dans ce cas, on utilise la boucle do---while.

• Ici, instruction sera exécutée tant que expression est non nulle.
Cela signifie donc que instruction est toujours exécutée au moins
une fois.

54
Chapitre 2: les bases du langage C

Instructions de branchement : BREAK

• break peut être employée à l'intérieur de n'importe quelle boucle.
– Elle permet d'interrompre le déroulement de la boucle, et passe à la première
instruction qui suit la boucle. En cas de boucles imbriquées, break fait sortir
de la boucle la plus interne.

55
Chapitre 2: les bases du langage C

Les bibliothèques
• La pratique du C exige l'utilisation de bibliothèques de fonctions.
• Sont disponibles sous forme précompilées (.lib).
• Afin de pouvoir les utiliser, il faut inclure des fichiers en-tête (.h)
dans nos programmes.
• Pour inclure les fichiers en-tête: #include
• Exemple
#include <stdio.h>

56
Chapitre 2: les bases du langage C

Les fonctions sur les caractères <ctype.h>

• isalnum() teste si le caractère est alphanumérique.
• isalpha() teste si le caractère est alphabétique.
• iscntrl() teste si l'argument est un caractère de contrôle.
• isdigit() teste si le caractère est numérique.
• isgraph() teste si le caractère est visible.
• islower() teste si le caractère représente une lettre minuscule.
• isprint() teste si le caractère est imprimable.
• ispunct() teste si le caractère est un signe de ponctuation.
• isspace() teste si le caractère est un espacement.
• isupper() teste si le caractère représente une lettre majuscule.
• isxdigit() teste si le caractère est un chiffre héxadécimal valide.
• tolower() convertit le caractère en sa représentation minuscule.
• toupper() convertit le caractère en sa représentation majuscule.
57
Chapitre 2: les bases du langage C

Les fonctions sur les chaines <string.h>

• strcat() concaténation de deux chaînes de caractères.
• strncat() concaténation limitée en longueur de deux chaînes.
• strchr() recherche la première occurence d'un caractère dans un
chaîne.
• strrchr() recherche la dernière occurence d'un caractère dans une
chaîne.
• strcmp() comparaison lexicographique de deux chaînes de caractères.
• strcpy() recopie d'une chaîne de caractère.
• strncpy() recopie limitée en longueur.
• strlen() calcule la longueur d'une chaîne.
• strstr() calcule la position d'une sous-chaîne dans une chaîne.
• strtok() découpe une chaîne en lexèmes.

58
Chapitre 2: les bases du langage C

Les fonctions sur les nombres <math.h>

• cos() cosinus.
• sin() sinus.
• tan() tangente.
• exp() exponentielle (ex).
• log() logarithme népérien.
• log10() logarithme décimal.
• modf() décomposition en partie entière et décimale d'un réél.
• pow() élévation à la puissance (xy).
• sqrt() extraction de racine carrée.
• ceil() calcul de l'entier inférieur le plus proche (fonction plancher).
• fabs() valeur absolue.
• floor() calcul de l'entier supérieur le plus proche (fonction
plafond).
59
• fmod() reste de la division.
 TD 1 & TP 1
Voir fichier joint au cours

60
 Chapitre 3
Les tableaux et les
algorithmes de Tri
Chapitre 3: les tableaux et les algorithmes de Tri

Introduction
• Les variables, telles que nous les avons vues, ne permettent de
stocker qu'une seule donnée à la fois.
• Or, pour de nombreuses données, comme cela est souvent le cas,
des variables distinctes seraient beaucoup trop lourdes à gérer.
• Exemple:
– Les notes de la MIO 2
– La liste des étudiants de UASZ
– La liste des employés de la SGBS
• C’est pourquoi:
– Les langages de programmation tels que le langage C propose des
structures de données permettant de stocker l'ensemble de ces
données dans une unique « variable commune » : UN TABLEAU
• Un tableau est une suite de cases (espace mémoire) de
même taille destinée à stocker et manipuler un ensemble de
valeurs de même type
Chapitre 3: les tableaux et les algorithmes de Tri

Introduction
• Deux formes de tableaux usuels
– Tableaux à une dimension

– Tableaux à N dimension dont N>=2

Chapitre 3: les tableaux et les algorithmes de Tri

Tableau à une dimension: Définitions

• Une variable structurée formée d'un nombre entier N de variables
simples du même type
• 01 ligne + N colonnes ou vis versa (01 colonne + N lignes)
• Définitions
– La dimension ou la taille du tableau (N) : Le nombre de cellules
– Indice i : Le numéro de la cellule. Indice commence par 0 et s’arrête
à (N-1).
• Exemple : Un tableau de 10 elements (N=10):
– Premier indice Tab[0] et dernier indice Tab[9]
– Tab[1] désigne le contenu de la cellule numéro 1 c’est à dire la
deuxième cellule du tableau

64
Chapitre 3: les tableaux et les algorithmes de Tri

Tableau à une dimension: Déclaration

• Déclaration nécessite trois informations :
– Le type des éléments du tableau  ;
– le nom du tableau (son identificateur) ;
– la taille du tableau (le nombre d’éléments qui le composent)
type Nomtableau[Taille];
Exemple 1: on déclare un tableau nommé Tab1 de 04 entiers
int Tab1[4];
Exemple 2: on déclare un tableau TabP de 10 chaines de caractères
Char TabP[10];
• Initialisation = Action de déclarer un tableau et de lui donner
ses premières valeurs
int tab[3] = { 12, 24, 73 };

Il est possible d’initialiser sans donner la taille du tableau

int tab[] = { 1, 2, 3 }; 65
Chapitre 3: les tableaux et les algorithmes de Tri

Tableau à une dimension: Accès aux éléments

• Accéder aux éléments dans un tableau
– On utilise l’indice i
• tab [i] avec i étant l’indice (numéro de la cellule)
– Exemple d’utilisation :
• tab [3] = 12;
– Mettre la valeur 12 dans la case numéro 3 du tableau
• printf ("%d", tab [3])
– affiche la valeur numérique contenue dans la case
numéro 3 du tableau
• tab [3] = tab [3] + 2 ;
– Ajoute 2 à la valeur contenue dans la case numéro 3 du
tableau et le remttre dans la meme cellule tab [3] .
Exemple: Si elle contenait auparavant la valeur 12, elle
contiendra à présent la valeur 14. 66
Chapitre 3: les tableaux et les algorithmes de Tri

Tableau à une dimension : Parcourir d’un tableaux

• On utilise une boucle FOR allant i=0 à M
– 0 est le premier indice
– M est l’indice maximal du tableau (M=N-1) ou N est le nombre
d’éléments

Syntaxes:
for (i=0; i<=M; i++) { … }
for (i=0; i<N; i++) { … }

67
Chapitre 3: les tableaux et les algorithmes de Tri

Tableau à une dimension: Exemple

68
Chapitre 3: les tableaux et les algorithmes de Tri

Tableau à 02 dimensions: Définitions

• Ensemble de lignes et de colonnes
• Un tableau à deux dimensions contient donc L*C composantes.
– L le nombre de lignes
– C le nombre de colonnes.
– L et C sont alors les deux dimensions.
Chapitre 3: les tableaux et les algorithmes de Tri

Tableau à 02 dimensions: Définitions

• Exemple : La Liste (prénom, nom, Téléphone et adresse) de vos
camarades de classe)

Pape Ousmane DIOP 77 876 76 76 Dakar

Aliou FAYE 76 555 44 22 Ziguinchor

Fatou FALL 78 763 44 22 Touba

Jean Alain DIATTA 33 875 55 11 THIES

Amie Ka 77 765 77 11 Matam

Paul SARR 76 776 32 44 Mbour

• On dit qu'un tableau à deux dimensions est carré, si L est égal à C.

Chapitre 3: les tableaux et les algorithmes de Tri

Tableau à 02 dimensions: Déclaration

• Déclaration nécessite trois informations :
– Le type des éléments du tableau  ;
– le nom du tableau (son identificateur) ;
– La taille des différentes dimensions (Nombre de lignes et Nombre
de colonnes).

Type NomduTableau [Nb lignes] [Nb colonnes];

– Exemples
• int tab[20][35];
– On déclare un tableau de 20 lignes et 35 colonnes

• Char TabEtudiants [3][15];

– On déclare un tableau de 3 lignes et 15 colonnes 71
Chapitre 3: les tableaux et les algorithmes de Tri

Tableau à 02 dimensions: Initialisation

• Initialiser un tableau 2D
• int Tab[3][2] = {{ 51, 23 }, { 11, 32 }, { 83, 14 } };

51 23
• Tab[0][0] =51; 11 32
• Tab[1][1] =32;
83 51
• Tab[0][0] = Tab[2][1] ;

• Char tabE[2][2] = {{ ’Fatou’, ’BA’ }, { ’Amie’, ’FAYE’ }, { ’Jean”, ’SARR’ } };

Fatou BA

Amie FAYE

Jean SARR
72
Chapitre 3: les tableaux et les algorithmes de Tri

Tableau à 02 dimensions: Initialisation

• Initialiser un tableau 2D

73
Chapitre 3: les tableaux et les algorithmes de Tri

Tableau à 02 dimensions: Accès au éléments

• Utiliser les deux indices i et j
– i pour les lignes 0 à L
– j pour les colonnes 0 à C

74
Chapitre 3: les tableaux et les algorithmes de Tri

Tableau à 02 dimensions: Parcourir

• On utilise deux boucles FOR imbriquées
– La première boucle i pour les lignes for (i=0;i<L; i++)
– La seconde boucle j pour les colonnes for (i=0;i<C; i++)
• Principe: On se position à i=0 puis on parcourt tous les j ( 0 à C)
puis on passe à i=1 ainsi de suite jusqu’à i<L

int main(void) {
int Tab[3][2] = {{ 51, 23 }, { 11, 32 }, { 83, 14 } }; 51 23
int i=0, j=0;
11 32
for (i = 0; i < 3; ++i) {
for (j = 0; j < 2; ++j) { 83 14
printf("tab[%d][%d] = %d\n", i, j, tab[i][j]);
}
}
return 0;
} 75
Chapitre 3: les tableaux et les algorithmes de Tri

Introduction
• Trier = ordonner suivant un ou plusieurs critères

• Existe 6 types de tri:

1. tri par sélection
2. tri a bulle
3. tri par permutation
4. tri par insertion
5. tri par fusion
6. tri rapide

NB: Nous intéresserons juste aux trois premiers algorithmes

76
Chapitre 3: les tableaux et les algorithmes de Tri

Tri par sélection

• L'idée est simple :
1. Rechercher le plus grand élément (ou le plus petit)
2. Le placer en fin de tableau (ou en début)
3. Recommencer avec le second plus grand (ou le second plus petit)
4. Le placer en avant-dernière position (ou en seconde position)
5. Et ainsi de suite jusqu'à avoir parcouru la totalité du tableau.
• Ce tri ce fait par 2 boucles for

77
Chapitre 3: les tableaux et les algorithmes de Tri

Tri par sélection

78
Chapitre 3: les tableaux et les algorithmes de Tri

Tri à bulle ou «Bubble Sort»

• Cet algorithme parcourt le tableau en comparant 2 cases
successives, lorsqu'il trouve qu'elles ne sont pas dans l'ordre
souhaité ( croissant dans ce cas ) , il permute ces 2 cases
– les valeurs les plus petites se déplacent progressivement vers le haut, comme
une bulle d’air dans l’eau, et les valeurs les plus grandes descendent vers le
bas du tableau.
• A la fin d'un parcours complet on aura le déplacement du
minimum a la fin du tableau.
• En faisant cet opération N fois , le tableau serait donc trié.

79
Chapitre 3: les tableaux et les algorithmes de Tri

Tri à bulle
• Dans chaque boucle, les paires successives des éléments sont
comparées et permutées si nécessaire.
• Si la paire a la même valeur ou est en ordre croissant, on la garde
elle-même.
• S’il y a N éléments à trier, le tri à bulles fait N-1 pour traverser le
tableau.

80
Chapitre 3: les tableaux et les algorithmes de Tri

Tri par permutation

• Cet algorithme consiste a parcourir le tableau jusqu’à ce qu'il trouve
un élément inférieur que le précédent ( mal placé ),il prend cet
élément et il le range à sa place dans le tableau , et il continue le
parcours jusqu’à la fin. Et affin de ne pas écraser les valeurs du
tableau il faut réaliser une translation des valeurs a l'aide d'une
boucle .

81
 TD 2 & TP 2:
Les tableaux et algorithmes de tri

Voir fichier joint au cours

82
 Chapitre 4
Programmation modulaire
et récursivité
Chapitre 4: programmation modulaire et récursivité

La modularité des programmes

• La programmation modulaire est le fait de structurer le code
source d’un programme informatique en plusieurs fichiers.
• Un programme dépassant une ou deux pages est difficile à com
prendre
• Une écriture modulaire permet de scinder le programme en
plusieurs parties et sous - parties
• En C, le module se nomme la « fonction ».
• Le programme programme principal décrit essentiellement
essentiellement les enchaînements des fonctions
• Objectifs
– Lisibilité du code
– Réutilisation de la fonction
– Tests facilités
– Évolutivité du code
– Travail en equipe 84
Chapitre 4: programmation modulaire et récursivité

Les méthodes : fonctions et procédures

• Une méthode est une suite d’instructions séparée permettant
d’exécuter un traitement bien défini dans mon programme.
• Exemple: Pour un programme Calcul.C nous pouvons avoir en plus de la
méthode principale main() les méthodes suivantes:
• addition()
• soustraction()
• multiplication()
• division ()
• Les procédures et les fonctions ont pour objectif d'éviter les
répétitions de suite d'instructions
• Nous avons deux forme de méthodes en programmation :
– Les fonctions: retournent toujours un résultat après exécution
– Les procédures: ne retournent pas un résultat après exécution

– NB: Officiellement en langage C nous n’avons que des procédures c.-à-

d. que même les procédures sont nommées fonction
Chapitre 4: programmation modulaire et récursivité

Les méthodes : fonctions et procédures

• Les paramètres / Arguments
– Un paramètres est une information sous la forme d’une
variable qui est passée à la fonction lors de l’appel
– Elle peut subir des modification dans celle-ci
– Une méthode peut disposer de plusieurs paramètres
Type1 Parametre1, Type2 Parametre2 …
– Exemple
int Addition (int x, int y) { …. }
– Pas de déclaration multiple pour les paramètres
– Dans le cas où une fonction n'a pas de paramètres formels, le
mot clé void est mis en tant que liste-de-déclarations-de-
paramètres.
double pi(void) {
return(3.14159);
} 86
Chapitre 4: programmation modulaire et récursivité

Les méthodes : fonctions et procédures

• Une procédure
• Une méthode qui ne retourne pas un résultat après
exécution dont pas d’instruction return

• Déclarée avec le mot-clé VOID

• Peut prendre des paramètres
• Peut déclarée ses propres variables et constantes (locales)

87
Chapitre 4: programmation modulaire et récursivité

Les méthodes : fonctions et les procédures

• Une fonction
• Une méthode qui retourne toujours un résultat après exécution
dont dispose toujours de l’instruction return

• Déclarée en utilisant le type de la valeur de retour

– Exemple: Si une fonction doit retourner un entier alors elle sera
déclarer avec le mot int.
• Peut prendre des paramètres
• Peut déclarée ses propres variables et constantes (locales)

88
Chapitre 4: programmation modulaire et récursivité

Les méthodes : fonctions et les procédures

• Une fonction
• Déclaration

• Exemple

• NB
– En C, une fonction ne peut retourner qu’une valeur au plus
grâce à la commande return
– Le type de la fonction doit être le même que celui de la valeur
retournée
89
Chapitre 4: programmation modulaire et récursivité

Variables locales / Variables Globales

• Variables locales
– Un bloc est la partie de code compris entre {}
– Une variable créee dans un bloc n’existe que dans ce bloc
– C’est une variable variable locale au bloc
– Elle ne sera pas connue en dehors
– Sa valeur est perdue à la sortie du bloc
– « Sa durée de vie est celle du bloc »
• Une variable globale
– Existe en dehors de tout bloc
– A sa mémoire réservée pour toute l’exécution du programme
– « Sa durée de vie est celle du programme »

90
Chapitre 4: programmation modulaire et récursivité

Les fonction dans le programme: Prototype

• Une fonction doit toujours être déclarée sous forme de prototype
avant d’être implémenter
• Se fait après les #include

91
Chapitre 4: programmation modulaire et récursivité

Structure générale d’un programme avec méthodes

92
Chapitre 4: programmation modulaire et récursivité

Appel de fonction externe (Dans un autre fichier)

• Dans le cas de la programmation modulaire faisant appel à une
fonction se trouvant dans un autre fichier, nous remarquons
l'utilisation de 3 fichiers:
.c
Contient les définitions de nos fonctions on remarquera la
directive d’inclusion #include qui permet de prendre en
compte les entêtes définies dans le .h
.h
Contient les entêtes de nos fonctions (en langage c il est
possible de séparer les définitions des entêtes de fonctions
des définitions des fonctions elle-même)
main.c
Contient le programme principal, on remarquera que le fichier
main.c peut utiliser les fonctions d'opération grâce à la
directive de compilation #include. 93
Chapitre 4: programmation modulaire et récursivité

Le fichier header (.h)

• Si un programme main.c désire utiliser une (ou plusieurs) des
fonctions disponibles dans un autre fichier par exemple calcul.c, il
doit accéder à leurs déclarations pour pouvoir se compiler.
• C'est le rôle des fichiers en-tête (header) avec l'extension .h.
• On aura donc un couple de fichiers :
– un .h (pour les déclarations)
– un .c (pour les définitions) portant le même nom.

• Exemple de fichier calcul.h

int addition(int a, int b);

int soustraction(int a, int b);
int multiplication(int a, int b);
double division(int a, int b);
94
Chapitre 4: programmation modulaire et récursivité

Le fichiers module (.c) et main.c

• Le module contient l’ensemble des traitements avec leurs
prototypes+ implémentations
– Les procédures
– Les fonctions :

• Exemple de fichier calcul.c

• Dans le fichier main.c

– Utiliser un INCLUDE du fichier calcul.h
– Faire appel aux fonctions de clacul.c

95
Chapitre 4: programmation modulaire et récursivité

La récursivité
• La récursivité
– Une notion est dite récursive lorsqu’elle se contient elle-même
en partie ou si elle est partiellement définie à partir d’elle-
même.
– Typiquement, il s’agit d’une suite dont le terme général
s’exprime à partir de termes qui le précèdent.

• La forme récursive est généralement plus simple à comprendre et plus

élégante, elle peut être séduisante dans sa conception intellectuelle.

• Une fonction récursive void fct() {

– Une fonction qui s’appelle elle-même. ... fct();
}

96
Chapitre 4: programmation modulaire et récursivité

Récursive / Non Récursive

• la factorielle d’un nombre N donné est le produit des nombres
entiers inférieurs ou égaux à ce nombre N.
– Exemple: 5! =1*2*3*4*5 ou bien 5! =5*4!

Forme Normale Forme Recursive

N! = 1*2*3 ... *(N-1)*N N! = N*(N-1)!

int factorielle (int N) { int factorielle (int N) {

int i, fact=1; if (N<=1)
for (i=2;i<=N;i++) { return 1;
fact*=i; else
} return N*Factorielle(N-1);
return fact; }
}
97
Chapitre 5: Manipulation des fichiers en C

Récursive / Non Récursive

• Les entrées/sorties (E/S) ne font pas partie du langage C,
car ces opérations sont dépendantes du système. Néanmoins
puisqu'il s'agit de tâches habituelles, sa bibliothèque
standard est fournie avec des fonctions permettant de
réaliser ces opérations de manière portable. Ces fonctions
sont principalement déclarées dans le fichier stdio.h.
• Les entrées/sorties en langage C se font par l'intermédiaire
d'entités logiques, appelées flux
• Un flux de texte est organisé en lignes. En langage C, une
ligne est une suite de caractères terminée par le caractère
de fin de ligne (inclus) : '\n'.

98
 TD 3 & TP 3:
Programmation modulaire &
recursivité

Voir fichier joint au cours

99
 Références

• Bac, C. (2004). Support de Cours de Langage C. Institut National

de Télécommunications.
• Klaudel, H. Langage C: notes du cours.
• http://cours.pise.info/algo/introduction.htm
• https://www.i3s.unice.fr/~map/Cours/DUT_API_TD_TP/C1-
2_APIStructuresAlgorithmiquesdeBase.pdf
• https://www.lri.fr/~hivert/COURS/CFA-L3/00-Intro.pdf
• https://openclassrooms.com/fr/courses/4366701-decouvrez-le-
fonctionnement-des-algorithmes/4384756-tirez-pleinement-parti-
de-ce-cours
• https://www.gladir.com/CODER/C/deffonction.htm
• https://melem.developpez.com/tutoriels/langage-
c/fichiers/?page=cours
100
 Documentation

Logiciel Recommandé pour les TPs

101
 Algorithme &
Programmation
Cours Magistral
Licence Informatique & MIO

Dr Edouard Ngor SARR

Enseignant-Chercheur
Université Assane SECK de Ziguinchor (UASZ)
Ziguinchor-Sénégal
edouard-ngor.sarr@univ-zig.sn
2021-2022