Upload
idriss-ben-bassou
View
250
Download
4
Embed Size (px)
Citation preview
8/3/2019 Cour Algorithmique
1/115
AlgorithmiqueAlgorithmique
Mme Khadija BOUZAACHANE
Anne universitaire : 2009-2010
8/3/2019 Cour Algorithmique
2/115
INTRODUCTIONINTRODUCTION
03/01/2010 2
8/3/2019 Cour Algorithmique
3/115
IntroductionIntroduction
Avez vous dj dchiffr un mode demploipour faire fonctionner un DVD, ou bien la
tlvision ou un rpondeur tlphonique? Sioui, sans le savoir, vous avez dj excutdes algorithmes.
Avez-vous dj indiqu un chemin untouriste gar ?
Un algorithme, cest une suite dinstructions,
qui une fois excute correctement, conduit un rsultat donn. Si lalgorithme est juste, lersultat est le rsultat voulu, et le touriste seretrouve l o il voulait aller03/01/2010 3
8/3/2019 Cour Algorithmique
4/115
IntroductionIntroduction Quest-ce quun algorithme?
Est une suite dinstructions crite en langagedalgorithme qui rsout un problme et qui peuventtre programm par nimporte quel langage.
'1. Se lever2. Prendre sa douche
3. Prendre le petit djeuner4. S'habiller
03/01/2010 4
8/3/2019 Cour Algorithmique
5/115
IntroductionIntroduction
Un algorithme doit donc contenir uniquementdes instructions comprhensibles par celuiqui devra lexcuter.
03/01/2010 5
8/3/2019 Cour Algorithmique
6/115
DfinitionDfinition
Algorithmique: Dfinition1: dsigne l'ensemble des rgles et
des techniques qui sont impliques dans ladfinition et la conception des algorithmes.
Dfinition2: l'algorithmique c'est de savoircomment lire, crire, valuer et optimiser desalgorithmes.
03/01/2010 6
8/3/2019 Cour Algorithmique
7/115
DfinitionDfinition
Algorithme: Dfinition1: Un algorithme dcrit une
mthode de rsolution de problmeprogrammable sur machine.
Dfinitio : Un al orithme est un ensemble
d'oprations de calcul lmentaires, organisselon des rgles prcises dans le but dersoudre un problme donn. Pour chaque
donne du problme, l'algorithme retourneune rponse aprs un nombre finid'oprations(+, -,/,,... ).
03/01/2010 7
8/3/2019 Cour Algorithmique
8/115
DfinitionDfinition Quest-ce quun programme?
Un programme est donc une suite d'instructionsexcutes par la machine. La machine a son propre
langage appel langage machine. Un programme est lexpression dun algorithme par une
machine donne dans un langage de programmation
onn en u san e r per o re ac ons op ra ons,instructions) et les rgles de composition propres cette machine et ce langage donns.
Un programme est un assemblage et un enchanement
dinstructions lmentaires crit dans un langage deprogrammation, et excut par un ordinateur afin detraiter les donnes dun problme et renvoyer un ou
plusieurs rsultats.03/01/2010 8
8/3/2019 Cour Algorithmique
9/115
MthodologieMthodologie Pour rsoudre un problme, il est vivement conseill de
rflchir d'abord l'algorithme avant de programmer.
Exemple de construction dalgorithme: Exemple: calcul des racines de lquation du second ordreax2+bx+c=0
1re version: Lire a, b, c Calculer les racines de lquation Imprimer les racines
03/01/2010 9
8/3/2019 Cour Algorithmique
10/115
MthodologieMthodologie La rsolution dun problme est
caractris par 4 tapes : Comprendre la nature du problme pos Prciser les donnes fournies Entres Prciser les rsultats que lon dsire obtenir
(Sorties) Dterminer le processus de transformation
des donnes en rsultats.
03/01/2010 10
8/3/2019 Cour Algorithmique
11/115
MthodologieMthodologie
Comment on programme?
On utilise un pseudo-langage, comportant toutes lesstructures de base d'un langage de programmation
03/01/2010 11
On traduit notre "pseudo" en langage voluen fonction des possibilits de ce langage
Ce langage sera ensuite traduit en langage machine
8/3/2019 Cour Algorithmique
12/115
MthodologieMthodologie Un programme est donc une suite
d'instructions excutes par la machine.Ces instructions peuvent: soit s'enchaner les unes a rs les autres on
parle alors de squence d'instructions; ou bien s'excuter dans certains cas et pas dans
d'autres, on parle alors de structure alternative; ou se rpter plusieurs fois, on parle alors de
structure rptitive.
03/01/2010 12
8/3/2019 Cour Algorithmique
13/115
La squence dinstructionsLa squence dinstructions
Une instruction est une action que
l'ordinateur est capable d'excuter. Une squence d'instruction serait :
Prendre sa douche Prendre le petit djeuner
S'habiller
03/01/2010 13
8/3/2019 Cour Algorithmique
14/115
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
03/01/2010 14
8/3/2019 Cour Algorithmique
15/115
Structure rptitiveStructure rptitive La routine journalire dun employ est :
Ouvrir guichet
Appeler premier client TantQue " client dans file d'attente " et " pas fin
de journe "
Traiter client Appeler client suivant
FinTantQue
Les deux actions "Traiter client" et "Appelerclient suivant" vont se rpter tant que lacondition situe derrire l'instruction "Tant que"
est vrifie. 03/01/2010 15
8/3/2019 Cour Algorithmique
16/115
Pourquoi faire desPourquoi faire des
algorithmesalgorithmes la rdaction des algorithmes permet
plusieurs choses : d'tre comprhensible par tout informaticien
'programme
de vrifier la complexit du programme et donc
de l'optimiser de faire ressortir de manire comprhensible
les cas d'utilisations
03/01/2010 16
8/3/2019 Cour Algorithmique
17/115
NOTIONS DE BASENOTIONS DE BASEComment faire des algorithmes?Les variablesLe type de la variableLes instructionsSyntaxe gnral de lalgorithmeLes structures de contrle
Structure rptitiveLes tableauxOrganigrammeProcdures & FonctionsRcursivit
03/01/2010 17
8/3/2019 Cour Algorithmique
18/115
Comment faire des algorithmesComment faire des algorithmes
les algorithmes sont rdigs dans un langage mi-
chemin entre le franais et les langages deprogrammation, dit pseudo-code .
En programmation, le pseudo-code est une faon de
programmation particulier. L'criture en pseudo-codepermet souvent de bien prendre toute la mesure de ladifficult de l'implmentation de l'algorithme, et de
dvelopper une dmarche structure dans laconstruction de celui-ci.
03/01/2010 18
8/3/2019 Cour Algorithmique
19/115
Comment faire desComment faire des
algorithmes(suite)algorithmes(suite) La raison dtre dun algorithme est dersoudre un problme. La plus grande
attention doit tre porte lacomprhension du problme, faute de quoi
correct. Le langage utilis pour la dfinitiondun problme est un langage scientifiqueutilisant pour des raisons de simplicit unelangue naturelle(franais par exemple).
03/01/2010 19
8/3/2019 Cour Algorithmique
20/115
Les variablesLes variablesUne variable est un objet dont la valeurnest pas invariableUne variable peut tre reprsente par unecase mmoire, qui contient la valeur d'unedonne.
Chaque variable possde un nom uniqueappel identificateur par lequel on peutaccder son contenu.
Par exemple, on peut avoir en mmoire unevariable prix et une variable quantit.
03/01/2010 20
8/3/2019 Cour Algorithmique
21/115
Les variables(suite)Les variables(suite) Une variable possde 3 attributs :
Une valeur
Un nom(invariable) qui sert la dsigner Un type(invariable) qui dcrit lutilisation
possible de la variable
Une valeurUne valeur la valeur d'une variable(contenu) peut varier
au cours du programme. L'ancienne valeur
est tout simplement crase et remplace parla nouvelle.
La valeur peut tre de diffrents types et de
tailles diffrentes. 03/01/2010 21
8/3/2019 Cour Algorithmique
22/115
Les variables(suite)Les variables(suite) Nom de la variableNom de la variable
Cest une suite de lettres et de chiffrescommenant ncessairement par une lettre
Le nombre maximal de caractres impos varieselon les langages
a s es programmes pen e a choisir des noms reprsentatifs
Le nom de la variable doit tre le plusreprsentatif possible du contenu de celle-ci pourfaciliter la lecture de l'algorithme. En revanche, ilne doit pas non plus tre trop long pour ne pasnuire la lisibilit de l'ensemble.
03/01/2010 22
8/3/2019 Cour Algorithmique
23/115
Les variables(suite)Les variables(suite) Nom de la variableNom de la variable
Exemple Je veux mmoriser l'ge d'une personne dans une variable,
j'ai le choix de l'appeler : a ge a e
ageDeLaPersonneDontJeSuisEntrainDeParler Remarque :
Le premier cas est trop court, si je n'ai pas lu la descriptionplus haut, je suis totalement perdu. Le deuxime cas ne
convient pas non plus car on vitera tout caractre accentudans les noms de variable. Le dernier cas est certes trsprcis, mais tellement long qu'il en devient illisible. Bref, letroisime cas semble le plus appropri
03/01/2010 23
8/3/2019 Cour Algorithmique
24/115
Les variables(suite)Les variables(suite) Type de la variableType de la variable
Le type de la variable dfinit : La nature des informations qui seront reprsentes dans la
variable Les limitations concernant les valeurs reprsenter Les oprations ralisables avec les variables
corres ondantes.
Proprit: Une variable doit tre dclar avant sonutilisation
03/01/2010 24
8/3/2019 Cour Algorithmique
25/115
Les variables(suite)Les variables(suite)
Type de la variableType de la variable Entier : il s'agit des variables destines
contenir un nombre entier positif ou ngatif. Rel : il s'agit des variables numriques qui ne
sont pas des entiers, c'est dire qui
comportent es c ma es Caractre : Les variables de type caractre
contiennent des caractres alphabtiques ou
numriques seul(ex: c) Boolen : Les variables qui prennent les
valeurs (vrai ou faux) ou les valeurs (oui ou
non). 03/01/2010 25
8/3/2019 Cour Algorithmique
26/115
Les variables(suite)Les variables(suite)
Type de la variableType de la variable Chane de caractres : reprsentant un
texte, contenant un ou plusieurscaractres(ex: Bonjour tout le monde) Tous les traducteurs de langages prennent en
compte cette not on e type par es nstruct ons edclaration de type
Exemple:Variable Moyenne : rel;(Moyenne en numrique)
Variable NbreEtudiant : entier; (NbreEtudiant ennumrique)Variable c1, lettre, z : caractre;
03/01/2010 26
8/3/2019 Cour Algorithmique
27/115
Les variables(suite)Les variables(suite)
Type de la variable: ConstanteType de la variable: Constante
Dfinitions: une constante est un objet devaleur invariable. Elle est la ralisationdune valeur de type particulier.
Exemple:Exemple: Constante Zero=0: entier;
( Max:entier)100;
03/01/2010 27
8/3/2019 Cour Algorithmique
28/115
Les variables(suite)Les variables(suite) Les oprateurs de lalgorithmiqueType Exemple Opration possibles symbole
Rel -15.69, 0.49 AdditionSoustractionMultiplicationDivision
+-*
/
03/01/2010 28
Pourcentagecomparaisons
%=,=,
Entier -10, 4, 768 AdditionSoustractionMultiplicationDivisionModuloExposantPourcentage
+-*DIVMOD^%
8/3/2019 Cour Algorithmique
29/115
Les variables(suite)Les variables(suite) Les oprateurs de lalgorithmiqueType Exemple Opration
possiblessymbole
caractre B, \n comparaisons =,=,
Boolen Vrai, Faux ComparaisonNgation
=,=,NON
03/01/2010 29
Conjonctiondisjonction
ETOU
8/3/2019 Cour Algorithmique
30/115
Les instructionsLes instructions Linstruction daffectationLinstruction daffectation
Linstruction daffectation permet de manipuler lesvaleurs des variables. Son rle consiste placer
une valeur dans une variable. Notation X=YX=Y ou bien X:=YX:=Y ou bien XXYY
Exemple :
1. affecter une valeur une variable X:=5, On charge la variable X avec la valeur 5
2. Affecter le contenu dune variable une autre
variable X:=Y , On charge X avec le contenu de Y Y reprsente :
Constante ou Nom dune variable ou Expression
logique X et Y doivent tre de mme type03/01/2010 30
8/3/2019 Cour Algorithmique
31/115
Les instructions(suite)Les instructions(suite) Linstruction daffectationLinstruction daffectation
3. Affecter une formule une variable X:= X + 2 * Y
On charge la variable X par la valeur du rsultatde la formule et on crase sa valeur initiale
03/01/2010 31
3
11
4
8/3/2019 Cour Algorithmique
32/115
Les instructions(suite)Les instructions(suite) Les instructions dEntre/SortieLes instructions dEntre/Sortie
Un programme est amen : Prendre des donnes par le priphrique(clavier) : rle de
linstruction de lecture Communiquer des rsultats par lintermdiaire du
priphrique(cran) : rle de linstruction de lcriture
Rle : fournir des donnes au programme SyntaxeSyntaxe : Lire(variable) ExempleExemple : Lire( X) on saisie une valeur pour la stocker aprs
dans la variable X
Instruction dcriture Rle : fournir des rsultats directement comprhensibles SyntaxeSyntaxe : Ecrire( variable), Ecrire(chaine de caractres)
ExempleExemple : Ecrire(X), Ecrire(Bonjour)03/01/2010 32
8/3/2019 Cour Algorithmique
33/115
SyntaxeSyntaxe gnral de lalgorithmegnral de lalgorithme Le moule dun algorithmeLe moule dun algorithme
Un algorithme comportera : Une partie dclaration Une partie encadre par dbut fin o sont
dcrites les actions
_ _ _
Dclaration;Debut
Actions;Fin
03/01/2010 33
yntaxeyntaxe g n ra eg n ra e
8/3/2019 Cour Algorithmique
34/115
yntaxeyntaxe g n ra eg n ra elalgorithme(suite)lalgorithme(suite)
Le moule dun algorithmeLe moule dun algorithme Dans la partie dclarations, nous trouvons :
Dclaration de constantes dclaration de variables dclaration de fonctions
Dans la partie actions, nous trouvons : suite d'instructions Structure alternative
Structure rptitive
03/01/2010 34
yn axeyn axe g n ra eg n ra e
8/3/2019 Cour Algorithmique
35/115
yn axeyn axe g n ra eg n ra elalgorithme(suite)lalgorithme(suite)
Exemple :Exemple :Algorithme totoAlgorithme toto
/* les constantes: il est obligatoire de leur donner une valeur dsleur dclaration */
CONST titi 10 : entier
tutu "bonjour!" : chane
dclarations
VAR riri, fifi : relsloulou : chane
Debut
;;
.
;
Fin 03/01/2010 35
Corps de lalgorithme
8/3/2019 Cour Algorithmique
36/115
Des Questions ?Des Questions ?
03/01/2010 36
8/3/2019 Cour Algorithmique
37/115
Exercices : InstructionsExercices : Instructions Exercice 1:
crire un algorithme qui permet de saisir desvaleurs pour A et B , faire la somme etafficher le rsultat?
Exercice 2:crire un algorithme qui permet de calculer etafficher la surface dun cercle?
03/01/2010 37
8/3/2019 Cour Algorithmique
38/115
Exercices : Instructions(suite)Exercices : Instructions(suite) Exercice 3
crire un algorithme qui permet de calculer etafficher le salaire brut dun ouvrier connaissantle nombre dheure et le tarif dhoraire?
Exercice 4crire un algorithme qui fait la conversion
dune somme dargent donne en DH, en unesomme dargent en Euro?
03/01/2010 38
Les structures de contrlesLes structures de contrles
8/3/2019 Cour Algorithmique
39/115
Les structures de contrlesLes structures de contrles
Le branchement conditionnelLe branchement conditionnelLe branchement conditionnel Aide Structurer unensemble dinstructions
SyntaxeSyntaxe 11 ::Si alors
03/01/2010 39
Fsi Exemple :Exemple :SiSi (a
8/3/2019 Cour Algorithmique
40/115
Les structures de contrles(suite)Les structures de contrles(suite)
Le branchement conditionnelLe branchement conditionnelSyntaxeSyntaxe :
Si alors
03/01/2010 40
non
Fsi
Exemple :Exemple :SiSi (a
8/3/2019 Cour Algorithmique
41/115
L t t dL t t d
8/3/2019 Cour Algorithmique
42/115
Les structures deLes structures de
contrles(suite)contrles(suite) Exemple:
t < w VRAI5>6 FAUX2< 3 VRAI
Exercice: crire un algorithme qui demande un nombre
lutilisateur, et linforme ensuite si ce nombre
est positif ou ngatif (on laisse de ct le caso le nombre vaut zro).
03/01/2010 42
8/3/2019 Cour Algorithmique
43/115
contrles(suite)contrles(suite)
Conditions composes:Conditions composes: Certains problmes exigent parfois de formuler des
conditions composes lies entre eux par les
oprateurs logiques suivants : ET, OU, NON, etXOR. 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, oubien Condition2 est VRAI.
Mais si toutes les deux sont fausses, ou que toutes les deuxsont VRAI, alors le rsultat global est considr comme FAUX.
03/01/2010 43
8/3/2019 Cour Algorithmique
44/115
contrles(suite)contrles(suite)
le NON inverse une condition : NON(Condition1) estVRAI si Condition1 est FAUX, et il sera FAUX siCondition1 est VRAI.
tables de vrit (C1 et C2 reprsentent deux
conditions, et on envisage chaque fois les quatrecas possibles) :
CCCC1111 et Cet Cet Cet C2222 CCCC2222 VraiVraiVraiVrai CCCC2222 FauxFauxFauxFaux
03/01/2010 44
CCCC1111 VraiVraiVraiVrai Vrai Faux
CCCC1111 FauxFauxFauxFaux Faux Faux
CCCC1111 ou Cou Cou Cou C2222 CCCC2222 VraiVraiVraiVrai CCCC2222 FauxFauxFauxFaux
CCCC1111 VraiVraiVraiVrai Vrai Vrai
CCCC1111 FauxFauxFauxFaux Vrai Faux
es s ruc ures ees s ruc ures e
8/3/2019 Cour Algorithmique
45/115
contrles(suite)contrles(suite)
CCCC1111 xorxorxorxor CCCC2222 CCCC2222 VraiVraiVraiVrai CCCC2222 FauxFauxFauxFaux
CCCC1111 VraiVraiVraiVrai Faux Vrai
CCCC1111 FauxFauxFauxFaux Vrai Faux
Non CNon CNon CNon C1111
CCCC1111 VraiVraiVraiVrai Faux
xerc ce : crire un algorithme qui demande deuxnombres lutilisateur et linforme ensuite si
leur produit est ngatif ou positif (on laisse dect le cas o le produit est nul). Attentiontoutefois : on ne doit pas calculer le produitdes deux nombres.
03/01/2010 45
Exercices : structures deExercices : structures de
8/3/2019 Cour Algorithmique
46/115
contrlescontrles
Exercice 1: On dsire comparer deux valeurs ,crire un
algorithme qui affiche la plus grande des deux? Exercice 2:
crire un algorithme qui affiche le salaire brut dunouvrier sachant que les heures supplmentairesde 172 heures sont payes 50% de tarifsdhoraire en plus?
03/01/2010 46
Exercices : structures deExercices : structures de
8/3/2019 Cour Algorithmique
47/115
contrlescontrles Exercice 4:
Calculer le montant de la facture dun client ayantcommand une quantit dun 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 suprieur4500 DH
Exercice 5:Une bibliothque fait des rductions sur lachat deslivres : 25% pour les tudiants. 15% pour les enseignants
crire un algorithme qui calcule et affiche le prix payer03/01/2010 47
Exercices : structures deExercices : structures de
8/3/2019 Cour Algorithmique
48/115
contrlescontrles Exercice 6:
crire un algorithme qui calcule et affiche lemaximum de trois nombre A,B et C ?
Exercice 7:crire un algorithme qui permet de rsoudre qua on u prem er egr : a + =
Exercice 8:crire un algorithme qui permet de rsoudreune quation de second degr : aX+bX+c=0 ?
03/01/2010 48
8/3/2019 Cour Algorithmique
49/115
Les structures deLes structures de
8/3/2019 Cour Algorithmique
50/115
contrles(suite)contrles(suite) Le choix multipleLe choix multipleVariable i:entier;Variable i:entier;
Lire(i);Lire(i);Selon quei=i=11 :: faire
Ou que i=i=22 :: faire Ou que i=i=33 :: fairefaire
Autrement crire(mauvais choix)(mauvais choix)
Fselonque
03/01/2010 50
xerc ces : s ruc ures exerc ces : s ruc ures et lt l
8/3/2019 Cour Algorithmique
51/115
contrlescontrles
Exercice 10:crire un algorithme qui partir dun nombre
compris entre 1 et 7 affiche le jourcorrespendant?
03/01/2010 51
es structures ees structures el ( i )l ( i )
8/3/2019 Cour Algorithmique
52/115
contrles(suite)contrles(suite) Tests imbriqus:Tests imbriqus:
un algorithme doit donner ltat de leau selonsa temprature il doit choisir entre trois
rponses possibles (solide, liquide ou vapeur).Variable Temp : EntierDbut
n rez a emp ra ure e eau :
Lire (Temp)Si Temp 0 Et Temp < 100 Alors
Ecrire (Cest du liquide)FinsiSi (Temp > 100 )Alors
Ecrire Cest de la vapeurFinsi
Fin 03/01/2010 52
8/3/2019 Cour Algorithmique
53/115
es structures ees structures et l ( it )t l ( it )
8/3/2019 Cour Algorithmique
54/115
contrles(suite)contrles(suite)
Exercice:
crire un algorithme qui demande lge dunenfant lutilisateur. Ensuite, il linforme de sacatgorie :- Poussin de 6 7 ans- Pupille de 8 9 ans- Minime de 10 11 ans- Cadet aprs 12 ansPeut-on concevoir plusieurs algorithmesquivalents menant ce rsultat ?
03/01/2010 54
es s ruc ures ees s ruc ures econtrles(suite)contrles(suite)
8/3/2019 Cour Algorithmique
55/115
contrles(suite)contrles(suite) Variables Boolennes:Variables Boolennes:
Il existe des variables (les boolennes)susceptibles de stocker les valeurs VRAI ouFAUX. On peut donc entrer des conditionsdans ces variables, et tester ensuite la valeur
. Exemple:Exemple: Variable Temp : Entier
Variables A, B : Boolen
DbutEcrire (Entrez la temprature de leau :)Lire (Temp)A Temp
8/3/2019 Cour Algorithmique
56/115
contrles(suite)contrles(suite) Si A Alors
Ecrire( Cest de la glace)Sinon
Si B AlorsEcrire Cest du liquideSinon
cr re es e a vapeur
FinsiFinsiFin
Dans une condition compose employant la foisloprateur ET et loprateur OU, la prsence deparenthses possde une influence sur le rsultat.
03/01/2010 56
Exercice: Les structures deExercice: Les structures de
8/3/2019 Cour Algorithmique
57/115
contrlescontrles Ecrivez un algorithme qui lira au clavier
lheure et les minutes, et il afficheralheure quil sera une minute plus tard.
Par exem le si l'utilisateur ta e 21 uis
32, l'algorithme doit rpondre : "Dans uneminute, il sera 21 heure(s) 33". NB : on suppose que l'utilisateur entre une
heure valide. Pas besoin donc de lavrifier.
03/01/2010 57
Structure rptitiveStructure rptitive
8/3/2019 Cour Algorithmique
58/115
pp A quoi cela sert-il donc ?
Prenons le cas dune saisie au clavier (unelecture), o par exemple, le programme pose
une question laquelle lutilisateur doitrpondre par O (Oui) ou N (Non). Mais tt ou
, ,
que la rponse attendue. Alors, dans tout lalgorithme on met en place
ce quon appelle un contrle de saisie, afin
de vrifier que les donnes entres au claviercorrespondent bien celles attendues parlalgorithme.
03/01/2010 58
Structure rptitive(suite)Structure rptitive(suite)
8/3/2019 Cour Algorithmique
59/115
A quoi cela sert-il donc ? On pourrait essayer avec une structure de
contrle SI. Variable Rep : Caractre
Dbut
Lire (Rep)Si Rep O ET Rep N Alors
Ecrire( Saisie erronne. Recommencez)
Lire (Rep)FinSiFin
03/01/2010 59
Structure rptitive(suite)Structure rptitive(suite)
8/3/2019 Cour Algorithmique
60/115
A quoi cela sert-il donc ? Si lutilisateur ne se trompe quune seule fois,
et entre une valeur correcte la deuxime
demande, cest parfait. Par contre, sil commet une deuxime erreur, il
. ,
peut rajouter des centaines de SI, et crire unalgorithme lourd.
La solution consistant aligner des SI nest
pas correcte dans ce cas. La seule issue estdutiliser une structure de boucle.
03/01/2010 60
Structure rptitive(suite)Structure rptitive(suite)
8/3/2019 Cour Algorithmique
61/115
A quoi cela sert-il donc ? Qui ce prsente ainsi: TantQue boolen Faire
Instructions
FinTantQue
Le rinci e est sim le : lal orithme arrive sur la li ne du
TantQue. Il examine alors la valeur du boolen (qui, je lerappelle, peut tre une variable boolenne ou, plusfrquemment, une condition). Si cette valeur est VRAI,lalgorithme excute les instructions qui suivent, jusqu
ce quil rencontre la ligne FinTantQue. Il retourne ensuitesur la ligne du TantQue, procde au mme examen, etainsi de suite. Le cycle ne sarrte que lorsque le boolenprend la valeur FAUX.
03/01/2010 61
Structure rptitive(suite)Structure rptitive(suite)
8/3/2019 Cour Algorithmique
62/115
A quoi cela sert-il donc ? Illustration avec notre problme de contrle de
saisie. Une premire approximation de la solution
consiste crire :Variable Rep :Caractre
Ecrire (Voulez vous un caf ? (O/N))lire(Rep)TantQue Rep O ET Rep N Faire
Lire (Rep)FinTantQueFin
03/01/2010 62
Structure rptitive(suite)Structure rptitive(suite)
8/3/2019 Cour Algorithmique
63/115
A quoi cela sert-il donc ? Une deuxime approximation de la solution, avec
affectation, consiste crire :
Variable Rep :CaractreDbutRe X
Ecrire (Voulez vous un caf ? (O/N))TantQue Rep O ET Rep N FaireLire (Rep)
FinTantQue
Fin Cette manire de procder est connatre, car
elle est employe trs frquemment.
03/01/2010 63
Structure rptitive(suite)Structure rptitive(suite)
8/3/2019 Cour Algorithmique
64/115
Structure rptitive, dite aussi itrativeou boucle permet, de rpter une ouplusieurs actions un certain nombre de
fois. On identifie en rgle gnrale 3types de rptitive :
TantQue Rpter Jusqu' Pour
03/01/2010 64
Structure rptitive(suite)Structure rptitive(suite)
8/3/2019 Cour Algorithmique
65/115
Tant queTant que Les rptitives o la condition darrt
est place au dbut. Syntaxe ::
Tant que faire
FtantqueTantQue condition
actionsFTantQue
Ce qui signifie : tant que la condition est
vraie, on excute les actions.03/01/2010 65
Des Questions ?Des Questions ?
8/3/2019 Cour Algorithmique
66/115
Des Questions ?Des Questions ?
03/01/2010 66
ExercicesExercices
8/3/2019 Cour Algorithmique
67/115
1. Ecrire un algorithme qui demande lutilisateur unnombre compris entre 1 et 3 jusqu ce que larponse convienne.
2. Ecrire un algorithme qui demande un nombrecompris entre 10 et 20, jusqu ce que la rponseconvienne. En cas de rponse suprieure 20, onera appara re un message : us pe , e
inversement, Plus grand ! si le nombre estinfrieur 10.
3. crire un algorithme qui demande un nombre de
dpart, et qui ensuite affiche les dix nombressuivants. Par exemple, si l'utilisateur entre lenombre 17, le programme affichera les nombres de
18 27. 03/01/2010 67
Structure rptitive(suite)Structure rptitive(suite)
8/3/2019 Cour Algorithmique
68/115
Boucler en comptant, ou compter enBoucler en comptant, ou compter enbouclantbouclant Il arrive trs souvent quon ait besoin
deffectuer un nombre dtermin de passages.Or, a priori, notre structure TantQue ne saitpas lavance combien de tours de boucleelle va effectuer:
Cest pourquoi une autre structure de boucleest notre disposition : la structure : Pour
03/01/2010 68
Structure rptitive(suite)Structure rptitive(suite)
8/3/2019 Cour Algorithmique
69/115
Variable Num1 : EntierDbutNum1 0TantQue Num1 < 15 Faire
Num1 = Num1 + 1
Variable Num1 : EntierDbutPour Num1 = 1 15FaireEcrire( Passage
numro : , Num1)FinTantQueFin
num ro : , um
Num1 SuivantFin
03/01/2010 69
la structure :Pour est un cas particulier de TantQue :celui o le programmeur peut dnombrer lavance lenombre de tours de boucles ncessaires.
Structure rptitiveStructure rptitive
8/3/2019 Cour Algorithmique
70/115
Pour Les rptitives o le nombre ditration est
fixe une fois pour toute. Syntaxe : Pour Compteur = Initial Final Pas
ValeurDuPas
Instructions
Compteur suivant (nest pas indispensable)FPour
03/01/2010 70
Structure rptitive(suite)Structure rptitive(suite)
8/3/2019 Cour Algorithmique
71/115
la progression du compteur est laisse votre libredisposition. Dans la plupart des cas, on a besoin dunevariable qui augmente de 1 chaque tour de boucle. Onne prcise alors rien linstruction Pour ; celle-ci, par
dfaut, comprend quil va falloir procder cetteincrmentation de 1 chaque passage, en commenant
.
Si vous souhaitez une progression plus spciale, de 2en 2, ou de 3 en 3, ou en arrire, de 1 en 1, ou de 10en 10, il faut prciser votre instruction Pour en luirajoutant le mot Pas et la valeur de ce pas.
Quand on met un pas ngatif dans une boucle, la valeurinitiale du compteur doit tre suprieure sa valeurfinale si lon veut que la boucle tourne !
03/01/2010 71
Structure rptitive(suite)Structure rptitive(suite)
8/3/2019 Cour Algorithmique
72/115
Les structures TantQue sont employes dansles situations o lon doit procder untraitement sur les lments dun ensemble dont
on ne connat pas davance la quantit, commepar exemple :
. la gestion des tours dun jeu (tant que la partie
nest pas finie, on recommence).
Les structures Pour sont employes dans les
situations o lon doit procder un traitementsur les lments dun ensemble dont on connatdavance la quantit.
03/01/2010 72
Structure rptitive(suite)Structure rptitive(suite)
8/3/2019 Cour Algorithmique
73/115
Des boucles imbriques:Des boucles imbriques: De mme que quune structure SI ALORS
peut contenir dautres structures SI ALORS,
une boucle peut tout fait contenir dautresboucles.
ar a es um , um : n er
Pour Num1 1 15Ecrire (Il est pass par ici)
Pour Num2 1 6Ecrire (Il repassera par l)
FpourFPour
03/01/2010 73
Structure rptitive(suite)Structure rptitive(suite)
8/3/2019 Cour Algorithmique
74/115
Rpter..Jusqu :Rpter..Jusqu : la condition darrt est place la fin
Syntaxe :Rpter
Jusqu Frpter
Exemple :Num1:=1Rpter
Ecrire (Passage numro : , Num1)Num1 = Num1 + 1
Jusqu (Num1 >= 15 )
03/01/2010 74
Des Questions ?Des Questions ?
8/3/2019 Cour Algorithmique
75/115
s Q s ss Q s s
03/01/2010 75
ExercicesExercices
8/3/2019 Cour Algorithmique
76/115
1. crire un algorithme qui saisie N entier etaffiche leur somme et leur moyenne ?2. crire un algorithme pour calculer et afficher la
somme et la moyenne de100 premiers nombresentiers ?. ,
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/N03/01/2010 76
ExercicesExercices
8/3/2019 Cour Algorithmique
77/115
4. Ecrire un algorithme qui vrifie si unnombre est premier o pas ?5. crire un algorithme qui saisit deux entiers,
calcule et affiche la somme de ces 2 entiers(on arrte la saisie avec la valeur 0) ?
6. Ecrire un algorithme qui permet decalculer le factoriel dun nombre positif ?
03/01/2010 77
Devoir NDevoir N11 Une salle de cinma dsire automatiser la gestion de la
8/3/2019 Cour Algorithmique
78/115
Une salle de cinma dsire automatiser la gestion de labilletterie pour chaque client qui se prsente, on calcule leprix du billet en fonction des donnes suivantes: NF : Numro du film
Age : Age de spectateur Le prix normal de la facture est de 30 DH, cependant des
remises euvent tre accorder en fonction du critressuivants : NF=2 ou Age < 15 remise de 50%
NF=2 et Age >75 remise 25%
NF=3 et Age < 15 entre refuse
crire un algorithme qui permet de calculer et dcider leprix payer pou chaque client qui se prsente . on arrtela saisie par "non"
03/01/2010 78
Devoir NDevoir N22
8/3/2019 Cour Algorithmique
79/115
Une entreprise dsire automatise la gestion depaie de son personnel. Pour chaque employ,on doit introduire le nom, le prnom, le salaire debase(SB), le nombre d'enfant etl'anciennet(ANC).
n rix 1 DH r r
chaque enfant . Si anciennet
8/3/2019 Cour Algorithmique
80/115
Supposons que nous avons besoin decalculer la moyenne de 12 notes duntudiant.
la seule solution dont nous disposonsconsiste dclarer douze variables
appeles par exemple: X1, X2, X3,X12. La premire tape est de lire les valeurs
de toute ces variables une par une, ce qui
nous fait douze instructions de lecture etaprs calculer la moyenne par linstruction:
Moy (X1+X2+X3+X4+X5+NX6+X7+X8+X9+X10+X11+X12)/12
03/01/2010 80
Les tableaux(suite)Les tableaux(suite)
8/3/2019 Cour Algorithmique
81/115
Cest pourquoi lalgorithmique (laprogrammation) nous permet derassembler toutes ces variables en une
seule, au sein de laquelle chaque valeursera dsigne par un numro.
03/01/2010 81
Un ensemble de valeurs portant le mme nom de variable et repres parun nombre, sappelle un tableau, ou encore une variable indice.Le nombre qui, au sein dun tableau, sert reprer chaque valeursappelle lindice.
Chaque fois que lon doit dsigner un lment du tableau, on fait figurerle nom du tableau, suivi de lindice de llment, entre parenthses.Ex: Nom_tableau(5)
Les tableaux(suite)Les tableaux(suite)
8/3/2019 Cour Algorithmique
82/115
Notation et utilisation algorithmiqueNotation et utilisation algorithmique Dans notre exemple, nous crerons donc un
tableau appel Note. Tableau Note(12) : Entier On peut crer des tableaux contenant des
variables de tous types : tableaux denumriques, tableaux de caractres, tableauxde boolens, tableaux de tout ce qui existedans un langage donn comme type de
variables. Lnorme avantage des tableaux, cest quon
va pouvoir les traiter en faisant des boucles.03/01/2010 82
Les tableaux(suite)Les tableaux(suite)
8/3/2019 Cour Algorithmique
83/115
Notation et utilisation algorithmiqueNotation et utilisation algorithmiqueTableau Note(12) : EntierVariables i, Som : Entier
Variable Moy : RelPour i 0 11
Lire( Note(i))FPourSom 0
Pour i
0 11Som = Som + Note(i)Fpour
Moy = Som / 12 03/01/2010 83
Les tableaux(suite)Les tableaux(suite)
8/3/2019 Cour Algorithmique
84/115
Remarque gnrale : lindice qui sert dsigner les lments dun tableau peut treexprim directement comme un nombre en clair,mais il peut tre aussi une variable, ou uneexpression calcule.
La valeur dun indice doit tou ours :
tre gale au moins 0 (dans quelques rareslangages, le premier lment dun tableau portelindice 1). Mais nous avons choisi ici de commencerla numrotation des indices zro, comme cest le
cas en langage C. tre un nombre entier. Quel que soit le langage.
tre infrieure ou gale au nombre dlments du
tableau (moins 1, si lon commence la03/01/2010 84
ExercicesExercices
8/3/2019 Cour Algorithmique
85/115
crire un algorithme qui dclare etremplisse un tableau de 7 valeursnumriques en les mettant toutes zro.
crire un algorithme qui dclare etremplisse un tableau contenant les sixvoyelles de lalphabet latin.
On saisit des entiers et on les range dansun tableau (maximum 50) crire un
programme qui affiche le maximum, leminimum et la valeur moyenne de cesnombres.
03/01/2010 85
ExercicesExercices crivez un algorithme permettant
8/3/2019 Cour Algorithmique
86/115
lutilisateur de saisir un nombrequelconque de valeurs, qui devront tre
stockes dans un tableau. Lutilisateur doitdonc commencer par entrer le nombre de .
ensuite cette saisie. Enfin, une fois lasaisie termine, le programme affichera lenombre de valeurs ngatives et le nombrede valeurs positives.
03/01/2010 86
ExercicesExercices
8/3/2019 Cour Algorithmique
87/115
Que produit lalgorithme suivant ?Tableau Nb(6) : EntierVariable i en Entier
DbutPour i 0 5 *
FPourPour i 0 5crire Nb(i)
FPourFin
Peut-on simplifier cet algorithme avec le mme
rsultat ? 03/01/2010 87
ExercicesExercices
8/3/2019 Cour Algorithmique
88/115
Que produit lalgorithme suivant ?Tableau N(7) en EntierVariables i, k en Entier
DbutN(0) 1
N(k)
N(k-1) + 2FPourPour i 0 6
Ecrire N(i)FPourFin
Peut-on simplifier cet algorithme avec le mme03/01/2010 88
OrganigrammeOrganigramme
Dfi itiDfi iti
8/3/2019 Cour Algorithmique
89/115
DfinitionDfinition un organigramme est la reprsentation schmatique
qui permet de faire apparatre dune faon claire etlogique lenchanement des diffrentes oprations.
LesLes symbolessymboles utilissutiliss pourpour construireconstruire ununorganigrammeorganigramme
03/01/2010 89
Symbole dbut-fin-interruption
Symbole embranchement(choix)
Symbole commentaire
Les lignes deliaison
OrganigrammeOrganigramme
8/3/2019 Cour Algorithmique
90/115
Exemple :
Condition
03/01/2010 90
Instruction 1Instruction 2
suite
OrganigrammeOrganigramme
8/3/2019 Cour Algorithmique
91/115
Exemple :Le branchement conditionnelLe branchement conditionnel
conditio
03/01/2010 91
instruction1
n
instruction2
OrganigrammeOrganigramme
8/3/2019 Cour Algorithmique
92/115
Exemple :Structure rptitive
V
03/01/2010 92
instruction
condition
F
OrganigrammeOrganigramme
8/3/2019 Cour Algorithmique
93/115
Exemple : Structure rptitive
F
03/01/2010 93
instruction
condition
V
Notions de sousNotions de sous--algorithmealgorithme Dfinition
Un so s algorithme est n lment dalgorithme
8/3/2019 Cour Algorithmique
94/115
Un sous-algorithme est un lment dalgorithmenomm et ventuellement paramtr que lon dfinitafin de pouvoir ensuite lappeler par son nom en
affectant, sil y a lieu, des valeurs aux paramtres. Intrt :Intrt :
- . Effectuer une seule description dune tche commune Concevoir une application de manire descendante en
entrant de plus en plus dans les dtails
Structure :Structure : un sous-algorithme est compos
Dune tteDune tte nom sous-algorithme, paramtres(arguments)avec leur type Dun corpsDun corps des dclarations dobjets locaux aux sous-
algorithme, instructions excuter
03/01/2010 94
Notions de sousNotions de sous--algorithmealgorithme Sous-algorithme NomNom(liste des paramtres)
d l ti d i bl l l
8/3/2019 Cour Algorithmique
95/115
dclarations des variables localesDbut
Corps du sous-algorihtmeFin
Dclaration des variablesDbut
Instructions
Appel du sous-algorithmeInstructions
Fin03/01/2010 95
Procdures & FonctionsProcdures & Fonctions
P dP d
8/3/2019 Cour Algorithmique
96/115
ProcduresProcdures Syntaxe
Procdure nom_procdure(var:type;var:type)Variable interne
InstructionsFinprocdure
03/01/2010 96
Procdures & FonctionsProcdures & Fonctions
FonctionsFonctions
8/3/2019 Cour Algorithmique
97/115
FonctionsFonctions Syntaxe
Fonction nom_fonction(var:type;var:type):type
Variable interne;Dbut fonction
Instructions;
Retourner variable;Fin fonction
03/01/2010 97
Procdure & FonctionProcdure & FonctionRep1,Rep2 : caractre
Fonction RepOuiNon() : caractres
8/3/2019 Cour Algorithmique
98/115
Fonction RepOuiNon() : caractresvariable Rep ""
TantQue Rep "Oui" et Rep "Non"
Ecrire( "Tapez Oui ou Non")Lire (Rep)
FinTantQue
Renvoyer Rep
FinDbut
Ecrire( "Etes-vous mari ?")
Rep1
RepOuiNon()Ecrire( "Avez-vous des enfants ?" )
Rep2 RepOuiNon()
Fin03/01/2010 98
8/3/2019 Cour Algorithmique
99/115
EXERCICESEXERCICES
03/01/2010 99
ExercicesExercices EX0
Ecrire un algorithme qui lit une valeur qlq x et qui
8/3/2019 Cour Algorithmique
100/115
Ecrire un algorithme qui lit une valeur qlq x et quidtermine la valeur de lexpression :
1+x+x
2
++x
20
EX1 cr re une proc ure qu men s en
paramtre et retourne la somme de ceslments dans une variable somme.
EX2 Ecrire une fonction entire statistique qui lit
100 notes et retourne le nombre de notescomprises entre 10 et 20 compris
03/01/2010 100
ExercicesExercices
EX3
8/3/2019 Cour Algorithmique
101/115
EX3 Ecrire un algorithme qui permet de faire les
traitements suivants :
Soit un tableau T de N entiers1. Rem lir les N cases du tableau
2. Compter le nombre des lments non nuls3. Trouver le plus grand lments du tableauet le mettre dans la variable MAX
4. Rechercher la place du plus petit lment etle mettre dans la variable position.
03/01/2010 101
ExercicesExercices EX4
Ecrire un algorithme qui cherche dans un
8/3/2019 Cour Algorithmique
102/115
Ecrire un algorithme qui cherche dans untableau non tri si un nombre xexiste aumoins une fois.
EX5
tableau tri si un nombrex
existe au moinsune fois.
EX6
Ecrire un algorithme qui permet de lire lesges de 25 stagiaires(ils ont au moins 23anset au plus 30ans) et fournit le nombre destagiaires de chacun des ges.
03/01/2010 102
ExercicesExercices EX7
Le tableau factures contient N constantes de
8/3/2019 Cour Algorithmique
103/115
Le tableau factures contient N constantes defactures, le tableau PAYES de N boolensindique si chacune des factures a t rgles ou
pas, on veut recopier squentiellement dans un3me tableau RESTESAPAYES, les sommesrestant dues.
03/01/2010 103
RcursivitRcursivit
Un algorithme est dit rcursiflorsquil intervientdans sa description cest--dire lorsquil est
8/3/2019 Cour Algorithmique
104/115
Un algorithme est dit lorsqu il intervientdans sa description, c est dire lorsqu il estdfini en fonction de lui-mme.
Exemple: x0
= 1, xn
= x*xn-1
si n1
Fonction fact(x: entier, n: entier):entier
Dbut
Si(n=0) alors
Rsultat =1;
Sinon
Rsultat = x*fact(x,n-1);Fsi
Renvoyer Rsultat;
Fin03/01/2010 104
MTHODES DE TRIMTHODES DE TRILMENTAIRESLMENTAIRES
8/3/2019 Cour Algorithmique
105/115
Dfinition
Tri par slectionTri par bullesTri par insertion
03/01/2010 105
DfinitionDfinition
trier signifie rpartir en plusieursl l i i
8/3/2019 Cour Algorithmique
106/115
trier signifie rpartir en plusieursclasses selon certains critres . De manire plus restrictive, le terme de
tri en algorithmique est trs souvent'
ensemble d'lments dans un ordre donn. Par exemple, trier N entiers dans l'ordre
croissant, ou N noms dans l'ordre
alphabtique. Tout ensemble muni d'un ordre total peut
fournir une suite d'lments trier.03/01/2010 106
Tri par slectionTri par slection
Tri par slection est lun des algorithmesde tri les plus simple elle procde la
8/3/2019 Cour Algorithmique
107/115
Tri par slection est l un des algorithmesde tri les plus simple, elle procde laslection successive de llment
minimal parmi ceux restant. Il fonctionnede la manire suivante : On commence par rechercher llment de
plus petite valeur du tableau pour lchangeravec celui en premire position.
On recherche ensuite llment ayant ladeuxime plus petite valeur pour lchangeravec celui en deuxime position, et loncontinue ainsi jusqu ce que le tableau soit
03/01/2010 107
Tri par slection(suite)Tri par slection(suite) Le sous-algorithme suivant est une implantation de ce processus.
Pour tout i entre1
et N-1
, on change T[i] avec llment de valeurminimal parmi T[i].T[N] :
8/3/2019 Cour Algorithmique
108/115
Pocdure TriSelectionTriSelection(T: 1N: entier; N: entier)
Var i, j, min, q:entier;
Dbutpour i de 1jusqu N faire
=
pour j de i+1jusqu N faire
Si(T[j]
8/3/2019 Cour Algorithmique
109/115
p p qsoit l ordre du tableau initial, le nombre de comparaisonsreste le mme, ainsi que le nombre d'changes. chaque itration, on considre l'lment tab[i] et on lecompare successivement tab[i+1], ..., tab[N]. On faitdonc 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
slection est en O (N2), la fois dans le meilleur des cas,
en moyenne et dans le pire des cas, c'est--dire que sontemps d'excution est de l'ordre du carr du nombred'lments trier.
03/01/2010 109
Tri par bulleTri par bulle Le tri bulle est une variante du tri par slection.
Il consiste parcourir le tableau tab en permutant
8/3/2019 Cour Algorithmique
110/115
p ptoute paire d'lments conscutifs (tab[k],tab[k+1])non ordonns - ce qui est un change et ncessite
donc encore une variable intermdiaire de typeentier. Aprs le premier parcours, le plus grandlment se retrouve dans la dernire case du
tableau, en tab[N], et il reste donc appliquer lamme procdure sur le tableau compos deslments tab[1], ..., tab[N-1]. Le nom de ce tri
provient du dplacement des bulles les plusgrandes vers la droite.
03/01/2010 110
Tri par bulle(suite)Tri par bulle(suite)/* Procdure de tri bulle */
procedure triBulle(entier[] tab)
8/3/2019 Cour Algorithmique
111/115
p ocedu e t u e(e t e [] tab)entier i, k; entier tmp;
pour (i de N 2 en dcrmentant de 1) fairepour (k de 1 i-1 en incrmentant de 1) faire
si (tab[k] > tab[k+1]) alors
tmp
8/3/2019 Cour Algorithmique
112/115
Le nombre d'changes quant lui dpend de l'ordre deslments dans le tableau :
dans le meilleur des cas, le tableau initial est tri et il n'y a pasd'change faire ;
en moyenne, on montre ue le nombre d'changes est de :
dans le pire des cas, les entiers du tableau sont initialement
donns dans l'ordre dcroissant. Dans ce cas, on effectuel'change chaque comparaison, c'est--dire que le nombred'changes est alors de :
Quoi qu'il en soit, la complexit du tri bulle reste en O (N2),c'est--dire du mme ordre de grandeur que le carr dunombre d'lments.
03/01/2010 112
Tri par insertionTri par insertion Cette mthode de tri est trs diffrente de la mthode de tri
par slection et s'apparente celle utilise pour trier sescartes dans un jeu : on prend une carte tab[1] puis la
8/3/2019 Cour Algorithmique
113/115
cartes dans un jeu : on prend une carte, tab[1], puis ladeuxime, tab[2], que l'on place en fonction de la premire,ensuite la troisime tab[3] que l'on insre sa place enfonction des deux premires et ainsi de suite. Le principegnral est donc de considrer que les (i-1) premirescartes, tab[1],..., tab[i-1] sont tries et de placer la ie carte,
tab[i], sa place parmi les (i-1) dj tries, et ce jusqu' ceque i = N.
Pour placer tab[i], on utilise une variable intermdiaire tmppour conserver sa valeur qu'on compare successivement chaque lment tab[i-1],tab[i-2],... qu'on dplace vers ladroite tant que sa valeur est suprieure celle de tmp. Onaffecte alors l'emplacement dans le tableau laiss libre
par ce dcalage la valeur de tmp.03/01/2010 113
Tri par insertion(suite)Tri par insertion(suite)
/* Procdure de tri par insertion */procedure triInsertion(entier[] tab)
8/3/2019 Cour Algorithmique
114/115
pprocedure triInsertion(entier[] tab)
entier i, k,tmp;pour (i de 2 N en incrmentant de 1) faire
k 1 et tab[k - 1] > tmp) fairetab[k]
8/3/2019 Cour Algorithmique
115/115
fortement dpendante de l'ordre du tableau initial.Nous comptons ici le nombre de comparaisons (qui
est le nombre de dcalages un prs) : 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 :
03/01/2010 115