Algorithmique 2

Issu de : http://www.est-usmba.ac.ma/ALGORITHME/co/module_ALGORITHME_3.html

I. DÉFINITION

INTRODUCTION

Le mot algorithme est issu de la transcription phonétique de al-Kwharizmi.

Al-Kwharizmi, (783-850) est un grand mathématicien et astronome perse.

Son apport en mathématiques fut tel qu'il est également surnommé « le père de l'algèbre »,

Définition :

Selon le LAROUSSE, la définition d'algorithme est « un ensemble de règles opératoires dont l'enchaînement permet de résoudre un problème au moyen d'un nombre fini d'opérations. »

Quelques points importants :

• Un algorithme décrit un traitement sur un ensemble fini de données de nature simple (nombres ou caractères), ou plus complexes (données structurées)
• Un algorithme est constitué d'un ensemble fini d'actions composées d'opérations ou actions élémentaires. Ces actions élémentaires doivent être effectives (réalisable par la machine), non ambiguës.
• Un algorithme doit toujours se terminer après un nombre fini d'opérations.
• L'expression d'un algorithme nécessite un langage clair (compréhension) structuré (enchaînements d'opérations) non ambiguë, universel (indépendants du langage de programmation choisi)

Syntaxe : STRUCTURE D'UN ALGORITHME

Un algorithme est constitué

• d'un entête composé du MOT Réservé ALGORITHME et d'un nom de l'algorithme à réaliser
• d'une zone de déclaration des identificateurs (variables) utilisés dans l'algorithme
• et d'un corps délimité par deux mots réservés DEBUT et FIN. C'est ici qu'on écrit les actions de l'algorithme

ALGORITHME <NOM>

<Déclaration des variables>

DEBUT

<Actions>

FIN

II. NOTIONS D'OBJETS

Introduction

Un algorithme ou une action manipule des données pour obtenir un résultat.

Pour cela on manipule des objets simples ou structurés.

Un objet va être caractérisé par :

• un identificateur (son nom) : pour le désigner cet identificateur doit être parlant : q=quotient; Moy=Moyenne; ADR=Adresse...
• Un type (nature de l'objet : entier, caractère...) simple ou structuré. Un type détermine en particulier les valeurs possibles de l'objet et les opérations primitives applicables à l'objet.

Exemple q: ENTIER ; Moy :REEL;

CAR : CARACTERE ; Adresse: CHAINE (‘suite de caractères')

• Une valeur (contenu de l'objet) unique. Cette valeur peut varier au cours de l'algorithme ou d'une exécution à l'autre : ces objets sont des variables.

Dans les cas contraires (valeur fixe) ce sont des constantes.

Tous les objets manipulés par un algorithme doivent être clairement définis :

Mots clefs

VAR a, b : ENTIER

x, y : CARACTERE

a, b, x, y sont des identificateurs

1. Constantes et variables

On sépare les objets en deux classes : les constantes et les variables.

Une constante est un objet dont l'état reste inchangé durant toute l'exécution d'un programme. On ne peut jamais modifier sa valeur et celle-ci doit donc être précisée lors de la définition de l'objet.

CONST PI=3.14

NOM="PASCAL"

Une variable est un objet dont le contenu peut être modifié par une action.

Les types les plus utilisées sont:

ENTIER: Pour représenter les nombres entiers

Les opérations utilisables sur les entiers sont :

· les opérateurs arithmétiques classiques : + (addition), - (soustraction), * (produit)

· la division entière, notée ÷ ou DIV : n DIV p donne la partie entière du quotient de la division entière de n par p

· le modulo, (MOD) : n MOD p donne le reste de la division entière de n par p

· les opérateurs de comparaison classiques : <, >, =, ...

REEL : Pour représenter les nombres réels.

Les opérations utilisables sur les réels sont :

· les opérations arithmétiques classiques : + (addition), - (soustraction), * (produit), / (division)

· les opérateurs de comparaison classiques : <, >, =, ...

Exemples

VAR Classement : ENTIER

Moyenne : REEL

2. Type logique

Une variable de type logique (booléen) peut prendre deux valeurs VRAIE ou FAUSSE.

Exemple :

VAR EXISTE :BOOLEEN

EXISTE VRAIE

Les opérations principales les plus utilisées sont :

• Les opérateurs logiques: NON, ET , OU

Tables de vérité

A B A ET B A OU B

FAUX FAUX FAUX FAUX

FAUX VRAI FAUX VRAI

VRAI FAUX FAUX VRAI

VRAI VRAI VRAI VRAI

A NON A

FAUX VRAI

VRAI FAUX

Exemple :

VAR A , B , TROUVE :BOOLEEN

TROUVE   (A ET B)

• Opérateurs de comparaison : = , ≤ , ≥ , ≠

VAR X,Y :REEL

SUP :BOOLEEN

SUP (X > Y)

3. Type CARACTERE

Il s'agit du domaine constitué des caractères alphabétiques et numériques . Une variable de ce type ne peut contenir qu'un seul et unique caractère. Les opérations élémentaires réalisables sont les comparaisons : <, >, =, ...

Exemple :

Var C : CARACTERE

C ‘A'

Ensemble de définition : la table ASCII

Complément :

NB : il existe d'autres Opérations sur les caractères :

· SUCC(c) : caractère suivant dans la table ASCII ;

· PRED(c) : caractère précédent dans la table ASCII.

4. Type CHAINE DE CARACTERE

Une chaine de caractère est un objet qui peut contenir plusieurs caractères de manière ordonnée.

Exemple :

VAR NOM : CHAINE[30] → Chaine de 30 caractères maximum

ADRESSE : CHAINE → Chaine de 128 caractères maximum

5. Type énumérés

Un type énuméré est un type permettant de représenter des objets pouvant prendre leur valeur dans une liste finie et ordonnée de noms.

Exemple :

TYPE SEMAINE=(lundi, mardi, mercredi, jeudi, vendredi, samedi, dimanche)

TYPE COULEUR=(rouge, vert, bleu)

6. Type intervalles

Un type intervalle est un type dont les objets prennent leur valeur dans une portion de l'intervalle des valeurs d'un autre type (entier, énuméré ou caractère).

Exemple : NBRE=0..99

OUVRABLE=lundi..vendredi

7. Type structurés

Une structure est un objet contenant un ensemble d'objets de types différents, appelés champs. Un type doit donc décrire l'ensemble des champs contenus dans ses objets.

Syntaxe :

STRUCTURE <NOM>

{ champ1 : type

champ2 : type

....

}

Exemple :

STRUCTURE ETUDIANT

{ NOM : CHAINE

NOTE : REEL

Classement :ENTIER

}

La principale opération définie sur ce type STRUCTURE est l'accès aux champs qui le compose.

VAR ETUD : ETUDIANT

DEBUT

ETUD.NOM "MOUJTAHID"

ETUD.NOTE 19.5

ETUD.Classement 1

FIN

Pour accéder au champ NOM de l'étudiant: ETUD.NOM

8. Type pointeur

Un pointeur est une adresse mémoire: il permet de désigner directement une zone de la mémoire et donc l'objet dont la valeur est rangée à cet endroit.

Un pointeur est souvent typé de manière à préciser quel type d'objet il désigne dans la mémoire.

Un type pointeur est défini par le symbole ^ suivi par le nom du type de l'objet pointé:

VAR P1: ^ENTIER ! ! ! ! ! !

ET1: ^ETUDIANT

• $0100= (0100)₁₆ dans la base 16
• P1 est l'adresse ($0100) ;

son contenu est la valeur $1020

• A sa création un pointeur contient une valeur qui ne représente rien (NUL).
• Pour désigner l'objet pointé par un pointeur, il suffit d'utiliser l'opérateur ^ après le nom de l'objet pointeur.
• On utilise l'opérateur @ pour obtenir l'adresse d'une variable déjà existante.

Exemple:

ALGORITHME ESSAI

VAR P :^ENTIER

E : ENTIER

DEBUT

E <- 1 (* E=1*)

P <- @E (* On met dans P l'adresse de E → E est l'objet pointé par P *)

P^ <- 2 (* On met dans l'objet pointé par P la valeur 2 → E=2 *)

FIN

III. ACTIONS ÉLÉMENTAIRES

Introduction

les actions élémentaires sont des opérations simples, directement utilisables.

1. Affectation

Définition :

L'affectation permet de donner une valeur à une variable .

A <- 28 « reçoit » Si A avait une valeur auparavant, cette valeur disparaît : elle est écrasé par 28

Fondamental :

Format général :

<id_variable> <expression>

A <- 28+13

A « l'exécution » : l'expression est évaluée (calculée) et sa valeur est rangée dans la variable.

Donc les types <id_variable> et <expression> doivent être compatibles.

Exemple :

Attention : A <- B+3

B doit avoir une valeur. Or au début d'une action, les variables ont une valeur indéterminée . B doit avoir été initialisé.

Remarque :

La notion de littéral : A <- 28

28 est un objet caractérisé par son type (entier [numérique]), son nom (sa valeur), et sa valeur (28)

Le littéral est l'objet « constante », le nom est sa valeur

On note les littéraux de type caractère entre quotte ‘A'.

On note les littéraux de type chaîne de caractères entre double quotte : ‘'bonjour''

2. Les opérations entrées / sorties

Définition :

Elles permettent de récupérer une valeur venant de l'extérieur (lecture) ou de transmettre une valeur à l'extérieur (écriture).

Exemple :

Lecture : saisie (entrée) par clavier

Ecriture : Affichage sur écran (Moniteur)

Exemple :

VAR A, B, C : ENTIER

DEBUT

LIRE (A, B)

C <- A+B

ECRIRE(C)

FIN

OU

(Variable C en moins ! !)→

VAR A, B : ENTIER

DEBUT

LIRE (A, B)

ECRIRE (A+B)

FIN

IV. LES STRUCTURES DE CONTRÔLE CONDITIONNELLES

Introduction

Une action décrit un enchaînement d'actions élémentaires. L'enchaînement est décrit par les structures de contrôle.

Une structure de contrôle déjà vue c'est l'enchaînement séquentiel :

LIRE (A, B)

C <- 2*A + B

Deux actions élémentaires : Lecture et affectation

La plupart des autres structures de contrôle utilise la notion de condition (expression booléenne) :

Une condition a une valeur qui est, soit vraie, soit fausse.

Pour déterminer la réalité de cette valeur on utilise :

• les opérateurs de comparaisons = , ≤ , ≥ , ≠
• les opérateurs booléens (logique) : ET, OU, NON

1. L'alternative SI-ALORS-SINON

Définition :

Elle permet d'effectuer tel ou tel traitement en fonction de la valeur d'une condition.

Syntaxe :

Alternative SI_ALORS :

Syntaxe :

SI <condition>

ALORS < action _alors>

FINSI

Organigramme : Alternative SI_ALORS.

Syntaxe :

Alternative SI_ALORS_SINON:

Syntaxe :

SI <condition>

ALORS < action _alors>

SINON < action _SINON>

FINSI

Organigramme : Alternative SI_ALORS_SINON

Exemple :

ALGORITHME resultat

VAR note  :REEL

DEBUT

LIRE (note)

SI note ≥ 10

ALORS ECRIRE(‘'Admis'' )

SINON ECRIRE(‘'Ajourné'')

FINSI

FIN

Méthode :

Principe de fonctionnement :

1 : la condition est évaluée

2 : Si la condition a la valeur vraie on exécute <action_alors>

Si la condition a la valeur fausse on exécute <action_sinon>

Remarque :

Les <action_alors> ou <action_sinon> peuvent être soit :

• des actions élémentaires
• des composées (bloc)

Dans ce cas on utilise les structures imbriquées.

Exemple de structure imbriquée:

SI (A ≥ 10)

ALORS

• SI ( A ≥ 12)

ALORS ECRIRE (‘'Admis mention'')

SINON ECRIRE (‘'Admis passable'')

FINSI

SINON ECRIRE (‘'Ajourné'')

FINSI

2. Structure à choix multiples SELON-QUE

Syntaxe :

La structure SELONQUE permet d'effectuer tel ou tel traitement en fonction de la valeur des conditions 1ou 2 ou ..n .

Syntaxe :

SELONQUE

<condition 1> : <action 1>

<condition 2> : <action 2>

...

<condition n> : <action n>

SINON : <action_sinon>

FINSELONQUE

Méthode :

Fonctionnement :

1 : la condition 1 est évaluée :

• Si la condition 1 est vraie, alors on exécute l'action correspondante et on quitte la structure selon-que

• Si la condition 1 est fausse, on évalue la condition 2...et ainsi de suite.

2.Si aucune n'est vraie on effectue l'action sinon ( au cas où l'action sinon n'existe pas alors aucune action n'est exécutée !).

Exemple :

SELONQUE

Note ≥ 16 : ECRIRE (‘'TB'')

Note ≥ 14 : ECRIRE (‘'B'')

Note ≥ 12 : ECRIRE (‘'AB'')

Note ≥ 10 : ECRIRE (‘'Passable'')

SINON : ECRIRE (‘'ajourné'')

FINSELONQUE

Remarque :

NB :

En programmation, cette structure peut exister mais avec une forme ou un fonctionnement éventuellement différent. Si elle n'existe pas, il faut se souvenir que, en fait, SELONQUE est un raccourci d'écriture pour des SI imbriqués.

V. STRUCTURES RÉPÉTITIVES

Introduction

Idée : répéter un ensemble d'opérations, arrêter la répétition en fonction d'une condition

1. Structure TANTQUE

Syntaxe :

TANTQUE <condition>

FAIRE

<actions>

FINTANTQUE

Ces actions peuvent être simples ou composées ! !

Exemple :

i 1

TANTQUE ( i≤5)

FAIRE

ECRIRE (i*i)

i i+1

FINTANTQUE

Question : Qu'est ce qu'il fait la programme ?

Remarque :

Le contenu de la structure TANTQUE peut ne jamais être exécuté. Donc cette structure permet en réalité de répéter un traitement 0, 1 ou plusieurs fois.

La condition étant évaluée au début, les variables utilisées dans la condition doivent avoir été initialisées.

On doit s'assurer de la terminaison (sinon le programme ne se termine jamais)

Pour cela, il faut nécessairement que dans le corps de la structure, la condition soit modifiée quelque part.

2. Structure REPETER

Syntaxe :

REPETER

<actions simples>

JUSQU'A <condition>

Fonctionnement :

1. on exécute le corps
2. on évalue la condition , puis

• si la condition est vraie : on quitte le REPETER
• si la condition est fausse on recommence

Remarque :

Il y a toujours au moins une exécution du corps. La structure REPETER permet de répéter un traitement 1 ou plusieurs fois.

Pour choisir entre REPETER et tant que il faut se poser la question : faut-il éventuellement ne jamais faire le traitement ? Si oui : il faut utiliser tant que, sinon utiliser la structure REPETER qui exécute au moins une fois l'action.

NB : Attention, en C++ :

La structure est do...while : c'est à dire Faire...TANTQUE . Alors que la structure algorithmique est répéter...jusqu'à.

C'est à dire qu'en C++ on exécute l'action tant qu'une condition est vraie alors qu'en algorithme on exécute une action tant que la condition est fausse, c'est à dire jusqu'à ce que la condition inverse soit vraie.

BOUCLE TANQUE

BOUCLE REPETER

3. Structure POUR

Définition :

Il est fréquent que le nombre de répétitions soit connu à l'avance, et que l'on ait besoin d'utiliser le numéro de l'itération afin d'effectuer des calculs ou des tests. Le mécanisme permettant cela est la boucle POUR.

Cette boucle permet de parcourir un intervalle en répétant un traitement pour chacune des valeurs de cet intervalle

Syntaxe :

Syntaxe :

POUR <id_variable> DE <val_inférieure> A <val_supérieure>

[ PAR PAS de <val_pas>] →facultatif

FAIRE <actions>

FINPOUR

Les actions peuvent être simples ou composées.

Méthode :

Fonctionnement :

1 : Automatiquement, on a id_variable ≤ val_inférieure

Donc, on n'a pas besoin d'initialiser, la structure se charge de la faire

2 : id_variable > val_supérieure ? :

Si oui alors STOP, on quitte la structure

Sinon :

• on exécute le programme
• automatiquement, l'incrémentation se fait (+1 ou + pas si l'on a définit un pas particulier, par défaut, le Pas est 1)
• on remonte au début du 2 pour tester la condition id_variable > val_supérieure ?

Remarque :

Remarques :

• Il est possible que l'action ne soit jamais exécutée.
• Il est possible aussi d'avoir un intervalle inversé à condition d'avoir un pas négatif.

IMPORTANT : Il est absolument interdit de modifier <id_variable>, <val_inférieure>, <val_supérieure>, <val_pas> dans le corps de boucle.

Parfois cette structure n'est pas présente dans un langage de programmation, il faut donc retenir que ce n'est qu'un raccourci pour écrire des TANTQUE (ou REPETER).

Boucle_Pour

Utilisation du POUR :

On s'en sert dès que l'on connaît au début de la boucle le nombre de répétitions à effectuer.

Dans les cas contraires, on utilisera des TANTQUE ou des REPETER

VI. PROCEDURES ET FONCTIONS

Introduction

Lorsque l'on développe un programme et que le problème à résoudre est complexe, le nombre d'instruction devient vite important. Il est nécessaire de l'organiser (Modularité)Il suffit de regrouper sous un même nom les instructions agissant dans le même but.

On distingue :

· les Procédures qui réalisent un traitement (lecture d'un complexe, tri du fichier étudiant)

· les Fonctions qui effectuent un calcul et retournent un résultat

Les fonctions et les procédures peuvent être appelées plusieurs fois à partir du programme principal ou à partir d'autres fonctions en recevant à chaque fois des paramètres ayant des valeurs différentes. Les Fonctions et les Procédures sont donc des moyens de réutilisation de portions de code.

Les Fonctions et les procédures sont parfois appelées des sous-programmes

1. Syntaxe d'une fonction/Procédure

Syntaxe : SYNTAXE D'UNE FONCTION

FONCTION <nom_fonction> ( <liste des paramètres> ) : <type de résultat>

< déclaration des objets locaux à la fonction>

DEBUT

{ corps de la fonction}

RETOURNER(résultat)

FIN

Exemple :

Exemple:

FONCTION perimetre_rectangle (largeur, longueur : ENTIER) : ENTIER

DEBUT

RETOURNER (2*(largeur+longueur))

FIN

Syntaxe : SYNTAXE D'UNE PROCEDURE

PROCEDURE <nom_procedure>( <liste des paramètres> )

< déclaration des objets locaux de la procedure>

DEBUT

{corps de la procedure}

FIN

Exemple :

2. Fonction et de procédure qui fait appel à une fonction

Maintenant, on peut créer la procédure qui détermine le maximum et le minimum de trois entiers, en faisant appel à la fonction max3 :

Remarques :

x, y, z sont les paramètres formels de la fonction max3(x,y,z).

Ce sont des paramètres d'entrées : lors de l'appel de la fonction max3, les valeurs des arguments d'appel (ici : a, b, c) ou (-a, -b, -c)) sont transmises aux paramètres x, y, z en fonction de leur ordre.

Les arguments sont des expressions (par exemple : max max3 (2*a+b, c-b, a*c)) qui sont évaluées à l'appel. Leur valeur est transmise aux paramètres.

Naturellement, le type des expressions doit être compatible avec le type des paramètres.

3. Modes de transmission des paramètres

Définition :

Il existe deux modes de transmission des paramètres:

• Par valeur: le paramètre transmis n'est jamais affecté par les modifications dans la procédure ou la fonction (on ne récupère pas les résultats !)
• Par adresse (référence) : le paramètre transmis dans ce cas peut être modifié et on récupère les résultats.

4. Récursivité

Définition :

La récursivité consiste à remplacer une boucle par un appel à la fonction elle-même.

Exemple : Factorielle

Considérons la suite factorielle, elle est définie par :

0!=1

n!=n(n-1)!

La fonction peut s'écrire simplement:

Prenons l'exemple pour n=3, on a le déroulement suivant :

VII . STRUCTURES DE DONNÉES : LES TABLEAUX

1. DEFINITIONS

Un tableau est un ensemble de même type indicé par un ensemble non vide d'indices, permettant un accès direct à chacun des objets.

La contrepartie de cette possibilité d'accès direct est que le tableau doit être contigu en mémoire: L'adresse d'un objet peut alors facilement être calculée à partir de l'adresse de départ du tableau, de l'indice de l'objet et de la taille de chaque objet.

Syntaxe :

nom_tableau : TABLEAU[min_indice..max_indice] DE <type_predefini>;

• ce qui signifie que les éléments ont pour type le type_predefini
• les indices des éléments vont de min_indice à max_indice,
• avec min_indice < max_indice,

NB: on peut déclarer un tableau de N valeurs comme ceci:

nom_tableau: TABLEAU[ N ] DE <type_predefini>

Exemple :

Exemple de tableau de 5 entiers

T :TABLEAU [5] d' ENTIER

• T signifie que c'est un objet de type TABLEAU.
• Les numéros en indices 1, 2, 3, 4, 5 correspondent aux valeurs colonnes.
• Le contenu de T : les 5 entiers (dans un certain ordre)
• La première valeur est T[1] où 1 correspond donc à l'indice de la première colonne.

Définition : Définition d'un TYPE de TABLEAU

TYPE <Nom> = <description>

Exemple : déclaration d'un nouveau type Mot, tableau de 10 caractères

TYPE MOT = TABLEAU [10 ] DE CARACTERE

VAR nom, verbe : MOT

Définition : TABLEAU Multi-dimension:

On peut aussi avoir un tableau de dimension NxM (N lignes, M colonnes)

à Compléter ! ! !

Exemple :

Tableau à deux dimensions ( 2x M)

Déclaration :

T:TABLEAU[1..2,1..M] D'ENTIER

2. Fonctions les plus utilisées dans un tableau

Parmi les traitements opérant sur des tableaux on peut:

· créer des tableaux

· ranger (Saisir) des valeurs dans un tableau

· récupérer, consulter des valeurs rangées dans un tableau

· rechercher si une valeur est dans un tableau

· mettre à jour des valeurs dans un tableau

· modifier la façon dont les valeurs sont rangées dans un tableau (par exemple : les trier de différentes manières)

· effectuer des opérations entre tableaux : comparaison de tableaux, addition multiplication,...

Dans la suite du cours on déclare un type de tableau TABL de cette manière:

TYPE TABL= TABLEAU [TAILLE] D' ENTIER

TAILLE est la constante qui indique le nombre de case du tableau.

Voila quelques fonctions qui seront fréquemment utilisées

Exemple : Procédure saisie d'un tableau:

PROCEDURE SAISIE_Tab(VAR T: TABL; N:ENTIER)

VAR i: ENTIER

DEBUT

POUR i DE 1 A N

FAIRE LIRE(T[i])

FINPOUR

FIN

Cette PROCEDURE permet de rentrer(saisir) les variables dans un tableau.

NB: on désigne le tableau par T et N par le nombre de colonnes, ainsi, même si l'on a déclaré auparavant un tableau à 50 colonnes et que l'on n'utilise en fait que 30 colonnes, N=30 permet de définir à l'ordinateur le nombre de colonnes réellement utilisées et limiter la durée du traitement. N est donc indépendant de TAILLE( mais N≤ TAILLE).

Exemple : Procédure d'affichage d'un tableau :

PROCEDURE AFFICH_Tab(T: TABL; N:ENTIER)

VAR i: ENTIER

DEBUT

POUR i DE 1 A N

FAIRE ECRIRE(T [i])

FINPOUR

FIN

Exemple : Recherche du minimum d'un tableau

FONCTION Mintableau (T :TABL,N: ENTIER) : ENTIER

VAR i:ENTIER

Min :ENTIER

DEBUT

Min  T[1]

POUR i DE 2 A N

FAIRE

SI T[i] < Min ALORS

Min T[i]

FINSI

FINPOUR

RETOURNER(Min)

FIN

3. Tri d'un tableau

Introduction

Trier des objets est à la fois un problème fondamental de l'algorithmique, comme étape de prétraitement d'algorithmes plus complexes ou pour ordonner des structures de données (à quoi servirait un annuaire non trié ?)... et une bonne illustration de différents paradigmes de programmation (diviser pour régner)

Déterminer si un tableau est trié ?

Première proposition :

FONCTION est_trié (T : TABL N : ENTIER) : BOOLEEN

VAR i : ENTIER

DEBUT

i <- 1

TANTQUE (i < N) ET (T[i] ≤ T[i+1]))

FAIRE i <- i+1

FINTANTQUE

RETOURNER (i=N)

FIN

Remarque :

Il y a un problème quand i vaut N : on évalue la condition i<N ET (T[i] ≤ T[i+1]) or la case T[N+1] n'existe pas.

La première partie (i<N) de la condition renvoie faux --> la condition va renvoyer aussi faux ; Mais certains langages évalue quand même la deuxième condition (ce n'est pas le cas du C++) : Don à éviter de l'appliquer en algorithmique.

Deuxième proposition :

On utilise une variable booléenne :

FONCTION est_trié (T : TABL, N : ENTIER) : BOOLEEN

VAR i : ENTIER

TRIE : BOOLEEN

DEBUT

i <- 1

TRIE <- vrai

TANTQUE ((i<N) ET TRIE)

FAIRE

SI T[i]≤T[i+1]

ALORS i <- i+1

SINON TRIE <- faux

FINSI

FINTANTQUE

RETOURNER( TRIE)

FIN

a.Tri par sélection

L'idée du tri du consiste à chaque étape à rechercher le plus petit élément non encore trié et à le placer à la suite des éléments déjà triés.

A une étape i, les i − 1 plus petits éléments sont en place, et il nous faut sélectionner le ième élément à mettre en position i.

L'analyse de cet algorithme donne :

A chaque étape i

• Rechercher le ième élément !
• Le placer en position i !

Méthode :

CONST TAILLE=50

TYPE TABL=TABLEAU [TAILLE] DE REEL

PROCEDURETriSélection(VAR T :TABL; TAILLE :ENTIER)

VAR i,pos :ENTIER

DEBUT

POUR i DE 1 A TAILLE -1 

FAIRE

pos <- trouverMin(T ,i) // Plus petit élément du tableau restant

echanger(T,i,pos) // Echanger avec l'élément en position i

FINPOUR

FIN

-------------------------------------------------------------------------------

// Fonction retournant l'indice du plus petit élément dans le tableau entre les indices i et la fin du tableau

FONCTION trouverMin(T:TABL i: ENTIER ):ENTIER

VAR i_Min, j :ENTIER

DEBUT

i_Min <- i

POUR j DE i_Min +1 A TAILLE

FAIRE

SI T [j] < T[i_Min]

ALORS

i_Min <- j

FINSI

FINPOUR

RETOURNER( i_Min)

FIN

-------------------------------------------------------------------------------

// PROCEDURE échangeant les éléments d'indices i et j dans un tableau

PROCEDURE Echanger (VAR T: TABL; i,j: ENTIER)

VAR Aux :ENTIER;

DEBUT

Aux <- T[i]

T[i] <- T[j]

T[j] <- Aux

FIN

b. Tri par Insertion

Méthode :

Méthode: Trier le tableau de gauche à droite en insérant à chaque fois l'élément i+1 dans le tableau (déjà trié) des premiers éléments.

c. Tri à bulle

Définition :

Le tri à bulle consiste à parcourir le tableau, par exemple de gauche à droite, en comparant les éléments côte à côte et en les permutant s'ils ne sont pas dans le bon ordre. Au cours d'une passe du tableau, les plus grands éléments remontent de proche en proche vers la droite comme des bulles vers la surface.

On s'arrête dès que l'on détecte que le tableau est trié : si aucune permutation n'a été faite au cours d'une passe.

Méthode :

Fondamental :

VIII. LISTES CHAÎNÉES

1. liste

a.Définition

Définition :

Une liste chaînée étant une succession de maillons, dont le dernier pointe vers une adresse invalide (NULL); voici une représentation possible :

Syntaxe : MAILLON

Un maillon aura la structure suivante:

STRUCTURE MAILLON

{

Element : type

Suivant :^MAILLON /*Pointeur vers le maillon suivant */

}

Soit m de type maillon; pour accéder au maillon suivant : m→suivant

Une liste chaînée est caractérisée par un pointeur tete (ou premier) vers le premier élément et un pointeur queue (ou dernier) vers le dernier élément de la liste

Syntaxe : LISTE

Une liste chaînée est caractérisée par un pointeur tete (ou premier) vers le premier élément et un pointeur queue (ou dernier) vers le dernier élément de la liste

STRUCTURE LISTE

{ Tete : ^ MAILLON

Queue: ^ MAILLON

}

b. Fonctions utilisées dans les listes

Au vu de l'utilisation des listes chaînées, il se dessine clairement quelques fonctions indispensables :

• Initialisation
• Ajout d'un élément
• Suppression d'un élément
• Accès à l'élément suivant
• Accès aux données utilisateur
• Accès au premier élément de la liste
• Accès au dernier élément de la liste
• Calcul de la taille de la liste
• Suppression de la liste entière

Exemple : Ajout d'un élément:

Exemple : Suppression d'un élément :

On veut supprimer l'élément P de la liste chaînée :

Remarque :

Le principal problème des listes simplement chaînées est l'absence de pointeur sur l'élément précédent du maillon, il est donc possible de parcourir la chaîne uniquement du début vers la fin !

c. Liste doublement chaînée:

A la différence des listes simplement chaînées, les maillons d'une liste doublement chaînée possèdent un pointeur sur l'élément qui les précède :

Exemple : Implémentation d'une LISTE par un Tableau

Soit T un tableau d'entier de dimension N :

STRUCTURE LISTE

{ premier: ENTIER

dernier:ENTIER

T :TABLEAU[1..N] d'ENTIER

taille : ENTIER (* taille de la liste *)

}

NB :

On peut introduire un champ taille dans la structure Liste Mais ce n'est pas indispensable puisqu'on peut calculer la taille d'une liste en introduisant la fonction TAILLE(L)

La structure de la Liste sera:

STRUCTURE LISTE

{ premier: ENTIER

dernier:ENTIER

T :TABLEAU[1..N] d'ENTIER

}

On suppose que la liste est circulaire. Des cas suivant peuvent se présenter :

2. Pile

a. Définition

Les piles peuvent être représentées comme une pile d'assiettes:

· On peut ajouter des assiettes au sommet de la pile

· Lorsqu'on veut en enlever une, il s'agit de la dernière ajoutée

On parle alors de liste LIFO (Last In First Out).

Les piles ne sont que des cas particuliers de listes chaînées dont les éléments ne peuvent être ajoutés et supprimés qu'au sommet de liste (Dernier).

De ce fait la manipulation s'en trouve grandement simplifiée puisqu'elle ne nécessite que deux fonctions :

· Une fonction pour ajouter (Empliler) un élément au sommet de la pile

· Une seconde pour le retirer (Dépiler)

b. Fonctions utilisées dans les piles :

Les procédures les plus utilisées suivantes:

· Initialiser(p) : Initialisation d'une pile

· Est_vide(p) : Vérification est qu'une pile est vide

· Taille(p) : Taille d'une pile

· Sommet(p) : sommet de la pile

· Empiler(p,element) : ajouter un élément à la pile

· Depiler(p) : supprimer un élément de la pile

c. Implémentation d'une PILE par un Tableau

Soit T un tableau d'entier de dimension N

pile_assiette

Syntaxe : Structure Pile

STRUCTURE PILE

{ premier: ENTIER

Sommet : ENTIER

T :TABLEAU[1..N] d'ENTIER

}

Remarques:

• Sommet de la pile représente le dernier élément de la liste
• Premier élément de la pile ici dans ce cas particulier sera toujours égal à 1 et donc le champ premier de la structure n'est plus nécessaire

La structure d'une pile représentée par un tableau sera simplifiée:

STRUCTURE PILE

{ Sommet : ENTIER

T :TABLEAU[1..N] d'ENTIER

}

Complément : Initialiser la pile

La fonction Initialiser(p) permet d'initialiser une pile ( taille= 0)

Complément : Pile est-elle vide ?

La fonction Est_vide(p) prend la valeur vraie si la pile est vide

FONCTION Est_vide(p:PILE):BOOLEEN

DEBUT

Si p.sommet = 0

ALORS Retourner(VRAIE)

SINON Retourner(FAUX)

FINSI

FIN

Complément : Taille de la pile

La fonction Taille(p) permet de calculer la taille de la pile.

FONCTION Taille(p:PILE):ENTIER

DEBUT

Retourner(p.sommet)

FIN

Complément : Sommet de lapile

La fonction sommet(p) permet d'accéder au sommet de la pile (" sans aucune modification de la pile)

FONCTION sommet(p:PILE):ENTIER

DEBUT

Retourner(p.T[p.sommet])

FIN

Fondamental : Ajout d'un élément (Empiler)

La procedure Empiler(p,element) permet d'ajouter sur le sommet de la pile un élément

Fondamental : Suppression d'un élément (Dépiler)

La procedure Depiler(p) permet de "retirer" le sommet de la pile.

3. File

a. Définition

Une File est une liste linéaire particulière :

· On ne peut ajouter qu'en queue,

· consulter qu'en tête,

· et supprimer qu'en tête.

Comme pour une file d'attente ... !

Les files sont aussi appelées structures FIFO pour First In First Out: c-à-d premier-entré-premier-sorti.

b. Fonctions utilisées dans les files

Les procédures les plus utilisées sont:

· Initialiser(f)

· Est_vide(f)

· Taille(f)

· Tete(f)

· Queue(f)

· Enfiler(f,element)

· Defiler(f)

c. Implémentation d'une FILE par un Tableau

Dans ce cas la structure de la FILE est la suivante :

EXEMPLE :

Complément : Initialisation d'une file

la fonction initialiser(p) permet de réutiliser la pile ! ( pas d'initialisation du tableau ! !)

Complément : La file est-elle vide ?

La fonction Est_vide(f) prend la valeur vraie si la File est vide

FONCTION Est_vide(f:FILE) :BOOLEEN

DEBUT

SI f.tete = 0

ALORS RETOURNER(VRAIE)

SINON RETOURNER(FAUX)

FIN

Complément : TAILLE de la file

La fonction Taille(f) permet de calculer la taille de la FILE.

Complément : Ajout d'un élément (Enfiler)

Procedure Enfiler(f,element) qui permet d'ajouter en queue de la File un élément.

Complément : Suppression d'un élément (Défiler)

La procédure Defiler(f) qui permet de "supprimer" le premier élément de la tête de la File

Cas particuliers :