Algorithmique II

Pr. Mohammed EL AMRANI

[email protected]

S2 : Informatique appliquée
Faculté des Sciences de Rabat
 Contenu
01 02 03
Rappel Récursivité Structures
Notion de base en Fonctions et procédures Gestion des enregstrements
Algorithmique récursives et de fichiers

04 05 06
Tri & Recherche Complexité Conclusion
Tri et recherche dans les Classes et calcul de la Exemples classiques
tableaux complexité algorithmique
01
Notion de base en Algorithmique
(Rappel)
 CONCEPTS IMPORTANTS EN INFORMATIQUE

Algorithme : mot dérivé du nom du mathématicien al_Khwarizmi qui a vécu au

9ème siècle, était membre d’un académie des sciences à Bagdad .

Un algorithme prend des données en entrée, exprime un traitement particulier et

fournit des données en sortie.

Programme: série d’instructions pouvant s’exécuter en séquence, ou en parallèle

(parallélisme matériel) qui réalise (implémente) un algorithme
 ALGORITHME

• Savoir expliquer comment faire un travail sans la moindre ambiguïté avec un

langage simple (instructions élémentaires).

• Suite finie d'actions à entreprendre en respectant une chronologie imposée.

• L’écriture algorithmique : un travail de programmation à visée universelle.

• Un algorithme ne dépend pas du langage dans lequel il est implanté, ni de la

machine qui exécutera le programme correspondant.
 RÉSOLUTION DE PROBLÈMES

Lire l’énoncé du problème, être certain de bien le comprendre

◼ utiliser une loupe
◼ ressortir les informations pertinentes
◼ données ? résultats ?

Réfléchir à la résolution du problème en ignorant l’existence de

l’ordinateur
◼ déterminer les points principaux à traiter
◼ exploiter l’ensemble de vos connaissances
◼ adapter ou réutiliser des recettes existantes
◼ encore difficile ?
Décomposer le problème!! Analyse descendante!!
 RÉSOLUTION DE PROBLÈMES

Écrire formellement la solution (algorithme) sur papier

◼ utiliser un pseudo langage

Vérifier votre solution sur un exemple

◼ preuve formelle de l ’algorithme : encore mieux !!

Traduire dans un langage de programmation

Tester le programme sur différents jeux de tests

◼ le jeux de tests doit être « suffisant »
◼ ne pas oublier les cas particuliers, …
 EXEMPLE D’ÉNONCÉ D’UN PROBLÈME

Exemple 1 : Un algorithme de résolution de l'équation ax+b = 0

Données : a et b entiers
Algorithme :
afficher(‘ résolution de l ’équation : ax+b=0 ’)
saisir(a), saisir(b)
Si a est non nul,
alors on obtient la solution : x = -b/a
sinon si b est non nul,
alors l'équation est insoluble
sinon tout réel est solution
Résultat : la solution de l ’équation ax+b=0; si elle existe
 DÉCLARATION DES DONNÉES

Variable <nom de donnée>: <type>

• Instruction permettant de réserver de l’espace mémoire pour stocker des données.

• Dépendant du type des données : entiers, réels, caractères, etc.)

• Exemples :
Variables
nombre : entier
nom, prénom : chaîne de caractères
 DÉCLARATION DES DONNÉES

Constante <nom de donnée>: <type> ← <valeur ou expression>

• Instruction permettant de réserver de l’espace mémoire pour stocker une
constante dont la valeur ne varie pas.

• Exemples :
Constantes
MAX : entier ← 10
DEUX_MAX : entier ← MAX*2
 LECTURE ÉCRITURE DE DONNÉES

• écrire("Texte à afficher ou bien nom de variable")

• lire(nom_variable)
Fonction ou Instruction permettant
• de visualiser des données placées en mémoire. (écrire)
• de placer en mémoire les informations fournies par l'utilisateur. (lire)
• Exemples:
écrire ("C’est quoi ton nom ? ")
lire (nom)
écrire ("Bonjour monsieur ", nom)
 EXEMPLE D’ALGORITHME

Exemple 2 :

▪ On souhaite calculer et écrire, à partir d’un motant hors taxe saisi,

la TVA ainsi que le prix TTC
▪ Le montant TTC dépend de :
• du prix HT
• du taux de TVA de 20%
 EXEMPLE D’ALGORITHME

Algorithme CalculTVA
{ Saisit un prix HT et affiche le prix TTC correspondant }
Constantes
TVA : réel ← 20/100
TITRE : chaîne ← "Résultat"
Variables
prixHT, prixTTC: réel

début
écrire ("Donnez-moi le prix hors taxe : ")
lire (prixHT)
prixTTC ← prixHT * (1+TVA) { calcul du prix TTC }
écrire (TITRE) {présentation du résultat}
écrire (prixHT, " dh H.T. + TVA ", TVA, " devient ", prixTTC, " dh T.T.C. ")
fin
 STRUCTURE ALTERNATIVE
«SI … ALORS … SINON … FSI»
Exemple 3 :

Algorithme SimpleOuDouble
{ Cet algorithme saisit une valeur entière et affiche son double si cette donnée est inférieure à un seuil donné }
Constante
SEUIL : entier ←10
Variable
val : entier
Début
écrire("Donnez-moi un entier : ") { saisie de la valeur entière }
lire(val)
si val < SEUIL alors { comparaison avec le seuil }
écrire ("Voici son double :" , val ×2)
sinon
écrire ("Voici la valeur inchangée :" , val)
fsi
Fin
 STRUCTURE ALTERNATIVE
«SI … ALORS … SINON SI … ALORS … SINON … FSI»

Algorithme equation1degre { Un algorithme de résolution de l'équation ax+b = 0 }

Variables
a, b: réel
Début { Préparation du traitement }
écrire ("Un algorithme de résolution de l'équation ax+b = 0 ")
lire (a), lire (b) Condition imbriquée
si a <> 0 alors si a <> 0 alors
écrire ("La solution est x = ", -b/a) { x = -b/a } écrire ("La solution est x = ", -b/a) { x = -b/a }
sinon
sinon si b <> 0 alors
si b <> 0 alors
écrire ("L'équation est insoluble") écrire ("L'équation est insoluble")
sinon sinon
écrire ("Tout réel est solution") écrire ("Tout réel est solution")
fsi fsi
Fin fsi
 SELECTION de CHOIX MULTIPLES «SELON»

selon <identificateur>
valeur1 : instructions1 {si identificateur = valeur1, on exécute instructions1}
valeur2 : instructions2 {si identificateur = valeur2, on exécute instructions1}
…
[autres: instructions0] {sinon, on exécute instructions0}

Remarque
• S’il y a plus de deux choix possibles, l’instruction selon permet une facilité d’écriture
 SELECTION de CHOIX MULTIPLES «SELON»
Exemple:

selon abréviation
"M" : écrire( " Monsieur " )
"Mme" : écrire( " Madame " )
"Mlle" : écrire( " Mademoiselle " )
autres : écrire( " Monsieur, Madame " )

Équivalent avec instruction Conditionnelle

si abréviation = "M" alors écrire( "Monsieur" )
sinon si abréviation = "Mlle" alors écrire("Mademoiselle")
sinon si abréviation = "Mme" alors écrire( "Madame" )
sinon écrire( "Monsieur, Madame" )
fsi
 RÉPÉTITION D’UN TRAITEMENT
BOUCLE «POUR»

Algorithme FaitLeTotal { Cet algorithme fait la somme de N nombres réels}

Variables
N, cpt : entiers
valeur, totalValeurs: réels
début
écrire("Combien de valeurs voulez-vous saisir ?")
lire(N)
totalValeurs ← 0 { initialisation du total à 0 avant cumul }
Pour cpt ←1 à N faire { traitement qui se répète N fois }
écrire("Donnez une valeur :")
lire(valeur)
totalValeurs ← totalValeurs + valeur { cumul }
fpour
écrire("Le total des ", N, "valeurs est " , totalValeurs)
fin
 RÉPÉTITION D’UN TRAITEMENT
BOUCLE «POUR»
Valeur Valeur
Initiale Finale

Pour <var> ← valInit à valfin [par <pas>] faire

traitement {suite d’instructions}
fpour Valeur à ajouter à <var> à
chaque passage dans la
boucle

Objectif:
Répéter une suite d’instructions un certain nombre de fois
La boucle « pour » est utilisée quand le nombre d’itération est connu.
 RÉPÉTITION D’UN TRAITEMENT
BOUCLE «POUR»
L’instruction Pour:
• initialise une variable de boucle (le compteur)
• incrémente cette variable de la valeur de «pas»
• vérifie que cette variable ne dépasse pas la borne supérieure

Attention:
le traitement ne doit pas modifier la variable de boucle

Pour cpt ← 1 à MAX faire

si (…) alors cpt ← MAX
fpour
 RÉPÉTITION D’UN TRAITEMENT
BOUCLE «Tant que … faire»

Algorithme FaitLeTotal
{ Cet algorithme fait la somme de N données saisies au clavier, s’arrêt quand -1 est saisi}
Constante
STOP : entier ← -1
Variables
val, totalValeurs: entier
Début
totalValeurs ← 0
écrire("Donnez une valeur, ou ", STOP, " pour finir.")
lire(val) {Amorçage}
Tant que val <> STOP faire
totalValeurs ← totalValeurs + val
écrire("Donnez une autre valeur, ou ", STOP, " pour finir.")
lire(val)
ftq
écrire("La somme des valeurs saisies est ", totalValeurs)
Fin
 RÉPÉTITION D’UN TRAITEMENT
BOUCLE «Tant que … faire»
initialisation de la
variable de condition

<amorçage>
Tant que <expression logique (vraie)> faire suite d’instructions à
traitement exécuter si la condition
est vraie
relance
ftq
réaffectation de la variable
de condition

Objectif:
• Répéter une suite d’instructions un certain nombre de fois
• La boucle « tant que » est utilisée quand le nombre
d’itération n’est pas connu.
 COMPARAISON
BOUCLES «POUR» ET «TANT QUE»

Pour cpt ←1 à nbVal par 1 faire cpt ← 1

Tant que cpt <= nbVal faire
écrire("Donnez une valeur :") écrire("Donnez une valeur :")
lire(valeur) lire(valeur)
é𝒒𝒖𝒊𝒗𝒂𝒍𝒆𝒏𝒄𝒆 { cumul }
{cumul}
totalValeurs←totalValeurs+ valeur
totalValeurs←totalValeurs+ valeur cpt ← cpt + 1
fpour ftq

Boucle Pour Boucle Tant que

Nombre d’itération connu à l’avance Boucle s’arrête sur événement particulier
• Parcours de tableaux • Itération avec arrêt décidé par saisie
• Test sur un nombre donné de utilisateur
valeurs
 RÉPÉTITION D’UN TRAITEMENT
BOUCLE «RÉPÉTER … JUSQU’À»

Algorithme Essai
{Cet algorithme a besoin d’une valeur positive paire}
Variables
valeur : entier
Début
Répéter
écrire("Donnez une valeur positive non nulle : ")
lire(valeur)
jusqu’à valeur <= 0
écrire("La valeur positive non nulle que vous avez saisie est ")
écrire( valeur )
Fin
 RÉPÉTITION D’UN TRAITEMENT
BOUCLE «RÉPÉTER … JUSQU’À»

Remarques :
La structure Répéter permet de répéter un traitement 1 ou plusieurs fois.
Pour choisir entre Répéter et Tant que il faut se poser la question :
faut-il éventuellement ne jamais faire le traitement ?
Si oui : utiliser Tant que,
sinon utiliser la structure Répéter qui exécute au moins une fois l'action.
NB: Attention, en C :
La structure est do...while : c'est à dire Faire...Tant que.
Alors que la structure algorithmique est Répéter...jusqu'à.
C'est à dire qu'en C on exécute l'action tant qu'une condition est vraie alors qu'en
algorithme on exécute une action tant que la condition est fausse, c'est à dire jusqu'à
ce que la condition inverse soit vraie.
 COMPARAISON
« TANT QUE » vs «RÉPÉTER … TANT QUE»

« Tant que » « Répéter … jusqu’à »