Algorithmique Mme Khadija BOUZAACHANE Année universitaire : 2009-2010

AlgorithmiqueAlgorithmique

Mme Khadija BOUZAACHANE

Année universitaire : 2009-2010

INTRODUCTIONINTRODUCTION

11/04/23 2

IntroductionIntroduction Avez vous déjà déchiffré un mode d’emploi

pour faire fonctionner un DVD, ou bien la télévision ou un répondeur téléphonique? Si oui, sans le savoir, vous avez déjà exécuté des algorithmes.

Avez-vous déjà indiqué un chemin à un touriste égaré ?

Un algorithme, c’est une suite d’instructions, qui une fois exécutée correctement, conduit à un résultat donné. Si l’algorithme est juste, le résultat est le résultat voulu, et le touriste se retrouve là où il voulait aller

11/04/23 3

IntroductionIntroductionQu’est-ce qu’un algorithme?

◦ Est une suite d’instructions écrite en langage d’algorithme qui résout un problème et qui peuvent être programmé par n’importe quel langage.

Une suite d'instructions serait :1.Se lever2.Prendre sa douche3.Prendre le petit déjeuner4.S'habiller

11/04/23 4

IntroductionIntroduction

Un algorithme doit donc contenir uniquement des instructions compréhensibles par celui qui devra l’exécuter.

11/04/23 5

DéfinitionDéfinition

Algorithmique: ◦Définition1: désigne l'ensemble des

règles et des techniques qui sont impliquées dans la définition et la conception des algorithmes.

◦Définition2: l'algorithmique c'est de savoir comment lire, écrire, évaluer et optimiser des algorithmes.

11/04/23 6

DéfinitionDéfinition

Algorithme: ◦Définition1: Un algorithme décrit une

méthode de résolution de problème programmable sur machine.

◦Définition2 : Un algorithme est un ensemble d'opérations de calcul élémentaires, organisé selon des règles précises dans le but de résoudre un problème donné. Pour chaque donnée du problème, l'algorithme retourne une réponse après un nombre fini d'opérations(+, -,/,<,>,... ).

11/04/23 7

DéfinitionDéfinitionQu’est-ce qu’un programme?

◦ Un programme est donc une suite d'instructions exécutées par la machine. La machine a son propre langage appelé langage machine.

◦ Un programme est l’expression d’un algorithme par une machine donnée dans un langage de programmation donné en utilisant le répertoire d’actions(opérations, instructions) et les règles de composition propres à cette machine et à ce langage donnés.

◦ Un programme est un assemblage et un enchaînement d’instructions élémentaires écrit dans un langage de programmation, et exécuté par un ordinateur afin de traiter les données d’un problème et renvoyer un ou plusieurs résultats.

11/04/23 8

MéthodologieMéthodologiePour résoudre un problème, il est vivement

conseillé de réfléchir d'abord à l'algorithme avant de programmer.

Exemple de construction d’algorithme: ◦ Exemple: calcul des racines de l’équation du second ordre

ax2+bx+c=0◦ 1ère version:

Lire a, b, c Calculer les racines de l’équation Imprimer les racines

11/04/23 9

MéthodologieMéthodologie

La résolution d’un problème est caractérisé par 4 étapes :◦Comprendre la nature du problème posé◦Préciser les données fournies (Entrées)◦Préciser les résultats que l’on désire

obtenir (Sorties)◦Déterminer le processus de

transformation des données en résultats.

11/04/23 10


Comment on programme?

11/04/23 11

On utilise un pseudo-langage, comportant toutes les structures de base d'un langage de

programmation

On traduit notre "pseudo" en langage évoluéen fonction des possibilités de ce langage

Ce langage sera ensuite traduit en langage machine


Un programme est donc une suite d'instructions exécutées par la machine. Ces instructions peuvent:◦soit s'enchaîner les unes après les autres, on

parle alors de séquence d'instructions;◦ou bien s'exécuter dans certains cas et pas

dans d'autres, on parle alors de structure alternative;

◦ou se répéter plusieurs fois, on parle alors de structure répétitive.

11/04/23 12

La séquence La séquence d’instructionsd’instructions

Une instruction est une action que l'ordinateur est capable d'exécuter.

Une séquence d'instruction serait :◦Se lever◦Prendre sa douche◦Prendre le petit déjeuner◦S'habiller

11/04/23 13

Structures AlternativesStructures Alternatives

Une alternative s'exprime par si … Sinon…◦Si fin de semaine ou congé

Mettre sa tenue de sport Faire son jogging

◦Sinon Mettre sa tenue de travail Aller travailler

◦Fin Si

11/04/23 14

Structure répétitiveStructure répétitiveLa routine journalière d’un employé est :

◦Ouvrir guichet◦Appeler premier client◦TantQue " client dans file d'attente " et

" pas fin de journée " Traiter client Appeler client suivant

◦FinTantQueLes deux actions "Traiter client" et

"Appeler client suivant" vont se répéter tant que la condition située derrière l'instruction "Tant que" est vérifiée.

11/04/23 15

Pourquoi faire des Pourquoi faire des algorithmesalgorithmes

la rédaction des algorithmes permet plusieurs choses :◦d'être compréhensible par tout

informaticien même s'il ne connait pas le langage du programme

◦de vérifier la complexité du programme et donc de l'optimiser

◦de faire ressortir de manière compréhensible les cas d'utilisations

11/04/23 16

NOTIONS DE BASENOTIONS DE BASE

Comment faire des algorithmes?Les variablesLe type de la variableLes instructionsSyntaxe général de l’algorithmeLes structures de contrôleStructure répétitiveLes tableauxOrganigrammeProcédures & FonctionsRécursivité

11/04/23 17

Comment faire des Comment faire des algorithmesalgorithmes

les algorithmes sont rédigés dans un langage à mi-chemin entre le français et les langages de programmation, dit pseudo-code .

En programmation, le pseudo-code est une façon de décrire un algorithme sans référence à un langage de programmation particulier. L'écriture en pseudo-code permet souvent de bien prendre toute la mesure de la difficulté de l'implémentation de l'algorithme, et de développer une démarche structurée dans la construction de celui-ci.

11/04/23 18

Comment faire des Comment faire des algorithmes(suite)algorithmes(suite)

La raison d’être d’un algorithme est de résoudre un problème. La plus grande attention doit être portée à la compréhension du problème, faute de quoi l’algorithme n’a aucune chance d’être correct. Le langage utilisé pour la définition d’un problème est un langage scientifique utilisant pour des raisons de simplicité une langue naturelle(français par exemple).

11/04/23 19

Les variablesLes variablesUne variable est un objet dont la valeur n’est pas invariableUne variable peut être représentée par une case mémoire, qui contient la valeur d'une donnée.Chaque variable possède un nom unique appelé identificateur par lequel on peut accéder à son contenu.

◦Par exemple, on peut avoir en mémoire une variable prix et une variable quantité.

11/04/23 20

Les variables(suite)Les variables(suite)Une variable possède 3 attributs :

◦Une valeur◦Un nom(invariable) qui sert à la désigner◦Un type(invariable) qui décrit l’utilisation

possible de la variableUne valeurUne valeur

◦la valeur d'une variable(contenu) peut varier au cours du programme. L'ancienne valeur est tout simplement écrasée et remplacée par la nouvelle.

◦La valeur peut être de différents types et de tailles différentes.

11/04/23 21

Les variables(suite)Les variables(suite)Nom de la variableNom de la variable

◦C’est une suite de lettres et de chiffres commençant nécessairement par une lettre

◦Le nombre maximal de caractères imposé varie selon les langages

◦La lisibilité des programmes dépend de l’habilité à choisir des noms représentatifs

◦Le nom de la variable doit être le plus représentatif possible du contenu de celle-ci pour faciliter la lecture de l'algorithme. En revanche, il ne doit pas non plus être trop long pour ne pas nuire à la lisibilité de l'ensemble.

11/04/23 22

Les variables(suite)Les variables(suite)Nom de la variableNom de la variable

◦Exemple Je veux mémoriser l'âge d'une personne dans une

variable, j'ai le choix de l'appeler : a âge age ageDeLaPersonneDontJeSuisEntrainDeParler

◦ Remarque : Le premier cas est trop court, si je n'ai pas lu la

description plus haut, je suis totalement perdu. Le deuxième cas ne convient pas non plus car on évitera tout caractère accentué dans les noms de variable. Le dernier cas est certes très précis, mais tellement long qu'il en devient illisible. Bref, le troisième cas semble le plus approprié

11/04/23 23

Les variables(suite)Les variables(suite)Type de la variableType de la variable

◦ Le type de la variable définit : La nature des informations qui seront représentées

dans la variable Les limitations concernant les valeurs à représenter Les opérations réalisables avec les variables

correspondantes.

◦Propriété : Une variable doit être déclaré avant son utilisation

11/04/23 24

Les variables(suite)Les variables(suite)Type de la variableType de la variable

◦Entier : il s'agit des variables destinées à contenir un nombre entier positif ou négatif.

◦Réel : il s'agit des variables numériques qui ne sont pas des entiers, c'est à dire qui comportent des décimales

◦Caractère : Les variables de type caractère contiennent des caractères alphabétiques ou numériques seul(ex: ‘c’)

◦Booléen : Les variables qui prennent les valeurs (vrai ou faux) ou les valeurs (oui ou non).

11/04/23 25

Les variables(suite)Les variables(suite)

Type de la variableType de la variable◦Chaîne de caractères : représentant

un texte, contenant un ou plusieurs caractères(ex: ’’Bonjour tout le monde’’)

◦ Tous les traducteurs de langages prennent en compte cette notion de type par des instructions de déclaration de type

◦Exemple: Variable Moyenne : réel;(Moyenne en numérique) Variable NbreEtudiant : entier; (NbreEtudiant en

numérique) Variable c1, lettre, z : caractère;

11/04/23 26

Les variables(suite)Les variables(suite)

Type de la variable: ConstanteType de la variable: Constante◦Définitions : une constante est un

objet de valeur invariable. Elle est la réalisation d’une valeur de type particulier.

◦Exemple:Exemple: Constante Zero=0: entier; ( Max:entier)100;

11/04/23 27

Les variables(suite)Les variables(suite)Les opérateurs de l’algorithmique

11/04/23 28

Type Exemple Opération possibles symbole

Réel -15.69, 0.49

AdditionSoustractionMultiplicationDivisionExposantPourcentagecomparaisons

+-*/^%<,<=,>,>=,=,…

Entier -10, 4, 768 AdditionSoustractionMultiplicationDivisionModuloExposantPourcentage

+-*DIVMOD^%

Les variables(suite)Les variables(suite)Les opérateurs de l’algorithmique

11/04/23 29

Type Exemple Opération possibles

symbole

caractère ‘B’, ‘\n’ comparaisons <,<=,>,>=,=,…

Booléen Vrai, Faux ComparaisonNégationConjonctiondisjonction

<,<=,>,>=,=,…NONETOU

Les instructionsLes instructions

11/04/23 30

Les instructions(suite)Les instructions(suite)L’instruction d’affectationL’instruction d’affectation

3. Affecter une formule à une variable X:= X + 2 * Y On charge la variable X par la valeur du

résultat de la formule et on écrase sa valeur initiale

X Y

11/04/23 31

3

11

4

Les instructions(suite)Les instructions(suite)Les instructions d’Entrée/SortieLes instructions d’Entrée/Sortie

◦ Un programme est amené à : Prendre des données par le périphérique(clavier) : rôle de

l’instruction de lecture Communiquer des résultats par l’intermédiaire du

périphérique(écran) : rôle de l’instruction de l’écriture

◦ Instruction de lecture Rôle : fournir des données au programme SyntaxeSyntaxe : Lire(variable) ExempleExemple : Lire( X) on saisie une valeur pour la stocker

après dans la variable X

◦ Instruction d’écriture Rôle : fournir des résultats directement compréhensibles SyntaxeSyntaxe : Ecrire( variable), Ecrire(’’chaine de caractères’’) ExempleExemple : Ecrire(X), Ecrire(’’Bonjour’’)

11/04/23 32

Syntaxe général de Syntaxe général de l’algorithmel’algorithme

Le moule d’un algorithmeLe moule d’un algorithme◦Un algorithme comportera :

Une partie déclaration Une partie encadrée par ’’début’’ ’’ fin’’ où

sont décrites les actions

Algorithme Nom_de_l_algorithme : Déclaration;Debut Actions;Fin

11/04/23 33

Syntaxe général de Syntaxe général de l’algorithme(suite)l’algorithme(suite)

Le moule d’un algorithmeLe moule d’un algorithme◦Dans la partie déclarations, nous

trouvons : Déclaration de constantes déclaration de variables déclaration de fonctions

◦Dans la partie actions, nous trouvons : suite d'instructions Structure alternative Structure répétitive

11/04/23 34

Syntaxe général de Syntaxe général de l’algorithme(suite)l’algorithme(suite)

Exemple :Exemple :Algorithme totoAlgorithme toto

/* les constantes: il est obligatoire de leur donner une valeur dès leur déclaration */

CONST titi 10 : entier

tutu "bonjour!" : chaîne

// les variables au sens strict

VAR riri, fifi : réels

loulou : chaîne

Debut

<Instruction1>;

<Instruction2>;

….

<Instruction3>;

Fin11/04/23 35

déclarations

Corps de l’algorithme

Des Questions ?Des Questions ?

11/04/23 36

Exercices : InstructionsExercices : Instructions

Exercice 1: Écrire un algorithme qui permet de

saisir des valeurs pour A et B , faire la somme et afficher le résultat?


calculer et afficher la surface d’un cercle?

11/04/23 37

Exercices : Exercices : Instructions(suite)Instructions(suite)

Exercice 3 Écrire un algorithme qui permet de

calculer et afficher le salaire brut d’un ouvrier connaissant le nombre d’heure et le tarif d’horaire?

Exercice 4 Écrire un algorithme qui fait la conversion

d’une somme d’argent donnée en DH, en une somme d’argent en Euro?

11/04/23 38

Les structures de contrôlesLes structures de contrôlesLe branchement conditionnelLe branchement conditionnel

Le branchement conditionnel Aide à Structurer un ensemble d’instructions

11/04/23 39

Syntaxe 1 :Syntaxe 1 :Si <conditions> alors <Instruction1> … <Instruction N>Fsi Exemple :Exemple :

SiSi (a<b) (a<b) alorsalors maxmaxb;b; minmina;a;FsiFsi

Les structures de Les structures de contrôles(suite)contrôles(suite)

Le branchement conditionnelLe branchement conditionnel

11/04/23 40

SyntaxeSyntaxe : Si <expression booléenne> alors <Instruction1> … <Instruction N> Sinon <Instruction1> … <Instruction N> Fsi

Exemple :Exemple :SiSi (a<b) (a<b) alorsalors maxmaxbbSinonSinon maxmaxaaFsiFsi

Les structures de Les structures de contrôles(suite)contrôles(suite)Qu’est ce qu’une condition ?Qu’est ce qu’une condition ?

◦une condition est composée de trois éléments : une valeur, un opérateur de comparaison, une

autre valeur◦Les valeurs peuvent être a priori de n’importe quel

type (numériques, caractères…). Mais si l’on veut que la comparaison ait un sens, il faut que les deux valeurs de la comparaison soient du même type !

◦Les opérateurs de comparaison sont : = égal à, <> différent de < strictement plus petit que, > strictement plus

grand que, <= plus petit ou égal à, >= plus grand ou égal à…

11/04/23 41


Exemple:◦‘t’ < ‘w’ VRAI

5>6 FAUX2< 3 VRAI

Exercice:◦Écrire un algorithme qui demande un

nombre à l’utilisateur, et l’informe ensuite si ce nombre est positif ou négatif (on laisse de côté le cas où le nombre vaut zéro).

11/04/23 42


Conditions composées:Conditions composées:◦Certains problèmes exigent parfois de

formuler des conditions composées liées entre eux par les opérateurs logiques suivants : ET, OU, NON, et XOR. Condition1 ET Condition2 : VRAI, si Condition1

est VRAI et Condition2 est VRAI. Condition1 OU Condition2 : VRAI, si Condition1

est VRAI ou bien Condition2 est VRAI. Le XOR (ou OU exclusif)

Condition1 XOR Condition2 : VRAI, si Condition1 est VRAI, ou bien Condition2 est VRAI.

Mais si toutes les deux sont fausses, ou que toutes les deux sont VRAI, alors le résultat global est considéré comme FAUX.

11/04/23 43

Les structures de Les structures de contrôles(suite)contrôles(suite)◦ le NON inverse une condition : NON(Condition1) est VRAI si

Condition1 est FAUX, et il sera FAUX si Condition1 est VRAI.

◦ tables de vérité (C1 et C2 représentent deux conditions, et on envisage à chaque fois les quatre cas possibles) :

11/04/23 44

C1 et C2 C2 Vrai C2 Faux

C1 Vrai Vrai Faux

C1 Faux Faux Faux

C1 ou C2 C2 Vrai C2 Faux

C1 Vrai Vrai Vrai

C1 Faux Vrai Faux


Exercice :◦Écrire un algorithme qui demande deux

nombres à l’utilisateur et l’informe ensuite si leur produit est négatif ou positif (on laisse de côté le cas où le produit est nul). Attention toutefois : on ne doit pas calculer le produit des deux nombres.

11/04/23 45

C1 xor C2 C2 Vrai C2 Faux

C1 Vrai Faux Vrai

C1 Faux Vrai Faux

Non C1

C1 Vrai Faux

C1 Faux Vrai

Exercices : structures de Exercices : structures de contrôlescontrôles

Exercice 1: ◦On désire comparer deux valeurs ,Écrire un

algorithme qui affiche la plus grande des deux?

Exercice 2: ◦Écrire un algorithme qui affiche le salaire

brut d’un ouvrier sachant que les heures supplémentaires de 172 heures sont payées à 50% de tarifs d’horaire en plus?

11/04/23 46


Exercice 4: Calculer le montant de la facture d’un client ayant

commandé une quantité d’un produit avec un prix unitaire hors taxe Le taux de T.V.A est : 20% Les frais de transport sont 0.8 DH de Km , Le client est

disposé du frais de transport si le montant est supérieur 4500 DH

Exercice 5: Une bibliothèque fait des réductions sur l’achat des

livres : 25% pour les étudiants. 15% pour les enseignants

Écrire un algorithme qui calcule et affiche le prix à payer selon le type du client?

11/04/23 47


Exercice 6: Écrire un algorithme qui calcule et affiche le

maximum de trois nombre A,B et C ? Exercice 7:

Écrire un algorithme qui permet de résoudre l’équation du premier degré : aX+b=0?


résoudre une équation de second degré : aX²+bX+c=0 ?

11/04/23 48


Exercice 9: Écrire un algorithme qui lie trois nombre A,B et C

, puis il détermine si l’un est égal à la somme de 2 autres sinon il affiche un message « pas de solution »?

11/04/23 49


Le choix multipleLe choix multipleVariable i:entier;Variable i:entier;

Lire(i);Lire(i);Selon que

i=1 : i=1 : faire <instruction1> <instruction1>Ou que i=2 : i=2 : faire <instruction2> <instruction2>Ou que i=3 : i=3 : fairefaire <instruction3> <instruction3>Autrement écrire(’’mauvais choix’’)(’’mauvais choix’’)Fselonque

11/04/23 50


Exercice 10: Écrire un algorithme qui à partir d’un

nombre compris entre 1 et 7 affiche le jour correspendant?

11/04/23 51

Les structures de Les structures de contrôles(suite)contrôles(suite)Tests imbriqués: Tests imbriqués:

◦un algorithme doit donner l’état de l’eau selon sa température il doit choisir entre trois réponses possibles (solide, liquide ou vapeur).

Variable Temp : EntierDébut Ecrire (“Entrez la température de l’eau :”) Lire (Temp) Si Temp <= 0 Alors Ecrire (“C’est de la glace“) Finsi Si Temp > 0 Et Temp < 100 Alors Ecrire (“C’est du liquide”)FinsiSi (Temp > 100 )Alors Ecrire “C’est de la vapeur”FinsiFin

11/04/23 52

Les structures de Les structures de contrôles(suite)contrôles(suite)Tests imbriqués: Tests imbriqués: deuxième solution qui

imbrique le test Variable Temp : Entier

DébutEcrire (“Entrez la température de l’eau :”)Lire (Temp)Si Temp =< 0 Alors Ecrire (“C’est de la glace“)Sinon Si Temp < 100 Alors Ecrire( “C’est du liquide”) Sinon Ecrire( “C’est de la vapeur”) FinsiFinsiFin

11/04/23 53


Exercice:◦Écrire un algorithme qui demande l’âge

d’un enfant à l’utilisateur. Ensuite, il l’informe de sa catégorie : - « Poussin » de 6 à 7 ans- « Pupille » de 8 à 9 ans- « Minime » de 10 à 11 ans- « Cadet » après 12 ansPeut-on concevoir plusieurs algorithmes équivalents menant à ce résultat ?

11/04/23 54


Variables Booléennes:Variables Booléennes:◦Il existe des variables (les booléennes)

susceptibles de stocker les valeurs VRAI ou FAUX. On peut donc entrer des conditions dans ces variables, et tester ensuite la valeur de ces variables.

◦Exemple:Exemple: Variable Temp : Entier

Variables A, B : BooléenDébutEcrire (“Entrez la température de l’eau :”)Lire (Temp)A ← Temp <= 0B ← Temp < 100

11/04/23 55


◦ Si A Alors Ecrire( “C’est de la glace“)Sinon

Si B Alors Ecrire “C’est du liquide” Sinon Ecrire “C’est de la vapeur” Finsi

FinsiFin

Dans une condition composée employant à la fois l’opérateur ET et l’opérateur OU, la présence de parenthèses possède une influence sur le résultat.

11/04/23 56

Exercice: Les structures de Exercice: Les structures de contrôlescontrôles

Ecrivez un algorithme qui lira au clavier l’heure et les minutes, et il affichera l’heure qu’il sera une minute plus tard.

Par exemple, si l'utilisateur tape 21 puis 32, l'algorithme doit répondre : "Dans une minute, il sera 21 heure(s) 33".

NB : on suppose que l'utilisateur entre une heure valide. Pas besoin donc de la vérifier.

11/04/23 57

Structure répétitiveStructure répétitiveA quoi cela sert-il donc ?

◦Prenons le cas d’une saisie au clavier (une lecture), où par exemple, le programme pose une question à laquelle l’utilisateur doit répondre par O (Oui) ou N (Non). Mais tôt ou tard, l’utilisateur, risque de taper autre chose que la réponse attendue.

◦Alors, dans tout l’algorithme on met en place ce qu’on appelle un contrôle de saisie, afin de vérifier que les données entrées au clavier correspondent bien à celles attendues par l’algorithme.

11/04/23 58

Structure répétitive(suite)Structure répétitive(suite)A quoi cela sert-il donc ?

◦On pourrait essayer avec une structure de contrôle SI.

◦Variable Rep : CaractèreDébutEcrire (“Voulez vous un café ? (O/N)“)Lire (Rep)Si Rep <> “O“ ET Rep <> “N” Alors Ecrire( “Saisie erronnée. Recommencez“) Lire (Rep)FinSiFin

◦

11/04/23 59


◦Si l’utilisateur ne se trompe qu’une seule fois, et entre une valeur correcte à la deuxième demande, c’est parfait.

◦Par contre, s’il commet une deuxième erreur, il faudrait rajouter un SI. Et ainsi de suite, on peut rajouter des centaines de SI, et écrire un algorithme lourd.

◦La solution consistant à aligner des SI n’est pas correcte dans ce cas. La seule issue est d’utiliser une structure de boucle.

11/04/23 60


◦Qui ce présente ainsi: TantQue booléen Faire … Instructions … FinTantQue

Le principe est simple : l’algorithme arrive sur la ligne du TantQue. Il examine alors la valeur du booléen (qui, je le rappelle, peut être une variable booléenne ou, plus fréquemment, une condition). Si cette valeur est VRAI, l’algorithme exécute les instructions qui suivent, jusqu’à ce qu’il rencontre la ligne FinTantQue. Il retourne ensuite sur la ligne du TantQue, procède au même examen, et ainsi de suite. Le cycle ne s’arrête que lorsque le booléen prend la valeur FAUX.

◦

11/04/23 61


◦Illustration avec notre problème de contrôle de saisie. Une première approximation de la solution consiste à écrire :

Variable Rep :CaractèreDébutEcrire (“Voulez vous un café ? (O/N)“)lire(Rep)

TantQue Rep <> “O“ ET Rep <> “N“ Faire Lire (Rep)FinTantQueFin

◦

11/04/23 62


◦Une deuxième approximation de la solution, avec affectation, consiste à écrire :

Variable Rep :CaractèreDébutRep ← “X“Ecrire (“Voulez vous un café ? (O/N)“)TantQue Rep <> “O“ ET Rep <> “N“ Faire Lire (Rep)FinTantQueFin

◦Cette manière de procéder est à connaître, car elle est employée très fréquemment.

◦

11/04/23 63

Structure répétitive(suite)Structure répétitive(suite)Structure répétitive, dite aussi

itérative ou boucle permet, de répéter une ou plusieurs actions un certain nombre de fois. On identifie en règle générale 3 types de répétitive :◦TantQue◦Répéter Jusqu'à◦Pour

11/04/23 64

Structure répétitive(suite)Structure répétitive(suite)Tant queTant queLes répétitives où la condition

d’arrêt est placée au début.◦Syntaxe : :

Tant que <expression logique> faire <séquence d’instructions> FtantqueTantQue condition actionsFTantQue

Ce qui signifie : tant que la condition est vraie, on exécute les actions.

11/04/23 65


11/04/23 66

ExercicesExercices1. Ecrire un algorithme qui demande à l’utilisateur

un nombre compris entre 1 et 3 jusqu’à ce que la réponse convienne.

2. Ecrire un algorithme qui demande un nombre compris entre 10 et 20, jusqu’à ce que la réponse convienne. En cas de réponse supérieure à 20, on fera apparaître un message : « Plus petit ! », et inversement, « Plus grand ! » si le nombre est inférieur à 10.

3. Écrire un algorithme qui demande un nombre de départ, et qui ensuite affiche les dix nombres suivants. Par exemple, si l'utilisateur entre le nombre 17, le programme affichera les nombres de 18 à 27.

11/04/23 67

Structure répétitive(suite)Structure répétitive(suite)Boucler en comptant, ou compter en Boucler en comptant, ou compter en

bouclantbouclant◦Il arrive très souvent qu’on ait besoin

d’effectuer un nombre déterminé de passages. Or, a priori, notre structure TantQue ne sait pas à l’avance combien de tours de boucle elle va effectuer:

◦C’est pourquoi une autre structure de boucle est à notre disposition : la structure : Pour

11/04/23 68

Structure répétitive(suite)Structure répétitive(suite)Variable Num1 : Entier

DébutNum1 ← 0TantQue Num1 < 15 Faire Num1 = Num1 + 1 Ecrire (“Passage numéro : “, Num1)FinTantQueFin

Variable Num1 : EntierDébutPour Num1 = 1 à 15 Faire

Ecrire( “Passage numéro : “, Num1)Num1 SuivantFin

11/04/23 69

la structure :Pour est un cas particulier de TantQue : celui où le programmeur peut dénombrer à l’avance le nombre de tours de boucles nécessaires.

Structure répétitiveStructure répétitivePour

◦Les répétitives où le nombre d’itération est fixée une fois pour toute.

◦Syntaxe : Pour Compteur = Initial à Final Pas

ValeurDuPas … Instructions … Compteur suivant (n’est pas indispensable)

FPour11/04/23 70

Structure répétitive(suite)Structure répétitive(suite) la progression du compteur est laissée à votre libre

disposition. Dans la plupart des cas, on a besoin d’une variable qui augmente de 1 à chaque tour de boucle. On ne précise alors rien à l’instruction « Pour » ; celle-ci, par défaut, comprend qu’il va falloir procéder à cette incrémentation de 1 à chaque passage, en commençant par la première valeur et en terminant par la deuxième.

Si vous souhaitez une progression plus spéciale, de 2 en 2, ou de 3 en 3, ou en arrière, de –1 en –1, ou de –10 en –10, il faut préciser à votre instruction « Pour » en lui rajoutant le mot « Pas » et la valeur de ce pas.

Quand on met un pas négatif dans une boucle, la valeur initiale du compteur doit être supérieure à sa valeur finale si l’on veut que la boucle tourne !

11/04/23 71

Structure répétitive(suite)Structure répétitive(suite)Les structures TantQue sont employées

dans les situations où l’on doit procéder à un traitement sur les éléments d’un ensemble dont on ne connaît pas d’avance la quantité, comme par exemple :◦ le contrôle d’une saisie.◦ la gestion des tours d’un jeu (tant que la

partie n’est pas finie, on recommence).Les structures Pour sont employées dans

les situations où l’on doit procéder à un traitement sur les éléments d’un ensemble dont on connaît d’avance la quantité.

11/04/23 72

Structure répétitive(suite)Structure répétitive(suite)Des boucles imbriquées:Des boucles imbriquées:

◦De même que qu’une structure SI … ALORS peut contenir d’autres structures SI … ALORS, une boucle peut tout à fait contenir d’autres boucles.Variables Num1, Num2 : Entier

Pour Num1 ← 1 à 15 Ecrire (“Il est passé par ici“) Pour Num2 ← 1 à 6 Ecrire (“Il repassera par là“)

Fpour FPour

◦

11/04/23 73

Structure répétitive(suite)Structure répétitive(suite)Répéter..Jusqu’à :Répéter..Jusqu’à :

◦ la condition d’arrêt est placée à la fin◦ Syntaxe :

Répéter <séquence d’instructions> Jusqu’à <expression logique> Frépéter

◦ Exemple : Num1:=1Répéter

Ecrire (“Passage numéro : “, Num1) Num1 = Num1 + 1

Jusqu’à (Num1 >= 15 )

11/04/23 74


11/04/23 75

ExercicesExercices1. Écrire un algorithme qui saisie N entier et

affiche leur somme et leur moyenne ?2. Écrire un algorithme pour calculer et

afficher la somme et la moyenne de100 premiers nombres entiers ?

3. Écrire un algorithme qui permet de calculer S1, S2,S3,S4,S5,S6 tel que:

◦ S1 = 1 + ½ + 1/3 + ¼ +……..1/N◦ S2 = 1 + ½ + ¼ + 1/6 +……..1/N◦ S3 = 1 + 1/3 + 1/5 +……..1/N◦ S4 = 1 - ½ + ¼ - 1/6……..1/N◦ S5 = 1 + x+x²……..xN

◦ S6 = 1 + x+x²/2…….. xN /N11/04/23 76

ExercicesExercices4. Ecrire un algorithme qui vérifie si un

nombre est premier où pas ?5. écrire un algorithme qui saisit deux

entiers, calcule et affiche la somme de ces 2 entiers (on arrête la saisie avec la valeur 0) ?

6. Ecrire un algorithme qui permet de calculer le factoriel d’un nombre positif ?

11/04/23 77

Devoir N° 1Devoir N° 1Une salle de cinéma désire automatiser la gestion de

la billetterie pour chaque client qui se présente, on calcule le prix du billet en fonction des données suivantes:◦ NF : Numéro du film◦ Age : Age de spectateur

Le prix normal de la facture est de 30 DH, cependant des remises peuvent être accorder en fonction du critères suivants :◦ NF=2 ou Age < 15 remise de 50%◦ NF=2 et Age >75 remise 25%◦ NF=3 et Age < 15 entrée refusée

Écrire un algorithme qui permet de calculer et décider le prix à payer pou chaque client qui se présente . on arrête la saisie par "non"

11/04/23 78

Devoir N°2Devoir N°2Une entreprise désire automatisée la gestion de

paie de son personnel. Pour chaque employé, on doit introduire le nom, le prénom, le salaire de base(SB), le nombre d'enfant et l'ancienneté(ANC).

Un prix de 100 DH est accordé pour chaque enfant .◦ Si ancienneté<=10 ans et SB < 1000 DH une prime

de 50% du SB◦ Si l'ancienneté est 10 ans < ANC <20 ans et SB >

1000 DH prime de 70% du SBCalculer le salaire brute (SB+ le prime + les

enfants) et afficher le nom, prénom, l'ancienneté , SB, prime et le salaire brute

11/04/23 79

Les tableauxLes tableauxSupposons que nous avons besoin de

calculer la moyenne de 12 notes d’un étudiant.

la seule solution dont nous disposons consiste à déclarer douze variables, appelées par exemple: X1, X2, X3,…X12.

La première étape est de lire les valeurs de toute ces variables une par une, ce qui nous fait douze instructions de lecture et après calculer la moyenne par l’instruction:

Moy ← (X1+X2+X3+X4+X5+NX6+X7+X8+X9+X10+X11+X12)/12

11/04/23 80

Les tableaux(suite)Les tableaux(suite)C’est pourquoi l’algorithmique (la

programmation) nous permet de rassembler toutes ces variables en une seule, au sein de laquelle chaque valeur sera désignée par un numéro.

11/04/23 81

Un ensemble de valeurs portant le même nom de variable et repérées par un nombre, s’appelle un tableau, ou encore une variable indicée.Le nombre qui, au sein d’un tableau, sert à repérer chaque valeur s’appelle l’indice.Chaque fois que l’on doit désigner un élément du tableau, on fait figurer le nom du tableau, suivi de l’indice de l’élément, entre parenthèses. Ex: Nom_tableau(5)

Les tableaux(suite)Les tableaux(suite)Notation et utilisation algorithmiqueNotation et utilisation algorithmique

◦Dans notre exemple, nous créerons donc un tableau appelé Note.

◦Tableau Note(12) : Entier◦On peut créer des tableaux contenant des

variables de tous types : tableaux de numériques, tableaux de caractères, tableaux de booléens, tableaux de tout ce qui existe dans un langage donné comme type de variables.

◦L’énorme avantage des tableaux, c’est qu’on va pouvoir les traiter en faisant des boucles.

11/04/23 82

Les tableaux(suite)Les tableaux(suite)Notation et utilisation algorithmiqueNotation et utilisation algorithmique

Tableau Note(12) : EntierVariables i, Som : EntierVariable Moy : RéelPour i ← 0 à 11 Ecrire (“Entrez la note n°”, i) Lire( Note(i))FPour

Som ← 0Pour i ← 0 à 11 Som = Som + Note(i)

FpourMoy = Som / 12

11/04/23 83

Les tableaux(suite)Les tableaux(suite)Remarque générale : l’indice qui sert à

désigner les éléments d’un tableau peut être exprimé directement comme un nombre en clair, mais il peut être aussi une variable, ou une expression calculée.

La valeur d’un indice doit toujours :◦ être égale au moins à 0 (dans quelques rares

langages, le premier élément d’un tableau porte l’indice 1). Mais nous avons choisi ici de commencer la numérotation des indices à zéro, comme c’est le cas en langage C.

◦ être un nombre entier. Quel que soit le langage.◦ être inférieure ou égale au nombre d’éléments

du tableau (moins 1, si l’on commence la numérotation à zéro).

11/04/23 84

ExercicesExercicesÉcrire un algorithme qui déclare et

remplisse un tableau de 7 valeurs numériques en les mettant toutes à zéro.

Écrire un algorithme qui déclare et remplisse un tableau contenant les six voyelles de l’alphabet latin.

On saisit des entiers et on les range dans un tableau (maximum 50) Écrire un programme qui affiche le maximum, le minimum et la valeur moyenne de ces nombres.

11/04/23 85

ExercicesExercicesÉcrivez un algorithme permettant à

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

11/04/23 86

ExercicesExercicesQue produit l’algorithme suivant ?

Tableau Nb(6) : EntierVariable i en EntierDébutPour i ← 0 à 5Nb(i) ← i * iFPourPour i ← 0 à 5Écrire Nb(i)FPourFin

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

11/04/23 87

ExercicesExercicesQue produit l’algorithme suivant ?

Tableau N(7) en EntierVariables i, k en EntierDébutN(0) ← 1Pour k ← 1 à 6 N(k) ← N(k-1) + 2FPourPour i ← 0 à 6 Ecrire N(i)FPourFin

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

11/04/23 88

OrganigrammeOrganigrammeDéfinitionDéfinition

◦ un organigramme est la représentation schématique qui permet de faire apparaître d’une façon claire et logique l’enchaînement des différentes opérations.

Les symboles utilisés pour construire un Les symboles utilisés pour construire un organigrammeorganigramme

11/04/23 89

Symbole général traitement

Symbole début-fin-interruption

Symbole embranchement(choix)

Symbole commentaire

Les lignes de liaison

OrganigrammeOrganigramme

11/04/23 90

Exemple :

Condition

Instruction 1Instruction 2

suite


11/04/23 91

Exemple :Le branchement conditionnelLe branchement conditionnel

instruction1

condition

instruction2


11/04/23 92

Exemple :Structure répétitive

instruction

condition

V

F


11/04/23 93

Exemple : Structure répétitive

instruction

condition

F

V

Notions de sous-algorithmeNotions de sous-algorithmeDéfinition

◦ Un sous-algorithme est un élément d’algorithme nommé et éventuellement paramétré que l’on définit afin de pouvoir ensuite l’appeler par son nom en affectant, s’il y a lieu, des valeurs aux paramètres.

◦ Intérêt : Intérêt : Réaliser un découpage d’une tâche en sous-tâche. Effectuer une seule description d’une tâche commune Concevoir une application de manière descendante en

entrant de plus en plus dans les détails

◦ Structure : Structure : un sous-algorithme est composé D’une tête D’une tête nom sous-algorithme,

paramètres(arguments) avec leur type D’un corps D’un corps des déclarations d’objets locaux aux sous-

algorithme, instructions à exécuter11/04/23 94

Notions de sous-algorithmeNotions de sous-algorithme◦Sous-algorithme NomNom(liste des paramètres) déclarations des variables locales Début Corps du sous-algorihtme Fin◦Algorithme Nom Nom Déclaration des variables Début Instructions Appel du sous-algorithme Instructions Fin

11/04/23 95

Procédures & FonctionsProcédures & Fonctions

ProcéduresProcédures◦Syntaxe

Procédure nom_procédure(var:type;var:type)

Variable interneDébut procédure InstructionsFinprocédure

11/04/23 96

Procédures & FonctionsProcédures & FonctionsFonctionsFonctions

◦SyntaxeFonction

nom_fonction(var:type;var:type):type Variable interne;Début fonction Instructions; Retourner variable;Fin fonction

11/04/23 97

Procédure & FonctionProcédure & FonctionRep1,Rep2 : caractère

Fonction RepOuiNon() : caractères

variable Rep ← ""

TantQue Rep <> "Oui" et Rep <> "Non"

Ecrire( "Tapez Oui ou Non")

Lire (Rep)

FinTantQue

Renvoyer Rep

Fin

Début

Ecrire( "Etes-vous marié ?")

Rep1 ← RepOuiNon()

Ecrire( "Avez-vous des enfants ?" )

Rep2 ← RepOuiNon()

Fin11/04/23 98

EXERCICESEXERCICES

11/04/23 99

ExercicesExercicesEX0

◦Ecrire un algorithme qui lit une valeur qlq x et qui détermine la valeur de l’expression :

1+x+x2+…+x20

EX1◦Ecrire une procédure qui lit N éléments en

paramètre et retourne la somme de ces éléments dans une variable somme.

EX2◦Ecrire une fonction entière statistique qui

lit 100 notes et retourne le nombre de notes comprises entre 10 et 20 compris

11/04/23 100


◦Ecrire un algorithme qui permet de faire les traitements suivants :

Soit un tableau T de N entiers1.Remplir les N cases du tableau2.Compter le nombre des éléments non nuls3.Trouver le plus grand éléments du tableau

et le mettre dans la variable MAX4.Rechercher la place du plus petit élément

et le mettre dans la variable position.

11/04/23 101


◦Ecrire un algorithme qui cherche dans un tableau non trié si un nombre x existe au moins une fois.

EX5◦Ecrire un algorithme qui cherche dans un

tableau trié si un nombre x existe au moins une fois.

EX6◦Ecrire un algorithme qui permet de lire les

âges de 25 stagiaires(ils ont au moins 23ans et au plus 30ans) et fournit le nombre de stagiaires de chacun des âges.

11/04/23 102


◦Le tableau factures contient N constantes de factures, le tableau PAYES de N booléens indique si chacune des factures a été réglées ou pas, on veut recopier séquentiellement dans un 3ème tableau RESTESAPAYES, les sommes restant dues.

11/04/23 103

RécursivitéRécursivitéUn algorithme est dit récursif lorsqu’il

intervient dans sa description, c’est-à-dire lorsqu’il est défini en fonction de lui-même.

Exemple: x0 = 1, xn = x*xn-1 si n≥1Fonction fact(x : entier, n : entier):entier

Variable Résultat : entier;

Début

Si(n=0) alors

Résultat =1;

Sinon

Résultat = x*fact(x,n-1);

Fsi

Renvoyer Résultat;

Fin

11/04/23 10

4

MÉTHODES DE TRI MÉTHODES DE TRI ÉLÉMENTAIRESÉLÉMENTAIRES

•Définition•Tri par sélection•Tri par bulles•Tri par insertion

11/04/23 105

DéfinitionDéfinition« trier » signifie « répartir en plusieurs

classes selon certains critères ». De manière plus restrictive, le terme de

« tri » en algorithmique est très souvent attaché au processus de classement d'un ensemble d'éléments dans un ordre donné.

Par exemple, trier N entiers dans l'ordre croissant, ou N noms dans l'ordre alphabétique.

Tout ensemble muni d'un ordre total peut fournir une suite d'éléments à trier.

11/04/23 106

Tri par sélectionTri par sélectionTri par sélection est l’un des algorithmes

de tri les plus simple, elle procède à la sélection successive de l’élément minimal parmi ceux restant. Il fonctionne de la manière suivante :◦On commence par rechercher l’élément de

plus petite valeur du tableau pour l’échanger avec celui en première position.

◦On recherche ensuite l’élément ayant la deuxième plus petite valeur pour l’échanger avec celui en deuxième position, et l’on continue ainsi jusqu’à ce que le tableau soit entièrement trié.

11/04/23 107

Tri par sélection(suite)Tri par sélection(suite) Le sous-algorithme suivant est une implantation de ce

processus. Pour tout i entre 1 et N-1, on échange T[i] avec l’élément de valeur minimal parmi T[i]….T[N] :

Pocédure TriSelectionTriSelection(T: 1…N: entier; N: entier)

Var i, j, min, q:entier;

Début

pour i de 1 jusqu’à N faire

min=i;

pour j de i+1 jusqu’à N faire

Si(T[j]<T[min]) alors

min=j;

Fsi

Fpour

q=T[min]; T[min]=T[i]; T[i]=q;

Fpour

Finprocédure

11/04/23 108

A mesure que l’indice i progresse vers la droite du

fichier, les éléments situés à sa gauche ont pris leur position

définitive et le tableau est trié lorsque l’indice i atteint

l’extrémité droite

Tri par sélection(suite)Tri par sélection(suite) Il est facile de compter le nombre d'opérations.

Quel que soit l'ordre du tableau initial, le nombre de comparaisons reste le même, ainsi que le nombre d'échanges. À chaque itération, on considère l'élément tab[i] et on le compare successivement à tab[i+1], ..., tab[N]. On fait donc N-i comparaisons.

Le nombre total de comparaisons est donc de :et il y a (N-1) échanges.En ce qui concerne sa complexité, on dit que le tri

par sélection est en O (N2), à la fois dans le meilleur des cas, en moyenne et dans le pire des cas, c'est-à-dire que son temps d'exécution est de l'ordre du carré du nombre d'éléments à trier.

11/04/23 109

Tri par bulleTri par bulleLe « tri bulle » est une variante du tri par

sélection. Il consiste à parcourir le tableau tab en permutant toute paire d'éléments consécutifs (tab[k],tab[k+1]) non ordonnés - ce qui est un échange et nécessite donc encore une variable intermédiaire de type entier. Après le premier parcours, le plus grand élément se retrouve dans la dernière case du tableau, en tab[N], et il reste donc à appliquer la même procédure sur le tableau composé des éléments tab[1], ..., tab[N-1]. Le nom de ce tri provient du déplacement des « bulles » les plus grandes vers la droite.

11/04/23 110

Tri par bulle(suite)Tri par bulle(suite) /* Procédure de tri bulle */ procedure triBulle(entier[] tab)

entier i, k; entier tmp; pour (i de N à 2 en décrémentant de 1) faire pour (k de 1 à i-1 en incrémentant de 1) faire si (tab[k] > tab[k+1]) alors tmp <- tab[k]; tab[k] <- tab[k+1]; tab[k+1] <- tmp; fin si fin pour fin pour fin procedure

11/04/23 111

Tri par bulle(suite)Tri par bulle(suite)Le nombre de comparaisons dans la procédure de tri

bulle est le même que pour le tri par sélection : Le nombre d'échanges quant à lui dépend de l'ordre

des éléments dans le tableau : ◦ dans le meilleur des cas, le tableau initial est trié et il n'y a pas

d'échange à faire ;◦ en moyenne, on montre que le nombre d'échanges est de :

dans le pire des cas, les entiers du tableau sont initialement donnés dans l'ordre décroissant. Dans ce cas, on effectue l'échange à chaque comparaison, c'est-à-dire que le nombre d'échanges est alors de :

Quoi qu'il en soit, la complexité du tri bulle reste en O (N2), c'est-à-dire du même ordre de grandeur que le carré du nombre d'éléments.

11/04/23 112

Tri par insertionTri par insertionCette méthode de tri est très différente de la méthode de

tri par sélection et s'apparente à celle utilisée pour trier ses cartes dans un jeu : on prend une carte, tab[1], puis la deuxième, tab[2], que l'on place en fonction de la première, ensuite la troisième tab[3] que l'on insère à sa place en fonction des deux premières et ainsi de suite. Le principe général est donc de considérer que les (i-1) premières cartes, tab[1],..., tab[i-1] sont triées et de placer la ie carte, tab[i], à sa place parmi les (i-1) déjà triées, et ce jusqu'à ce que i = N.

Pour placer tab[i], on utilise une variable intermédiaire tmp pour conserver sa valeur qu'on compare successivement à chaque élément tab[i-1],tab[i-2],... qu'on déplace vers la droite tant que sa valeur est supérieure à celle de tmp. On affecte alors à l'emplacement dans le tableau laissé libre par ce décalage la valeur de tmp.

11/04/23 113

Tri par insertion(suite)Tri par insertion(suite)

/* Procédure de tri par insertion */ procedure triInsertion(entier[] tab)

entier i, k,tmp; pour (i de 2 à N en incrémentant de 1) faire tmp <- tab[i]; k <- i; tant que (k > 1 et tab[k - 1] > tmp) faire tab[k] <- tab[k - 1]; k <- k - 1; fin tant que tab[k] <- tmp; fin pour fin procedure

11/04/23 114

Tri par insertion(suite)Tri par insertion(suite)La comparaison avec les deux algorithmes

précédents montre que la complexité du tri par insertion est plus fortement dépendante de l'ordre du tableau initial. Nous comptons ici le nombre de comparaisons (qui est le nombre de décalages à un près) : ◦ dans le meilleur des cas, le tableau initial est trié et on

effectue alors une comparaison à chaque insertion, on effectue donc N-1 comparaisons ;

◦ en moyenne, on montre que le nombre de comparaisons est de :

11/04/23 115

Documents

Algorithmique Mme Khadija BOUZAACHANE Année universitaire : 2009-2010