Algorithme au BTS Informatique - DoualaTour

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected]

Maîtriserl’Algorithmeau BTSInformatique1

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] O M M A I R E

Introduction à la Programmation et Algorithmes (Tome 1)

1. Initiation à la Programmation 2. Structure et objets d'un algorithme 3. Les instructions structurées

• Instructions alternatives (SI, CAS)• Instructions itératives (REPETER, TANT QUE, POUR)

4. Les objets composés • Tableaux et matrices• Enregistrements

5. Quelques algorithmes élaborés • Les problèmes de recherche• Les problèmes de tri

6. Procédures et Fonctions 7. Les fichiers 8. Listes chaînées et Récursivité

Migration vers TURBO PASCAL (Tome 2)

1. Compilation d'un algorithme2. Le mode graphique3. Turbo Pascal avancé

• Création des fichiers exécutables• Création des unités

2


Tome 1 :

Introduction à la Programmation et Algorithmes

3

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] 1 :

INITIATION À LA PROGRAMMATION

I- INTRODUCTION AUX ALGORITHMES

I-1) Définitions :

- Un algorithme est une méthode structurée de résolution d’un problème. Il a pour but de décrire le travail qu’on veut que l’ordinateur effectue à notre place. Un bon algorithme ne doit dépendre ni du langage dans lequel il est traduit, ni de la machine sur laquelle il va être exécuté.

- L’algorithmique ou algorithmie est l’étude des techniques de conception des algorithmes. Ainsi, dans le cadre de notre cours, nous allons concevoir des algorithmes orientés Pascal.

- Programme : traduction d’un algorithme dans un langage de programmation.

- Un langage de programmation est un ensemble de règles s’appliquant à un vocabulaire particulier dont le but est de traduire des algorithmes en programmes.

- Une structure de données est un objet permettant de garder des informations pendant et après les traitements. On l’appelle aussi variable.

- Implémentation : validation d’un programme à l’issue de plusieurs tests.

- Le code source : texte original d’un programme informatique ou d’un script.

- Portabilité : aptitude d’un programme à être utilisé sur des machines différentes.

I-2) Objectifs :

Les objectifs de cet enseignement sont :

- Rendre l’étudiant capable de raisonner comme un ordinateur, c'est-à-dire savoir décortiquer un problème complexe en suite finie d’opérations simples (instructions).

4

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] Savoir concevoir de bons algorithmes et faciliter l’apprentissage de nouveaux

langages. Un bon algorithme est un algorithme qui occupe moins d’espace dans la mémoire et qui permet d’obtenir rapidement les résultats. Le fait d’améliorer la qualité d’un algorithme s’appelle l’optimisation.

I-3) Intérêts des algorithmes :

Nous pratiquons plusieurs algorithmes dans la vie de tous les jours : en allant à l’école le matin, en préparant un repas, en organisant une fête, etc.

Cependant, la maîtrise de la conception des algorithmes informatiques permet, grâce à un langage compris par l’ordinateur (C, PASCAL, PHP, BASIC…), de demander à celui-ci de réaliser un traitement spécifique. Le résultat de ce traitement est appelé programme.

Un Programme n’est pas en lui-même un élément de résolution d’un problème. Il traduit juste un algorithme pour produire des valeurs cherchées à partir des valeurs connues.

NB : On utilise les programmes pour exploiter la formidable capacité de calcul de l’ordinateur.

I-4) Les 4 étapes de construction d’un programme :

Étape 1 : ici on décrit clairement le problème à résoudre pour savoir s’il peut être solutionné par l’ordinateur. (e.g : si le problème est de faire la lessive, la réponse est non)

Étape 2 : ici on échafaude un modèle de résolution du problème. Ce modèle est en général une relation existant entre les grandeurs connues et les grandeurs cherchées. (Exemple : si le problème est de calculer le carré d’un nombre, la relation est C=N*N)

Étape 3 : dans cette étape il est question de choisir les structures de données qu’on va utiliser ainsi que les algorithmes à mettre en œuvre. Ces algorithmes devront contenir la description détaillée des actions à exécuter pour résoudre le problème. (Exemple : pour concevoir un algorithme qui fait la somme de deux nombres, il faut : 1°) recueillir les valeurs de ces deux nombres 2°) faire leur somme 3°) afficher le résultat)

Étape 4 : c’est le choix d’un langage de programmation pour l’implémentation finale. Ce choix est fait en fonction du résultat qu’on veut obtenir, car chaque langage a ses forces et ses faiblesses.

5

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] LA PROGRAMMATION

II-1) Définitions :

Comme nous l’avons vu plus haut, la programmation c’est la technique qui consiste à traduire un algorithme dans un langage compréhensible par l’ordinateur, et ensuite à l’exécuter. Il existe plusieurs sortes de programmation parmi lesquelles :

- La programmation structurée : c’est une programmation dans laquelle on utilise des structures de contrôle standardisées (boucles, conditions…). C’est le cas du langage Turbo Pascal que nous allons étudier.

- La programmation événementielle : ici le programme est défini suivant les principaux événements produits par l’utilisateur (clic de souris, focus, sélection de texte…). Les langages qui admettent ce type de programmation sont par exemple le JavaScript ou encore le Visual Basic.

- La programmation orientée objet (POO) : elle consiste à modéliser informatiquement un ensemble d'éléments du monde réel en un ensemble d'entités informatiques. Ces entités informatiques sont alors appelées objets. Exemple de langage : UML.

- La programmation fonctionnelle : ici tous les programmes sont des fonctions.

- La programmation visuelle : ici l’utilisateur réagit essentiellement au moyen de la souris. Ce type de programmation n’est pas très utilisé pour les gros projets.

II-2) Les différents types de langages :

Nous venons de voir quelques types de programmations. Toutefois, il est utile de remarquer qu’un langage de programmation peut appartenir à plusieurs de ces types en même temps. C’est par exemple le cas du C++ qui permet en même temps de faire des programmations structurées ainsi que des programmations orientées objets.

Ceci dit, il existe deux grandes catégories de langages de programmation : les langages compilés et les langages interprétés. Lorsqu’un algorithme est traduit dans un langage de programmation pour être exécuté par l’ordinateur, cela peut donc se faire de 2 manières :

1- La compilation consiste à vérifier tout le contenu du code source avant de lancer l’exécution du programme. S’il y a une seule erreur de syntaxe, l’implémentation est annulée et aucune partie du programme n’est exécutée. Si par contre la compilation se déroule avec succès, un nouveau fichier (exécutable) est généré.

6

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] L’interprétation consiste à interpréter chaque ligne du code source une à une, et à

l’afficher au fur et à mesure. S’il y a erreur sur une ligne, l’interpréteur l’ignore et continue le traitement avec le reste de la page. Ce type de programme est très répandu dans les scripts de conception de pages web (HTML, JavaScript…)

NB : pour qu’un programme soit exécuté sur un ordinateur, il faudrait que cet ordinateur possède l’environnement permettant de compiler ce programme, ou alors de l’interpréter. Dans certains cas il sera donc nécessaire d’installer un compilateur ou un interpréteur.

II-3) Le langage machine :

En fait, pendant l’exécution d’un programme, chaque instruction décrite dans l’algorithme représente en réalité une action à effectuer par le processeur. Hors le seul langage que comprenne le processeur c’est le langage machine.

Le langage machine est un codage complexe de 0 et de 1 incompréhensibles par l’être humain. C’est pourquoi des langages plus évolués ont été mis au point afin de faciliter la conception de programmes sophistiqués.

Cependant, quel que soit le langage évolué utilisé, il est d’abord traduit en langage machine avant d’être exécuté par le processeur.

Ainsi, plus un langage est proche du langage machine, plus il est dit « de bas niveau ». Plus il s’en éloigne, plus il est dit « de haut niveau ». L’Assembleur est un exemple de langage de bas niveau, et le PASCAL est un exemple de langage de haut niveau.

TRAVAUX DIRIGÉS1. En ignorant tous les langages cités dans ce chapitre, faire des recherches et citer 3

langages de programmation compilés ainsi que 3 langages de programmation interprétés.

2. La plupart des navigateurs possèdent des environnements permettant d’interpréter les scripts du web. Citer donc 4 navigateurs en dehors d’Internet Explorer.

7


STRUCTURE ET OBJETS D’UN ALGORITHME

I- STRUCTURE

Un algorithme est caractérisé par son nom et comporte trois grandes parties :

- L’en-tête : liste des objets utilisés par l’algorithme. On l’appelle aussi déclaration.

- Les traitements : manipulation des objets connus pour obtenir des objets cherchés. Il est possible de les expliciter à l’aide des commentaires.

- La gestion des résultats : dans cette partie il est question de restituer les résultats obtenus. On peut le faire soit en les affichant à l’écran, soit en les stockant dans un fichier physique de l’ordinateur.

NB : étant donné qu’un programme c’est la traduction d’un algorithme dans un langage compréhensible par l’ordinateur, il comprendra lui aussi les 3 parties citées ci-haut.

II- OBJETS

II-1) Les caractéristiques d’un objet :

Pour qu’un algorithme soit correctement implémenté, il a besoin de plusieurs objets dans sa structure. Les principaux objets sont les variables et les constantes.

Un objet est caractérisé par :

• Un nom ou identificateur : il permet d’identifier l’objet dans l’algorithme.

• Un type : il définit l’ensemble dans lequel l’objet prend ses valeurs.

• Une nature : elle indique si l’objet est une constante ou une variable.

• Un sens : il indique si l’objet est en entrée ou en sortie.

8

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected]• Une utilité : elle indique à quoi sert l’objet dans l’algorithme.

• Une valeur : c’est une constante que prend l’objet à un moment donné.

II-2) Définitions et Détails :

A-Définitions

- Une variable est un emplacement mémoire destiné à stocker une donnée pouvant changer au cours de l’exécution du programme.

- Une constante est une « variable » dont la valeur est connue d’avance et ne change pas au cours de l’exécution du programme.

B- Détails sur les caractéristiques des objets

1- Le nom : il est unique dans le programme et doit être composé de caractères alphanumériques. cependant :

a. Aucun nom ne doit commencer par un caractère numérique.

b. En langage Pascal, les noms d’objets ne sont pas sensibles à la casse. Mais il existe des langages où c’est le cas, comme en PHP ou en C++.

c. Les caractères accentués ne sont pas autorisés, de même que les espaces.

d. Un nom d’objet ne doit pas être le même que celui d’un mot-clé (Var, Type…)

2- Le type : il existe plusieurs types auxquels peut appartenir un objet. On peut citer :

a. Le type entier : il s’agit des nombres entiers appartenant à [-32 768, 32 767]

b. Le type réel : il s’agit pratiquement de l’ensemble des nombres réels.

c. Le type caractère : il s’agit d’un caractère alphanumérique ou spécial (@, $..). Ce type d’objet a une valeur délimitée par des cotes. exemple : ‘M’ <> ’m’

d. Le type chaîne : il s’agit d’un objet pouvant contenir une chaîne de caractères. La longueur maximale de ce type est de 255.

e. Le type booléen : il autorise l’objet à ne prendre que les valeurs Vrai ou Faux.

9

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected]. Les types prédéfinis : la plupart des langages offrent des possibilités

permettant au programmeur de créer ses propres types. Cela est très utile pour optimiser les algorithmes (par exemple les types intervalle et énumérer).

III- OPÉRATIONS ET INSTRUCTIONS DE BASE

III-1) Les opérations :

A- Les opérations arithmétiques

1- L’addition : elle est notée (+) et s’applique en général sur les objets de type numérique (entiers, réels…). Elle a pour but de calculer leur somme. Lorsqu’on l’applique sur des objets de type texte, elle effectue ce qu’on appelle la concaténation. Exemple : ‘maman’ + ‘bonjour’ = ‘mamanbonjour’

2- La soustraction : elle est notée (-) et ne s’applique que sur des objets de type numérique. Elle a pour but d’effectuer une soustraction entre deux objets.

3- La multiplication : elle est notée (*) et s’applique pour calculer le produit des objets.

4- La division : il existe deux types de divisions en algorithme :

a. La division réelle notée (/) permet d’obtenir un résultat décimal exact. Son résultat est forcément un nombre réel. Exemple : 7 / 2 = 3.5

b. La division entière notée (div) ne conserve que la partie entière du résultat obtenu. Elle est utilisée uniquement avec les entiers. Exemple : 7 div 2 = 3

5- Le modulo : il est noté (mod) et donne le reste de la division entière entre 2 entiers (uniquement les entiers). Exemple : 7 mod 2 = 1

NB : l’ordre de priorité des opérations ci-dessus est le suivant : multiplication, division, addition et soustraction. On peut cependant le redéfinir en effectuant un bon parenthésage.

B- Les opérations logiques (ou connecteurs logiques)

Les opérations logiques s’appliquent essentiellement sur des objets de type booléen ou alors sur des comparaisons. Elles permettent de tester la simultanéité, l’exclusion, ou encore la réalisation ou non de certains événements. Les plus utilisées sont :

10

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] ET : cette opération s’applique entre deux objets ou groupes d’objets. Elle est donc

binaire. Elle permet de vérifier si ces objets sont réalisés (Vrai) en même temps.

2- OU : également binaire, il vérifie si l’un au moins des objets qu’il relie est réalisé.

3- NON : c’est une opération unaire car elle ne s’applique que sur un seul objet ou groupe d’objets. Elle permet de vérifier si cet objet n’est pas vrai.

C- Les opérations de comparaison

1- Égalité (=) : permet de vérifier si deux objets ont la même valeur.

2- Inégalité (<> ou ≠) : permet de vérifier si deux objets n’ont pas la même valeur.

3- Infériorité (<) : permet de vérifier si l’objet à gauche est strictement inférieur à l’objet de droite. On a aussi l’infériorité simple (<= ou ≤).

4- Supériorité (>) : permet de vérifier si l’objet de gauche est strictement supérieur à l’objet de droite. On a aussi la supériorité simple (>= ou ≥).

Remarques :

• Deux objets booléens sont égaux si et seulement si ils ont la même valeur de vérité.

• La comparaison entre deux caractères est équivalente à la comparaison entre leur numéro de code ASCII. Ainsi, ‘a’ > ‘A’ car 97 > 65. ‘1’ < ‘M’ car 49 < 77.

• La comparaison entre 2 chaînes de même casse se fait comme dans un dictionnaire. Sinon les caractères sont comparés un à un en commençant à gauche.

III-2) Les instructions de base :

A- L’affectation

Elle est notée ( ). Elle consiste à affecter à un objet la valeur d’un autre objet de type compatible. Elle peut également affecter à un objet la valeur d’une expression arithmétique. Exemples : X Y ou encore : X (Y+Z) * W

B- La lecture ou saisie

C’est le mode communication entre l’utilisateur et la mémoire centrale. C’est par ce moyen qu’on peut interagir avec le programme à l’aide du clavier.

Syntaxe : Lire(objet) ou encore Saisir(objet1, objet2, objet3)

11

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] L’écriture ou affichage

C’est la communication entre l’ordinateur et l’utilisateur à travers l’écran. Elle permet de donner les instructions à suivre et également d’afficher les résultats des traitements.

Syntaxe : Ecrire(objet) ou Afficher(objet1, objet2) ou encore Ecrire(‘C’’est beau’)

NB : l’apostrophe doit être doublée pour être compréhensible par la fonction ‘Ecrire’.

IV- RÉSUMÉ

Nous venons de voir les éléments nécessaires à la fabrication d’un algorithme. De façon générale, la structure finale d’un programme ressemblera donc à ceci :

Algorithme <nom de l’algorithme>

[const <liste des constantes>=<valeurs>] {les crochets signifient que l’objet est facultatif}

[type <liste des types prédéfinis>=<définition des types prédéfinis>]

[var <liste des variables> :<type>] {fin de la partie Déclarations}

DEBUT {corps de l’algorithme}

<LISTE DES ACTIONS>

FIN.

NB : dans un programme les mots-clés const, type et var sont écrits une seule fois. C'est-à-dire que s’il y a plusieurs constantes on écrit ‘const’ puis on définit la liste des constantes.

EXEMPLE : écrire un algorithme qui fait la somme de deux nombres entiers

Algorithme Somme

Var nbre1, nbre2, S : entier

DEBUT

Lire(nbre1, nbre2)

S nbre1 + nbre2

12

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected](S)

FIN

TRAVAUX DIRIGÉS3. Identifier les noms de variables qui sont corrects en Pascal : « ma variable ; ma_variable ;

m1VARIABLE ; 1variable ; mon_élément ; debut ; +value ; value+ ; $NOTE ; em@il »

4. Identifier les caractères dont le code ASCII vaut : 8 – 13 – 32 – 46 – 55 – 64 – 65 – 97 – 253

5. Écrire un algorithme qui calcule la surface d’un cercle dont l’utilisateur entre le rayon.

6. Écrire un algorithme qui permute les valeurs de deux variables remplies par l’utilisateur, puis faire le même programme pour permuter 3 variables.

7. Écrire un algorithme qui prend en entrée le nombre de kilomètres parcourus, le nombre de litres d’essence consommés, et la durée du parcours (en minutes). Puis le programme retourne la vitesse moyenne (km/min) ainsi que la consommation au kilomètre.

8. Écrire un programme qui permet de saisir 3 notes d’un étudiant, les coefficients de ces notes, et qui ensuite renvoie la moyenne de cet étudiant.

9. Écrire un programme qui renvoie le discriminant de la fonction f(x) = ax² + bx – c, avec a, b, et c rentrés par l’utilisateur. Le programme calculera ensuite la valeur de f(x) pour x=2.

13


LES INSTRUCTIONS STRUCTURÉES

Jusqu’à présent nous n’avons utilisé que des algorithmes séquentiels, c'est-à-dire que pour exécuter l’action N il fallait d’abord exécuter l’action N-1. Dans ce chapitre nous verrons à quoi ressemble un algorithme optimisé. Pour cela, nous étudierons les schémas alternatifs et itératifs. Ces schémas permettent au programme d’aller plus vite.

I- NOTION DE PRÉDICAT

Un prédicat est une proposition d’algèbre de Boole à laquelle on ne peut répondre que par Vrai ou Faux. La formulation des prédicats permet au processeur d’opérer des choix ou alors des répétitions. L’expression d’un prédicat se résume généralement à la comparaison entre 2 variables de même type : on parle alors de prédicat élémentaire (exemple : X >= Y).

Les prédicats composés sont obtenus par juxtaposition des prédicats élémentaires à l’aide des connecteurs logiques (exemple : (X < Y) ET ( (X + 5 = Z) OU (Z=5) ) ).

II- LE SCHÉMA ALTERNATIF OU SCHÉMA CONDITIONNEL

Le schéma alternatif c’est la construction d’un bloc d’instructions qui ne seront exécutées que si une certaine condition est réalisée (ou non réalisée). On en distingue 3 principaux types : l’alternative simple, l’alternative emboîtée, et l’alternative multiple. À noter que le bloc d’instructions contenu dans un schéma alternatif peut également contenir une instruction structurée.

II-1) L’alternative simple :

Elle a pour but d’exécuter une série d’instructions si un prédicat est réalisé. Si ce n’est pas le cas, le processeur ignore la série d’instructions et passe au reste du programme.

Syntaxe : SI PRÉDICAT ALORS

14

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected]<série d’instructions> {la série ne doit pas être vide}

FINSI

EXEMPLE : écrire un algorithme qui fait la division de deux nombres entiers

Algorithme division

Var nbre1, nbre2 : entier ; S : réel

DEBUT

Lire(nbre1, nbre2)

SI nbre2 <> 0 ALORS

S nbre1 / nbre2

Ecrire(‘Résultat = ‘, S)

FINSI

FIN

II-2) L’alternative emboîtée :

Tout comme l’alternative simple, elle a pour but d’exécuter une série d’instructions si un prédicat est réalisé. Seulement, elle permet en plus d’exécuter une autre série d’instructions si ce prédicat de départ n’est pas réalisé.

Syntaxe : SI PRÉDICAT ALORS

<série d’instructions 1> { la série ne doit pas être vide }

SINON { c’est le contraire du prédicat qui est réalisé }

<série d’instructions 2> {la série ne doit pas être vide}

FINSI

EXEMPLE : écrire un algorithme qui dit si un nombre entier est pair ou impair.

Algorithme parité

15

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] nbre : entier

DEBUT

Lire(nbre)

SI (nbre mod 2 = 0) ALORS

Ecrire(‘Nombre pair‘)

SINON

Ecrire(‘Nombre impair’)

FINSI

FIN

II-3) L’alternative multiple :

Lorsque l’on a affaire à plusieurs choix possibles, il devient parfois rébarbatif et aussi complexe de s’en sortir avec des schémas alternatifs simples ou emboîtés. D’où les alternatives multiples. Ici, il est possible de définir en une fois l’ensemble des actions à entreprendre pour chacune des valeurs d’un intervalle.

Syntaxe : CAS VARIABLE VAUT

Valeur 1 : <série d’instructions 1>

Valeur 2 : <série d’instructions 2>

Valeur n : <série d’instructions n>

SINON {n’est pas obligatoire}

<série d’instructions n+1>

FINCAS

NB : <Valeur i> est de n’importe quel type et peut prendre plusieurs formes :

- Une valeur unique.

- Une énumération de valeurs séparées par des virgules.

16

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] Un intervalle où les bornes inférieure et supérieure sont séparées par ‘..’ (exemple :

l’intervalle [8, 100] sera représenté par 8..100)

- Une énumération d’intervalles ([3, 9] U [14, 16[ sera représenté par 3..9, 14..15)

Remarque : les intervalles délimités par des caractères sont valides puisque c’est leur numéro de code ASCII qui est utilisé.

EXEMPLE : écrire un algorithme qui donne la mention d’un étudiant.

Algorithme mention

Var note : entier

DEBUT

Lire(note)

CAS note VAUT

0..7 : Ecrire(‘Faible’)

8..9 : Ecrire(‘Médiocre’)

10..11 : Ecrire(‘Passable’)

12..13 : Ecrire(‘Assez Bien’)

14..15 : Ecrire(‘Bien’)

16..20 : Ecrire(‘Très Bien’)

SINON Ecrire(‘Erreur’)

FINCAS

FIN

III- LES SCHÉMAS ITÉRATIFS OU SCHÉMAS RÉPÉTITIFS

17

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] appelle itération la répétition d’une action ou d’une séquence d’actions. Cette

technique programmatique a pour but de permettre au développeur d’effectuer le maximum d’opérations avec un minimum d’instructions.

Il existe trois principaux schémas itératifs, également appelés boucles : la boucle Tant Que, la boucle Répéter, la boucle Pour.

III-1) La boucle Répéter :

C’est une instruction structurée qui permet de répéter une série d’opérations jusqu’à ce qu’une certaine condition soit réalisée. Ce prédicat de sortie doit être bien défini, sinon le programme risque d’être bloqué dans la boucle et ainsi provoquer un bug (ou bogue) dans l’ordinateur.

Syntaxe : REPETER

<série d’instructions>

JUSQU'À <prédicat>

Remarques :

• On ne connaît pas à l’avance le nombre de fois qu’on va répéter les instructions, mais le programme va y faire au moins un tour.

• Il faut absolument que dans la boucle il y ait une opération qui permette de modifier le prédicat de sortie.

EXEMPLE : écrire un algorithme qui force l’utilisateur à entrer un nombre pair.

Algorithme nombre_pair

Var nbre : entier

DEBUT

REPETER

Ecrire(‘Entrez un nombre pair’)

Lire(nbre)

JUSQU'À (nbre mod 2 = 0)

18

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected](‘Vous avez enfin entré un nombre pair qui est ‘, nbre)

FIN

III-2) La boucle Tant Que :

De même que REPETER, TANT QUE est une instruction structurée qui permet de réitérer une série d’opérations autant de fois qu’une certaine condition est réalisée. Pourtant elle est beaucoup plus implémentée dans les langages de programmation que l’autre. Les deux présentant quelques différences sur la syntaxe et sur l’intelligence.

Syntaxe : <initialisation>

TANT QUE <prédicat> FAIRE


FINTANTQUE

Remarques :

• Contrairement à la boucle REPETER le programme n’est pas forcé de faire au moins un tour dans la boucle. Cela se produit si le prédicat d’entrée est faux dès le départ.

• De plus, pour un même programme, le prédicat qui permet de rentrer dans TANT QUE est très souvent le contraire de celui qui permet de sortir de REPETER.

• En général il faut une initialisation pour permettre au processeur de tester une première fois la condition d’entrée dans la boucle. Ensuite il faut que dans cette boucle il y ait une opération qui permette de modifier ce prédicat d’entrée.

• Une fois de plus, on ne connaît pas à l’avance le nombre de fois que le programme va répéter les instructions.

EXEMPLE : écrire un algorithme qui force l’utilisateur à entrer un nombre pair.

Algorithme nombre_pair

Var nbre : entier

DEBUT

Nbre 1 {initialisation}

19

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] QUE (nbre mod 2 <> 0) FAIRE

Ecrire(‘Entrez un nombre pair’)

Lire(nbre)

FINTANTQUE

Ecrire(‘Vous avez enfin entré un nombre pair qui est ‘, nbre)

FIN

III-3) La boucle Pour :

La boucle POUR est une boucle à part. Contrairement aux deux autres, elle permet de répéter une série d’opérations un nombre connu de fois. Pour ce faire, elle nécessite l’utilisation d’un compteur qui doit être initialisé et borné.

Syntaxe : POUR <compteur> <Bi> A <Bs> FAIRE


FINPOUR

Remarques :

• Bi = Borne inférieure et Bs = Borne supérieure. Naturellement, il faut que Bs >= Bi

• On sait à l’avance que les actions vont être répétées (Bs – Bi + 1) fois.

• Dès que le compteur vaut Bs, on exécute la série une dernière fois puis le programme sort de la boucle.

• Dans une boucle POUR, il faut en général éviter les instructions qui modifient la valeur du compteur. Étant donné que celui-ci est incrémenté automatiquement, une modification manuelle de sa valeur peut causer un bug qui éternisera le programme.

EXEMPLE : écrire un algorithme qui fait la somme des N premiers nombres, N étant un nombre entier entré par l’utilisateur.

Algorithme sommes

Var nbre, i, S : entier

20


Ecrire(‘Entrez un nombre’)

Lire(nbre)

S 0

POUR i 1 A nbre FAIRE

S S + i

FINPOUR

Ecrire(‘La somme des ‘, nbre, ‘ premiers nombres est ‘, S)

FIN

TRAVAUX DIRIGÉS10. Écrire un algorithme qui dit si un nombre entré par l’utilisateur est un multiple de 3. Si ce

n’est pas le cas, le programme dira si ce nombre est quand même un multiple de 2.

11. Écrire un programme qui permet à l’utilisateur d’entrer le sport qu’il pratique (football, tennis, basket, natation) ainsi que son âge. Le programme dira ensuite si l’utilisateur pratique un sport collectif ou individuel, et dans quelle catégorie il le pratique (-13 ans MINIME, -17ans CADET, -21 ans JUNIOR, -35 ans SENIOR, +35 ans VETERAN).

12. En utilisant la boucle REPETER puis la boucle TANT QUE, écrire un algorithme qui force l’utilisateur à entrer un nombre positif N supérieur à 4. Le programme calculera la somme des N premiers entiers positifs et permettra à l’utilisateur de recommencer l’opération avec un autre nombre ou alors de quitter le programme.

13. Faire un algorithme qui recueille un entier N, et qui affiche tous les nombres entiers positifs pairs inférieurs strictement à N. Réaliser ce programme avec toutes les boucles.

14. Écrire un algorithme qui permet de trouver le factoriel d’un nombre entier entré par l’utilisateur, en sachant que 0!=1 et que les nombres négatifs n’ont pas de factoriel.

15. Réaliser un programme qui affiche les 100 premiers termes de la suite de Fibonacci.

16. Écrire un algorithme qui prend 2 nombres entiers positifs en entrée, et qui calcule leur PGCD ainsi que leur PPCM.

21


LES OBJETS COMPOSÉS

Depuis le début de notre cours, nous n’avons eu affaire qu’à des objets de type simple. C'est-à-dire que jusqu’ici chaque variable ou chaque constante que nous avons rencontrée ne pouvait contenir qu’une et une seule valeur à un moment donné.

Dans ce chapitre nous étudierons des objets plus élaborés, à savoir des objets pouvant contenir plusieurs valeurs différentes au même moment. Ces objets appartiennent à des types dits composés ou prédéfinis. Les informations que renferme un objet de type composé peuvent être :

- De même type : on parle alors de type composé homogène (tableaux et matrices).

- De types différents : on parle de type composé hétérogène (enregistrements).

I- LES TABLEAUX

I-1) Les tableaux à une dimension (vecteurs) :

Un vecteur est un objet prédéfini pouvant contenir un ensemble d’informations de même type. Chacune de ces informations est repérée par un entier appelé indice ou rang.

A- Déclaration d’un vecteur

Syntaxe : Type <nom_du_tableau> = Tableau[Bi..Bs] de <TypeElt>

Remarques :

• Bi = indice du 1er élément du tableau. Bs = indice du dernier élément du tableau. Naturellement, il faut que Bs >= Bi.

• Le nombre maximum d’éléments que peut contenir le tableau est Bs – Bi + 1.

22

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected]• Une fois de plus, les intervalles délimités par des caractères sont valides puisque

c’est leur numéro de code ASCII qui est utilisé.

• Le nom du tableau doit respecter les mêmes contraintes que celui d’un objet simple.

• <TypeElt> représente le type auquel doit appartenir chacun des éléments du tableau.

EXEMPLE : déclarer un tableau de 50 éléments de type réel

Algorithme declaration_tableau

Type notes=tableau[1..50] de réel

Var v : notes

B- Accès à un élément du tableau

Pour accéder à un élément du tableau, il suffit juste de connaître son rang. Ainsi, suivant la déclaration de l’exemple précédent, le 1er élément du tableau sera noté v[1]. On peut donc effectuer n’importe quelle opération classique avec cet élément :

v[1] 5 ou encore Lire(v[1])

C- Un cas particulier de vecteurs : les chaînes de caractères

Une chaîne de caractères est en réalité la concaténation d’un ensemble de caractères. Sa déclaration se fait comme suit : var nom_objet : chaîne[taille]

Où :

Nom_objet est le nom de la variable devant recueillir la chaîne de caractères.

Taille est la taille de la chaîne, autrement dit le nombre maximum de caractères qu’elle peut contenir. Si elle n’est pas précisée elle vaut 255.

Remarques :

• Étant donné qu’une chaîne de caractères est assimilable à un tableau de caractères, sa manipulation est donc quasi-identique à celle d’un vecteur.

Exemple : soit la variable phrase représentant la chaîne ‘BONJOUR PAPA’. On a phrase[1]=’B’ et phrase[8]=’ ’. Si on effectue l’opération phrase[11] ‘R’, on obtient phrase=’BONJOUR PARA’.

23

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected]• Ceci dit, une variable de type chaîne peut aussi être manipulée comme un objet de

type simple. Exemple : phrase phrase + ‘ ET AU REVOIR’.

• Lorsque la chaîne entrée par l’utilisateur a une longueur supérieure à celle définie par le programmeur, le processeur effectue ce qu’on appelle une troncature. C'est-à-dire que la variable ne retiendra que les [taille] premiers caractères. Si par contre la longueur de l’utilisateur est inférieure, la variable contiendra l’intégralité de la chaîne saisie. Avec possibilité de la rallonger par une concaténation ou une réaffectation.

I-2) Les tableaux à deux dimensions (matrices) :

Une matrice est un tableau à deux dimensions. Chacun des éléments d’une matrice est repéré par 2 indices (l’un pour la ligne et l’autre pour la colonne).

A- Déclaration d’une matrice

Elle se fait presque de la même manière que pour un vecteur. C'est-à-dire qu’on précise le nom, le nombre de lignes et de colonnes, ainsi que le type des éléments de la matrice.

Syntaxe : Type <nom_de_la_matrice> = Tableau[Bi1..Bs1, Bi2..Bs2] de <TypeElt>

NB : un vecteur est en réalité une matrice d’une seule ligne et de plusieurs colonnes.

Remarques :

• Bi1 et Bs1 représentent les bornes inférieure et supérieure du nombre de lignes. Bi2 et Bs2 les bornes inférieure et supérieure du nombre de colonnes. Naturellement, il faut que Bi1 <= Bs1 et que Bi2 <= Bs2.

• Le nombre maximum d’éléments que peut contenir une matrice est (Bs1 – Bi1 + 1) * (Bs2 – Bi2 + 1). Autrement dit Nombre de lignes * Nombre de colonnes.

• Une matrice est dite carrée si le nombre de lignes est égal au nombre de colonnes. On parlera alors de matrice carrée d’ordre N (N=nombre de lignes / colonnes).

• On peut définir des tableaux à plus de 2 dimensions (ligne, colonne, profondeur…)

EXEMPLE : déclarer une matrice de 10 lignes et 5 colonnes d’éléments de type réel

Algorithme declaration_matrice

Type notes=tableau[1..10, 1..5] de réel

24

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] m : notes

B- Accès à un élément d’une matrice

Pour accéder à un élément d’une matrice il faut connaître sa position exacte, c'est-à-dire ses indices de ligne et de colonne. Ainsi, suivant la déclaration précédente, le 1er élément du tableau sera noté m[1, 1]. On pourra aussi faire : m[1, 1] 5 ou Lire(m[1, 1]).

Soit M un objet de type matrice et le couple (i, j) deux entiers. M[i, j] désigne l’élément de la ième ligne et de la jème colonne.

Exemple : dans le tableau suivant :

1 2 31 ‘a’ ‘b’ ‘c’

2 ‘d’ ‘e’ ‘f’

3 ‘g’ ‘h’ ‘i’

4 ‘j’ ‘k’ ‘l’On a : m[1, 1] = ‘a’ et m[3, 2] = ‘h’

EXEMPLE : écrire un algorithme qui permet à l’utilisateur de remplir une matrice de 7 lignes et de 5 colonnes avec des entiers.

Algorithme remplir_matrice

Const ligne=7 ; colonne=5

Type matrice=tableau[1..ligne, 1..colonne]

Var i, j : 1..50 ; m : matrice

DEBUT

POUR i 1 A ligne FAIRE

POUR j 1 A colonne FAIRE

Ecrire(‘Entrez un nombre’)

Lire(m[i, j])

25


FINPOUR

FIN

II- LES ENREGISTREMENTS

Dans la section précédente, nous avons vu que toutes les valeurs contenues dans un vecteur ou une matrice sont obligatoirement de types identiques. Avec les enregistrements, nous allons voir qu’un objet composé peut aussi contenir des valeurs de différents types.

La notion d’enregistrement est très proche de la conception des bases de données. Elle permet de représenter un objet du monde réel par la description de ses principales caractéristiques. Chacune de ces caractéristiques étant alors appelée champ. Par exemple, une voiture peut être représentée par sa marque, sa puissance, sa couleur, etc.

II-1) Déclaration d’un enregistrement :

La déclaration d’un objet de type Enregistrement se fait de manière suivante :

Type <nom_objet> = Enregistrement

<champ 1> : <type 1>


<champ n> : <type n>

FinEnregistrement

Remarques :

• <champ i> est une variable à part entière qui représente une propriété de l’objet.

• <type i> est le type de <champ i> et est indépendant des autres types de l’objet. Ainsi il peut être simple ou composé, à condition d’être défini avant l’enregistrement.

EXEMPLE : définir un enregistrement pour sauvegarder les informations sur des voitures.

26

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] les_voitures

Type chevaux = 10..60

voitures = enregistrement

Immatriculation : chaine[10]

Couleur : chaine[17]

Puissance : chevaux

Garantie : booléen

FinEnregistrement

Var p : voitures

II-2) Manipulation des enregistrements :

A-Manipulation classique

Manipuler un objet de type enregistrement revient à manipuler chacun des champs qui le constituent. Cela se fait grâce à la variable Nom_objet.nom_champ. Ainsi, si on tient compte de l’exemple précédant concernant les voitures, on peut faire :

Voitures.garantie vrai ou encore Lire(voitures.puissance)

NB : on a vu que le type d’un champ peut également être un enregistrement prédéfini. Dans ce cas sa manipulation se fera ainsi : Nom_objet.nom_champ.nom_sous_champ

EXEMPLE : écrire un algorithme qui permet de saisir les informations sur 5 étudiants (nom, prénom, âge, sexe, date de naissance, date d’inscription, total versements, solde).

Algorithme etudiants

Const pension=350.000

Effectif=5

Type calendrier=enregistrement

Jour : 1..31

27

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] : 1..12

Annee : 1950..2020

FinEnregistrement

etudiants=enregistrement

Nom : chaîne[27]

Prenom : chaîne[49]

Age : 1..100

Sexe : chaîne[5]

Date_naiss : calendrier

Date_inscription : calendrier

Versements : réel

Solde : réel

FinEnregistrement

Ecole=tableau[1..effectif] de etudiants

Var i : 1..effectif

V : ecole

DEBUT

POUR i 1 A effectif FAIRE

Lire(v[i].nom)

Lire(v[i].prenom)

Lire(v[i].age)

Lire(v[i].sexe)

Lire(v[i].date_naiss.jour)

Lire(v[i].date_naiss.mois)

28

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected](v[i].date_naiss.annee)

Lire(v[i].date_inscription.jour)

Lire(v[i].date_inscription.mois)

Lire(v[i].date_inscription.annee)

Lire(v[i].versements)

v[i].solde v[i].versements – pension

FINPOUR

FIN

B-Le cas AVEC

Avec AVEC, il devient possible de manipuler les objets de type Enregistrement d’une façon un peu moins rébarbative. Il s’agit en effet de sélectionner la variable qu’on désire manipuler, et ensuite de travailler uniquement avec les noms de champ de cet objet.

EXEMPLE : à l’aide des structures définies précédemment, écrire un algorithme qui permet de saisir les informations sur 5 étudiants (nom, âge, date de naissance).

DEBUT

POUR i 1 A 5 FAIRE

AVEC v[i] FAIRE

Lire(nom)

Lire(age)

AVEC v[i].date_naiss FAIRE

Lire(jour)

Lire(mois)

Lire(annee)

FINAVEC

29


FINPOUR

FIN

TRAVAUX DIRIGÉS17. Écrire un algorithme qui demande à l’utilisateur de saisir un nombre entier positif N. Le

programme permettra ensuite de remplir un tableau en saisissant N valeurs réelles positives. Puis il affichera la somme des valeurs contenues dans ce tableau, puis leur moyenne, ainsi que la valeur la plus haute et la valeur la plus basse.

18. À l’aide d’une matrice à 2 dimensions, concevoir un programme qui permet de saisir les 10 notes d’un étudiant ainsi que leur coefficient, et calcule sa moyenne générale. Le programme donnera également le nombre de sous-moyennes obtenues par l’étudiant.

19. Écrire un programme qui permet, grâce à un tableau à 3 dimensions, de saisir les 5 notes du 1er semestre de 10 étudiants, ainsi que leurs 5 notes du 2nd semestre. Le programme retournera ensuite la meilleure et la pire moyenne de chaque semestre, ainsi que la meilleure et la pire moyenne de l’année.

20. Écrire un algorithme qui prend en entrée une chaîne de caractères de longueur indéterminée. Le programme effectuera ensuite les opérations suivantes : 1°) afficher le nombre de mots contenus dans la chaîne 2°) réaliser un acrostiche, donc un mot composé des 1ères lettres de chaque mot 3°) réaliser un palindrome, donc afficher la même chaîne avec les caractères placés de droite à gauche 4°) enfin, le programme dira combien de fois la lettre ‘e’ (ou ‘E’) apparaît dans la chaîne.

21. Écrire un programme qui permet de sauvegarder les informations sur 5 produits d’une entreprise. Chaque produit est caractérisé par son code, son libellé, son prix, sa quantité en stock, et sa date de livraison. Le programme déterminera ensuite le chiffre d’affaires que représentent ces 5 produits, il indiquera le produit le plus cher, et il affichera le libellé du produit le plus ancien dans le magasin.

22. Soit un tableau contenant les enregistrements sur 1000 étudiants (matricule, nom, prénom, sexe, date de naissance, date d’inscription, versement). En considérant que la pension est de 100.000 frs dans cet institut, le programme doit afficher 1°) la liste des étudiants en règle 2°) la liste des filles qui ne sont pas en règle. Le programme prendra également une date en entrée et permettra de connaître la somme des versements effectués à cette date. Enfin, pour un matricule saisi, le programme devra indiquer si cet étudiant est inscrit ou pas.

30


QUELQUES ALGORITHMES ÉLABORÉS : LA RECHERCHE ET LE TRI

Dans ce chapitre il ne sera pas question d’apprendre une nouvelle leçon, mais plutôt d’utiliser les concepts déjà étudiés pour s’habituer à développer des algorithmes optimisés. Nous verrons donc successivement comment vérifier manuellement l’exécution d’un programme (trace), nous utiliserons les matrices pour construire un triangle de Pascal, et enfin nous verrons les cas particuliers des algorithmes de recherche et de tri.

I- LA TRACE

C’est une manière détaillée de suivre le déroulement d’un programme au fur et à mesure de son exécution. Elle se fait au moyen d’un tableau :

Variables

InstructionsVar 1 Var i

Instruction 1Instruction i

Par exemple, soit un algorithme où il faut faire la somme des 3 premiers entiers.

Algorithme somme_3

Var i, S : entier

DEBUT

S 0

POUR i 1 A 3 FAIRE

S S + i

31


Ecrire(‘La somme des 3 premiers nombres est ‘, S)

FIN

La vérification d’un tel algorithme sera donc :

Variables

Instructionsi S

S 0 NULL 0i 1 1 0

S S + i 1 1i 2 2 1

S S + i 2 3i 3 3 3

S S + i 3 6

II- CONSTRUCTION DU TRIANGLE DE PASCAL

Le triangle de Pascal est un triangle inventé par le mathématicien Français Blaise Pascal. Initialement il avait pour but d’aider au calcul des probabilités.

RAPPEL : un triangle de Pascal est en réalité une matrice carrée où :

- La 1ère colonne de chaque ligne a la valeur 1.

- Chaque case appartenant à la diagonale a la valeur 1.

- Les cases situées à droite de la diagonale n’ont pas de valeur (NULL).

- À partir de la 3ème ligne, les cases situées entre la 1ère colonne et la diagonale sont la somme de la case du dessus et celle à gauche de cette dernière.

Exemple : voyons ce que ça donne si nous avons une matrice carrée d’ordre 7 :

11 11 2 11 3 3 1

32

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1

EXEMPLE : écrire un algorithme qui effectue un triangle de Pascal d’ordre 10.

Algorithme triangle_pascal

Const n=10

Type matrice=tableau[1..n, 1..n] de entier

Var i, j : 1..n ; M : matrice

DEBUT

POUR i 1 A n FAIRE

M[i, 1] 1 ; M[i, i] 1

FINPOUR

POUR i 3 A n FAIRE

POUR j 2 A (i-1) FAIRE

M[i, j] m[i-1, j] + m[i-1, j-1]

FINPOUR

FINPOUR

III- LES PROBLÈMES DE RECHERCHE

La recherche est une opération très importante lorsqu’il s’agit de manipuler de grandes quantités de données en informatique. Elle permet de retrouver une information spécifique dans un tableau, un fichier, un enregistrement, une liste chaînée, une base de données…

En programmation algorithmique, il existe plusieurs principes de recherche. Nous allons en étudier 2 qui sont : la recherche séquentielle et la recherche dichotomique.

III-1) La recherche séquentielle :

33

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] La recherche séquentielle sans sentinelle

C’est une recherche effectuée entre les différentes valeurs d’un tableau. On parcourt progressivement chacune des cellules (cases), et dès que la valeur recherchée est trouvée le programme renvoie VRAI. Sinon il renvoie FAUX.

EXEMPLE : écrire un algorithme qui recherche une valeur ‘val’ dans un tableau déjà rempli.

Algorithme recherche_sequentielle

Const N=25

Type vecteur=tableau[1..N] de entier

Var i : 1..N

Val : entier ; V : vecteur ; trouve : booléen

DEBUT

Ecrire(‘Entrez la valeur recherchée’)

Lire(val)

i 1

TANT QUE (v[i] <> val) ET (i <= N) FAIRE

i i + 1

FINTANTQUE

Trouve i <= N

SI trouve ALORS

Ecrire(‘La valeur ‘, val, ‘ se trouve dans le tableau’)

SINON

Ecrire(‘La valeur ‘, val, ‘ n’’est pas dans le tableau’)

FINSI

FIN

34

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] La recherche séquentielle avec sentinelle

Le principe reste le même que précédemment, sauf que cette fois on utilisera une sentinelle en fin de tableau pour savoir si la valeur recherchée est bel et bien présente.

EXEMPLE : écrire un algorithme qui recherche une valeur ‘val’ dans un tableau déjà rempli.

Algorithme recherche_avec_sentinelle

Const N=25

Type vecteur=tableau[1..N+1] de entier

Var i : 1..N+1

Val : entier ; V : vecteur

DEBUT


Lire(val)

V[N+1] val

i 1

TANT QUE (v[i] <> val) FAIRE

i i + 1

FINTANTQUE

Si i <= N ALORS


SINON


FINSI

FIN

35

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected]) La recherche dichotomique :

Contrairement à la recherche séquentielle, la recherche dichotomique ne peut être effectuée que sur un tableau préalablement ordonné (par ordre croisant ou décroissant). Ainsi, soient <Bi> et <Bs> les indices inférieur et supérieur du vecteur croissant sur lequel on veut effectuer notre recherche dichotomique. On va procéder comme suit :

1. Diviser le vecteur en 2 parties égales. Cela se fait en calculant l’indice du milieu : Milieu = (Bi + Bs) div 2

2. Si l’élément qu’on veut trouver est égal à la valeur qui se situe au milieu du vecteur, alors la recherche s’arrête. Dans le cas contraire il y a 2 cas de figure :

a. Soit l’élément recherché est inférieur à la valeur du milieu. Auquel cas la recherche se poursuit dans le demi-vecteur borné par <Bi> et <Milieu-1>.

b. Soit l’élément recherché est supérieur à la valeur du milieu. Auquel cas la recherche se poursuit dans le demi-vecteur borné par <Milieu+1> et <Bs>.

3. Réitérer le processus jusqu’à ce qu’un élément du milieu soit égal à l’élément recherché, ou alors jusqu’à ce que <Bi> soit supérieur à <Bs>

EXEMPLE : écrire un algorithme qui recherche une valeur ‘val’ dans un tableau de valeurs ordonnées par ordre croissant.

Algorithme recherche_dichotomique

Const inf=1

Sup=100

Type vecteur=tableau[inf..sup] de entier

Var milieu, val, bi, bs : entier

V : vecteur

trouve : booléen

DEBUT

Bi inf

36

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] sup


Lire(val)

milieu (bi + bs) div 2

TANT QUE (v[milieu] <> val) ET (bi <= bs) FAIRE

SI v[milieu] > val ALORS

Bs milieu – 1

SINON

Bi milieu + 1

FINSI

milieu (bi + bs) div 2

FINTANTQUE

Trouve v[milieu] = val

Si trouve ALORS


SINON


FINSI

FIN

NB : cet algorithme peut être optimisé en supprimant la variable booléenne ‘trouve’. Il suffira alors de remplacer SI trouve ALORS par SI v[milieu]=val ALORS.

IV- LES PROBLÈMES DE TRI

Nous venons de voir, avec la recherche dichotomique, qu’il y a des opérations qui ne sont valables que sur des variables rangées selon un certain ordre (croissant, décroissant,

37

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected]étique…). En effet, il est possible de développer des algorithmes très performants dès lors qu’on a une liste triée. Ainsi, dans cette partie nous étudierons quelques méthodes usuelles d’ordonnancement des valeurs dans un vecteur.

III-1) Notion de tri :

Soit V un vecteur, Bi et Bs ses bornes inférieur et supérieur. Le vecteur V est trié si et seulement si l’une des conditions suivantes est respectée :

V ne contient aucun élément.

V contient un seul élément.

V contient plusieurs éléments et, quel que soit i compris entre Bi et Bs, on a toujours v[i] <= v[i+1] (si V croissant) ou alors v[i] >= v[i+1] (si V décroissant).

III-2) Le tri par sélection :

Le tri par sélection consiste à parcourir tout le vecteur à la recherche du plus petit élément. Dès qu’on l’obtient, on le positionne à la 1ère case. Ensuite on répète l’opération avec le vecteur non encore trié, jusqu’à ce qu’il n’en reste qu’un singleton.

EXEMPLE : écrire un algorithme qui ordonne de façon croissante un tableau déjà rempli.

Algorithme tri_selection

Const n=100

Type vecteur=tableau[1..n] de réel

Var i, j : entier

Aux : réel

V : vecteur

DEBUT

POUR i 1 A (n-1) FAIRE

POUR j (i+1) A n FAIRE

SI v[j]<=v[i] ALORS

38

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] v[i]

V[i] v[j]

V[j] aux

FINSI

FINPOUR

FINPOUR

FIN

III-3) Le tri par insertion :

C’est la méthode utilisée pour trier un paquet de cartes. On prend d’abord la 2ème carte, on la trie par rapport à la 1ère. Ensuite on prend la 3ème carte, on la trie par rapport aux deux premières. Ainsi de suite jusqu’à ce que la dernière carte soit ordonnée.

EXEMPLE : écrire un algorithme qui ordonne de façon croissante un tableau déjà rempli.

Algorithme tri_insertion

Const n=100

Type vecteur=tableau[1..n] de réel

Var i, j : entier

Aux : réel

V : vecteur

DEBUT

POUR i 2 A n FAIRE

J i

TANT QUE (j > 1) ET (v[j] <= v[j-1]) FAIRE

Aux v[j-1]

V[j-1] v[j]

39

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected][j] aux

J j - 1

FINTANTQUE

FINPOUR

FIN

TRAVAUX DIRIGÉS23. Soit un algorithme qui permet de permuter les valeurs de 3 variables x, y, et z en utilisant

une variable auxiliaire nommée aux. Concevoir cet algorithme puis effectuer la trace de ces variables dans un tableau pour x=1, y=14, et z=7.

24. Faire le même exercice que précédemment en permutant 2 variables x et y sans utiliser d’objet intermédiaire.

25. En imitant l’exemple du triangle de Pascal, concevoir un triangle carré d’ordre 10 où :

o Chaque case de la diagonale a la valeur 0

o À partir de la 2ème ligne, La 1ère colonne de chaque ligne vaut 1

o À partir de la 3ème ligne, les cases situées entre la 1ère colonne et la diagonale sont la somme de la case du dessus et celle de gauche.

o Les autres cases n’ont pas de valeur.

Le résultat final doit donner ceci :

01 01 1 01 2 2 01 3 5 5 01 4 9 14 14 01 5 14 28 42 42 01 6 20 48 90 132 132 01 7 27 75 165 297 429 429 01 8 35 110 275 572 1001 1430 1430 0

40

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected]. Soit une matrice contenant plusieurs valeurs entières. Concevoir un algorithme qui

renvoie le nombre total de nombres impairs contenus dans cette matrice, ainsi que leur somme.

27. Soit une matrice M de 10 lignes et 7 colonnes contenant des réels. Concevoir un algorithme permettant de ranger les valeurs de M dans une autre matrice T de même structure. Le classement se fera par ordre croissant.

41


PROCÉDURES ET FONCTIONS

Tous les algorithmes que nous avons étudiés jusqu’à présent étaient constitués d’un seul bloc (dit principal). Dans certains cas le programmeur peut vouloir décrire et sauvegarder un enchaînement d’actions qui n’existe pas de façon standard dans le compilateur (ou l’interpréteur). Cette sauvegarde lui permettra d’utiliser cet enchaînement autant de fois qu’il en aura besoin dans le programme, et cela au moyen d’un simple appel.

Cet usage est pratique lorsqu’on fait face à un algorithme complexe. Le programmeur décompose donc le problème en mini-blocs ayant chacun un rôle bien précis. Ces mini-blocs sont des sous-programmes (sous-algorithmes) appelés Procédures ou Fonctions.

I- PROCÉDURES

I-1) Définition :

Comme son nom l’indique, une procédure c’est le déroulement classique d’un processus. Elle peut être judiciaire, culinaire, mathématique, informatique, etc. Mais dans tous les cas elle est toujours déclenchée par quelque chose ou bien par quelqu’un. On peut également dire qu’une procédure est une fonction qui ne renvoie pas de résultat.

I-2) Structure :

Une procédure est un mini-programme qu’on déclare en général dans la partie réservée aux variables, ce afin de pouvoir utiliser les variables globales. Étant donné qu’il s’agit d’un bloc à part entière, elle possèdera éventuellement un en-tête, une série de traitements, et une gestion des résultats tout comme l’algorithme qui la contient. En outre, une procédure peut également recevoir des arguments qui lui seront alors passés en paramètres.

La déclaration d’une procédure se fait comme suit :

PROCEDURE <nom_de_la_procedure> [ (liste des paramètres : type) ]

42

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] : liste des variables

DEBUT {corps de la procédure}

<LISTE DES ACTIONS> {la liste ne doit pas être vide}

FINPROCEDURE

Remarques :

• lorsque la déclaration ci-dessus est faite, il suffit ensuite d’écrire le nom de la procédure dans le bloc principal pour déclencher la liste des actions décrites.

• Une procédure peut appeler d’autres sous-programmes définis avant elle.

• La liste des paramètres est facultative. Mais quand elle existe, ces paramètres sont déclarés de la même façon qu’on déclare une série de variables de différents types.

• Les variables déclarées à l’intérieur de la procédure sont inutilisables à l’extérieur du bloc. Si leur type est prédéfini, alors ce type sera déclaré dans l’en-tête du bloc principal. Idem pour les paramètres de la procédure au cas où il en existe.

EXEMPLE : voici un algorithme utilisant une procédure qui fait une somme de N nombres.

Algorithme essai_procedure

Const N=100

Var i, s : entier

Procedure Somme

DEBUT

S 0

POUR i 1 A N FAIRE

S s + i

FINPOUR

Ecrire(‘La somme des ‘, N, ‘ premiers nombres est ‘, s)

43


DEBUT

somme

FIN

II- FONCTIONS

II-1) Définition :

De la même manière qu’une procédure, une fonction est un sous-programme destiné à effectuer un enchaînement de traitements à l’aide d’un simple appel. Cependant, une fonction a pour but principal d’effectuer un calcul puis de renvoyer un résultat.

II-2) Structure :

Une fonction est un mini-programme qu’on déclare dans la partie réservée aux variables, ce afin de pouvoir utiliser les variables globales. Étant donné qu’il s’agit d’un bloc à part entière, elle possèdera éventuellement un en-tête, une série de traitements, et une gestion des résultats tout comme l’algorithme qui la contient. En outre, une fonction peut également recevoir des arguments qui lui seront alors passés en paramètres. Déclaration :

FONCTION <nom_de_la_fonction> [ (liste des paramètres : type) ] : type_fonction

Var : liste des variables

DEBUT {corps de la fonction}

<LISTE DES ACTIONS> {la liste ne doit pas être vide}

<nom_de_la_fonction> résultat_des_calculs

FINFONCTION

Remarques :

• Dans le bloc principal il suffit d’écrire le nom de la fonction pour déclencher le calcul.

• Étant donné qu’une fonction a pour but principal de renvoyer une valeur, il est donc nécessaire de préciser le type de la fonction qui est en réalité le type de cette valeur.

44

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected]• Une fonction peut appeler d’autres sous-programmes définis avant elle.

• On peut utiliser le nom d’une fonction presque comme une variable globale, puisqu’elle renferme une valeur (affectation, affichage, mais pas lecture)

• La liste des paramètres est facultative. Mais quand elle existe, ces paramètres sont déclarés de la même façon qu’on déclare une série de variables de différents types.

• Les variables déclarées à l’intérieur de la fonction sont inutilisables à l’extérieur du bloc. Si leur type est prédéfini, alors ce type sera déclaré dans l’en-tête du bloc principal. Idem pour les paramètres de la fonction au cas où il en existe.

• À l’intérieur du sous-programme le nom de la fonction ne doit figurer qu’en recevant le résultat final ; sinon la fonction risque de s’appeler indéfiniment et donc de provoquer un bug (voir Récursivité).

EXEMPLE : voici un algorithme utilisant une fonction qui calcule la somme de N nombres.

Algorithme essai_fonction

Const N=100

Var i : entier

Fonction Somme : entier

Var s : entier

DEBUT

S 0

POUR i 1 A N FAIRE

S s + i

FINPOUR

Somme s

FINFONCTION

DEBUT

45

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected](‘La somme des ‘, n, ‘ premiers nombres entiers est ‘, somme)

FIN

III- LES PARAMÈTRES D’UN SOUS-PROGRAMME

III-1) Généralités :

Avant de voir comment un sous-bloc exploitera ses paramètres, voici quelques notions :

Une variable globale est une variable définie dans l’en-tête du programme principal. Elle est utilisable dans n’importe quel sous-programme sans nécessité de redéfinition. Toutefois, si dans un sous-bloc il existe une variable qui porte le même nom que la variable globale, alors c’est cette variable locale qui sera considérée à l’intérieur du sous-bloc.

Une variable locale est une variable définie à l’intérieur d’un sous-programme. Sa portée (visibilité) est limitée au bloc qui la contient. Il serait donc erroné de l’utiliser dans le bloc principal ou dans un autre sous-bloc appartenant à l’algorithme.

Considéré comme une variable locale, un paramètre est une valeur du bloc principal dont le sous-programme a besoin pour exécuter avec des données réelles l’enchaînement d’actions qu’il est chargé d’effectuer. On distingue 2 types de paramètres :

o Les paramètres formels qui sont la définition du nombre et du type de valeurs que devra recevoir le sous-programme pour se mettre en route avec succès. On déclare les paramètres formels pendant la déclaration du sous-programme.

o Les paramètres effectifs qui sont des valeurs réelles (constantes ou variables) reçues par le sous-programme au cours de l’exécution du bloc principal. On les définit indépendamment à chaque appel du sous-programme dans l’algorithme principal.

III-2) Fonctionnement et utilisation des paramètres :

Lorsque la déclaration d’un sous-programme comporte des paramètres formels, ceux-ci doivent être représentés chacun par son identificateur ainsi que par son type.

Ainsi pendant la construction de l’algorithme principal, il faudra toujours veiller à ce que chaque appel du sous-programme soit suivi d’une liste de paramètres effectifs correspondant (en nombre, rang, et type) à la liste des paramètres formels. Cependant les noms des paramètres de même ordre ne sont pas obligatoirement identiques.

46

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] a vu plus haut qu’un paramètre effectif pouvait être une constante ou une variable.

Lorsqu’il s’agit d’une variable, 2 cas de figures se proposent :

1) Utiliser la valeur de la variable et à la sortie du sous-programme lui restituer cette valeur malgré les éventuelles modifications subies. On parle de passage de paramètre par valeur.

2) Utiliser la variable elle-même et lui attribuer dans le bloc principal les modifications rencontrées dans le sous-programme. On parle de passage de paramètre par adresse.

NB : un sous-programme avec paramètres est très utile parce qu’il permet de répéter une série d’opérations complexes pour des valeurs qu’on ne connaît pas à l’avance.

A- Passage de paramètres par valeur

Comme on l’a dit, passer un paramètre par valeur revient à n’utiliser que la valeur de la variable au moment où elle est passée en paramètre. À la fin de l’exécution du sous-programme, la variable conservera sa valeur initiale.

Syntaxe : PROCEDURE <nom_procédure> (param1 :type1 ; param2, param3 :type2)

B- Passage de paramètres par adresse (ou par variable)

Ici, il s’agit non plus d’utiliser simplement la valeur de la variable, mais également son emplacement dans la mémoire (d’où l’expression « par adresse »). En fait, le paramètre formel se substitue au paramètre effectif durant le temps d’exécution du sous-programme. Et à la sortie il lui transmet sa nouvelle valeur.

Un tel passage de paramètre se fait par l’utilisation du mot-clé var (uniquement sur le paramètre formel, et jamais sur un paramètre effectif).

Syntaxe : FONCTION <nom_fonction> (VAR param1 :type1 ; param2 :type2) : entier

NB : les paramètres passés par valeur et par adresse peuvent cohabiter à l’intérieur d’un même sous-programme.

EXEMPLE : écrire un algorithme dans lequel une fonction utilise le résultat d’une procédure ‘Produit de 2 entiers’ pour en calculer le carré. Calculer ensuite le carré de ce carré.

Algorithme produit_carre

47

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] nbre1, nbre2 : entier

produit : réel

Procedure multiplier(nbre1, nbre2 : entier)

DEBUT

produit nbre1 * nbre2

Ecrire(‘Le résultat de ce produit est ‘, produit)

FINPROCEDURE

Fonction carre(var racine : réel) : réel

DEBUT

Racine racine * racine

carre racine

FINFONCTION

DEBUT

Ecrire(‘entrer les deux nombres qu’’il faudra multiplier’)

Lire(nbre1, nbre2)

Multiplier(nbre1, nbre2)

Ecrire(‘Le carré de cette multiplication est ‘, carre(produit))

Ecrire(‘Le carré de ce carré sera alors ‘, carre(produit))

FIN

TRAVAUX DIRIGÉS28. Écrire un algorithme utilisant une procédure qui permet de saisir un nombre entier positif

et d’afficher un message indiquant si ce nombre est premier ou pas.

48

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected]. Écrire programme permettant à l’utilisateur de saisir un nombre entier positif. En se

servant d’une fonction booléenne, le programme principal affichera ensuite un message indiquant si cet entier est premier ou pas.

30. Écrire un programme dans lequel une procédure prend en paramètres un prénom et un âge. La procédure affichera ensuite un message disant ‘BONJOUR’, PRENOM, puis indiquera s’il s’agit d’un enfant (-20), d’un adulte (-50), ou d’une personne âgée.

31. Écrire un programme dans lequel une fonction prend 3 paramètres a, b et c, et renvoie ensuite le résultat de l’équation ax+b=c

32. Écrire un sous-programme (procédure ou fonction) qui prend en paramètres 2 entiers p et n rentrés par l’utilisateur dans le bloc principal, et qui calcule ensuite la valeur pn. p devra changer de valeur pour prendre cette nouvelle valeur.

33. Concevoir une fonction booléenne qui prend en paramètre une variable de type tableau, et qui prend la valeur VRAI si la somme des éléments contenus dans ce tableau est paire.

34. Écrire une procédure qui prend en paramètres une matrice M et un entier i, et qui ensuite permet de remplir uniquement les cases de la ième ligne.

49


LES FICHIERS

Dans ce chapitre nous verrons qu’on peut sauvegarder de façon pérenne les informations découlant de l’exécution d’un programme. Concomitamment, nous verrons qu’un programme peut exploiter des données qui existent physiquement sur l’ordinateur.

I- GÉNÉRALITÉS

Un fichier est un ensemble d’informations homogènes regroupées sous un même nom. En algorithmique, nous dirons qu’un fichier c’est également un ensemble de données organisées en unités d’accès appelées ‘enregistrements’ ou ‘articles’ (tous du même type).

Un fichier est toujours enregistré sur un support externe à la mémoire centrale (disque dur, clé USB, disquette…). C’est pour cela que les informations qu’il contient sont dites non volatiles. Les actions les plus courantes sur les fichiers sont :

Création : définir le type du fichier ainsi que son emplacement physique.

Consultation : exploiter les articles du fichier sans en modifier un seul.

Mise à jour : ajouter, modifier ou supprimer des enregistrements ou des champs.

Le mode de représentation physique des fichiers varie d’un ordinateur à un autre. Et pour cause, cette représentation ressortit au Système d’Exploitation. Ainsi, chaque langage de programmation gère les fichiers en fonction du système sur lequel il est installé.

II- MANIPULATION DES FICHIERS DANS UN PROGRAMME

II-1) Le type Fichier :

Pascal admet 3 classes : les fichiers typés, les fichiers non typés, les fichiers texte.

50

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] :

- Les fichiers typés et non typés sont des fichiers binaires, c'est-à-dire qu’ils ne contiennent pas des informations directement lisibles par l’être humain.

- La taille maximale d’un fichier est limitée par l’espace disponible sur son support, et sa manipulation dans un programme se fait à l’aide d’un pointeur.

II-2) Déclaration des fichiers :

Soit F un fichier physique existant sur support non volatile. Utiliser F dans un algorithme revient à lui associer une variable interne f par le biais de son chemin d’accès (de F).

Il est possible que plusieurs programmes utilisent les données contenues dans un même fichier physique F. Dans un tel cas, les noms internes de F dans chacun de ces programmes ne seront pas obligatoirement identiques. Par contre leur déclaration, si.

A- Les fichiers typés

En ce qui concerne les fichiers typés, il y a 2 façons de déclarer une variable interne f.

Syntaxe 1 : Type <identificateur_fichier>=fichier de <type_des_articles>

Var f : <identificateur_fichier>

Ou plus simplement :

Syntaxe 2 : Var f : fichier de <type_des_articles>

Ces 2 déclarations permettent au programmeur de définir des fichiers constitués d’articles du type qu’il désire. Par exemple, si on veut définir un fichier qui sera constitué uniquement de nombres entiers, on va faire : Var f : fichier de entier.

* Explications

La déclaration précédente crée une variable interne f qu’on utilisera pour accéder à un fichier externe F. Ce fichier F ne pourra contenir qu’une série de nombres entiers tous codés en binaire. La taille maximale de F sera fonction de l’espace disponible sur le disque.

NB : On peut définir un fichier constitué d’articles appartenant à un type prédéfini, à l’exception du type Fichier lui-même (un fichier ne peut pas contenir d’autres fichiers).

B- Les fichiers non typés

51

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] sont très peu utilisés dans la programmation académique. Ils permettent d’introduire

dans un même fichier des articles appartenant à des types différents.

Syntaxe 1 : Type <identificateur_fichier>=fichier



Syntaxe 2 : Var f : fichier

C- Les fichiers Texte

Un fichier texte est un fichier particulier ne pouvant contenir que des informations de type texte. Il se constitue de plusieurs lignes et on le déclare à l’aide du mot-clé ‘Text’.

Syntaxe 1 : Type <identificateur_fichier>=texte



Syntaxe 2 : Var f : texte

II-3) Utilisation des fichiers :

A- L’assignation

On a vu que pour utiliser un fichier physique F dans un algorithme, il fallait que cet algorithme comporte une variable fichier f. L’association entre f et F s’effectuera donc au moyen d’un procédé appelé assignation, de telle sorte que les modifications apportées à f dans le programme affecteront directement F sur son support.

Syntaxe : ASSIGNER(f, ‘chemin_dacces_F’)

Remarques :

- ASSIGNER() est valable pour tous les types de fichiers (binaires ou texte).

- On peut utiliser une même variable f pour effectuer des modifications sur 2 fichiers physiques F et G de même type. Il suffit pour cela d’effectuer une 1ère

assignation avec le chemin d’accès de F, de travailler avec lui, puis de le fermer et d’effectuer une 2nde assignation avec cette fois le chemin d’accès de G.

52

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] L’ouverture

Après l’assignation il est question d’ouvrir le fichier pour effectuer modifications, ajouts, ou suppressions nécessaires ; ou alors pour opérer une simple consultation des données.

Syntaxes :

• OUVRIR(f) si F est un fichier existant déjà sur disque (ouverture en lecture).

• REECRIRE(f) si on veut créer un fichier F qui n’existe pas encore sur disque, ou bien qui existe déjà mais dont on veut écraser tout le contenu (ouverture en écriture).

• AJOUTER(f) si on veut ouvrir un fichier texte F en pouvant y ajouter des données (uniquement en fin de fichier).

Remarques :

- OUVRIR() rend F consultable et positionne le pointeur en début de fichier.

- Sur un fichier texte, la primitive OUVRIR() n’autorise que la lecture.

- Dans le cas où F n’existe pas sur le disque, REECRIRE() permet de créer un fichier dont le nom et le chemin d’accès sont ceux précisés pendant l’assignation.

- Il peut arriver qu’on ouvre un fichier qui ne contient aucune donnée. Le début de fichier sera alors la fin de fichier. La variable booléenne Eof(f) permet à tout moment de vérifier si le pointeur s’y trouve déjà.

C- La lecture et la mise à jour

Après l’ouverture du fichier, plusieurs possibilités sont offertes (lire les informations qu’il contient, en modifier quelques-unes, en supprimer certaines, ou alors en ajouter d’autres). Nous n’utiliserons ces possibilités que sur les fichiers typés et sur les fichiers texte.

1°) Les fichiers typés

On a vu qu’un fichier typé F était constitué d’un ensemble d’articles tous appartenant forcément à un même type. La lecture et la mise à jour de F dans l’algorithme nécessitent donc la présence d’une variable p du type de ces articles.

Syntaxes :

Lire(f, p) pour lire un article de F et insérer les données qu’il contient dans la variable p.

53

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected](f, p) pour insérer dans F un article ayant les données contenues dans la variable p. Il y a écrasement si un autre article occupait déjà le même emplacement dans le fichier.

NB : après la lecture/écriture d’un article, le pointeur se positionne immédiatement sur l’article suivant. S’il n’y en a plus, la position du pointeur devient alors la fin de fichier.

2°) Les fichiers texte

Le procédé est presque le même que précédemment, sauf que le fichier texte est considéré comme un fichier typé constitué exclusivement de lignes de texte. Ainsi, notre variable p sera obligatoirement une chaîne de caractères.

Syntaxes :

Lire(f, p) pour lire une ligne de F et l’insérer dans la variable p.

Ecrire(f, p) pour insérer à la fin de F une ligne de texte dont la valeur est contenue dans p.

Remarques :

• Lire() n’est possible que si on a ouvert le fichier texte en lecture avec OUVRIR(). Après la lecture, le pointeur se positionne immédiatement sur la ligne suivante. S’il n’y en a plus, la position du pointeur devient alors la fin de fichier.

• Ecrire() n’est possible que si on a ouvert le fichier texte en écriture avec AJOUTER().

• Pour éviter les erreurs, il vaut mieux fermer F avant de changer le mode d’ouverture.

D- La fermeture

La fermeture est une opération essentielle dans la manipulation des fichiers. Un bon programmeur ne doit donc jamais la négliger, car elle permet d’éviter les erreurs d’entrée/sortie, de préserver l’intégrité des données d’un fichier, d’optimiser un algorithme en utilisant un minimum de variables internes avec un maximum de fichiers externes.

Syntaxe : FERMER(f)

EXEMPLE : écrire un algorithme qui permet d’afficher toutes les valeurs contenues dans un fichier d’entiers F et qui permet d’ajouter une ligne de texte dans un nouveau fichier texte G

Algorithme fichiers

54

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] p : entier ; ligne : chaîne

f : fichier de entier

g : texte

DEBUT

ASSIGNER(f, ‘c:\entiers.txt’)

ASSIGNER(g, ‘c:\texte.doc’)

OUVRIR(f)

TANT QUE NON(Eof(f)) FAIRE

Lire(f, p)

Ecrire(‘Nous venons de lire le nombre ‘, p)

FINTANTQUE

FERMER(f)

Ecrire(‘Entrez un texte à ajouter dans le second fichier’)

Lire(ligne)

REECRIRE(g)

AJOUTER(g)

Ecrire(g, ligne)

FERMER(g)

FIN

TRAVAUX DIRIGÉS35. Soit un tableau contenant 100 valeurs entières. Concevoir un algorithme qui permet de

ranger les valeurs paires dans un fichier F, et les autres dans un fichier G. S’assurer que chacun de ces fichiers ne contienne pas 2 fois le même nombre.

55

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected]. Écrire un programme qui affiche tout le contenu d’un fichier texte F, puis ajoute la phrase

« BIENVENUE AU CAMEROUN » à la fin de ce fichier.

37. Soit G un fichier externe contenant une série de valeurs réelles dont on ne connaît pas le nombre, mais dont on est sait qu’il est strictement inférieur à 100. Écrire un programme qui permet de ranger ces valeurs par ordre croissant dans un nouveau fichier externe F.

38. Soit F un fichier constitué de plusieurs enregistrements de type ETUDIANTS(matricule, nom, prenom, age, sexe, solde). Concevoir des sous-programmes (procédures ou fonctions) permettant de : 1°) vérifier si un matricule est présent dans le fichier ou pas 2°) compter le nombre d’étudiants qui ont pour prénom une chaîne entrée en paramètre 3°) donner l’âge moyen des filles ayant soldé leur compte 4°) ajouter un nouvel étudiant dans le fichier 5°) ajouter 1 an à l’étudiant nommé ‘MILLA SAMUEL’.

56


LISTES CHAÎNÉES ET RÉCURSIVITÉ

Notre cours d’initiation touche à son terme. Nous avons déjà approché tous les concepts fondamentaux de création des algorithmes. Dans ce chapitre, nous aborderons légèrement 2 autres notions qui appartiennent au domaine de la programmation avancée.

I- LES LISTES CHAÎNÉES

En étudiant les tableaux, nous avons constaté qu’ils peuvent conserver un grand nombre d’informations durant le temps d’exécution du programme. Cependant, avec eux il faut obligatoirement déclarer ce nombre à l’avance ; ce qui présente un net désavantage :

- Soit ce nombre est petit et donc l’utilisateur ne peut pas rentrer toutes les informations qu’il désire.

- Soit ce nombre est trop grand et donc le programmeur gaspille de l’espace mémoire, ce qui a pour inconvénient de rendre le programme moins efficace.

Avec les listes chaînées il devient possible d’utiliser une structure contenant plusieurs valeurs différentes, ce avec l’avantage que le nombre de ces valeurs n’est jamais connu à l’avance. Cela permet de solliciter la mémoire en fonction des besoins réels du programme.

I-1) Les pointeurs :

Un pointeur est une variable contenant une adresse mémoire. Il peut donc contenir n’importe quel type de données, mais il ne sauvegardera que l’adresse de cette donnée.

Il est cependant possible de définir des pointeurs sur des zones destinées à ne recevoir que des variables d'un certain type. On utilise pour cela le symbole ^ suivi du nom du type.

Exemple : type pointeursurentier=êntier ; var p : pointeursurentier

Ou plus simplement : var p : êntier

57

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected], pour accéder à la variable pointée on utilise une fois de plus le symbole ^

derrière le nom de la variable pointeur. Exemple : Lire(p^) ou Ecrire(‘résultat=’, p^). Cela signifie que p^ sera utilisé comme n’importe quelle variable de type entier.

* Cas particulier des pointeurs sur enregistrements

La déclaration d’un pointeur sur enregistrements se fait comme suit :

Type <nom_pointeur> = ^nom_enregistrement

Nom_enregistrement=enregistrement



<champ n> : <type n>

Suivant : nom_pointeur

FinEnregistrement

Var p : nom_pointeur

Remarques :

• Le champ « suivant » permet de stocker l’adresse d’une autre variable de type pointeur, étant donné qu’on n’en connaît ni le nombre ni les emplacements. Cela aide à garder un œil sur toutes les adresses générées pendant l’exécution du programme, ainsi que sur toutes leurs valeurs, et donc à pouvoir les réutiliser.

• Lorsqu’en plus du champ « suivant » on a également un champ « précédent », on parle alors de liste chaînée double. Elle permet de parcourir la liste dans les 2 sens.

• Tout pointeur peut prendre la valeur spéciale Nil qui signifie « nulle part ». Cette valeur nous permettra de savoir que nous nous trouvons à la fin de la liste chaînée.

• La manipulation d’un champ de p se fera avec p^.champ et non avec p.champ^.

Au vu de ces remarques, on peut donc définir une liste chaînée comme étant une chaîne de valeurs repérées par leur adresse, et dans laquelle :

Chaque élément comporte l’adresse d’au moins un autre élément de la chaîne.

58

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] Le 1er élément est appelé tête et c’est par lui qu’on débute le parcours de la liste.

Le dernier élément a la valeur NIL et indique la fin de la liste chaînée.

I-2) Primitives utilisées sur les pointeurs :

Les compilateurs offrent 2 principales primitives pour gérer les adresses mémoires :

NOUVEAU(p) : elle permet d’allouer une nouvelle adresse mémoire pour stocker la variable p du type défini par le pointeur.

DISPOSER(p) : elle permet de libérer l’adresse occupée par une variable p de type pointeur, et donc de pouvoir la réaffecter à une autre variable.

EXEMPLE : écrire un algorithme qui permet d’enregistrer un nombre inconnu d’étudiants (nom, sexe, age) et permet ensuite d’afficher la liste de ces informations.

Algorithme pointeurs_etudiants

Type ecole=êtudiants

Etudiants=enregistrement

nom : chaîne[27]

sexe : chaîne[10]

age : 10..80

suivant : ecole

FinEnregistrement

Var p, q, tete : ecole

Reponse : caractère

DEBUT

NOUVEAU(p)

AVEC p^ FAIRE

Lire(nom)

59

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected](sexe)

Lire(age)

suivant NIL

FINAVEC

Tete p

Ecrire(‘Continuer ? O/N’)

Lire(reponse)

TANTQUE reponse <> ‘n’ FAIRE

NOUVEAU(q)

AVEC q^ FAIRE

Lire(nom)

Lire(sexe)

Lire(age)

suivant NIL

FINAVEC

P^.suivant q

P q

Ecrire(‘Voulez-vous ajouter un étudiant ? O/N’) ;

Lire(reponse)

FINTANTQUE

P tete

TANTQUE p <> NIL FAIRE

AVEC p^ FAIRE

Ecrire(‘Le nom de l’’étudiant est ’, nom)

60

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected](‘le sexe de l’’étudiant est ’, sexe)

Ecrire(‘l’’âge de l’’étudiant est ‘, age’)

p suivant

FINAVEC

FINTANQUE

FIN

II- LA RÉCURSIVITÉ

Une définition récursive est une définition dans laquelle intervient ce que l’on veut définir (exemple : un programme est un ensemble de petits programmes destinés à accomplir une même tâche).

En programmation, la récursivité c’est le fait pour un sous-programme de s’appeler lui-même au moins une fois.

Pour qu’une procédure ou bien une fonction soit dite récursive, elle doit avoir :

- Un nombre de cas simples pour lesquels la résolution du problème est connue. C’est en atteignant un de ces cas que le sous-programme met fin à la récursion.

- Des paramètres qui changent de valeur chaque fois que le sous-programme fait appel à lui-même. Sinon on risque de se retrouver dans une boucle indéfinie.

EXEMPLE 1 : Voici une procédure qui fait décroitre un paramètre entier jusqu’à 0 :

Algorithme recursif

Var n : entier

Procedure decroissant(n :entier)

DEBUT

SI n<>0 ALORS

Ecrire(n)

61

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected](n-1)

FINSI

FINPROCEDURE

DEBUT

Ecrire(‘ entrez un nombre entier’)

Lire(n)

Decroissant(n)

FIN

EXEMPLE 2 : Soit une machine qui ne sait réaliser que l’addition. Voici une fonction qui permet d’obtenir le produit de 2 nombres entiers :

Algorithme produit_recursif

Var a, b : entier

Fonction produit(a, b :entier) : réel

DEBUT

SI b=0 ALORS

Produit 0

SINON

Produit a + produit(a, b-1)

FINSI

FINFONCTION

DEBUT

Ecrire(‘ entrez deux nombres entiers’)

Lire(a, b)

Ecrire(‘ le produit de ces deux nombres est ‘, Produit(a, b))

62


EXEMPLE 3 : Soit une machine qui ne sait réaliser que l’addition du chiffre1. Voici une fonction qui permet d’obtenir la somme de 2 nombres entiers :

Algorithme produit_recursif

Var a, b : entier

Fonction somme(a, b :entier) : entier

DEBUT

SI b=0 ALORS

SI a=0 ALORS

Somme 0

SINON

Somme 1 + somme(a-1, 0)

FINSI

SINON

Somme 1 + somme(a, b-1)

FINSI

FINFONCTION

DEBUT

Ecrire(‘ entrez deux nombres entiers’)

Lire(a, b)

Ecrire(‘ la somme de ces deux nombres est ‘, somme(a, b))

FIN

63

Cours de Programmation par Ecclésiaste DEUDJUI (+237) 96 46 96 37 [email protected] DIRIGÉS

39. Créer une liste chaînée (avec pointeurs SUIVANT et PRECEDENT) qui permet d’enregistrer un nombre inconnu de voitures (immatriculation, couleur, marque, année de fabrication), puis affiche toutes les informations concernant les voitures de couleur rouge.

40. Concevoir un sous-programme qui utilise la structure précédente et permet à l’utilisateur de remplacer une marque entrée en paramètre par une marque de son choix. Toutes les voitures de la chaîne ayant la marque entrée en paramètre devront subir les changements.

41. Toujours avec cette même structure, concevoir un sous-programme qui prend en paramètre une immatriculation, et supprime la voiture correspondante de la chaîne.

42. Écrire une fonction récursive qui calcule la factorielle d'un entier.

43. Écrire une procédure récursive qui prend en argument un tableau d'entiers, et qui renverse ce tableau de façon que le 1er élément devienne le dernier, le 2ème l'avant-dernier…

44. Soit une machine qui ne sait que faire la soustraction du chiffre 1. Écrire un sous-programme récursif qui calcule la différence entre 2 entiers a et b, sachant qu’on ne sait pas à l’avance lequel de ces 2 nombres sera supérieur à l’autre.

45. Soit une machine qui ne sait réaliser que l’addition du chiffre1. Écrire une fonction récursive qui permettra d’obtenir le produit de 2 nombres entiers.

64

Documents

Algorithme au BTS Informatique - DoualaTour