Cour Algorithmique

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