Notion d'algorithme

Algorithme

Algorithmique

L'algorithme est la science qui a pour but de concevoir et d'analyser les algorithmes.
Concevoir un algorithme de résolution d'un problème, c'est proposer une méthode de
résolution du dit problème. La conception d'un algorithme requière donc quelques qualités:

 Avoir une certaines intuition: C'est à ce niveau qu'intervient l'intelligence nécessaire

en algorithmique.
 Etre méthodique et rigoureux: Chaque fois qu'il faut écrire un algorithme le
programmeur doit se mettre à la place de la machine qui va exécuter cet algorithme
pour vérifier si le résultat obtenu est bien celui qu'on attendait.
 L'analyse des algorithmes: C'est l'étude mathématiques dans le but de déterminer leur
efficacité.
 L'efficacité: C'est une mesure du temps nécessaire à l'exécution de l'algorithme, c'est
l'analyse des algorithmes qui peut nous permettre de choisir entre plusieurs
algorithmes proposés pour résoudre un problème, celui qui est le plus efficace.

L'algorithme

Un algorithme est une suite d'instruction ordonnée qui décrit de façon exhaustive les
différentes étapes à suivre par un processeur ou un automate pour résoudre un problème
donné en un temps fini.

Le processeur

Un processeur: C'est tout unité capable de comprendre un énoncé et de réaliser le travail

correspondant.

Exemple d'algorithme

Exemple 1
Toto achète au marché de Mokolo, 20Kg de viande sans os à 2€ le Kg.
Quelle est la dépense totale effectuée par Toto?
Ecrire un algorithme pour permettre à Toto de calculer rapidement la dépense totale.

Exemple2

Ecrire un algorithme qui permet de calculer la somme de 5 premiers entier naturels non nuls.

Production d'un algorithme

La démarche à suivre pour obtenir un algorithme de résolution d'un problème donné compte
plusieurs étapes:

Définition des objectifs

On se pose la question: Qu'est-ce qu'on demande de faire? Quel est le travail à fournir ?
En général l'énoncé du problème fait ressortir les objectifs.

Spécification d'une méthode de résolution

Comment doit-je procéder pour résoudre ce problème?

Quelle est la méthode à utiliser pour résoudre ce problème?
Il s'agit de dire sans entrer dans les détails comment le problème sera résolu. La spécification
peut se faire par des courtes phrases en langage naturel ou à l'aide des symboles
mathématiques.

La mise en ouvre de la méthode retenue

Elle consiste à choisir les structures de données appropriées et à développer l'algorithme.

Le texte de l'algorithme

Le texte a pour but de vérifier que l'algorithme marche et fournir de bons résultats. Le travail
à faire ici consiste à essayer l'algorithme avec des données choisies au hasard pour s'assurer
de son bon comportement.

Le dossier algorithmique

Le dossier algorithmique est un document qui résume la démarche utilisée pour produire
l'algorithme qui comporte 4 étapes:

 Enoncé du problème: Il s'agit de dire de façon consiste en quoi consiste le problème à

résoudre.
 Principe de résolution: Il s'agit de dire en utilisant le langage naturel ou des symboles
mathématiques comment le problème sera résolu.
 L'environnement: C'est la liste des objets ou récipients nécessaires au processus pour
résoudre le problème. Chaque objet de l'environnement est caractérisé par son nom,
son type, sa nature, son utilisation, sa valeur initiale, sa valeur finale et son sens. Le
tout doit être résumé dans un tableau de la manière suivante.

No Valeur
Type Nature Utilisation Valeur initiale Sens
m finale

 L'algorithme proprement dit:

Algorithme: Nom de l'algorithme

Déclaration {Permet à l'ordinateur de réserver un espace mémoire pour chaque objet}

début

Corps de l'algorithme (liste des instructions)

Fin
Comment déclarer un objet (constantes, types, variables...)

On distingue la déclaration des constantes, la déclaration des types et la déclaration des

variables.
Exemple:
const: Pi=3,14; deux=2;

Un type

C'est un ensemble.
Exemple:
Semaine = (Lundi, Mardi, Mercredi, Jeudi, Vendredi, Samedi, Dimanche)

Les variables

Un variable peut changer de valeur.

var nom_de_l'objet: type Exemple:
var a:entier
jour:entier

Exemple d'algorithme

Algorithme: Somme
var x, y, S : réel
debut
lire(x)
lire(y)
S←x+y
écrire ("le résultat est ", S)
Fin

Résolution d'un problème en informatique

La résolution d'un problème en informatique ne comporte qu'une seule phase automatique qui
est l'exécution d'un programme, et le programme quant à lui matérialise dans un langage
compréhensible par l'ordinateur un principe de résolution ou un algorithme.
L'écriture d'un programme n'est qu'une étape dans le processus de programmation. Cette étape
comporte deux phases:

 La première est la résolution du problème (écriture de l'algorithme)

 La deuxième est l'adaptation de l'algorithme à l'ordinateur.

La résolution du problème
Elle consiste à la mise sur pied d'un algorithme de résolution du dit problème. Cette phase est
la plus difficile et représente plus de 70% du travail à fournir. C'est la phase dans laquelle le
programmeur doit faire appel à son intelligence et à son intuition pour produire des solutions
efficaces. Cette phase est dépendante de la machine obtenue.

L'adaptation de l'algorithme à l'ordinateur

Le travail ici consiste à coder dans un langage de programmation l'algorithme obtenu à la

première phase: on obtient alors un programme.

Instructions de base

Algorithme

Concept d'objet

La matière première manipulée en informatique est l'information, cette information en

algorithmique se présente sous forme de données.
Une donnée est une valeur stockée en mémoire centrale dans un objet. Un objet est un
récipient utilisé part le processeur pour stocker les données nécessaires à la résolution d'un
problème.
Chaque objet est caractérisé par:

Le nom
Encore appelé identificateur, le nom permet d'identifier un objet dans un algorithme, il est
posé d'un ensemble de caractères alphabétiques ou alpha numérique.
Remarque:

 Un nom commence toujours par un caractère alphabétique, par conséquent ne jamais

commencer un nom par un chiffre.
 Un nom peut contenir les caractères de soulignement.
 Un nom ne contient ni caractère, ni puissance, ni indice.
 De préférence choisir des noms significatifs c'est-à-dire des noms qui ont un sens par
eux-mêmes.

Le type

Il indique dans lequel un objet prend ses valeurs, il indique aussi implicitement les opérations
qui pourrait être réalisées sur cet objet.

Le type entier
C'est un type qui prend ses valeurs dans l'ensemble Z.
Les opérations possibles sur objet de type entier son: l'addition (+); la soustraction (-); la
multiplication (x); la division (div), le modulo (mod) qui permet de trouver le reste de la
division, exemple: 3mod4=3; 5mod2=1; 4mod2=0

Le type réel

Ce type prend ses valeurs dans l'ensemble R. Les opérations possibles sont l'addition (+), la
soustraction (-), la multiplication (x), la puissance (**), la division (/).

Le type booléen

C'est un ensemble à deux valeur: "vraie" ou "faux", les opérations possibles sur les éléments
du types booléen sont : "nom", "ou", "et".

A B non A A ou B A et B
F F V F F
F V V V F
V F F V F
V V F V V
Le type caractère

C'est l'ensemble constitué par les lettres ("a", ..., "z") des chiffres ("0", ..., "9") et les
caractères spéciaux (+; -; *; #).
L'opération possible sur les éléments de type caractère est appelée concaténation. Le symbole
sera "+"
Exemple:
'A'+'B'='AB'
'3'+'4'='34'

Le type chaîne de caractères

C'est une combinaison de caractère entre les côtes, exemple: 'papa'

La nature

Un objet peut être soit une variable, soit une constante

Variable

Une variable est un objet qui peut changer de valeur lors de l'exécution d'un algorithme.
Exemple:
var b: réel

Une constante

Une constante est un objet qui ne change pas de valeur lors de l'exécution d'un algorithme. Sa
valeur est fixée au début de l'algorithme (lors de la déclaration) et toute tentative de
modification de cette valeur provoque une erreur.
Exemple:
const Pi=3.14

L'utilisation
Un objet peut être objet d'entrée, objet de sortie ou objet interne.
Un objet d'entrée contient une valeur du problème à résoudre. Sa valeur finale n'est pas
importante.
Un objet de sortie contient à la fin du déroulement d'un algorithme une valeur de sortie qui
peut être un résultat. Sa valeur initiale n'a pas d'importance.

Objet interne

C'est un objet intermédiaire utilisé dans un algorithme, le plus souvent il joue le rôle de
compteur. Ainsi sa valeur finale et sa valeur initiale n'ont pas d'importance.

Valeur initiale

C'est la valeur que prend un objet pour la première fois dans un algorithme.
Exemple:
x←4
y ← -2

Valeur finale

C'est la valeur que l'objet contient à la fin de son utilisation dans l'algorithme.

Le sens

Le sens est donné par une courte phrase, celle-ci indique le rôle que joue l'objet dans
l'algorithme. Cependant si l'objet a un nom significatif, on peut ne pas préciser le sens.

Le nom x
Le type entier
Nature variable
Utilisation entrée
Valeur initiale 4
Valeur finale 5
Sens objet à additionner

Les actions élémentaires

Ce sont des ondes ou instructions contenues dans un algorithme et que l'ordinateur devra
interpréter et exécuter afin de résoudre un problème donné. Dans la plus part des cas:

 L'ordinateur sait additionner, soustraire, multiplier, diviser.

 Il sait comparer les valeurs de 2 objets, il sait attribuer une valeur à un objet.
 Il sait obtenir la valeur d'un objet à partir de l'extérieur.

Sait communiquer la valeur d'un objet à l'extérieur.

l'affectation

Elle permet d'attribuer une valeur à un objet et la notation est ←

Exemple:

x←3 : A x j'affecte la valeur 3

y←x : A y j'affecte la valeur de x
x←y-2 : A x j'affecte la valeur de y-2
L'affectation peut se réaliser avec des objets de n'importe quel type, mais l'objet de gauche
doit être d'un type compatible avec celui de l'objet de droite.

La lecture

Elle permet la communication de l'extérieur vers l'intérieur, la lecture permet donc

d'introduire une valeur dans un objet à partir de l'extérieur.
Exemple: Clavier, scanner.
La notation: lire (liste des objets)
Exemple: lire(x)

L'écriture

L'écriture permet la communication de l'ordinateur vers l'extérieur, elle permet donc de

ressortir le résultat du traitement effectué par l'ordinateur.
La notation: écrire(liste d'objets)

Exercice d'application

Exercice 1

Ecrire un algorithme qui lit deux nombres entiers, calcule et affiche la somme des deux
nombres, la moyenne de ces 2 nombres et le reste de la division du second nombre par le
premier nombre.

Objectifs:

 Lire deux nombres

 Calculer:
 Somme
 Moyenne
 Reste

 Afficher
Principe de résolution:
Somme=a+b
moyenne=(a+b)/2
reste = bmod(a)

Algorithme: Calcul
var a,b,somme,reste:entier
moyenne:réel
debut
lire(a)
lire(b)
 somme ← a+b
moyenne ← (a+b)/2
reste ← b mod a
écrire('la somme est:', somme)
écrire('la moyenne est:', moyenne)
écrire('le reste est:', reste)
Fin

Exercice 2

Une structure de la place emploie les temporaires à l'heure à raison de 4€ l'heure. Des retenus
sur salaire de l'ordre 15% sont effectuée sur le salaire mensuel. Ecrire un algorithme
permettant de lire la durée de travail mensuel d'un employer et de calculer son net à percevoir.

Exercice 3

Ecrire un algorithme qui permet de lire deux nombres et qui les permute dans les deux cas
suivants:

 En utilisant un objet intermédiaire.

 Sans utiliser un objet intermédiaire.

Exercice 4

Ecrire un algorithme qui lit deux caractères et affiche leur concaténation.

Structures de contrôle

Algorithme

Généralités
On distingue les structures séquentielles, les structures conditionnelles et les structures
répétitives.

Structure séquentielle

C'est la structure la plus simple car il y’a aucune condition, aucune répétition, toutes les
institutions s'exécute de façon séquentielle (étape par étape)
Exemple:
debut
lire(a)
lire(b)
c←a
a←b
b←c
écrire(a,b)
fin

Structure conditionnelle

Elle est utilisée pour résoudre des problèmes ayant une ou plusieurs alternatives. On distingue
la structure "si" et "cas où".

La structure conditionnelle "si"

Elle existe sous deux formes:

syntaxe:
premier cas:
si condition alors action
fin si

deuxième cas:
si condition alors action 1
sinon action 2
fin si

Sémantique (explication)

Les mots soulignés sont reconnus par l'ordinateur.

Condition est un booléen
action peut être soit une instruction, soit un ensemble d'instruction, soit une structure de
contrôle.

Fonctionnement
Premier cas: On exécute "action" uniquement lorsque la condition est vraie.
Deuxième cas: On exécute "action 1" uniquement lorsque la condition est vraie, et on exécute
"action 2" uniquement lorsque la condition est fausse.

Exemple 1:

Ecrire un algorithme qui permet de lire un entier et affiche sa valeur lorsqu'il est positif
Algorithme: nombre positif
var a:entier
debut
lire(a)
si a>0 alors
écrire(a)
fin si
fin

Exemple 2:

Ecrire un algorithme qui lit deux caractères et les affiches dans l'ordre alphabétique.

Algorithme: ordre_alphabet
var A,B: caractère
debut
lire(A)
lire(B)
si A<B alors
écrire(A,B)
sinon
écrire(B,A)
fin si
fin

La structure "cas où"

Syntaxe:

cas où
condition 1 : Action 1
condition 2 : action 2
condition n : action n
[ sinon
action n+1 ]
fin cas

Explications:

Les mots suivants sont reconnus par l'ordinateur: condition 1; condition 2; condition n sont
des booléens, action 1; action 2; ...; action n. Chaque d'elle peuvent être soit une instruction,
soit un ensemble.
On exécute action 1 uniquement lorsque condition 1 uniquement lorsque condition 1 est vraie
et on exécute action 2 uniquement lorsque condition 2 est vraie et on exécute action n+1
lorsque condition n+1 est vraie.
Dès qu'une condition est vraie les autres conditions sont fausses.

Exemple 1: ax+b=0

Algorithme: equation-1
var a,b : réel
debut
lire(a)
lire(b)
cas où
a=0 et b=0 : écrire('infinité de solution')
a=0 et b≠0 : écrire('pas de solution')
a#0 : écrire('la solution est :', -b/a)
fin cas
fin

Exemple 2:

Algorithme: Equation_dégré_2
var a, b, c, x1, x1: réel
debut
lire(a)
lire(b)
lire(c)
cas où
a=0 et b≠0 et c≠0 : écrire('la solution est :' -b/c)
a=0 et b=0 et c=0 : écrire('infinité de solution')
a=0 et b=0 et c≠0 : écrire('pas de solution')
a≠0 et b**2-4*a*c<0 : écrire('pas de solution')
a≠0 et b**2-4*a*c=0 : écrire('la solution est :' -b/c)
a≠0 et b**2-4*a*c>0 : écrire('la solution est :', (-b*-D½)/2*a, (-b+D½)/2*a)
fin cas
fin

Exercice

Ecrire un algorithme qui lit 3 nombres et les affiches dans l'ordre croissant. Utilisez la
structure "si" et le récrire avec "cas où".

Les structures itératives (répétitions ou boucles)

Encore appelé structure répétition ou boucle, les structures itératives permettent d'effectuer
des traitements répétitifs, c'est-à-dire qu'on exécute une action plusieurs fois. Dans une boucle
le nombre d'itération peut être connu d'avance ou pas.
Si le nombre d'itération n'est pas connu d'avance, on utilise un prédicat (une condition) pour
mettre fin à l'itération. On distingue:
  La boucle "pour"
 La boucle "tant que"
 La boucle "répéter"

La boucle "pour"

On utilise la boucle "pour" lorsqu'on connaît d'avance le nombre d'itération à effectuer, c'est-
à-dire lorsqu'on connaît le nombre de fois qu'on doit exécuter une action.
Exemple: Ecrire un algorithme qui permet de lire 10 notes

La syntaxe:

pour compteur = N à M faire [pas]

action
fin pour

Sémantique
Les mots en gras sont reconnus par l'ordinateur.
Compteur est un objet intermédiaire de type entier, il a pour première valeur N. M est la
valeur finale de compteur.
pas est un objet intermédiaire de type entier, c'est un objet optionnel qui a pour valeur par
défaut "1", et dans ce cas on ne le précise pas.
action peut être soit une instruction, soit un ensemble d'instruction, soit une structure de
contrôle.

Comment fonctionner la boucle "pour"

On exécute action pour les valeur de compteur allant de N à M en fonction du pas.
Exemple:
(((((N+pas)+pas)+pas)+pas)+pas)/M

Exemple 1:

Ecrire un algorithme qui permet de lire 5 notes.

Algorithme: lecture_notes
var note: réel
i: entier
debut
pour i=1 à 5 faire
lire(note)
fin pour
fin

Exemple 2:

Ecrire un algorithme qui calcul xN où x est différent de 0 et N supérieur ou égale à 0.

Algorithme: puissance
var p, x: réel
i, n: entier
debut
lire(x)
lire(n)
p←1
pour i=1 à n faire
p←x**p
fin pour
écrire(p)
fin

La boucle "tant que"

On utilise la boucle "tant que" lorsqu'on ne connaît pas d'avance le nombre de répétition à
effectuer. Mais on connaît une condition d'arrêt.
Syntaxe:
tant que condition faire
action
fin tant que

Sémantique
Les mots en gras sont reconnus par l'ordinateur.
condition est un booléen
action peut être une instruction, soit un ensemble d'instruction, soit une structure de contrôle.

Fonctionnement
On exécute "action" tant que la condition est vraie, on arrête l'exécution lorsque la condition
devient fausse.
Si initialement la condition est fausse on n'exécute pas action.

Exemple 1:

Ecrire un algorithme qui permet d'écrire un nombre strictement positif.

Algorithme: nombre_positif
var N: réel
debut
lire(N)
tant que N<=0 faire
lire(N)
fin tant que
Fin

Exercice 2

Ecrire un algorithme qui permet de lire les nombres compris entre 1 et 3

Algorithme: lecture_en_interval
var n: réel
debut
lire(n)
tant que (n<1) ou (n>3) faire
lire(n)
fin tant que
fin
Tous les problèmes qu'on peut résoudre avec la boucle "pour" peut également se résoudre
dans la boucle "tant que"

Boucle "répéter"

On utilise la boucle "répéter" dans les mêmes conditions que la boucle "tant que", c'est-à-dire
lorsqu'on ne connaît pas d'avance le nombre de répétition à effectuer.

Syntaxe

répéter
Action
jusqu'à condition

Les mots soulignés sont reconnus par l'ordinateur

Sémantique
action peut être une instruction, un ensemble d'instruction ou une structure de contrôle.
condition est un booléen qui vaut vrai ou faux.

Fonctionnement
On exécute action jusqu'à ce que la condition devienne vraie, autrement dit on exécute action
tant que la condition est fausse.

Exemple:

Algorithme: nombre_positif
var N: réel
debut
répéter
lire(N)
jusqu'à N>0
Fin

Exercice:

Ecrire un algorithme qui lit un nombre entier n>1 et qui affiche la table de multiplication
correspondante.

correction:

Algorithme: table_de_multiplication
var i, n: entier
debut
répéter
lire(n)
jusqu'à n>1
pour i=1 à 10 faire
écrire(i,'x',n'=',i*n)
fin pour
fin

Les sous-programmes

Algorithme

Généralités
Lorsque la complexité d'un problème s'accroît, il devient nécessaire d'utiliser les sous-
programmes pour alléger la tâche. Ces sous-programmes sont les procédures et les fonctions.
De façon générale les sous programmes nous permettent:

 D'éviter de copier un segment de code plusieurs fois dans un même algorithme.

 De décomposer un grand problème en petit module ou sous problème, chacun
effectuant une tâche bien précise. Les modules peuvent être écrites par plusieurs
personnes de façon indépendante.
 De constituer une bibliothèque sous-programme.

Définition

 Le sous-programme est une suite d'instruction ordonnée que la machine n'exécute

lorsque c'est nécessaire
 La procédure est un sous programme qui peut calculer et mettre à la disposition de
l'utilisation plusieurs valeurs
 La fonction est un sous-programme qui calcule et met à la disposition de l'utilisateur
une valeur unique. La valeur calculée est mise à la disposition de l'utilisateur par
l'intermédiaire du nom de la fonction qui est une variable d'un type donné: celui de la
valeur calculée.

Syntaxe des sous-programmes

Procédure: nom (liste des paramètres)

déclaration
début
corps de la procédure
fin

Exemple:
Ecrire une procédure qui prend en paramètre deux nombres "a" et "b", qui calcule la somme et
la moyenne de ces nombres
Algorithme: somme(A, B, S, M: réel)
debut
S←A+B
M←S/2
fin

Syntaxe d'une fonction

Fonction: nom (liste des paramètres): type

déclaration
debut
corps de la fonction
nom_de_la_foncton←valeur_calculée
fin

Exemple:

Ecrire une fonction qui prend en paramètre deux nombres et renvoie la moyenne de ces
nombres.
fonction moyenne(A, B: réel):réel
var m: réel
debut
m←(A+B)/2
moyenne←m
fin

Passage de paramètres

On distingue les paramètres effectifs et les paramètres formels.

 Un paramètre formel est un paramètre utilisé dans la définition d'un sous programme.
 Un paramètre effectif ou réel est un paramètre utilisé lors de l'appel d'un sous-
programme.

Un sous-programme peut avoir trois types de paramètre:

 Les paramètres d'entrée fournissent les données au sous-programme. Exemple: A et B

étaient les paramètres d'entrée précédemment)
 Les paramètres de sortie: les paramètres de sortie contiennent les résultats à la fin du
déroulement du sous-programme. Exemple: S et M était les paramètres de sortie
précédemment)
 Les paramètres d'entrée-sortie jouent deux rôles: Il jouent le rôle de paramètre d'entré
et celui de paramètre de sortie.
Introduction à l'analyse descendante

Soit un travail T décrit par un énoncé E, l'analyse descente du travail T consiste à trouver une
décomposition de l’énoncer E en une suite d’énoncer E0, E1, ..., En-1 tel que la décomposition
obtenue soit élémentaire.
La réalisation des travaux associées T0, T1, ..., Tn-1 réalise le travail T.
L'arbre hiérarchique ou arborescence hiérarchique correspondant respective à l'énoncé E et le
travail T se présente comme suite:

Chaque Ei ou Ti peut également être décomposé:

La décomposition s'arrête lorsque l'on obtient des énoncés pouvant être réalisés simplement à
l'aide d'action élémentaire.
Après la décomposition chaque énoncé peut être réalisé par un algorithme ou un sous-
programme indépendant. L'enchaînement approprié de ces algorithmes ou sous-programme
permet de réaliser le travail T.

Application

Problème 1
Ecrivons un algorithme qui permet de calculer Cpn avec P inférieur ou égal à n. Ce problème
peut être décomposé en trois modules comme suite:

 La lecture de "p" et "n" avec les conditions suivantes: n supérieur ou égale à 0; p

supérieur ou égale à 0; p est inférieur ou égale à n.
 Le calcule de la factoriel d'un nombre
 Le calcul du quotient A/B*C

L'arborescence hiérarchique de ce problème est sous la forme:

Résolution:

procédure: lecture(x, y: entier)

debut
répéter
lire(x)
jusqu'à x>=0
répéter
lire(y)
jusqu'à y>=0 et y<=n
fin

fonction: factorielle(m:entier):entier
var i, fact: entier
debut
si m=0 alors
fact←1
sinon
fact←1
pour i=1 à m faire
fact←fact*i
fin pour
fin si
factorielle←fact
fin
fonction: combinaison(a, b, c: entier):entier
var z: entier
debut
z←a div(b*c)
combinaison←z
fin

Algorithme: combinaison_P_N
var n, P, R, A, A, B, C: entier
debut
lecture(n,P)
A←factorielle(n)
B←factorielle(p)
C←factorielle(n-P)
R←combinaison(A,B,C)
écrire(R)
fin

Problème 2

Ecrire un algorithme qui permet de résoudre une équation du second degré de la forme
ax2+bx+c=0 avec a différent de zéro.
Arborescence:

Procédure: lecture(a,b,c: réel)

debut
répéter
lire(a)
jusqu'à a#0
lire(b,c)
fin

Fonction discriminant(a, b, c: réel):réel

var d: réel
debut
d←b**2-4*a*c
discriminant←d
fin

Procédure: solution(d:réel)
var x0, x1, x2: réel
debut
si d<0 alors
écrire('pas de solution')
sinon
si d=0 alors
x0← -b/2
écrire('la solution est x0= ',x)
sinon
x1←(-b-sqrt(d))/2*a
x2←(-b+sqrt(d))/2*a
écrire('les solutions sont: ', x1, x2)
fin si
fin si
fin

Algorithme: équation
var dit, a, b, c: réel
debut
lecture(a,b,c)
det←discriminant(a,b,c)
solution(det)
fin

NB: "sqrt" permet d'avoir la racine carrée d'un nombre

Tableaux à une dimension

Algorithme

Généralités
Les objets manipulés jusqu'ici sont de types simples, c'est-à-dire qu'ils ne peuvent contenir
qu'une valeur à la fois. Cependant il peut arriver qu'on ait envie d'utiliser plusieurs valeurs à la
fois et de pouvoir les récupérer dans la suite du traitement. Dans ce cas, il est conseillé
d'utiliser les objets de type composé comme:

 Les vecteurs
 Les fichiers
 Les enregistrements
 Les listes chaînées
 Les piles
 Les files
 Les arbres
  Les graphes

Un tableau à une dimension encore appelé vecteur est une suite de données contiguëes logées
en mémoire centrale et référencé par un indexe (suite contiguë; c'est lorsque ses éléments se
suivent).

Caractéristiques et déclaration d'un vecteur

Un vecteur est caractérisé par:

 Le nom
 Le type de ses éléments
 la borne inférieure et la borne supérieure
 la taille (taille d'un vecteur: c'est le nombre d'élément que contient un vecteur).
taille=Sup-inf+1

Déclaration d'un vecteur

Premier cas:

type vecteur=tableau[inf..sup] de type d'élément

var v : vecteur

Deuxième cas:

var v: tableau[inf..sup] de type d'élément

Exemple 1:

const max = 100

type vecteur = tableau[1..max] d'entier
var v: vecteur

Exemple 2:

var v : tableau[1..100] d'entier

Référence d'un élément de vecteur

Chaque élément du vecteur est repéré par son rang dans ce vecteur. Si "inf" est le rang du
premier élément du vecteur alors le rang du ‘’ième’’ élément est donné par la formule inf+(i-
1)
Soit un vecteur
-5 2 1 10 0

V[1]=-5
V[2]=2
V[3]=1
V[4]=10
V[5]=0
V[i] = ieme élément du vecteur V

Opération sur les vecteurs: Opération de base

La lecture

pour i=1 à n faire

lire(V[i])
fin pour

Ecriture

pour i=1 à n faire

écrire(V[i])
fin pour

Exemple 1

Ecrivons une procédure qui permet de lire un vecteur de 10 entiers et qui ensuite met tous les
éléments de ce vecteur à zéro.

Correction:

type vecteur = tableau[1..10] d'entier

procédure lecture_zero(T: vecteur)
var i: entier
debut
pour i=1 à 10 faire
lire(T[i])
fin pour
pour i =1 à 10 faire
T[i] ←0
fin pour
fin

Exemple 2

Ecrire une fonction qui prend en paramètre un vecteur d'entier et qui renvoie la somme des
éléments de ce vecteurs.

Correction

fonction somme(V: vecteur) entier

var S, i: entier
debut
S←0
pour i=1 à 10 faire
S←V[i]+S
fin pour
somme←S
fin

Exercice 1:

Ecrire une procédure qui prend en paramètre deux vecteurs de réel "A" et "B" et qui transfert
les éléments du vecteur "A" dans le vecteur "B".

Exercice 2:

Ecrire une procédure qui prend en paramètre un vecteur de caractère V et n le nombre

d'élément de ce vecteur, et qui permet de lire n caractères dans le vecteur V. Ensuite cette
procédure doit pouvoir compter le nombre de fois que le caractère "A" apparaît dans le
vecteur.

Selon que le vecteur est trié ou pas les opérations suivantes peuvent être effectuées:

 La consultation.
 La mise à jour.

La consultation d'un vecteur

Consulter un vecteur consiste à parcourir tous les éléments de ce vecteur sans toutefois les
modifier. Exemple: le transfert, la copie etc.
La mise à jour d'un vecteur

Mettre à jour un vecteur consiste à le modifier:

 Soit en ajoutant d'autres éléments dans ce vecteur.

 Soit en supprimant certaines valeurs du vecteur.
 Soit en modifiant la valeur d'un élément du vecteur.

Le vecteur est trié lorsque les éléments sont classés dans un ordre précis (croissant,
décroissant, etc.)

Ajout d'un élément dans un vecteur

Premier cas: Le vecteur est non trié (les éléments sont en désordre)
Pour insérer un nouvel élément dans un vecteur non trié, on ajoute une case à la suite du
vecteur. On insère le nouvel élément dans cette case.

4 5 2 -5 4 5 2 -5 1
V: → V:

procédure: ajout_non_trié(V: entier, n, val: entier)

debut
n←n+1
V[n]←val
fin

Deuxième cas: Vecteur trié.

val = 6
3 4 8 12 14 3 4 6 8 12 14
V: →V :

Pour insérer un nouvel élément dans un vecteur trié:

 On ajoute une case à la fin du vecteur.

  On recherche la position d'insertion de la nouvelle valeur en effectuant un décalage à
droite de tous les éléments qui sont supérieur à droite de tous les éléments qui sont
supérieurs ou égaux à lui.
 Lorsque la position d'insertion est trouvée on ajoute cette nouvelle valeur dans la case
correspondante.

procédure: ajout_trié(V: vecteur, n, val: entier)

var i: entier
debut
n←n+1
i←n
tant que val<=V[i-1] et i>1 faire
V[i] ←V[i-1]
i←i-1
fin tant que
V[i] ←val
fin

Suppression

Val = 2

4 7 1 2 5 8
V:

Pour supprimer un élément dans un vecteur:

 On recherche si cet élément existe dans le vecteur.

 Si l'élément à supprimer existe on le supprime alors en effectuant un décalage à
gauche de tous les éléments situés à sa droite.
 On diminue la taille du vecteur.

La procédure correspondante est:

procédure: supprime(V: vecteur, n, val: entier)

var i: entier
debut
i←1
tant que i<=n et val≠V[i] faire
i←i+1
fin tant que
si val=V[i] alors
tant que i<n faire
V[i] ←V[i+1]
i←i+1
fin tant que
n←b-1
fin si
fin

Modification d'un élément du vecteur

Premier cas: vecteur non trié

val=7 par Nval=6

4 7 1 5 8
V:

Pour modifier une valeur dans un vecteur non trié:

 On recherche si cette valeur existe dans le vecteur.

 Dans le cas où elle existe on la remplace par la nouvelle valeur

Ecrivons la procédure correspondante

Procédure: modifier_nom_trié(V: vecteur, n, val, Nval: entier)

var i: entier
debut
i←-1
tant que i<=n et val#V[i] faire
i←i+1
fin tant que
si val=V[i] alors
V[i] ←Nval
fin si
fin

Deuxième cas: Vecteur trié

val=7 par Nval=9

4 5 7 8 10 14
V:
Principe 1:

Pour modifier une valeur dans un vecteur trié:

 On recherche si cette valeur existe dans le vecteur.

 Dans le cas où elle existe on la supprime en effectuant un décalage vers la gauche de
tous les éléments situés à droite.
 On recherche la position d'insertion de la nouvelle valeur en effectuant un décalage à
droite.
 Lorsque la position d'insertion est retrouvée, on insère la nouvelle valeur dans la case
correspondante.

Principe 2:

Pour modifier une valeur dans un vecteur trié:

 On recherche si cette valeur existe dans le vecteur.

 Dans le cas où cette valeur existe. On vérifie si cette valeur est plus petite que la
nouvelle valeur. Si c'est le cas on effectue un décalage à gauche de toute les éléments
situés à sa droite à la recherche de la position d'insertion de "Nval". Dans le cas
contraire on effectue un décalage à droite de tous les éléments situés à sa gauche à la
recherche de la position d'insertion de "Nval".
 Lorsque cette position est retrouvée, on insère la nouvelle valeur dans la case
correspondante.

procédure: ajout_trié_1(V: vecteur, n, Nval, val: entier)

var i: entier
debut
i←1
tant que i<=n et val≠V[i] faire
i←i+1
fin tant que
si val=V[i] alors
tant que i<n faire V[1] ←V[i+1]
i←i+1
fin tant que
fin si
tant que Nval<=V[i-1] et i>1 faire
V[1] ←V[i-1]
i←i-1
fin tant que
V[i] ←Nval
fin

Procédure: ajout_trié_2(V: vecteur, n, val, Nval: entier)

var i: entier
debut
i←1
tant que i<=n et val≠V[i] faire
i←i+1
fin tant que
si val=V[i] alors
si val<V[i] alors
tant que i<n et Nval>=V[i+1] faire
V[i] ←V[i+1]
i←i+1
fin tant que
sinon
tant que i>1 et Nval<=V[i-1] faire
V[i] ←V[i-1]
i←i-1
fn tant que
fin si
V[i] ←Nval
fin si
fin

Les chaînes de caractères

Une chaîne de caractères est un ensemble de caractères portant le même nom de variable.
Chaque caractère est repéré par son rang dans la chaîne.
Une chaîne de caractères correspond alors à un vecteur donc les éléments sont les caractères.

Déclaration

const max=20
type chaîne = tableau[1..max] de caractères
var ch: chaîne

ou alors

var ch: chaîne.

Remarque:

 Le premier élément d'une chaîne de caractère commence toujours au rang "1".

Exemple:
ch←'ESSO'
ch[1]='E'
  Généralement la longueur d'une chaîne de caractère ne dépasse pas 255 caractères.
 Une chaîne de caractère se manipule exactement comme un vecteur de caractère à
l'exception de la lecture, l'écriture et de l'affectation

Exemple

var c: tableau[1..20] de caractère

ch1, ch: chaîne

 Lecture des caractères:

pour i=1 à 20 faire
lire(C[i])
fin pour
 Lecture de chaîne:
lire(ch)
 Ecriture des caractères:
pour i=1 à 20 faire
écrire(C[i])
fin pour
 Ecriture des chaînes
écrire(ch)
 Affectation des caractères:
pour i=1 à 20 faire
A[i] ←C[i]
fin pour
 Affectation des chaînes:
ch1←ch

Avec les objets de types chaîne de caractère on peut effectuer les opérations suivantes:

 Calculer la longueur de la chaîne de caractères on utilise la fonction lon(ch)

 On peut effectuer la concaténation de deux chaînes de caractères.
Exemple:
ch1←'je suis'
long(ch1)=7
ch2←'je pense, donc je suis.'
long(ch2)=23

Exercice

Gestion des congressistes

Les congressistes et les sessions sont stockés dans le vecteur. Les informations sur un hôtel
sont:

 Le nom de l'hôtel
  Localité
 Numéro de téléphone
 Prix de l'hôtel

Les informations sur une session sont:

 Numéro de la session
 Désignation
 Le nombre de place max
 Le nombre d'inscrit
 La durée de la session (jour, mois, année)
 Heure de debut de session.

Les informations sur un congressiste sont:

 Le nom
 L'adresse: le numéro de téléphone
 L'accompagnateur
 L'hébergement: la liste des sessions auquel il est inscrit.

Le champ accompagnateur est un entier qui vaut "1" si le congressiste est accompagné "0"
sinon.
Le champ hébergement est de type hôtel
Le champ liste des sessions est un tableau de session sachant que chaque congressiste ne peut
participer qu'à 10 sessions au maximum.
Le nombre de congressiste est de 100 avec un total de 20 sessions.

Questions:

1.
o Définit la structure de données correspondant à la liste des sessions.
o Définir la structure de donnée correspondante à un hôtel
o Définir la structure de donnée correspondante à un hôtel.
o Définir la structure de données correspondante à la liste des congressistes.
2. Ecrire une procédure qui permet de créer la liste des sessions.
3. Ecrire une fonction qui prend en paramètre la liste des congressistes et qui compte le
nombre de congressiste accompagné sachant qu'on a enregistré que 80 congressistes.
4. Ecrire une procédure qui affiche la liste des sessions qui se sont déroulée le
11/06/2009
5. Ecrire une procédure qui affichage la liste des congressistes inscrits dans la session
"base de données repartie"
6. Ecrire une fonction qui compte le nombre de congressistes affectés à " Prestige hôtel".
7. Ecrire une procédure qui recherche et affiche la session qui a le plus grand nombre
d'inscrit et celle qui a le plus petit nombre d'inscrit

Quelques algorithmes de base

Algorithme


 

Exemple d'algorithme

Algorithme 1

Ecrire un algorithme qui permet de lire un entier "n" strictement positif et qui calcule la
somme des "n" premier nombres positifs.

1) Algorithme

1a: somme
var N: entier
S: réel
debut
répéter
lire(N)
jusqu'à N>0
S←N*(N+1)/2
écrire('la somme de ',n,'premiers termes est: ,'S)
fin
Ici on a 3 opérations fixes

2) Algorithme

1b: somme
var n, i, S: entier
debut
écrire('Entrez un entier positif')
lire(x)
tant que n<=0 faire
écrire('Veuillez ressaisir votre nombre')
lire(x)
fin tant que
S←0
pour i=1 à n faire
S←i+S
fin pour
écrire('la somme des,'n', premier nombres positifs est ,'S)
fin
Ici on a n opération qui vont varier en fonction de n

Algorithme 2
Ecrire un algorithme qui permet de lire un entier "n" strictement positif et qui affiche tous les
multiples de 3 inférieurs ou égaux à "n"

1) Algorithme 2a: multiple 3

var i, n: entier
debut
répéter
lire(n)
jusqu'à n>0
pour i=1 à n faire
si imod(3)=0 alors
écrire(i)
fin si
fin tant que
fin

2) Algorithme 2b: multiple 3

var i, n: entier
debut

répéter
lire(n)
jusqu'à n>=0
i←1
tant que i<=n faire
si imod3=0 alors
écrire(i)
fin si
i←i+1
fin tant que
fin

Efficacité et complexité d'un algorithme

Dans l'algorithme 1a, on a fait n additions.

Dans l'algorithme 1b, on a fait 3 opérations (une addition, une multiplication et une division)
Dans l'algorithme 2a, on a fait 2n+3 comparaisons, et n+1 opérations.
Des algorithmes produisant les mêmes résultats peuvent être très différent du point de vu des
principes utilisés et du point de vu principes utilisés et du temps nécessaire pour obtenir les
résultats.
On dit qu'un algorithme a, est plus efficace qu'un algorithme b si l'algorithme a fait bon usage
des ressources de temps de traitement et mémoire par rapport à b. La mesure de l'efficacité
d'un algorithme s'effectue en utilisant les notions de complexité théorique.

La complexité pratique (Tn)

C'est la mesure précise du temps et de la taille mémoire nécessaire à l'exécution d'un
algorithme. Tn: Temps d'exécution

Complexité théorique

C'est un ordre de grandeur des coûts théoriques indépendants des conditions pratiques
l'exécution (c'est une généralisation de la complexité pratique).

Exercice 2:

Calculer la complexité théorique de l'algorithme qui effectue la multiplication de deux

matrices.
Pour des données de même taille le temps d'exécution peut être fonction de la valeur des
données dans ce cas on définit deux types de complexité:

 La complexité max: Elle s'obtient avec les données les plus défavorables.
 La complexité min: Qui s'obtient avec les données les plus favorables.

La recherche dans un vecteur

Recherche séquentielle linéaire

Il s'agit de rechercher un élément dans un vecteur en effectuant un parcours séquentiel. La

fonction correspondante est la suivante.

fonction recherche_sequentielle(V: vecteur, n, val, pos: entier): booléen

debut
i←2
tant que i<=N et val≠V[1] faire
i←i+1
fin tant que
si val=V[i] alors
recheche-sequentielle ← vraie
pos ← i
sinon
recherche-sequentielle ← faux
fin si
fin

Temps favorable (Tn)

TN=3TC
vals = 7

7 4 2 1 3 5
V:

Temps défavorable (TD)

val = 7

5 4 2 1 3 7
V:
TN = 5Ta+13TC = (n-1)Ta+(2n+1)TC

Recherche séquentielle avec sentinelle

fonction recherche_sequentielle(V: vecteur, N, val, pos: entier): booleen

var i: entier
debut
V[N+1] ← val
i ← i+1
fin tant que
si i<=N alors
recherche_sequentielle ←- vraie
pos ← i
sinon
recherche_sequentielle ← faux
fin si
fin

Recherche dichotomique

La recherche dichotomique suppose que le vecteur dans lequel on recherche une valeur "val"
donnée est triée. Supposons que le vecteur est trié dans l'ordre croissant. Soit "min" et "max"
les valeurs minimales et maximales de l'ensemble des indices du vecteur V. Le principe de la
recherche dichotomique est le suivant:

1. Calculer le milieu
mil = (min+max)/2
2. Si V du milieu = val V[mil]=val alors on arrête la recherche car on a trouvé "val".
3. Si V[mil]>val alors on continue la recherche dans la partie de V donc les indices
varies entre "min" et "mil".
4. Si V[mil]<val alors on continue la recherche dans la partie de V donc les indices
varies entre "mil" et "max"
5. Temps qu'on n'a pas trouvé val reprendre toute ces actions à partir de la première
jusqu'à l'obtention d'un intervalle de recherche de taille "1".
S'il n'y a pas toujours égalité alors la valeur recherchée n'existe pas dans le vecteur.

fonction rech(V: vecteur, n, val, pos: entier): booléen

var, mil, min, max: entier
trouve: booléen
debut
min ← 1
max ← n
trouve ← faux
tant que (min < max) et (non trouve) faire
mil ← (min+max)div2
si val < V[mil] alors
max ← mil
sinon
si val > V[mil] alos
mil ← mil+1
fin si
trouve ← val=V[mil]
fin tant que
rech ← trouve
fin

Les algorithmes simples de tri

Trier un ensemble de n informations consiste à classer ces fonctions selon certains critères
(ordre croissant, ordre décroissant, ordre alphabétique)

Le tri sélection
La procédure correspondante est la suivante

procédure tri_selection(V: vecteur, n: entier)

var i, j, aux, pos: entier
debut
pour i=1 à n-1 faire
pos <-- i
pour j=i+1 à n faire
si V[pos] > V[j] alors
pos ← j
fin si
fin pour
aux ← V[pos]
V[pos] ← V[i]
V[i] ← aux
fin pour
fin

Exercice:

Réécrire cet algorithme en remplaçant la boucle "pour" par la boucle "répéter" et par la boucle
"tant que".

Le tri par insertion

La procédure correspondante est la suivante:

procédure tri_insertion(V: vecteur, n: entier)

var i, j, x: entier
debut
pour i=2 à n faire
j ← i-1
x ← V[i]
tant que V[j]>x et j>0 faire
V[j+1] ← V[j]
j ← j-1
fin tant que
V[j+1] ← x
fin pour
fin

Exercice:

Réécrire cette procédure en remplaçant la boucle "tant que" par la boucle "répéter" et la
boucle "pour" par "tant que".

Le tri par échange ou tri bulle

La procédure correspondante est la suivante:

procédure tri_bulle(V: vecteur, n: entier)

var i, aux: entier
T: booléen
debut
répéter
T ← vraie
pour i=1 à n-1 faire
si V[i]>V[i+1] alors
aux ← V[i]
V[i] ← V[i+1]
V[i+1] ← aux
T ← faux
fin si
fin pour
jusqu'à T {T=vrai}
fin

Exercice:

Réécrire cet algorithme en remplaçant la boucle "répéter" par la boucle "tant que"

Notion d'organigramme

Algorithme


 

Généralités
En général, on peut représenter un algorithme sous forme structurée ou sous forme graphique.
L'organigramme est une représentation graphique d'un algorithme. C'est le plus ancien des
représentations et il constitue un diagramme qui montre le cheminement des données dans un
programme dans un système d'information, ainsi que les opérations pratiquées sur ces
données lors des différentes étapes du traitement.

Représentation d'un organigramme

Les opérations dans un organigramme sont représentées par les symboles dont les formes sont
normalisées. Ces symboles sont reliés entre eux par des lignes fléchées qui indiquent le
chemin. C'est ainsi qu'on a:
Exercices d'application

Exercice 1:

Ecrire un organigramme qui lit un entier N et qui calcule et affiche la somme et la moyenne
de N nombres.
Exercice 2:

Ecrivons un organigramme qui lit deux nombre et affiche le plus grand

Exercice 3:

Ecrire un organigramme qui lit la longueur et la largeur d'un rectangle, calcul et affiche son
périmètre et sa surface.
Exercice 4:

Ecrire un organigramme qui permet de lire le prix hors taxe et la quantité de cet article puis
calcule et affiche le montant de la facture sachant que le taux de la TVA est de 20,6%

Exercice 5:

Ecrire un organigramme qui lit un nombre N non nul et affiche le message: inférieure à "0" ou
supérieur à "0" suivant sa valeur.
Exercice 6:

Ecrire un organigramme qui affiche les 5 premier nombres paires

Récursivité

Algorithme

La récursivité encore appelée récurrence en mathématique permet de réaliser des traitements

répétitifs particulièrement complexes que les structures itératives classiques ne peuvent
aborder facilement. Elle permet de simplifier la structure des programmes. On dit qu'il y'a
récursivité lorsque la définition d'un objet fait apparaître l'objet lui-même.

Quelques exemples d'utilisation de la récursivité

Structure de données récursives

Exemple:

 Les listes.
 Les piles.
 Les files.
 Les arbres.

Le raisonnement récursif

Le raisonnement récursif comporte deux phases bien distinctes:

 Une formulation simpliste ou triviale: qui permet d'arrêter les traitements récursif.
 Une formulation récursive: qui permet de poursuivre le traitement, exemple: tant que
la condition est vraie on exécute l'action.

Récursivité indirecte

Encore appelée récursivité cachée ou croisée, la récursivité indirecte a lieu lorsqu'une

procédure appelle une seconde procédure qui à son tour appelle la première.
Exemples:
f(n) = g(n-1)
g(n) = f(n-1)

La récursivité directe

Ici la procédure s'appelle elle-même, la condition importante dans l'utilisation de la récursivité

directe est que les objets engendrés par une définition récursive doivent être fini. Ainsi dans
une procédure utilisant la récursivité directe on a deux notions:

 La procédure s'appelle elle-même: on ne commence avec de nouvelle données.

 Il y'a un texte de fin ou une condition d'arrêt: la procédure doit contenir une
construction telle que dans certains cas l'évolution puisse se faire directement sans
appel récursif. Pour cela il est souvent préférable d'indiquer le test de fin des appels
récursifs en début de procédure. On a donc la formulation suivante:
Premier cas:
si condition_fin alors
instruction
sinon
appel récursif
fin si
 Deuxième cas:
tant que non(condition_fin) faire
appel récursif
fin tant que
instruction

Application

Fonction factorielle

La factorielle d'un nombre entier n est le produit des nombres entiers inférieurs ou égaux à ce
nombre n. Cette définition peut se noter de plusieurs façons

1. 0!=1
1!=1
2!=2
3!=3x2x1
N!=N(N-1)x...x2x1
2. N!=1 si N=0
N!=N(N-1)x...x2x1 si N>0
3. N!=1 si N=0
N!=N(N-1)! si N>0

fonction factorielle(N:entier):entier
var p, i: entier
début
si N=0 alors
factorielle ←1
sinon
p←1
pour i=1 à N faire
p ← i*P
fin pour
factorielle ← p
fin si
fin

Autre fonction
fonction factorielle(N: entier): entier
debut
si N=0 alors
factorielle ← 1
sinon
factorielle ← n*factorielle(n-1)
fin si
fin
Exécution
F0 F1 F2 F3 F4
3*fact(2
N=3 2*fact(1) 1*fact(0)
) 1
fact(3) fact(1) fact(0)
fact(2)
Fonction de Fibonacci

f0 ; f1=1
fn=fn-2+fn-1 si n>1
f(n)=n si n<=1
f(n)=f(n-2)+f(n-1) si n>1

Correction:

fonction fibonacci(n:entier):entier
début
si n<=1 alors
fibonacci ← n
sinon← fibonacci(n-1)+fibonacci(n-2)
fin si
fin

Les enregistrements

Algorithme

Le type tableau nous a permis de définir une structure composée de plusieurs éléments, cette
structure nous permettrait de réunir les éléments de même type. Mais si nous voulons
regrouper les informations n'ayant pas nécessairement le même type au sein d'une même
structure, par exemple: les informations concernant un étudiant. Une nouvelle structure
appelée enregistrement est plus adaptée pour représenter ce type d'information.

Un enregistrement est un objet composé statique et hétérogène c'est-à-dire qui renferme

plusieurs informations qui peuvent être de type différent.
Un enregistrement est défini par un ensemble de données ou élément encore appelé champ.
Les champs sont les données élémentaires ou composées et peuvent être de type différent.

Déclaration
type nom=enregistrement
champ1 : type1
champ2 : type2
........
champn : type;
fin enregistrement

Exemple:
Déclarons un type étudiant
Application:
Type Etudiant=enregistrement
machine : chaîne
nom : chaîne
prénom : chaîne
sexe : caractère
age : entier
note : réel
fin enregistrement

Utilisation

En général on manipule un enregistrement champ par champ. On accède à un champ de

l'enregistrement en indiquant le nom de l'enregistrement suivi du nom du champ. Les deux
sont séparés par un point.
Exemple:
Etudiant.matricule
Etudiant.nom
Si un champ de l'enregistrement est d'un type donné alors on peut réaliser sur ce champ toutes
les opérations réalisables avec les objets de ce type.
Exemple d'application de valeur
Etudiant.matricule ← '05S001'
Etudiant.nom ← 'toto'
Etudiant.prénom ← 'Paul'
Etudiant.sexe ← 'M'
Etudiant.age ← 19
Etudiant.note ← 12.75

ou bien par lecture

lire(Etudiant.matricule)
lire(Etudiant.nom)

Application aux vecteurs

Nous voulons constituer une base de données des enseignements. Chaque enseignement est
caractérisé par:

 Le code.
 Le nom.
 Le prénom.
 Le grade.
 Le sexe.

Les enseignants seront stockés dans un vecteur

1. Donner une déclaration du type enseignant.

2. Ecrire une procédure sui permet de créer un vecteur de n enseignant.
3. Ecrire une procédure qui prend en paramètre le vecteur d'enseignement si cet
enseignement existe ou pas.
4. Ecrire une procédure qui affiche la liste des enseignements féminins

Application

1. Donnons la déclaration du type enseignant

type enseignant=enregistrement
code : chaîne
nom : chaîne
prénom : chaîne
grade : chaîne
sexe : caractère
fin enregistrement
vecteur = tableau[1..100] d'enregistrement
2. Ecrivons une procédure qui permet de créer un vecteur de n enseignement.

procédure: créer_enseignant(v: vecteur, n: entier)

début
pour i=1 à n faire lire(V[i].code)
lire(V[i].nom)
lire(V[i].prénom)
lire(V[i].grade)
lire(V[i].sexe)
fin pour
fin
3. Ecrivons une procédure qui prend en paramètre le vecteur d'enseignement et le
matricule d'un enseignant et qui recherche si cet enseignement existe ou pas.

procédure: recherche(V: vecteur, n: entier, codeE: chaîne)

var i: entier
début
i←1
tant que i<= et codeE≠V[i].code faire
i←i+1
fin tant que
si codeE=V[i].code alors
 écrire('Cet enseignant est dans la case N°: ',i)
sinon
écrire('Cet enseignant n'existe pas')
fin si
fin
4. Ecrivons une procédure qui affiche la liste des enseignant féminins.

procédure affiche_femini(V: vecteur, n:entier)

var i: entier
début
pour i=1 à n faire
si V[i].sexe = 'F' alors
écrire(V[i].code)
écrire(V[i].nom)
écrire(V[i].prénom)
écrire(V[i].grade)
fin si
fin pour
fin

Projets d'étude

Algorithme

Projet 1

Gestion de la CAMMTEL
A la fin du mois, la CAMMTEL distribue les factures de consommation à tous ses clients et
reçoit les cheques correspondants.
La CAMMTEL veut savoir à la fin de chaque mois quelles factures n'ont pas été payées, une
facture est composée par:

 Le code.
 Le nom du client
 L'adresse du client (BP, Ville, Téléphone)
 L'index de but et l'index de fin: pour la consommation
 Le montant
Un chèque est constitué par:

 Le numéro du chèque
 Le numéro du compte client
 Le montant payé
 Le nom du client
 Le code de la facture

Questions:

1. Ecrire une procédure "creer_cheque" qui permet de créer P chèque.

Une procédure "creer_facture" qui permet de créer n facture.
2. Ecrire une fonction qui permet de calculer la consommation mensuelle d'une facture.
3. Ecrire une procédure qui permet de rechercher une facture connaissant son chèque.
4. Ecrire une procédure qui permet d'insérer un nouveau chèque dans le vecteur de
chèque uniquement si la facture correspondante n'a pas encore été payée.
Les chèques sont triés dans l'ordre croissant des codes chèque.
5. Ecrire dans l'ordre alphabétique des noms des clients.
6. Ecrire une procédure qui affiche la liste de tous les clients de la ville d'Ebolowa donc
le montant à payer est supérieur à 3€
7. Ecrire une procédure qui prend les chèques dans l'ordre dont il se présente. Pour
chaque chèque, parcourir la liste des factures pour rechercher la facture
correspondante. Si cette facture est trouvée, enlever chèque et facture de leur vecteur
respectif.
NB: Envisager les deux cas suivants:
o Les chèques et les factures ne sont pas triés.
o Les chèques et les factures sont triés.
8. Ecrire une procédure qui affiche la liste des factures non payées.

Projet 2

Gestion d'un restaurant.

Le responsable du restaurant le "TOMATE" désire gérer chaque jour ses clients. Pour chaque
client on a les informations suivantes:

 Le nom
 Le prénom.
 La catégorie (étudiant, enseignant, travailleur etc.)
 Le menu
 Le montant

Chaque menu est caractérisé par:

 Le nom du menu
 La quantité
 Le prix

Questions:
  Ecrire une procédure "liste_client" qui permet de créer un vecteur de client.
 Ecrire une procédure qui affiche la liste des clients par catégorie avec leur
consommation (menu et le montant)
 Ecrire une facture qui calcule le montant total de consommation par jour.
 Ecrire une procédure qui ajoute un nouveau client dans la liste.
La liste est triée dans l'ordre alphabétique des clients.
 Ecrire une fonction qui affiche le nom du menu le plus sollicité.
 Ecrire une procédure qui affiche le nom du client qui a le plus consommé et le
montant de sa consommation.

Projet 3

Gestion d'une société de location de véhicule.

Dans cette société chaque véhicule est caractérisé par:

 Le numéro d'immatriculation.
 La marque.
 Le type

Immatriculation Type Marque

CE9723K Corola Toyota
LT5486M 12 Renault
Questions:

1. Ecrire une procédure qui permet de créer un vecteur de n voitures.

2. Ecrire une procédure qui permet d'afficher la liste de toutes les voitures de marque
Toyota et immatriculée CE
3. Ecrire une procédure qui permet de modifier le numéro d'immatriculation d'un
véhicule sachant que les véhicules sont triés dans l'ordre alphabétique des numéros
d'immatriculation.
4. Ecrire une procédure qui compte et affiche la liste des voitures immatriculées SU et
ayant pour série B

Projet 4

Gestionnaire d'adresse.
Chaque personne est caractérisée par:

 Son numéro
 Son nom
 Son prénom
 Son numéro de téléphone
 Son sexe

Questions:
 1. Donner la déclaration qui correspond à une personne.
Qui correspond à une liste de personne.
2. Ecrire une procédure qui permet de créer une liste de 50 personnes.
3. Ecrire une fonction qui prend en paramètre une liste de personne et renvoie le nombre
d'homme présent dans la liste.
4. Ecrire une procédure qui affiche la liste des filles abonnées à CAMMTEL (Nom,
numéro de téléphone)
5. Ecrire une procédure qui prend en paramètre une liste de personne et une personne.
Cette procédure permet de rechercher si cette personne existe.
6. On suppose que la liste de personne est triée dans l'ordre alphabétique. Ecrire une
procédure qui permet d'insérer une nouvelle personne dans la liste.
7. Ecrire une procédure qui permet de supprimer une personne donc le numéro de
téléphone est 36309424.

Les fichiers

Algorithme

Jusqu'après les objets utilisé dans nos algorithmes (objet simple tableau) n'ont qu'une durée de
vie brève. Leur existence est limitée à la période d'exécution du programme dont il constitue
l'environnement (parce qu'ils sont situés en mémoire centrale).
Ces informations ne pouvaient provenir que de deux sources:

 Elles étaient inclues dans l'algorithme par le programmeur, exemple: a←1.

 Elle étaient introduites lors de l'exécution par l'utilisateur, exemple lire(a).
 Et pourtant il existe plusieurs applications pour lesquelles les informations traitées
doivent être conservées bien au-delà de la durée d'exécution du programme, exemple:
la gestion du courrier, la gestion du personnel, la gestion des comptes des clients, la
gestion des vols d'une compagnie de voyage.

Le type fichier va nous permettre de manipuler des informations situées sur des supports
externes, exemple: le disque dur, le CD, la disquette.

Définition et déclaration d'un fichier

Un fichier est une collection d'information structuré en unité d'accès
appelée article ou enregistrement qui sont tous de même type.
Un fichier est toujours conservé sur un support externe à la mémoire centrale.
Déclaration du type fichier:
type article=enregistrement
champ1 : type1
champ2 : type2
..............
champn : typen
fin enregistrement
F_article = fichier de article

Exemple:

Type Etudiant = enregistrement

code : chaîne
nom : chaîne
prénom : chaîne
note : réel
fin enregistrement
F_Etudiant = fichier de Etudiant

Opération sur les fichiers

Les opérations avec les objets de type ficher sont:

 La création: Consulter un fichier consiste à épuiser une partie des informations qu'il
contient sans toute fois y apporter des modifications.
 La mise à jour: Elle consiste à modifier le contenu d'un fichier, à ajouter un nouvel
élément dans le fichier, supprimer un élément du fichier.

Lors du traitement d'un fichier l'algorithme doit assurer le contrôle de ce fichier à l'aide d'une
primitive d'ouverture de fichier, soit en lecture, soit en écriture, soit en lecture/écriture.

Ouverture d'un fichier en lecture

Syntaxe:

F: fichier
ouvrirL(F)

Sémantique:
L'exécution de cette instruction permet de lire les enregistrements dans le fichier F.

Ouverture du fichier en écriture

Syntaxe:

OuvrirE(F)

Sémantique:

L'exécution de cette instruction permet d'écrire des enregistrements dans le fichier F.

Ouverture d'un fichier en lecture/écriture

Syntaxe:

Ouvrir(F)

Sémantique:

L'exécution de cette instruction permet une utilisation du fichier en écriture et ou lecture.

Fermeture d'un fichier

A la fin de traitement du fichier l'algorithme doit indiquer qu'il n'a plus besoin du fichier F en
effectuant sa fermeture au moyen d'une primitive donc la syntaxe est:
Fermer(F)
L'exécution de cette instruction complète le fichier par une marque de fin en cas de création
du fichier.

Traitement d'un fichier

Traitement d'un fichier en lecture

F: fichier
val : article
lire(F, val)

Sémantique:
L'exécution de cette instruction permet d'introduire la valeur d'un ensemble de F dans la
variable val.

Traitement d'un fichier en écriture

Syntaxe:

écrire(F, val)

Sémantique:

L'exécution de cette instruction permet d'introduire la valeur de val dans le fichier F.

Traitement de fin de ficher

Syntaxe:

Fin(F)

Sémantique:

Cette instruction est une fonction booléenne qui est fausse quand aucune action de lecture est
exécutée. Elle garde cette valeur tant que les exécutions successives de lire(F, val) rencontrent
les articles F.
Elle prend la valeur vraie dès que l'exécution de lire(F, val) rencontre la marque de fin de
fichier.

Parcours des éléments d'un fichier

Parcourir un fichier consiste à accéder à chaque article ou élément du fichier une et une seule
fois. Les procédures générales de parcours d'un fichier sont:

procédure parcours1(F: fichier)

var val: article
début
ouvrir(F)
lire(F, val)
tant que non(Fin(F)) faire
action1
lire(F, val)
fin tant que
action2
fermeture(F)
fin
procédure parcours2(F: fichier)
var val: article
début
ouvrir(F)
répéter
lire(F, val)
action
jusqu'à fin(F)
fermer(F)
fin

Exemple1:

procédure creer_fichier_Etudiant(F: F_Etudiant)

var val: article
début
ouvrirE(F)
répéter
lire(val.code)
lire(val.nom)
lire(val.prenom)
lire(val.note)
si val.code≠' ' alors
écrire(F, val)
fin s i
jusqu'à val.code=' '
fermer(F)
fin

Exemple2:

Ecrire une fonction qui permet de calculer la taille d'un fichier

fonction taille_Fichier(F: fichier): entier

var val: Etudiant
cp: entier
début
ouvrirL(F)
cp ← 0
lire(F, val)
tant que nonfin(F) faire
cp ← cp+1
lire(F, val)
fin tant que
taille_Fichier ← cp
fermer(F)
fin
Problème: la gestion d'un hôtel

Les informations concernant un hôtel sont:

 Le code
 Le nom
 La ville
 L'adresse qui est un enregistrement composé de:
o La boîte postale
o Le numéro de téléphone
 La disponibilité: qui sera un booléen.

Questions:

1.
o Donnez la déclaration d'un fichier d'hôtel.
o Donnez la déclaration qui permet de créer un fichier d'hôtel.
o Ecrire une procédure qui affiche la liste des hôtels disponibles.
2. Ecrire une procédure qui prend en paramètre le fichier hôtel et renvoie la taille de ce
fichier.
3. On voudrait supprimer un hôtel du fichier:
o Ecrire une procédure qui permet de transférer les éléments du fichier dans le
vecteur hôtel.
o Ecrire une procédure qui prend en paramètre le vecteur hôtel et qui supprime
cet hôtel du vecteur.
Après suppression le vecteur d'hôtel est transféré à nouveau dans le fichier
hôtel

4.
o Ecrire une procédure qui permet d'effectuer ce transfert.
o Ecrire une fonction qui prend en paramètre le fichier d'hôtel et le code d'un
hôtel puis retourne vraie si cet hôtel existe dans le fichier et faux sinon.

Tableau à deux dimensions

Algorithme


Définition et caractéristiques

Une matrice est un ensemble de données de même type logées en mémoire centrale et
référencé par deux indices (les lignes et les colonnes).
Une matrice est caractérisée par:

 Le nom
 Le nombre de colonne
 Le nombre de ligne
 La taille de la matrice (nombre de ligne x nombre de colonnes)
 Le type des éléments de la matrice.

Chaque élément dans une matrice est caractérisé par le numéro de la ligne et le numéro de la
colonne.

Déclaration:

Type nom = tableau[inf1...Sup1, inf2..Sup2] de type élément

Exemple:

type matrice = tableau[1..5, 1..10] de entier

Opération sur les matrices

La lecture (lecture ligne par ligne)

Procédure Lecture(M: matrice, n: entier)

var i, j: entier
début
pour i=1 à n faire
pour j=1 à n faire
lire(M[i, j])
fin pour
fin pour
fin

Pour lire colonne par colonne, on inverse juste i et j

L'écriture

procédure écriture(M: matrice, n: entier)

var i, j: entier
début
pour i=1 à n faire
pour j=1 à n faire
écrire(M[i,j])
fin pour
fin pour
fin

Applications

La trace d'une matrice

C'est la somme des éléments de la diagonale

La diagonale

L'indice de la colonne est égal à l'indice de la ligne.

La matrice identité

La matrice symétrique

La matrice réflexive

Exercices

Exercice 1:

Ecrire une procédure qui recherche le plus grand et le plus élément dans une matrice d'entier.
Exercice 2:

Ecrire une procédure qui prend en paramètre une matrice carrée d'ordre n et qui met à zéro
tous les éléments de la diagonale et ceux de l'anti-diagonale.

Exercice 3:

Ecrire une fonction qui prend en paramètre une matrice carrée d'entier d'ordre n et qui renvoie
le nombre d'entier pair.

Exercice 4:

Ecrire une procédure qui prend en paramètre une matrice de caractère et qui compte le
nombre de fois qu'apparaît le caractère "A" et le nombre de fois qu'apparaît le caractère "B".

Exercice 5:

 Ecrire une procédure qui permet de transférer les éléments d'une matrice carrée d'ordre
n dans un vecteur d'entier.
 Donnez en fonction de n, i et j une formule permettant d'identifier un élément de la
matrice dans le vecteur.

Exercice 6:

Ecrire une procédure qui permet de rechercher un élément dans une matrice.

Exercice 7:

Ecrire une fonction qui prend en paramètre une matrice carrée d'ordre n et qui calcule la trace
de cette matrice.

Exercice 8:

Ecrire une procédure pour vérifier les critères suivants:

 Matrice identité.
 Matrice symétrique.

Exercice 9:

Ecrire une procédure:

 Pour calculer la somme de deux matrices.

 Le produit de deux matrices.

Exercice 10:

Ecrire une fonction qui vérifie si une matrice est triangulaire supérieure.