- Page : 1/104 -

Ministère de l’Enseignement Supérieur, de la Recherche Scientifique et de la Technologie

Direction Générale des Etudes Technologiques de Radès

Institut Supérieur des Etudes Technologiques de Radès

ALGORITHMIQUE et STRUCTURES DE DONNEES 1

2008-2009

Département : Technologies de l’Informatique

Manuel de L’Etudiant

Enseignant : Belhassen GUETTAT

I n f o r m a t i qu

e

@

- Page : 2/104 -

Matière : Algorithmique et Structures de Données 1

Population : L1S1 - Tronc Commun informatique Volume horaire : 3 heures par semaine sur 15 semaines. Coefficient : 03 Crédit : 03

Objectifs Généraux OG-0 : Acquérir les connaissances préalables à l’algorithmique. OG-1 : Avoir des compétences théoriques et techniques pour pouvoir appliquer les concepts de la programmation structurée sur des problèmes simples. OG-2 : Avoir des compétences théoriques et techniques pour pouvoir appliquer les concepts de la programmation structurée sur des problèmes nécessitant le recours à des structures de données avancées. OG-3 : Avoir des compétences théoriques et techniques pour pouvoir appliquer les concepts de la programmation procédurale sur des problèmes complexes. OG-4 : Acquérir les compétences nécessaires pour présenter des solutions algorithmiques relatives à des cas industriels. OG-5 : Comprendre les algorithmes de Tri. Objectif Général 0 : Acquérir les connaissances préalables à l’algorithmique.

OS 1 : Comprendre les notions d’information et de système d’information.

OS 2 : Distinguer entre système d’information et système informatique.

OS 3 : Expliquer les différentes catégories de logiciels.

OS 4 : Comprendre le cycle de vie d’un logiciel.

Objectif Général 1 : Avoir des compétences théoriques et techniques pour pouvoir appliquer les concepts de la programmation structurée sur des problèmes simples.

OS 1 : Identifier les trois (3) parties d’un algorithme.

OS 2 : Comprendre les structures de données simples.

OS 3 : Maîtriser les actions simples.

OS 4 : Savoir utiliser un schéma conditionnel.

OS 5 : Résoudre un problème faisant appel à une boucle.

Objectif Général 2 : Avoir des compétences théoriques et techniques pour pouvoir appliquer les concepts de la programmation structurée sur des problèmes nécessitant le recours à des structures de données avancées.

OS 1 : Comprendre les types construits.

- Page : 3/104 -

OS 2 : Comprendre le type tableau.

OS 3 : Appliquer le type tableau pour réaliser certains traitements.

OS 4 : Comprendre le type matrice.

OS 5 : Appliquer le type matrice sur certains problèmes.

OS 6 : Distinguer le type tableau de caractères du type chaîne de caractères.

OS 7 : Appliquer le type chaîne pour résoudre certains problèmes.

Objectif Général 3 : Avoir des compétences théoriques et techniques pour pouvoir appliquer les concepts de la programmation procédurale sur des problèmes complexes.

OS 1 : Comprendre le concept de la programmation procédurale.

OS 2 : Savoir décomposer un problème complexe en des sous problèmes simples.

OS 3 : Maîtriser l’utilisation des fonctions pour un problème donné.

OS 4 : Maîtriser l’utilisation des procédures pour un problème donné.

OS 5 : Appliquer les concepts de la programmation procédurale sur un problème complexe.

OS 6 : S’initier au concept de la récursivité.

Objectif Général 4 : Acquérir les compétences nécessaires pour présenter des solutions algorithmiques basées sur les structures enregistrement et fichier.

OS 1 : Comprendre le type Enregistrement.

OS 2 : Comprendre le type Fichier.

OS 3 : Appliquer les types enregistrement et fichier pour réaliser des traitements sur des données stockées.

Objectif Général 5 : Comprendre les algorithmes de Tri.

OS 1 : Comprendre les algorithmes de tri (3).

OS 2 : Exécuter à la main les 3 algorithmes précédents.

OS 3 : Comparer ces algorithmes en terme de performance.

- Page : 4/104 -

LES PREALABLES A L’ALGORITHMIQUE – L’Essentiel du Cours –

Information, Donnée, Système d’information, Système informatique, Logiciel, Progiciel, ERP, Cycle de vie d’un logiciel, Structure d’un Algorithme

Objectif Général 0 : Acquérir les connaissances préalables à l’algorithmique. Objectifs Spécifiques : OS 1 : Comprendre les notions d’information et de système d’information. OS 2 : Distinguer entre système d’information et système informatique. OS 3 : Expliquer les différentes catégories de logiciels. OS 4 : Comprendre le cycle de vie d’un logiciel. Rappel du Cours : RECOMMANDATIONS :

(i) Un algorithme n’est jamais lié à un langage. (ii) Un algorithme doit être lisible, clair et compréhensible. (iii) Un algorithme doit obligatoirement faire l’objet d’une analyse préalable. (iv) Un algorithme doit être testé en déroulant sa table d’exécution. (v) Dans certains algorithmes, il est conseillé de schématiser préalablement

l’arbre de décision du problème en question. (vi) Une fois l’algorithme écrit et testé, voir la possibilité de l’optimiser.

REGLES D’APPLICATION :

(i) Faire apparaître les trois parties : Identification, Déclaration et Actions. (ii) Tout nom attribué à un objet de l’algorithme (nom de l’algorithme, nom d’une

constante, nom d’une variable, nom d’un type, etc.) doit respecter les règles de constitution d’un identificateur (ne doit pas dépasser les 8 caractères, doit commencer obligatoirement par une lettre, ne doit pas contenir d’espaces, ne doit pas contenir de caractères spéciaux autre que le tiret-bas ‘_’, doit être unique).

(iii) Il est conseillé d’utiliser des identificateurs significatifs. (iv) Pour garantir la lisibilité d’un algorithme, faire apparaître des commentaires

et utiliser des indentations. (v) L’ordre d’apparition des actions est important dans un algorithme.

DEFINITIONS :

Information : Renseignement sur un sujet bien déterminé.

Donnée : Information qui n’a pas de sens.

Qualité d’une information : Rapidité d’obtention, Fiabilité et Diffusabilité.

- Page : 5/104 -

Système d’information : Ensemble d’informations, de moyens, d’outils, de procédures, de méthodes, de techniques, de règles, de normes et de documents permettant de gérer et de manipuler les informations.

Système informatique : Ensemble de moyens matériel et logiciels permettant de satisfaire les besoins informatiques des utilisateurs.

Catégories de systèmes d’information : Manuel, Mécanisé et Informatisé.

Classification des systèmes d’information : EDP, MIS, DSS et ES.

Logiciel : Ensemble de programmes destinés à faciliter l’exécution des tâches courantes des utilisateurs dans un domaine donné ; par exemple un logiciel de facturation ou de comptabilité.

Progiciel : Logiciel standard ; par exemple Microsoft Word, Autocad, Microsoft Access, etc.

Logiciel Libre : Logiciel qui n’a pas de propriétaire ; en l’achetant on aura tous les droits (changement de contenu, duplication, etc.). Comme exemple, on peut citer Linux, Kylix et MySql.

Progiciel de Gestion Intégrée (ERP) : Progiciel qui couvre toutes les fonctionnalités informatiques d’une organisation. Il est destiné aux grandes entreprises.

Cycle de vie d’un logiciel : Ce sont les différentes étapes par lesquelles un projet d’informatisation doit suivre pour aboutir à un logiciel de qualité. Il existe plusieurs modèles représentant un cycle de vie : Cascade, V, Spirale, etc.

Selon le modèle en cascade, les étapes sont : Spécifications, Analyse, Conception, Codage, Tests et Mise en exploitation.

L’algorithme fait partie de la conception logique de la solution.

Un algorithme est le résultat d’une démarche logique permettant la résolution d’un problème donné.

L’Algorithmique est la logique utilisée pour écrire des algorithmes. On dit également Algorithmie.

On distingue différents types de problèmes : Structurés, Semi-Structurés et Non-Structurés.

En Algorithmique, on ne traitera que des problèmes structurés : des problèmes dont on connaît à l’avance une solution mathématique.

Un Algorithme est constitué de trois parties : Identification, Déclaration et Actions.

- Identification : la partie dans laquelle on attribue un nom à l’algorithme ; ce nom doit respecter les règles de l’identificateur.

- Déclaration : Dans cette partie, on déclare tous les objets impliqués dans la partie Actions ; dans l’ordre, on mentionnera les Constantes, les Types, les Variables et les Sous-programmes.

- Actions : Dans cette partie, sont décrites dans un ordre logique et séquentiellement toutes les opérations à faire pour obtenir le résultat souhaité.

- Page : 6/104 -

LA PARTIE DECLARATION :

Une variable est un emplacement mémoire capable de prendre plusieurs valeurs lors de l’exécution d’un programme, mais à un instant donné de l’exécution, elle ne peut contenir qu’une et une seule valeur.

Une variable est caractérisée par son nom, son type, et son contenu.

Une constante est une variable dont le contenu reste inchangé tout au long de l’exécution d’un programme.

Un type est l’ensemble de valeurs que peut prendre une variable. Dans cette rubrique, on ne déclare que les types composés ; les types simples seront indiqués au moment de la déclaration des variables.

Les sous-programmes sont répartis en deux catégories : les fonctions et les procédures.

LA PARTIE ACTIONS :

Les actions doivent être finies, séquentielles et ordonnées.

On distingue différentes structures représentant les actions : structures linéaires (actions simples), structures conditionnelles (SI), structures de choix (SELON) et les structures répétitives (Répéter, Tant que et Pour).

- Page : 7/104 -

LES PREALABLES A L’ALGORITHMIQUE – Exercices Proposés –

Information, Donnée, Système d’information, Système informatique, Logiciel, Progiciel, ERP, Cycle de vie d’un logiciel, Structure d’un Algorithme

1- Parmi les termes suivants, le(s) quel(s) ne constitue(nt) pas une source d’information ?

Un tuyau.

Une rumeur.

Une histoire.

Un plan de ville. 2- Parmi les propositions suivantes, laquelle est correcte ?

L’information est une donnée.

L’information est un renseignement.

L’information est le journal télévisé.

Aucune de ces réponses. 3- Parmi les éléments suivants, le(s) quel(s) ne font pas partie des critères de qualité d’une information ?

Compréhensibilité.

Fiabilité.

Rapidité.

Diffusivité. 4- Parmi les exemples suivants, le(s) quel(s) constitue(nt) une donnée ?

Nom = « Mohamed ».

ISET de Radès.

PGCD(a,b)=c.

Aucune de ces réponses. 5- On veut calculer et obtenir la moyenne arithmétique M de deux réels N1 et N2 ; complétez la figure ci-dessous. Données ……………… En ……………. En Sortie 6- Parmi les informations suivantes, les quelles se rapportent à l’étudiant ?

Code classe.

Nom de l’institut.

Code de la matière.

Age de l’étudiant. 7- Parmi les verbes suivants, le(s) quel(s) ne figure(nt) pas dans la définition d’un système d’information ?

Restituer.

Jouer.

Traiter.

Enregistrer. 8- Enumérez les trois types de systèmes d’informations vus en cours ?

Étapes de Résolution

Opération 1 : Opération 2 : Opération 3 : Opération 4 :

- Page : 8/104 -

Système d’information ……………………

Système d’information ……………………

Système d’information …………………… 9- On considère le système d’information d’un petit commerce « Boutique de vente de produits cosmétiques » ; on vous demande d’associer aux rubriques suivantes les informations nécessaires ?

Moyens : ………………………………………………………………..

Outils : ………………………………………………………………..

Méthodes : ………………………………………………………………..

Techniques : ………………………………………………………………..

Règles : ………………………………………………………………..

Procédures : ………………………………………………………………..

Normes : ………………………………………………………………..

Documents : ……………………………………………………………….. 10- Parmi les propositions suivantes, laquelle est correcte ? Un système d’information informatisé est un

système informatique qui gère des informations.

système d’information dont toutes les procédures sont informatisées.

système d’information dont certaines procédures sont informatisées.

Aucune de ces réponses. 11- Enumérez selon les périodes, les architectures des systèmes d’informations présentées par les américains ?

de ………. à ……….. : Système d’Information …………. (Anglais : ……………….)

de ………. à ……….. : Système d’Information …………. (Anglais : ……………….)

de ………. à ……….. : Système ………..…………………. (Anglais : ………………)

de ………. à ……….. : Système ………..…………………. (Anglais : ………………) 12- Complétez le tableau suivant :

EDP MIS DSS ES Redondance des informations

Incohérence des données

Fiabilité des informations

Prise de décision facile

Prise de décision automatique

Proposition des solutions

Problèmes traités sont structurés

Utilisation des bases de données

Édition de tableaux de bord

13- Parmi les éléments suivants le quel n’est pas un progiciel ?

Microsoft Word.

Macro média Flash.

Gestion de la scolarité.

Adobe Photoshop. 14- Parmi les progiciels suivants le quel est un ERP ?

Microsoft Office.

- Page : 9/104 -

Saari Compta.

Navision.

Autocad. 15- Complétez le tableau suivant :

Logiciel Progiciel Adaptation et exploitation Livraison avec quoi ? Évolutivité ? Maintenabilité ? Coût ?

16- Parmi les propositions suivantes laquelle n’est pas correcte ?

un ERP est un progiciel qui couvre toutes les fonctionnalités informatisables d’un système d’information.

un ERP est destiné uniquement aux grandes entreprises.

un ERP peut-être acheté sans une étude et des actions préalables.

un ERP est coûteux. 17- Dans ce qui suit, on vous présente des propositions de systèmes informatiques et on vous demande de sélectionner la bonne.

Ensemble de logiciels utilisés par des utilisateurs.

Outils informatiques nécessaires pour le travail quotidien.

Ensemble de matériel et de connectique permettant de satisfaire les utilisateurs.

Aucune de ces réponses. 18- Les problèmes proposés ci-dessous ne sont pas tous structurés. Le(s) sélectionner.

Calcul de la racine carré d’un nombre réel.

Détermination du PGCD de deux entiers.

Détermination astronomique du jour de l’Aîd.

Choix d’un ordinateur. 19- Lors du développement de tout logiciel, on doit suivre un modèle de cycle de vie pour

Respecter les délais.

Satisfaire les besoins des utilisateurs.

Assurer une production de qualité.

Aucune de ces réponses. 20- Parmi les langages suivants, lequel est utilisé lors de l’écriture d’un algorithme ?

Java.

C.

Pascal.

Aucune de ces réponses. 21- Pour écrire un algorithme et en vue d’assurer une bonne lisibilité, on fait recours à certains outils tels que :

Un interpréteur.

Un éditeur de texte (Bloc Notes).

Un éditeur algorithmique (EDITALGO).

Un traitement de texte (Word). 22- Avant d’exécuter un programme, il faut :

Le compiler après l’avoir ouvert à partir du disque dur.

- Page : 10/104 -

Le compiler à partir de la mémoire centrale.

Le charger préalablement en mémoire centrale puis le compiler.

Aucune de ces réponses. 23- Pour chaque progiciel proposé, donnez une brève description :

Bloc Notes : * Paint :

Word Pad : * EditAlgo :

Word : * Storm :

Excel : * Ciel Compta:

Power Point : * Autocad :

Access : * Photoshop :

Turbo C : * FrontPage :

Visual C : * Director : 24- Pour chaque étape du cycle de vie d’un programme, faîtes correspondre l’output attendu :

N° Intitulé Etape Output Attendu

01 Spécifications des besoins

02 Analyse de l’existant

03 Solution logique

04 Réalisation

05 Test

06 Mise en exploitation 25- Enumérez les différentes parties d’un algorithme et indiquez pour chaque partie les précautions à prendre :

Intitulé Précautions

Partie 1

Partie 2

Partie 3

26- Pour chaque identificateur proposé, répondez par Valide ou Non Valide.

Nom de variable Réponse Nom de variable Réponse

prod_a Valide c123

$total new bal

moyenne sum.of

9ab6 grade1

_c3 réponse

Newbal 1234

27- Dans un algorithme, on distingue différents types d’actions ; lequel ne doit pas y figurer ?

Actions simples.

Structures de contrôle.

Structures de données.

Aucune de ces réponses. 28- Parmi les verbes suivants, lequel n’est pas un verbe de lecture ?

Saisir.

- Page : 11/104 -

Ecouter.

Donner.

Fournir. 29- Parmi les verbes suivants, lequel est un verbe d’écriture ?

Entrer.

Enregistrer.

Numériser.

Introduire. 30- Parmi les affectations suivantes, laquelle n’est pas correcte ?

a (b ou c) non(d).

a a*b

a Non(b)

Aucune des ces réponses. 31- Pour chaque expression proposée, donnez le résultat correspondant ?

N° Expression Résultat produit

01 3 * 4 / 6 + 6 02 2 * 3 / 12 * 8 / 4

03 10 * ( 1 + 7 * 3 ) 04 ( 20 - 2 ) / ( 6 + 3 )

05 10 + 15 % 2 + 4 * 3 06 10 + 17 % 3 + 4 07 (10 + 15 % 2 + 4.3)+( ( 20 - 2 ) / ( 6 + 3 ))

32- Quelle est la différence entre donnée et structure de données ? Donnée :……………………..…………………………………………………….… Structure de données : ……………………………………………………….….… ……………………………………………………………………………...…………

33- Énumérez les types simples ? Type 1 : ……….…………………………………………………………………… Type 2 : ……………………………………………………………………………. Type 3 : ……………………………………………………………………………. Type 4 : …………………………………………………………………………….

34- Donnez les tables de vérité des propositions suivantes ?

(A et B) ou (non B)

(non A) et (non B)

(A et B) et (non A)

non (A et (non B)) Pour chacune de ces propositions, trouvez une autre proposition plus simple (c'est à dire avec moins d'opérateurs) équivalente. Rappel: deux propositions sont équivalentes si elles ont la même valeur de vérité dans tous les cas possibles.

A B (A et B) ou (non B)

(non A) et (non B) (A et B) et (non A) non(A et (non B))

- Page : 12/104 -

Autre

Proposition

35- Pour chacun des tableaux proposés, on vous demande d’évaluer le contenu des variables I, J et S en fonction de l’avancement de l’exécution des différentes actions. Action I J S

I <- 5

I <- 2

I<- I+4

J<- I+1

J <- J-1

S <- I + J*2

S <- S -J

Action I J S

I <- 3

J <- 2

I<- -1+4

J<- I+1

I <- J-1

J <- I + J*2

S <- S -J

- Page : 13/104 -

LES ALGORITHMES DE BASE – l’Essentiel du Cours –

Structures de données simples, Lecture, Ecriture, Affectation, Structures conditionnelles (SI), Structures conditionnelles (SELON), Boucle REPETER,

Boucle TANT QUE, Boucle POUR.

Objectif Général 1 : Avoir des compétences théoriques et techniques pour pouvoir appliquer les concepts de la programmation structurée sur des problèmes simples. Objectifs Spécifiques : OS 1 : Identifier les trois (3) parties d’un algorithme. OS 2 : Comprendre les structures de données simples. OS 3 : Maîtriser les actions simples. OS 4 : Savoir utiliser un schéma conditionnel. OS 5 : Résoudre un problème faisant appel à une boucle. Rappel du Cours : LA PARTIE DECLARATION :

Une variable est un emplacement mémoire capable de prendre plusieurs valeurs lors de l’exécution d’un programme, mais à un instant donné de l’exécution, elle ne peut contenir qu’une et une seule valeur.

Une variable est caractérisée par son nom, son type, et son contenu.

Une constante est une variable dont le contenu reste inchangé tout au long de l’exécution d’un programme.

Un type est l’ensemble de valeurs que peut prendre une variable. Dans cette rubrique, on ne déclare que les types composés ; les types simples seront indiqués au moment de la déclaration des variables.

Les sous-programmes sont répartis en deux catégories : les fonctions et les procédures.

LA PARTIE ACTIONS :

Les actions doivent être finies, séquentielles et ordonnées.

On distingue différentes structures représentant les actions : structures linéaires (actions simples), structures conditionnelles (SI), structures de choix (SELON) et les structures répétitives (Répéter, Tant que et Pour).

LES TYPES SIMPLES :

Ils sont au nombre quatre : Entier, Réel, Caractère et Booléen (Logique).

Opérations sur les types simples :

Type : Entier Type : Réel Type : Caractère Type : Booléen Addition : + Addition : + Suivant : Suiv ET

Soustraction : - Soustraction : - Précédant : Prec OU

Multiplication : * Multiplication : * CHR(n) NON

Division entière : Div Division : / ORD(ch)

Reste de la Division : MOD

- Page : 14/104 -

LES ACTIONS SIMPLES : STRUCTURES LINEAIRES

Lecture : opération qui consiste à introduire les données à partir des périphériques d’entrée (clavier, souris, scanner, microphone, etc.) pour exécuter un programme.

Écriture : opération qui consiste à produire le(s) résultat(s) sur les périphériques de sortie (écran, imprimante, traceur, imprimante 3D, etc.), suite à l’exécution d’un programme.

Affectation : opération qui consiste à placer une valeur dans une variable (notée par le symbole ) ; cette valeur peut être une constante, le contenu d’une autre variable ou le résultat d’une expression arithmétique.

Lorsqu’une valeur est affectée à une variable, l’ancien contenu de cette variable sera écrasé.

Dans l’exécution d’une expression arithmétique, certaines règles de priorité doivent être respectées : l’ordre de priorité est accordé comme suit :

- Parenthèses. - Multiplication et Division. - Addition et Soustraction.

Si dans une expression, on aura deux opérateurs ayant la même priorité, on commence alors par exécuter l’opérateur situé le plus à gauche.

Un exemple typique de l’affectation : le problème de permutation. Dans ce cas, on doit toujours utiliser une seule variable intermédiaire (auxiliaire) quelque soit le nombre de variables à permuter.

Avant toute lecture, il est recommandé de faire une action d’écriture pour expliquer la nature de la lecture. Ça ne fait qu’améliorer la convivialité du programme.

LES STRUCTURES CONDITIONNELLES

On distingue trois formes de représentation d’une structure conditionnelle : - Structure conditionnelle à choix simple. - Structure conditionnelle à deux choix complémentaires. - Structure conditionnelle à choix imbriqués.

Structure conditionnelle à choix simple : Traitement qui s’exécute lorsqu’une condition logique est satisfaite ; dans le cas contraire, rien ne devra se passer.

SI (<Cond_Logique_Vraie>) ALORS <Traitement> FINSI

Cette structure est préconisée dans le traitement des exceptions.

Structure Conditionnelle à deux choix complémentaires : Traitement qui s’exécute lorsqu’une condition logique est satisfaite ; dans le cas contraire un autre traitement sera exécuté ; ces deux traitements ne contiennent que des actions simples.

SI (<Cond_Logique_Vraie>) ALORS <Traitement1>

- Page : 15/104 -

SINON <Traitement2> FINSI Avec <Traitement1> et <Traitement2> contenant que des actions simples.

Structure Conditionnelle à choix imbriqués : Traitement qui s’exécute lorsqu’une condition logique est satisfaite ; dans le cas contraire un autre traitement pourrait être exécuté ; l’un au moins de ces deux traitements doivent contenir des structures conditionnelles à choix simple ou à deux choix complémentaires.

SI (<Cond_Logique_Vraie>) ALORS <Traitement1> SINON <Traitement2> FINSI Avec <Traitement1> et/ou <Traitement2> contenant que des structures conditionnelles à choix simple ou à deux choix imbriqués.

Les Structures de Choix (SELON)

Traitement qui s’exécute parmi plusieurs traitements en fonction d’un choix donné parmi plusieurs ; l’exécution de ce traitement exclut systématiquement l’exécution de tous les autres qui sont avant et après ce choix.

SELON (nomvar) FAIRE Valeur 1 : <Traitement1> Valeur 2 : <Traitement2> Valeur 3 <Traitement3> . : . . : . . : . Valeur N : <TraitementN> Autre : <Traitement_Erreur> FINSELON

LES STRUCTURES REPETITIVES (LES BOUCLES) On distingue trois schémas de représentation d’une boucle :

- Le schéma Répéter ……………. Jusqu’à. - Le schéma Tantque …………… Fin Tantque. - Le schéma Pour ……………….. Fin Pour.

Le schéma itératif Répéter : Traitement qui s’exécute et qui continue à s’exécuter jusqu’à ce qu’une condition logique devienne vraie ; cette condition logique est appelée condition d’arrêt.

Répéter <Traitement>

nomvar est appelée Sélecteur ou variable de choix.

nomvar et les Valeur I doivent être de même type.

Le sélecteur doit être connu (lecture ou affectation) avant l’exécution de Selon.

Les seuls types autorisés pour le sélecteur sont : Entier, Caractère, Ensemble d’entiers, Ensemble de caractères, Intervalle d’entiers et Intervalle de caractères.

- Page : 16/104 -

Jusqu’à (<Cond_Arrêt_Atteinte>)

Déroulement de l’exécution de la boucle Répéter : - Etape 0 : Initialiser les variables de la condition d’arrêt. - Étape 1 : Exécuter le traitement de la boucle. - Étape 2 : Mettre à jour les variables de la condition d’arrêt. - Étape 3 : Tester la condition d’arrêt Si Vraie Alors Aller à l’étape 4 Sinon Aller à l’étape 1 - Etape 4 : Sortir de la boucle et continuer l’exécution du programme après

Jusqu’à.

Avec Répéter le traitement s’exécute au moins une seule fois quelle que soit la situation.

Le schéma itératif Tant que : Traitement qui ne peut s’exécuter que si une condition d’exécution est satisfaite ; le traitement continue alors à s’exécuter et ne s’arrêtera que lorsque la condition d’exécution cessera d’être vraie.

Tant que (<Cond_Exécution_Vraie>) Faire <Traitement> Fin Tantque

Déroulement de l’exécution de la boucle Tant que : - Etape 0 : Initialiser les variables de la condition d’exécution. - Étape 1 : Tester la condition d’exécution Si Vraie Alors Aller à étape 2 Sinon Aller à étape 4. - Etape 2 : Exécuter le traitement de la boucle. - Étape 3 : Mettre à jour les variables de la condition d’exécution et Aller à

Etape 1. - Étape 4 : Sortir de la boucle et continuer l’exécution du programme après

Fin Tant que.

Avec le schéma répéter, le traitement s’exécute zéro ou plusieurs fois.

Le schéma itératif Pour : Traitement qui s’exécute et qui continue à s’exécuter sur une plage de valeurs connue à l’avance. Le traitement s’arrête lorsque les bornes de cette plage sont dépassées.

Pour nomvar Allant de Vi à Vf (Pas=P) Faire <Traitement> Fin Pour

Vi : valeur initiale de la plage de valeurs. Vf : valeur finale de la plage de valeurs. P : valeur du Pas ; c’est la valeur utilisée pour incrémenter nomvar.

Dans le schéma Pour, nomvar est appelé Compteur ; il doit être de type Entier.

Dans le schéma Pour, l’incrémentation du compteur est automatique en fonction de la valeur du Pas.

Déroulement de l’exécution de la boucle Pour : - Etape 1 : Exécuter le traitement de la boucle.

- Page : 17/104 -

- Étape 2 : Incrémenter nomvar en fonction de la valeur du Pas (nomvar nomvar + P).

- Étape 3 : Tester si nomvar est toujours dans l’intervalle ou non Si Oui Alors Aller à Etape 1 Sinon Aller à Etape 4

- Etape 4 : Sortir de la boucle et continuer le traitement après Fin Pour.

Avec le schéma Pour, le traitement s’exécute (Vf – Vi + 1) fois.

L’Application de l’un de ces trois schémas dépend de la nature de l’énoncé ; par exemple, si on connaît à l’avance le nombre d’itérations à faire, on peut opter pour le schéma Pour.

- Page : 18/104 -

LES ALGORITHMES DE BASE – Exercices Proposés –

Structures de données simples, Lecture, Ecriture, Affectation, Structures conditionnelles (SI), Structures conditionnelles (SELON), Boucle REPETER,

Boucle TANT QUE, Boucle POUR.

Exercice 1 Déterminez et corrigez les erreurs se trouvant dans les algorithmes suivants: 1er Algorithme

Algorithme Initial Anomalies Algorithme Corrigé Algorithme calcul_aire largeur ← 15 aire ← largeur * longueur Fin

Algorithme …………………………… …………………………… Début ……………………..……. ………………………..…. ……………………..……. Fin

2éme Algorithme

Algorithme Initial Anomalies Algorithme Corrigé Algorithme calcul_périmètre début largeur entier longueur entier perimetre réel perimetre ← (largeur + longueur) * 2 largeur ← 15 longueur ← 10 fin

Algorithme …………………………… …………………………… …………………………… Début ……………………..……. ………………………..…. ……………………..……. Fin

3éme Algorithme

Algorithme Initial Anomalies Algorithme Corrigé Algorithme calcul_moyenne début note1 réel note2 réel moyenne réel note1 ← 15 note2 ← 15 (note1 + note2) /2 ← moyenne fin

Algorithme …………………………… …………………………… …………………………… Début ……………………..……. ………………………..…. ……………………..……. Fin

Exercice 2 Écrivez un algorithme qui met la valeur 16 dans la variable num1 et la valeur 18 dans la variable num2, ensuite il calcule et affiche leur total et leur moyenne. Pouvez-vous proposer une solution plus optimale ?

Algorithme TOTMOY Algorithme TOTMOY1 (*Optimal*)

- Page : 19/104 -

Variable

………………….………………………………

………………………………………………….

Début

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

Fin

Variable

………………….……………………..………

………………………………………………….

Début

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

Fin

Exercice 3 Écrivez un algorithme qui convertit une température en degré Fahrenheit en une température degré Celsius, sachant que la température en degré Fahrenheit est égale à 41. Temp_Cel = 5 / 9 * (Temp_Far - 32)

Algorithme Temperat Variable

………………….………………………………

………………………………………………….

Début

………………………………………………….

………………………………………………….

………………………………………………….

Fin

Algorithme Temperat (*Amélioré*) Variable

………………….………………………………

………………………………………………….

Début

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

Fin

Exercice 4 Écrivez un algorithme qui calcule et affiche l'intérêt fixe d'un prêt dont la valeur est égale à 7000 DT et le taux est de 12.5%. Intérêt = Prêt * Taux.

Algorithme Int_fixe Variable

Algorithme Int_fixe (*Amélioré*) Variable

- Page : 20/104 -

…………………………….……………………

………………………………………………….

Début

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

Fin

…………………………….……………………

………………………………………………….

Début

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

Fin

Exercice 5 Écrivez un algorithme permettant de lire le salaire brut, les primes et les indemnités, et les taxes puis afficher le salaire net.

Salaire net = salaire brut + primes + indemnités – taxes. Algorithme Sal_Net Variable

…………………………….……………………

………………………………………………….

Début

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

Fin

Algorithme Sal_Net (*Optimal*) Variable

………………….………………………………

………………………………………………….

Début

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

Fin

Exercice 6 Écrivez un algorithme qui affiche le nombre de centaines, de dizaines et d’unités d’un entier N (composé de trois chiffres), saisi à partir du clavier.

Algorithme Decomp_N Algorithme Decomp_N (*Optimal*)

- Page : 21/104 -

Variable

………………….………………………………

………………………………………………….

Début

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

Fin

Variable

…………………………….……………………

………………………………………………….

Début

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

………………………………………………….

Fin

Exercice 7 On considère l’algorithme suivant constitué de trois structures conditionnelles à un seul choix. Algorithme abc Variable a, b, c, temp : entier Début Écrire ("a=") lire (a) Écrire ("b=") lire (b) Écrire ("c=") lire (c)

si b > a alors

temp ← a

a ← b I

b ← temp

finsi

si c > a alors

temp ← a

a ← c II

c ← temp

finsi

- Page : 22/104 -

si c > b alors

temp ← b

b ← c III

c ← temp

finsi

Écrire (a,b,c)

Fin

7.1. Complétez le tableau ci-dessous en précisant la valeur contenue dans chaque variable après l'exécution des instructions I, II et III.

a b c

Valeurs initiales 1 5 10

( I )

( II ) ( III )

Valeurs initiales 20 14 17 ( I )

( II ) ( III )

Valeurs initiales 11 9 25 ( I )

( II ) ( III )

7. 2. Que fait cet algorithme ?

…………………………………………………………………………………………………

……

…………………………………………………………………………………………………

……

Exercice 8 Soient les instructions suivantes: Si a < b Alors c ← b + 10 Sinon c ← a +25 FinSi

- Page : 23/104 -

Donnez pour chaque valeur du couple a et b la valeur contenue dans c après l'exécution de ces instructions.

a b c

4 20

5 5

17 6

Exercice 9 Écrivez un algorithme qui vérifie si l’entier saisi à partir du clavier est pair ou impair.

Algorithme Pair_Imp Variable ………………………………………..

Début

…………………………………………………

.

…………………………………………………

.

…………………………………………………

.

…………………………………………………

.

…………………………………………………

.

…………………………………………………

.

…………………………………………………

..

Fin

Commentaires devant chaque ligne ……………………………………………….

……………………………………………

….

……………………………………………

….

……………………………………………

….

……………………………………………

….

……………………………………………

….

……………………………………………

….

……………………………………………

….

Exercice 10 Écrivez un algorithme qui lit un réel et affiche sa valeur absolue.

Algorithme Val_Abs Variable

Commentaires devant chaque ligne

- Page : 24/104 -

……………………….……………………….. Début …………………………………………………

.

…………………………………………………

.

…………………………………………………

.

…………………………………………………

.

…………………………………………………

.

…………………………………………………

..

Fin

………………………………………………. ……………………………………………

….

……………………………………………

….

……………………………………………

….

……………………………………………

….

……………………………………………

….

……………………………………………

….

Exercice 11 Écrivez un algorithme qui lit un caractère et affiche si c'est une lettre de l'alphabet.

Algorithme Alphabet Type Alphab = Variable ……………………..………………………….. Début

…………………………………………………

.

…………………………………………………

.

…………………………………………………

Commentaires devant chaque ligne ……………………………………………

….

……………………………………………

….

……………………………………………

….

……………………………………………

- Page : 25/104 -

.

…………………………………………………

.

…………………………………………………

.

…………………………………………………

..

Fin

….

……………………………………………

….

……………………………………………

….

……………………………………………

….

……………………………………………

….

……………………………………………

….

Exercice 12 Écrivez un algorithme qui lit les paramètres d'une équation de premier degré ax+b=0 et affiche sa solution. Algorithme Equat1 Variable ……………………………..………………….. Début …………………………………………………

.

…………………………………………………

.

…………………………………………………

.

…………………………………………………

.

…………………………………………………

.

…………………………………………………

.

Suite de l’algorithme Equat1 ………………………………………………

.

………………………………………………

.

………………………………………………

.

………………………………………………

.

………………………………………………

.

………………………………………………. Fin

Exercice 13 Écrivez un algorithme permettant de lire la valeur de la température de l'eau et d'afficher son état :

- Page : 26/104 -

• Glace : t ≤ 0

• Eau : 0 < t ≤ 100

• Vapeur : 100 < t ≤ 1500

• Plasma : 1500 < t

Algorithme Etat_Obj Variable.……………………………………….. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Algorithme Etat_Obj (* 2eme solution *) Variable.……………………………………….. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Exercice 14 A partir de la saisie du prix unitaire d’un produit (PU) et de la quantité commandée (QTCOM), afficher le montant à payer en détaillant le coût du transport et la remise.

• Le transport est gratuit si le montant total des produits TOT = PU x QTCOM est supérieur à 1000 dinars, dans le cas contraire le transport est de 2% du TOT. • La remise est de 5% si le montant total après transport est compris entre 500 et 2000 dinars et de 10% au delà.

Algorithme Montant Variable ………………………………………………….. ………………………………………………….. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Algorithme Montant (* Autre solution*) ………………………………………………….. ………………………………………………….. ………………………………………………….. ………………………………………………….. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

- Page : 27/104 -

…………………………………………………..

…………………………………………………..

Fin

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Exercice 15 Cet algorithme doit permettre de calculer un salaire net à partir d’un salaire brut et de certains renseignements concernant la situation de l'utilisateur. L’utilisateur devra saisir au clavier : • Son salaire brut [montant réel] • Sa situation :

• a-t-il des frères et/ou des soeurs (o/n) [caractère] • est-il boursier (o/n) [caractère]. Aucun contrôle de validité de la saisie des entrées ne sera effectué. Le taux d’imposition est déterminé à partir d’un taux de base, ici 10%, et de critères sociaux et familiaux. Le salaire net sera affiché à l’écran [montant réel]. • Impôt de base = 0.1 • Si la personne n’a ni frère ni soeur : impôt + 0.05 • Si la personne est boursière : impôt - 0.05

Le salaire net [montant réel] est le produit du taux d’imposition (1-impôt) et du salaire brut.

Algorithme Salaire Variable ………………………………………………….. ………………………………………………….. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Algorithme Salaire (* Autre solution*) ………………………………………………….. ………………………………………………….. ………………………………………………….. ………………………………………………….. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

- Page : 28/104 -

Exercice 16 Écrivez un algorithme qui permet de saisir un numéro de couleur de l'arc-en-ciel et d'afficher la couleur correspondante.

1- rouge 2- orangé 3- jaune 4- vert 5- bleu 6- indigo 7- violet

Exercice 17 17.1. Écrivez un algorithme permettant de répéter l'affichage de la question voulez-vous continuez? Jusqu'à ce que la réponse soit la lettre ‘o ‘pour oui ou la lettre ‘n’ pour non.

Algorithme Afficher Variable ………………………………………. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Algorithme Afficher (* avec Tant que *) Variable ………………………………………. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Solution

- Page : 29/104 -

Fin Fin 17.2. Réécrivez l'algorithme précédant de telle façon qu'il s'exécute de la façon suivante:

voulez-vous continuez? y o/n svp 1 o/n svp o vous avez dit oui.

Algorithme Afficher1 Variable ………………………………………. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Algorithme Afficher1 (* avec Tant que *) Variable ………………………………………. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Exercice 18

Écrivez un algorithme qui lit un entier à partir du clavier et affiche son carré ; il s'arrête lorsqu’on entre la valeur 0.

Algorithme Aff_ent Variable ………………………………………. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

Algorithme Aff_ent(* avec Tant que *) Variable ………………………………………. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

- Page : 30/104 -

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Exercice 19

Soit l'algorithme suivant: Algorithme aff_5nbr Variable i : entier val : réel Début val ← 1 i 1 Répéter val ← (val + 1) * 2 écrire (val) i i + 1 Jusqu’à (i=>5) Fin

Que va afficher cet algorithme ?

Affichage à l’écran

Etat Initial de val : ……

Itération 1 : ..…………..

Itération 2 : ..…………..

Itération 3 : ..…………..

Itération 4 : ..…………..

Itération 5 : ..…………..

Itération 6 : ..…………..

Commentaires sur l’affichage

C1 : …………………………………………. C2 : ………………………………………….

Exercice 20

Écrivez un algorithme qui lit 10 valeurs réelles et qui détermine la moyenne des valeurs strictement positives et la moyenne des valeurs strictement négatives.

Algorithme Aff_10nbr Variable ……………………………………….

Algorithme Aff_10nbr (* avec Répéter *) Variable ……………………………………….

- Page : 31/104 -

…………………………………………………. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

………………………………………………….. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Exercice 21

Écrivez un algorithme qui lit un entier et affiche les 5 entiers suivants.

Algorithme Aff_5suiv Variable ………………………………………. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Algorithme Aff_5suiv (* avec Pour *) Variable ………………………………………. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Exercice 22

Écrivez un algorithme qui lit un réel x et un entier positif p et affiche x puissance p.

Algorithme Aff_puiss Variable ………………………………………. ………………………………………………….. Début …………………………………………………..

…………………………………………………..

Algorithme Aff_puiss (* avec Tant que *) Variable ………………………………………. ………………………………………………….. Début …………………………………………………..

…………………………………………………..

- Page : 32/104 -

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Exercice 23

Écrivez un algorithme qui lit un entier n positif et affiche sa factorielle n!=n-1! * n et 0!=1. Algorithme Factoriel Variable ………………………………………. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Algorithme Factoriel (* avec Pour *) Variable ………………………………………. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Exercice 24

Écrivez l'algorithme qui permet de calculer le PGCD de deux nombres entiers x et y. Algorithme PGCDXY Variable ………………………………………. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Algorithme PGCDXY (* avec Tant que *) Variable ………………………………………. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

- Page : 33/104 -

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Exercice 25

Écrivez un algorithme qui détermine si un entier N est parfait ou non. Un entier est dit parfait s'il est égal à la somme de ses diviseurs stricts (Exemple: 6=3+2+1).

Algorithme Aff_puiss Variable ………………………………………. ………………………………………………….. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Algorithme Aff_puiss (* avec Tant que *) Variable ………………………………………. ………………………………………………….. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Exercice 26 Écrivez un algorithme Menu qui propose à l’utilisateur de saisir deux nombres et de choisir dans un menu parmi 4 opérations à réaliser dessus : 1. addition, 2. soustraction, 3. multiplication, 4. division. Attention à signaler une tentative de division par zéro !

Algorithme Menu Variable ………………………………………. ………………………………………………….. Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

- Page : 34/104 -

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Exercice 27 : Dans une entreprise, la convention collective applicable pour le personnel précise :

- Si les employés ont moins d’un an d’ancienneté, ils ont droit à deux jours et demi de congé par mois de présence même pour le premier mois quel que soit le jour de leur entrée dans l’entreprise.

- Si leur ancienneté est supérieure ou égale à un an, ils ont droit à 30 jours (soit cinq semaines) de congé.

- Une bonification de 2 jours est accordée aux cadres qui sont âgés de 35 ans et plus et qui ont plus de 3 ans d’ancienneté.

- Si les cadres ont 40 ans et plus et 5 ans et plus d’ancienneté, cette bonification est portée à 4 jours.

Écrivez un algorithme affichant pour un employé donné son droit au congé (Vous devez préalablement élaborer l’arbre de décision de ce problème). Exercice 28 : Vous vous rendez dans une agence de voyages dans le but de réserver une place d’avion pour vos prochaines vacances. Le principe de réservation est le suivant :

- Si le voyageur demande une place en première classe, « non fumeur », et qu’une place est disponible pour le vol qu’il désire, on lui délivre un billet ; sinon une place « fumeur » lui est proposée.

- Si le voyageur accepte, le billet est délivré ; sinon on lui propose une place en classe économique, d’abord en « non fumeur », puis en « fumeur ». S’il n’y a aucune place dans le vol, le voyageur est inscrit sur une liste d’attente.

- Si le voyageur demande une place en classe économique, avec priorité « non fumeur », et qu’une place est disponible, un billet lui est délivré, sinon on lui propose une place en première classe, toujours en respectant la priorité « non fumeur », et de même, en cas de non satisfaction de la demande, le voyageur est inscrit sur une liste d’attente.

28.1. Présentez le problème sous forme de table de décision. 28.2. Donnez l’algorithme de réservation de la place et de l’émission du billet. Exercice 29 : Le document ci-dessous, présente les résultats, par classe des étudiants de l’ISET de Radès.

ISET de Radès Année Univ. : _________ Département : Informatique Semestre N° : ____ Classe : _________

- Page : 35/104 -

Nom & Prénoms Notes Obtenues Moyenne

Moyenne/Matière

Écart type

Moyenne la plus forte : __________ Moyenne la plus faible : __________

Donnez l’algorithme détaillé permettant de réaliser ce document.

- Page : 36/104 -

LES ALGORITHMES A BASE DE TABLEAUX – L’Essentiel du Cours –

Les Types construits, Les Tableaux, Les Matrices, Les Chaînes de caractères, Les Algorithmes de base, Les Algorithmes de recherche, 1er Algorithme de Tri, Les Palindromes, Les fonctions prédéfinies sur les

chaînes de caractères.

Objectif Général 2 : Avoir des compétences théoriques et techniques pour pouvoir appliquer les concepts de la programmation structurée sur des problèmes nécessitant le recours à des structures de données avancées : Tableaux, Chaînes, etc. Objectifs Spécifiques : OS 1 : Comprendre les types construits : Ensembles, Intervalles et Types Enumérés. OS 2 : Comprendre le type Tableau. OS 3 : Appliquer le type tableau pour réaliser certains traitements. OS 4 : Comprendre le type Matrice OS 5 : Appliquer le type Matrice sur certains problèmes. OS 6 : Distinguer le type tableau de caractères du type chaîne de caractères. OS 7 : Appliquer le type Chaîne pour la résolution de certains problèmes. Rappel du Cours :

LES TYPES CONSTRUITS Dans certains problèmes, on est amené à utiliser des variables simples mais prenant des valeurs spécifiques qui doivent être prédéfinies dans le programme. On doit alors construire un type pouvant comporter ces différentes valeurs : Un tel type est dit Type Construit. Par exemple, si on veut manipuler des valeurs ne pouvant prendre que les couleurs rouge, vert, bleu et blanc, on doit déclarer un type qui contient ces quatre valeurs Couleur=(rouge, bleu, blanc, bleu). On distingue deux catégories de types construits : Le Type Enuméré et Le Type Intervalle. LE TYPE ENUMERE On définit en extension toutes les valeurs que peuvent prendre les variables de ce type. Les valeurs doivent être ordonnées. Elles sont en nombre fini. Représentation Algorithmique TYPE NomTypeEnuméré = (Val1, Val2, Val3, ….., ValN) VARIABLE NomVar : NomTypeEnuméré Exemple : Type Jour = (lundi, mardi, mercredi, jeudi, vendredi, samedi, dimanche) Variable j1, j2 : jour ;

- Page : 37/104 -

On peut écrire : j1 mardi j2 dimanche

Remarques :

(i) Les opérateurs relationnels (<, ≤ , >, ≥ , =, ≠ ) s’appliquent sur les différentes valeurs de ce type.

Exemple : lundi < mardi < mercredi < jeudi < vendredi < samedi < dimanche.

(ii) étant donné que les valeurs d’un type énuméré sont ordonnés, on peut appliquer les fonctions successeur et prédécesseur.

Exemple : successeur (lundi) donne mardi et prédécesseur (mardi) donne lundi. (iii) l’utilisation d’un tel type assure davantage de cohérence aux données

introduites. En effet, dans cette exemple on ne peut pas rencontrer une journée appelée « Pluie » : elle n’appartient pas au type Jour.

LE TYPE INTERVALLE Un type intervalle est un ensemble de valeurs ordonnés construits à partir des types simples et caractérisé par sa valeur minimale et sa valeur maximale. 3.2. Représentation Algorithmique TYPE NomTypeIntervalle = ValMin .. ValMax VARIABLE NomVar : NomTypeIntervalle Exemple : Type Chiffre = 0 .. 9 : intervalle d’entiers Lettre = ‘A’ .. ‘Z’ : intervalle de caractères Jour_ouvré = lundi .. samedi : intervalle de Jour Note = 0.0 .. 20.0 : intervalle de notes.

Remarque : Les valeurs appartenant à un intervalle sont nécessairement de type déjà défini. Bien que les types énumérés et intervalle soient peu utilisés, ils permettent néanmoins d’accroître la lisibilité des algorithmes et facilitent les contrôles (on ne peut pas donner une note > 20 si l’on dispose d’un type intervalle Note). LE TYPE TABLEAU : LES VECTEURS Un tableau est une structure de données permettant de regrouper sous un même nom un nombre fini d’éléments de même type. Remarques :

(i) Un tableau est constitué d’un nombre fini de cases contiguës situées en mémoire centrale.

(ii) Un tableau est caractérisé par : o son nom o sa taille (borne inférieure et borne supérieure connues à l’avance) o ses éléments : chaque élément est défini par son type et son contenu.

(iii) L’accès à un élément du tableau se fait à l’aide d’un indice. Représentation Algorithmique

- Page : 38/104 -

Type Nomtableau = Tableau[borne_inf .. borne_sup] de type_élément Variable Nomvar : Nomtableau Indice : entier Exemple : on veut déclarer un tableau de moyennes Type Tab_Moy = Tableau[1..20] de réel Variable T : Tab_Moy I : entier (* indice du tableau T *)

En mémoire, on va avoir une variable T comportant 30 cases et dans chacune on placera une moyenne qui est de type réel.

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20

T 10.5 08.2 09.7 11.0 10.5 13.6

Le premier élément de T contient la valeur 10.5 ; on note T(1) 10.5 Le deuxième élément de T contient la valeur 08.2 ; on note T(2) 08.2 D’une manière générale, le Ième élément de T est noté T(I) et contient une valeur de type réel. T(I) désigne également le contenu de la Ième case du tableau T. Remarques :

(i) L’indice du tableau doit être obligatoirement de type entier. (ii) Il serait préférable que cet indice soit initialisé à la valeur 1. (iii) Un tableau, s’il est rempli, ne doit pas faire l’objet d’une lecture

supplémentaire sauf s’il s’agit d’une opération de mise à jour où on doit modifier le contenu des éléments du tableau.

(iv) La taille du tableau doit être connu à l’avance. Opérations de bas Initialiser un Tableau Algorithme Ini_Tab Constante N = Val Type TabEnt = Tableau [1..N] de Entier Variable T : TabEnt I : entier Début

Pour I allant de 1 à N faire T(I) 0 Fin Pour

Fin Remplir un Tableau Algorithme Remp_Tab Constante N = Val Type TabEnt = Tableau [1..N] de Entier Variable T : TabEnt I : entier Début

Pour I allant de 1 à N faire Lire(T(I)) Fin Pour

Fin

- Page : 39/104 -

Remarque : Lire(T(I)) consiste à entrer une valeur à partir du clavier et la mémoriser dans la Ième case du tableau T. Affichage les éléments d’un tableau

On veut afficher les éléments strictement positifs du tableau T Algorithme Aff_Tab Constante N = Val Type TabEnt = Tableau [1..N] de Entier Variable T : TabEnt I : entier Début

Pour I allant de 1 à N faire Si T(I) > 0 Alors Ecrire(T(I)) Fin Si Fin Pour

Fin

Additionner les éléments de deux tableaux

On dispose de deux tableaux T1 et T2 et on veut réaliser la somme. Ça consiste à additionner les éléments de même indice et les mémoriser dans un tableau T3. Condition nécessaire : T1 et T2 de même taille et leurs éléments de même type. Algorithme Add_Tab Constante N = Val Type TabEnt = Tableau [1..N] de Entier Variable T1, T2, T3 : TabEnt I : entier Début

Pour I allant de 1 à N faire T3(I) T1(I) + T2(I) Fin Pour

Fin

Multiplier les éléments de deux tableaux Algorithme Mult_Tab Constante N = Val Type TabEnt = Tableau [1..N] de Entier Variable T1, T2, T3 : TabEnt I : entier Début

Pour I allant de 1 à N faire T3(I) T1(I) * T2(I) Fin Pour

Fin

Recherche d’un élément dans un tableau Il s’agit de rechercher un élément x saisi à partir du clavier, dans un tableau T. Dès qu’on le trouve ce n’est plus la peine de continuer le parcours du tableau ; on doit sortir et afficher un message d’existence. Deux façons de faire :

- Page : 40/104 -

- soit faire une recherche séquentielle, - soit faire une recherche plus optimisée dite recherche dichotomique et dans ce

cas, il y a des précautions et des actions préalables à faire. Recherche Séquentielle Algorithme Rech_Seq Constante N = 20 Type TabEnt = Tableau [1..N] de Entier Variable T : TabEnt I : entier X : entier (* X est l’élément à chercher dans le tableau *) Trouve : Booléen (* cette variable va nous permettre de sortir dès qu’on trouve X *) Début Lire(X) I1 Trouve Faux Tant que (I<=N) et (Trouve = Faux) Faire

Si (T(I) <> X) Alors I I + 1 Sinon Trouve Vrai Fin Si Fin Tant que Si (Trouve = Vrai) Alors Ecrire(X, ‘appartient à T’) Sinon Ecrire (X,’ne se trouve pas dans T’) Fin Si Fin

Recherche Dichotomique

Pour appliquer la recherche dichotomique, il faut que le tableau T soit Rempli et Trié. Il s’agit d’une recherche qui consiste à réduire le temps de recherche d’un élément X dans un tableau T qui doit être obligatoirement trié. On commence par comparer X avec le contenu de l’élément du milieu : si X est inférieur à cette valeur alors on va continuer la recherche dans la partie gauche du tableau T avec modification de la borne supérieure, sinon on continuera la recherche dans partie droite du tableau avec modification de la valeur de la borne inférieure. On s’arrêtera quand X serait égale à la valeur du milieu ou quand on dépasse les bornes du tableau. Algorithme Dichoto Constante N=Val1 M= Val2 Type TabEnt = Tableau [1..N] de Entier Variable T : TabEnt I,inf,sup,mil : entier X : entier (* X est l’élément à chercher dans le tableau *) Début Lire(X) infN supM

- Page : 41/104 -

Répéter mil (inf+sup) div 2 Si X < T(mil) Alors sup mil – 1

Sinon inf mil +1 Fin Si

Jusqu’à (X=T(mil)) ou (inf > sup) Fin

Comparaison de deux Tableaux

Pour écrire l’algorithme correspondant, on doit s’assurer que les deux tableaux soient de même type et de même taille. La comparaison va se faire sur les éléments des deux tableaux en les prenant deux à deux. Algorithme Compare Constante N=20 Type Tab_Ent = Tableau[1..N] d’Entier Variable T1,T2 : Tab_Ent I : entier Egal : Booléen Début (* on suppose que T1 et T2 déjà remplis *)

I1 Egal Vrai Tant que (I<=N) et (Egal=Vrai) Faire Si (T1(I) <> T2(I)) Alors Egal Faux

Sinon I I + 1 Fin Si Fin Tant que

Si (Egal=Vrai) Alors Ecrire (‘T1 et T2 sont égaux’) Sinon Ecrire (‘T1 et T2 sont différents’)

Fin Si Fin

Application : Palindrome

En utilisant l’algorithme de comparaison de deux tableaux, on vous demande d’écrire l’algorithme qui permet de tester si un mot est un palindrome ou non. Un mot est dit palindrome s’il se lit de la même façon de gauche à droite ou de droite à gauche (exemple : LAVAL, AZIZA, AFIFA). On suppose que le mot est un tableau de caractères complètement rempli. Algorithme Palindr Constante N=20 Type Mot = Tableau[1..N] de caractère Variable T1, T2 : Mot I : entier Egal : Booléen Début (* T1 étant déjà rempli complètement *) (* Remplir T2 avec les éléments de T1 mais dans le sens inverse *) Pour I allant de 1 à N Faire

- Page : 42/104 -

T2(I) T1(N-I+1) Fin Pour

I1 Egal Vrai Tant que (I<=N) et (Egal=Vrai) Faire Si (T1(I) <> T2(I)) Alors Egal Faux

Sinon I I + 1 Fin Si Fin Tant que

Si (Egal=Vrai) Alors Ecrire (‘Le Mot est un Palindrome’) Sinon Ecrire (‘Le Mot n’’est pas un Palindrome’)

Fin Si Fin

Algorithme Simple de Tri d’un Tableau

Il s’agit de représenter les éléments d’un tableau T dans un ordre bien déterminé : croissant ou décroissant. Algorithme Tri_1 Constante N=20 Type Tab_Ent = Tableau[1..N] d’Entier Variable T : Tab_Ent I,J,X : entier Début (* On suppose que le tableau en question est déjà rempli *)

Pour I allant de 1 à (N-1) Faire Pour J allant de I+1 à N Faire Si T(I) > T(J) Alors (* permuter T(I) et T(J) *) XT(I) T(I)T(J) T(J)X Fin Si Fin Pour Fin Pour

Fin

Table d’exécution de cet algorithme pour N=5

T 7 -1 2 -3 1

N I J T(I) T(J) T(1) T(2) T(3) T(4) T(5)

5 1 2 7 -1 -1 7 2 -3 1

1 3 -1 2 -1 7 2 -3 1

1 4 -1 -3 -3 7 2 -1 1

1 5 -3 1 -3 7 2 -1 1

2 3 7 2 -3 2 7 -1 1

2 4 2 -1 -3 -1 7 2 1

2 5 -1 1 -3 -1 7 2 1

3 4 7 2 -3 -1 2 7 1

3 5 2 1 -3 -1 1 7 2

- Page : 43/104 -

4 5 7 2 -3 -1 1 2 7

Les Tableaux à deux dimensions : Les Matrices Définition

Une matrice est une structure de données permettant d’organiser un nombre fini d’informations de même type en lignes et en colonnes. Représentation Algorithmique Constante Nbr_Lig = Val1 (* Nombre de Lignes *) Nbr_Col = Val2 (* Nombre de Colonnes *) Type Matrice = Tableau [1..Nbr_Lig, 1..Nbr_Col] de Type_Elément_Matrice Variable M : Matrice I, J : Entier (* I étant l’indice des lignes et J celui des colonnes *)

Remarques

(i) Le Type_Elément_Matrice peut être simple ou structuré. (ii) L’accès à un élément de la matrice ne peut se faire qu’avec deux indices :

un élément est identifié par son numéro de ligne et son numéro de colonne.

(iii) Si M est la matrice, M(I,J) désigne l’élément de M situé à la Ième Ligne et à la Jème Colonne.

Opérations de base sur une Matrice Initialiser une matrice Pour I allant de 1 à Nbr_Lig Faire

Pour J allant de 1 à Nbr_Col Faire M(I,J) 0 Fin Pour

Fin Pour

b-) Remplir une matrice Pour I allant de 1 à Nbr_Lig Faire

Pour J allant de 1 à Nbr_Col Faire Lire(M(I,J)) Fin Pour

Fin Pour

Remarque : La primitive Lire(M(I,J)) consiste à lire à partir du clavier un élément et le placer à la Ième Ligne et à la Jème Colonne.

T devient trié

- Page : 44/104 -

Parcourir une matrice Par exemple, on veut afficher tous les éléments de la matrice dont la valeur est > à 10. Pour I allant de 1 à Nbr_Lig Faire

Pour J allant de 1 à Nbr_Col Faire Si (M(I,J) >= 10) Alors Ecrire(M(I,J)) Fin Si Fin Pour

Fin Pour

Additionner deux matrices Condition nécessaire : les deux matrices doivent être de même type et de même taille. Pour I allant de 1 à Nbr_Lig Faire

Pour J allant de 1 à Nbr_Col Faire M(I,J) M1(I,J) + M2(I,J) Fin Pour

Fin Pour

Recherche d’un élément dans une matrice La recherche ne peut être que séquentielle. En pensant à la recherche dichotomique, elle ne sera pas possible étant donné qu’une matrice triée n’existe pas ! Algorithme Rech_Matrice Constante Nbr_Lig = Val1 (* Nombre de Lignes *) Nbr_Col = Val2 (* Nombre de Colonnes *) Type Matrice = Tableau [1..Nbr_Lig, 1..Nbr_Col] de Type_Elément_Matrice Variable M : Matrice I, J : Entier (* I étant l’indice des lignes et J celui des colonnes *) X : Entier Trouve : Booléen Début

Lire(X) I 1 Trouve Faux Tant que (I<=Nbr_Lig) et (Trouve =Faux) Faire J 1 Tant que (J<= Nbr_Col) et (Trouve=Faux) Faire Si (M(I,J) = X) Alors Trouve Vrai Sinon J J+1 Fin Si Fin Tant que I I+1 Fin Tant que Si (Trouve = Vrai) Alors Ecrire (X, ‘se trouve dans la matrice’) Sinon Ecrire (X,’est inexistant dans la matrice’) Fin Si

Fin

Remarque : Il ne faut pas confondre entre la boucle imbriquée utilisée dans un algorithme de tri et la boucle imbriquée utilisée pour manipuler les éléments d’une matrice. Ça n’a rien à voir.

- Page : 45/104 -

Les Chaînes de Caractères Il s’agit de trouver une structure de données permettant de représenter une suite de caractères. Deux structures peuvent être envisagées selon le mode de l’exploitation qu’on veut appliquer à cette suite :

- Si on veut la manipuler caractère par caractère, la solution est dans ce cas facile à deviner : il suffit d’utiliser un tableau de caractères.

- Si on veut exploiter cette suite dans sa totalité et en un seul coup, il conviendrait alors d’utiliser une structure de données capable de regrouper cette suite en une seule variable pour la manipuler dans sa totalité : Une telle structure s’appelle Chaîne de Caractères.

Définition

Une chaîne de caractères est une structure de données permettant de regrouper une suite finie de caractères dans une même variable pour pouvoir l’exploiter dans sa totalité.

Remarque

Une chaîne de caractères peut être exploitée en tant que variable chaîne, dans ce cas on manipule des variables chaînes : on peut lire un mot en un seul coup (Lire(nom)), ou bien en tant que tableau de caractères : parcourir la chaîne caractère par caractère (compter le nombre d’apparition de la lettre ‘A’ dans un nom). Représentation Algorithmique

Type Nom_Chaine = Chaine[Taille_Maxi] Variable Nom_Variable : Nom_Chaine Remarque Taille_Maxi désigne la taille maximale que peut avoir une chaîne de caractères ; il doit être strictement positif. Exemple Type Nom = Chaine[20] Variable Nom1, Nom2 : Nom On a déclaré une chaîne Nom qui est de taille maximale 20 et deux variables Nom1 et Nom2.

Remarque

Dans certains langages de programmation et lors de la déclaration d’une chaîne de caractères, on peut ne pas indiquer la taille maximale. En fait, c’est le langage qui s’en occupe et affectera automatiquement la taille maximale qu’il puisse supporter. En Pascal, cette taille est de 255. Les Opérations de base sur les Chaînes

- Page : 46/104 -

Lecture d’une chaîne

a-) en tant que Chaîne

Lire (Nom1,Nom2) b-) en tant que tableau de caractères

Pour I allant de 1 à Taille_Maxi Faire Lire(Nom1(I)) Fin Pour L’inconvénient dans cette lecture réside essentiellement dans la lecture

de cases parfois inutiles : imaginez que la taille maximale est de 50 et le nom qu’on va introduire est de 20 ; on est alors obligé de compléter la saisie par 30 espaces.

Affichage

a-) en tant que Chaîne Ecrire (Nom1, Nom2)

b-) en tant que tableau de caractères Pour I allant de 1 à Taille_Maxi Faire Écrire (Nom1(I)) Fin Pour

Initialisation

a-) en tant que Chaîne

Nom1 ‘’ (* chaîne vide *) Nom2 ‘’

b-) en tant que tableau de caractères Pour I allant de 1 à Taille_Maxi Faire Nom1(I) ‘ ‘ (* soit le caractère vide soit le caractère espace *) Fin Pour

Les Fonctions Prédéfinies sur les Chaînes

Les langages de programmation comportent un jeu de fonctions prédéfinies sur le type Chaîne de caractères. On cite principalement les fonctions suivantes :

- La fonction LONG qui retourne la longueur d’une chaîne. - La fonction CONCAT qui rassemble plusieurs chaînes en une seule. - La fonction POS qui retourne la position d’une sous chaîne dans une chaîne. - La fonction MAJ qui rend une chaîne en Majuscules - La fonction MIN qui rend une chaîne en minuscules - La fonction SUBSTR qui permet d’extraire une sous-chaîne à partir d’une

chaîne. La fonction LONG

- Page : 47/104 -

Cette fonction lorsqu’elle est appliquée à une chaîne de caractères, retourne sa taille réelle et non pas la taille maximale. Algorithmiquement, elle est notée LONG(nom_chaine).

Exemple

CH : chaine X : entier ------------------------------- CH ‘ISET de Radès’ X LONG(CH) Écrire (LONG(CH)) ------------------------------ Dans la variable X, on va trouver la valeur 13.

Remarque

La longueur d’une chaîne étant un entier, on ne peut pas le mettre isolé dans un algorithme ; on doit l’affecter à une variable de type entier ou on doit le mettre dans une primitive d’écriture. La fonction CONCAT Cette fonction permet de concaténer plusieurs chaînes non nécessairement de même taille, en une seule. Algorithmiquement, elle est notée CONCAT(CH1,CH2,…,CHN) où les CHI sont des chaînes.

Exemple

Nom : Chaîne Prenom : Chaîne Etudiant : Chaîne ----------------------------------------------------- Etudiant CONCAT(Nom, Prenom) Écrire (CONCAT(Nom, Prenom)) ------------------------------------------------------ Dans la variable Etudiant, on va trouver une chaîne contenant le nom et le prénom

ensemble.

Remarque

La concaténation de plusieurs chaîne est une chaîne, on ne peut pas la mettre isolée dans un algorithme ; on doit l’affecter à une variable de type Chaîne ou on doit la mettre dans une primitive d’écriture. La fonction POS La fonction POS retourne la position à partir de laquelle une sous-chaîne apparaisse dans une chaîne. Dans le cas où cette sous-chaîne n’existe pas, elle retourne la valeur zéro. Algorithmiquement, cette fonction est notée POS et le résultat est un entier.

X POS(nom_chaîne, nom_sous_chaîne)

- Page : 48/104 -

X prendre pour valeur, la position à partir de laquelle la sous_chaîne apparaîsse dans la chaîne.

Exemple

CH ‘ISET de Radès’ CH1 ‘Radès’ X POS(CH, CH1) on trouvera dans X la valeur 9 ; de même pour X POS(CH,’Radès’), on trouvera le même résultat.

Remarque

La position étant un entier, on ne peut pas la mettre isolée dans un algorithme ; on doit l’affecter à une variable de type entier ou on doit la mettre dans une primitive d’écriture. Les fonctions MAJ et MIN Ces fonctions permettent de transformer une chaîne en majuscules, respectivement en minuscules, en une chaîne en minuscules, respectivement en majuscules. Algorithmiquement, on les note par MAJ(CH) ou MIN(CH).

Exemple

CH ‘Iset’ CH MAJ(CH) dans ce cas CH prendra la valeur ‘ISET’ CH MIN(CH), on aura dans CH la valeur ‘iset’.

La fonction SUBSTR Il s’agit d’extraire une sous-chaîne de taille p à partir d’une position dans une chaîne. Algorithmiquement, elle est notée sous-chaîne. Pour faciliter son utilisation, on va utiliser la convention du langage Pascal qui est SUBSTR. Cette fonction retourne une chaîne de caractères.

CH1 SUBSTR(CH, pos, p) Où CH étant la chaîne principale à partir de laquelle on va faire l’extraction. pos est la position à partir de laquelle on va procéder l’extraction p est la taille de la sous-chaîne à extraire.

Exemple

CH ‘ISET de Radès’ CH1 SUBSTR(CH,7,4) dans CH1 on va trouver la sous-chaîne ‘e Ra’.

Application : Palindrome On va reprendre l’exercice du palindrome en utilisant les chaînes de caractères.

- Page : 49/104 -

Solution

Algorithme Palindr Type mot = chaine Variable CH1,CH2 : Chaine Début

Lire(CH1) (* lecture du mot en un seul coup *) Pour I allant de 1 à LONG(CH1) Faire CH2(I)CH1(LONG(CH)-I+1) Fin Pour (* exploitation du mot caractère par caractère *) Si (CH1=CH2) Alors Ecrire (CH1, ‘est un Palindrome’) Sinon Ecrire (CH1, ‘n’’est pas un palindrome’) Fin Si

Fin

- Page : 50/104 -

LES ALGORITHMES A BASE DE TABLEAUX – Exercices Proposés –

Les Types construits, Les Tableaux, Les Matrices, Les Chaînes de caractères, Les Algorithmes de base, Les Algorithmes de recherche, 1er Algorithme de Tri, Les Palindromes, Les fonctions prédéfinies sur les

chaînes de caractères.

Exercice 1 Écrivez un algorithme dans lequel vous déclarez une variable de type tableau d'entiers dans laquelle

vous mettez les diviseurs de 12 qui sont 12, 6, 4, 3, 2, 1.

Algorithme Div12

………………………………………………

…..

………………………………………………

…..

………………………………………………

…..

………………………………………………

…..

………………………………………………

…..

………………………………………………

…..

………………………………………………

…..

………………………………………………

…..

………………………………………………

…..

………………………………………………

…..

………………………………………………

…..

………………………………………………

…..

………………………………………………

…..

………………………………………………

…..

………………………………………………

…..

………………………………………………

…..

………………………………………………

…..

………………………………………………

…..

………………………………………………

…..

………………………………………………

…..

Exercice 2 Écrivez un algorithme qui met 10 notes dans un tableau, puis affiche leur somme, leur moyenne,

leur maximum et leur minimum.

- Page : 51/104 -

Algorithme Dix_Notes

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

Exercice 3 On dispose d’un tableau d’entiers T on veut afficher le nombre d’éléments positifs et le nombre

d’éléments négatifs contenus dans le tableau.

Algorithme Aff_Tab

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

- Page : 52/104 -

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

Exercice 4 Écrivez un algorithme qui affiche la première, la dernière et le nombre d’apparitions d’un entier

dans un tableau de 15 entiers.

Algorithme Apparit

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

Exercice 5 Écrivez un algorithme qui fait le tri dans l’ordre décroissant d’un tableau de 15 entiers.

Algorithme Tri_Decr

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

- Page : 53/104 -

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

Exercice 6 Écrivez un algorithme qui met dans une matrice la table d'addition de 1 à 9.

Algorithme Tab_Add

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

- Page : 54/104 -

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

Exercice 7 Écrivez un algorithme qui affiche le vecteur de la diagonale d’une matrice saisie à partir du clavier.

Par exemple :

Affichage :V(5,10,105)

Algorithme Diag_Mat

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

5 6 2

36 10 32

100 144 105

- Page : 55/104 -

Exercice 8 Écrivez un algorithme qui cherche le maximum, le minimum et un entier (lut à partir du clavier)

dans une matrice.

Algorithme Rech_Min_Max

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

Exercice 9 Écrivez un algorithme qui permet de lire pour 10 étudiants leur notes en programmation,

électronique et anglais et d'afficher pour chaque étudiant sa moyenne et la moyenne de la classe

pour chaque matière.

Algorithme Aff_Moy

………………………………………………….

- Page : 56/104 -

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

Exercice 10 Écrivez un algorithme dans lequel vous déclarez une variable Voyelle de type tableau de caractères

dans laquelle vous allez placer toutes les voyelles de l'alphabet: a, e, i, o, u, y.

Algorithme Plac_Voy

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

- Page : 57/104 -

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

Exercice 11 Écrivez un algorithme qui lit la classe d'un étudiant et affiche « vous êtes de ma classe » ou « vous

n'appartenez pas à ma classe »

Algorithme Ma_Class

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

- Page : 58/104 -

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

Exercice 12 Écrivez un algorithme qui lit un nom et affiche la 1

ère lettre seulement en majuscule et le reste en

minuscule.

Algorithme Aff_Nom

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

- Page : 59/104 -

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

Exercice 13 Écrivez un algorithme qui lit le nom et le prénom en même temps à partir du clavier et met le nom

dans une variable et le prénom dans une autre.

Algorithme Nom_Pren

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

- Page : 60/104 -

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

Exercice 14 Écrivez un algorithme qui lit une chaîne de caractères et affiche le pourcentage des lettres voyelles.

Algorithme Pourc_Voy

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

- Page : 61/104 -

. .

Exercice 15 Écrivez un algorithme qui permet de lire une chaîne de caractères et d'afficher si elle est palindrome

ou non. Une chaîne est dite palindrome, si elle se lit de gauche à droite de la même façon qu’elle se

lise de droite à gauche (exemples : AZIZA, LAVAL, etc.).

Algorithme Palindr

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

Exercice 16

- Page : 62/104 -

Écrivez un algorithme qui lit deux chaînes de caractères et qui affiche les caractères qui sont

communs.

Algorithme Car_Comm

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

Exercice 17 Écrivez un algorithme qui saisie une phrase et qui affiche le nombre de mots contenus dans cette

phrase.

Algorithme Mot_Phras

- Page : 63/104 -

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

Exercice 18 Écrivez un algorithme qui affiche l’occurrence de chaque caractère d’une chaîne saisie à partir du

clavier.

Par exemple : pour AZIZA, on doit avoir :

- L’occurrence de ’A’ est : 2

- L’occurrence de ’Z’ est : 2

- L’occurrence de ’I’ est :1

Algorithme Occ_Chain

- Page : 64/104 -

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

Exercice 19

Il s’agit de coder un message selon la codification suivante : - Si le caractère appartient à l’alphabet, on le remplacera par son suivant. - Pour les lettres ‘Z’ ou ‘z’, le suivant serait ‘$’. - Si le caractère est l’espace, on le remplacera par le caractère ‘*’. - Dans les autres cas, tout caractère sera remplacé par le caractère ‘-‘.

- Page : 65/104 -

On vous demande d’afficher le message initial et le message codé. En outre, on vous demande de compter le nombre de lettres dans le message codé et d’en extraire une sous-chaîne alphabétique.

Algorithme Mess_Code

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

………………………………………………….

.

- Page : 66/104 -

.

………………………………………………….

.

………………………………………………….

.

Exercice 20

À remettre dans le cadre du Devoir à la Maison N° 02. Cet exercice sera corrigé en classe lors des séances de révision.

- Page : 67/104 -

- Page : 68/104 -

LA PROGRAMMATION PROCEDURALE – L’Essentiel du Cours –

Fonctions, Procédures, Initiation à la Récursivité

Objectif Général 3 : Avoir des compétences théoriques et techniques pour pouvoir appliquer les concepts de la programmation procédurale sur des problèmes complexes. Objectifs Spécifiques :

OS 1 : Comprendre le concept de la programmation procédurale.

OS 2 : Savoir décomposer un problème complexe en des sous problèmes simples.

OS 3 : Maîtriser l’utilisation des fonctions pour un problème donné.

OS 4 : Maîtriser l’utilisation des procédures pour un problème donné.

OS 5 : Appliquer les concepts de la programmation procédurale sur un problème complexe.

OS 6 : S’initier au concept de la récursivité.

Rappel du Cours : AVANTAGES DE LA PROGRAMMATION PROCEDURALE

La décomposition d’un problème en sous-problèmes faciles à résoudre, permet d’obtenir des algorithmes qui sont :

- Lisibles et faciles à comprendre. - Facile à maintenir : détection rapide de l’erreur et correction sans difficultés. - Facile à faire évoluer : ajout facile d’autres fonctionnalités. - Réutilisable : dans la résolution d’un problème, on peut constater qu'une suite

d'actions revient plusieurs fois. Dans ce cas, il serait judicieux de l'écrire une seule fois, et de l'utiliser autant de fois que c'est nécessaire.

En définitif, on serait en présence d’un algorithme qui respecte les buts et principes du génie logiciel1 et par conséquent, on aurait un algorithme de qualité.

LES FONCTIONS Définition :

Une fonction est sous-programme contenant un certain nombre d’instructions, qui retourne un résultat unique affecté à son nom. On peut dire autrement :

Une fonction est un sous programme qui retourne obligatoirement une valeur. Cette dernière sera stockée dans une variable qui porte le même nom que la fonction.

Remarques

(i) une fonction retourne un résultat unique implique qu’une fonction possède obligatoirement un type.

(ii) dans une fonction, on trouve des instructions qui produisent le résultat ; ce dernier doit être affecté en fin de traitement au nom de la fonction.

1 Ensemble d’outils, de méthodes, de procédures, permettant la production de logiciels de qualité.

- Page : 69/104 -

Représentation algorithmique Algorithme nomalgo Constante ……….. Type ………………

Fonction nomfonct(param1:type1,param2:type2,…,paramN :TypeN) : typefonction

<partie déclarative>

Début (*fonction*) <partie instructions> nomfonct Résultat (* le résultat généré par les instructions doit être affecté au nom de la fonction *)

Fin (*fin fonction*) Début (* nomalgo *) <instructions et appel de la fonction> Fin (* nomalgo *)

Remarques :

(i) param1, param2, …, paramN sont appelés paramètres : ce sont des variables qui permettent à la fonction de communiquer avec l’extérieur.

(ii) Ces paramètres déclarés lors de la définition de la fonction sont appelés paramètres formels.

(iii) On peut trouver certaines fonctions sans paramètres ; on déclarera alors la fonction de la manière suivante : Fonction nomfonct() : typefonction.

(iv) Les paramètres de la fonction ne doivent jamais être lus à l’intérieur de la fonction sans que l’énoncé le précise.

Exemple 1

Écrire une fonction qui retourne la valeur absolue d’un entier N. Solution Fonction Val_abs(N : entier) : entier Variable a : entier Début Si (N > 0) Alors a N Sinon a -N FinSi Val_abs a (* affecter le résultat a au nom de la fonction : Val_abs *) Fin

Exemple 2

Écrire une fonction qui retourne la moyenne de deux réels x et y.

- Page : 70/104 -

Solution Fonction Moyenne(x : réel, y : réel) : réel Début Moyenne (x+y)/2 Fin Appel de la fonction L’appel de la fonction ne peut pas apparaître tout seul dans le programme appelant. En effet, si dans un programme on appelle la fonction moyenne pour les réels a et b uniquement par son nom, on obtient Début (* programme appelant *) Lire(a) Lire(b) Moyenne(a,b) ??????????? Fin Or, Moyenne(a,b) est un réel et on n’a jamais vu dans un programme un réel qui se promène tout seul !!. Il faut donc soit mettre ce réel dans une variable de même type en faisant une affectation, soit afficher ce réel à l’aide de la primitive d’écriture. En fait, l’appel d’une fonction est une expression, dont la valeur est le résultat retourné par cette fonction ; son appel doit alors se faire soit dans une affectation soit dans une écriture.

Nomvar nomfonct(var1, var2,…, varN) ou bien Écrire (nomfonct(var1,var2,…..,varN)

Remarques

(i) Nomvar et nomfonct doivent avoir le même type. (ii) On doit avoir autant de paramètres formels (param1, param2, …, paramN)

que de paramètres utilisés par le programme appelant (var1, var2,…., varN).

(iii) Les paramètres utilisés dans le programme appelant sont appelés paramètres effectifs.

(iv) L’ordre des paramètres formels doit être respecté lors de l’appel : les varI

doivent correspondre aux paramI. Si on revient à l’exemple moyenne, on doit le corriger comme suit : Algorithme Calcul (* programme appelant *) Variable a,b : réel Fonction Moyenne(x : réel, y : réel) : réel

- Page : 71/104 -

Début Moyenne (x+y)/2 Fin Début (* programme appelant *) Lire (a) Lire (b) Écrire (Moyenne(a,b)) Fin Remarques :

(i) Le programme qui appelle une fonction ou une procédure s’appelle programme appelant.

(ii) Le programme (fonction ou procédure) qui est appelé par un programme appelant est dit programme appelé.

Exemple : fonction sans paramètres

Écrire une fonction qui retourne le message ‘Bonjour’ Solution Fonction message() : chaine Début Message ‘Bonjour’ Fin

LES PROCEDURES

Définition

Une procédure est un sous-programme qui peut produire zéro ou plusieurs résultats. Représentation algorithmique Algorithme nomalgo Constante ……….. Type ………………

Procédure nomproc(param1:type1,param2:type2,…,paramN :TypeN) <Partie déclarative>

Début (*procédure*) <Partie instructions> Fin (*fin procédure*)

Début (* nomalgo *) <Instructions et appel de la procédure> Fin (* nomalgo *)

- Page : 72/104 -

Remarques :

(i) param1, param2, …, paramN sont appelés paramètres : ce sont des variables qui permettent à la procédure de communiquer avec l’extérieur.

(ii) Ces paramètres déclarés lors de la définition de la procédure sont appelés paramètres formels.

(iii) On peut trouver certaines procédures sans paramètres ; on déclarera alors la fonction de la manière suivante : Procédure nomproc().

(v) Les paramètres de la procédure ne doivent jamais être lus à l’intérieur de la procédure sans que l’énoncé ne l’indique.

Exemple

Écrire une procédure permettant d’afficher la somme de deux entiers. Solution Procédure aff_somme(a :entier, b :entier) Variable S : entier Début S a + b Écrire (S) Fin Appel de la procédure

A la différence d’une fonction, une procédure est appelée par son nom et ses

paramètres effectifs, dans le programme appelant. Nomproc(var1, var2, …., varN)

Exemple

Algorithme affiche Variable x,y : entier Procédure aff_somme(a :entier, b :entier) Variable S : entier Début (*proc*) S a + b Écrire(S) Fin (*proc*) Début (*algo*) Écrire(‘donnez un entier x : ‘) Lire(x) Écrire(‘donnez un entier y : ‘) Lire(y) (* appel de la procédure aff_somme *)

- Page : 73/104 -

aff_somme(x,y) Finalgo

Remarques

(i) On doit avoir autant de paramètres formels (param1, param2, …, paramN) que de paramètres utilisés par le programme appelant (var1, var2,…., varN).

(ii) Les paramètres utilisés dans le programme appelant sont appelés paramètres effectifs.

(iii) L’ordre des paramètres formels doit être respecté lors de l’appel : les varI

doivent correspondre aux paramI.

Exemple : Procédure sans paramètres

Procédure message() Variable mess : chaine Début Lire(mess) Écrire(mess) Fin Le Passage des Paramètres

Problématique On considère l’algorithme suivant :

Algorithme afficher Variable x, y : entier Procédure affich_ab (a :entier, b :entier) Variable c : entier Début a a – 1 b b – 1 c a + b Écrire(c) Début (*afficher*) Lire(x) Lire(y) affich_ab(x,y) Écrire(x) Écrire(y) Fin

Fin En appelant la procédure affich_ab(x,y), on va se poser automatiquement la question suivante : les valeurs de x et de y vont elles changer après l’exécution de cette procédure ?

- Page : 74/104 -

La réponse est oui et non, selon le comportement des paramètres lors de l’appel. Ce comportement doit être indiqué préalablement lors de la définition de la procédure et plus exactement lors de la déclaration des paramètres. Dans ce cas, un paramètre n’est plus caractérisé par son nom et son type mais en plus son comportement. Ce comportement est dit en terme de sous-programmes, le mode de passage du paramètre. On distingue trois modes de passage :

- Un mode de passage de type donnée ou par valeur qu’on note DON. - Un mode de passage de type résultat ou par référence qu’on note RES. - Un mode de passage de type donné et résultat qu’on note DONRES.

Le mode de passage de type DON

On dit qu’un paramètre est fourni en donnée s’il est fourni par le programme

appelant, sa valeur reste inchangée après l’exécution du sous-programme appelé.

Un paramètre de type donné est noté DON et déclaré de la manière suivante :

Procédure nomprocéd(DON param1 : typeparam1, DON param2 : typeparam2,….)

Exemple: Procédure Test1(DON p1 : réel) Remarque : dans une procédure, si un paramètre n’est précédé d’aucun mode de passage, il est par défaut de type DON.

Le mode de passage de type RES

On dit qu’un paramètre est fourni en résultat, s’il est retourné par la procédure appelée ; l’exécution de la procédure appelée calcule une valeur qui sera affectée à ce paramètre, en fin du traitement.

Un paramètre de type résultat est noté RES et déclaré de la manière suivante :

Procédure nomprocéd(RES param1 : typeparam1, RES param2 : typeparam2,….)

Exemple: Procédure Test2(RES p2 : réel)

- Page : 75/104 -

Le mode de passage de type DONRES

On dit qu’un paramètre est fourni en donnée et résultat, s’il est fourni par le

programme appelant et modifié par la procédure appelée.

Un paramètre de type résultat est noté RES et déclaré de la manière suivante : Procédure nomprocéd(DONRES param1 : typeparam1, DONRES param2 : typeparam2,….)

Exemple: Procédure Test3(DONRES p3 : réel)

Application Il s’agit de lire l’algorithme suivant et de dire à chaque appel de procédure, s’il est possible ou non ; dans les deux cas de réponse justifier. Algorithme appelant Variable a, b, c : réel Procédure Test1 (DON p1 :réel) Procédure Test2 (RES p2 :réel) Procédure Test3 (DONRES p3 :réel) Début (* algorithme appelant *) a45.0 Test1(33.0) Test1(a) Test1(35.0*a-2.0) Test1(b) Test2(a) Test2(b) Test2(a*4.0) Test2(35.0) Test3(a) Test3( c ) Test3(45.0) Test3(a*2.0) Fin (* Algorithme *) Solution

Contenu de la procédure Test1 supposé connu

Contenu de la procédure Test2 supposé connu

Contenu de la procédure Test3 supposé connu

- Page : 76/104 -

Appel Justification

Test1(33.0) 33 étant une constante donc fourni par le programme appelant cet appel est donc Correct.

Test1(a) a étant fourni par le programme appelant (a=45); cet appel est donc Correct.

Test1(35.0*a-2.0) L’expression (35*a-2) est fourni par le programme appelant; cet appel est donc Correct.

Test1(b) b n’étant pas fourni par le programme appelant; cet appel est donc Incorrect.

Test2(a) a peut être modifié par le programme appelé; cet appel est donc Correct.

Test2(b) b peut être modifié par le programme appelé; cet appel est donc Correct.

Test2(a*4.0) (a*4.0) ne peut pas être modifié par le programme appelé : ce n’est pas un nom de variable ; cet appel est donc Incorrect.

Test2(35.0) 35 étant une constante, elle ne peut pas être modifiée ; cet appel est donc Incorrect.

Test3(a) a est fourni par le programme appelant et peut être modifié par le programme appelé; cet appel est donc Correct.

Test3( c ) C n’est pas fourni par le programme appelant et peut être modifié par le programme appelé; cet appel est donc Incorrect.

Test3(45.0) 45 est fourni par le programme appelant et ne peut pas être modifié par le programme appelé (c’est une constante); cet appel est donc Incorrect.

Test3(a*2.0) (a*2) est fourni par le programme appelant et ne peut pas être modifié par le programme appelé(c’est une expression); cet appel est donc Incorrect.

INITIATION A LA RECURSIVITE Définition

Un programme est dit récursif si lors de son exécution, il fait appel à lui même. Autrement dit, un objet est dit récursif s’il fait référence à lui même dans sa propre définition. Exemples Factoriel (n) = [ Si n=0 Alors 1 Sinon n*Factoriel (n-1) ] Explication : Le factoriel d’un entier n est égal à zéro , s’il est nul, [n*Factoriel(n-1)] sinon. Comme on le constate, Factoriel(n) fait appel à Factoriel(n-1). PGCD(x,y) = [ Si x=y Alors x

- Page : 77/104 -

Sinon Si (x > y) Alors PGCD(x-y,y) Sinon PGCD(x,y-x) ] Remarque : Un schéma récursif est toujours caractérisé par une condition d’arrêt. Transformation en algorithme récursif

Le Factoriel Fonction Factoriel (n : entier) : entier Début Si (n=0) Alors Factoriel 1 Sinon Factoriel n * Factoriel (n-1) FinSi Table d’exécution pour déterminer le factoriel de n=5

Empilement Dépilement

Factoriel(5) 5*Factoriel(4) 120

Factoriel(4) 4*Factoriel(3) 24

Factoriel(3) 3*Factoriel(2) 6

Factoriel(2) 2*Factoriel(1) 2

Factoriel(1) 1*Factoriel(0) 1

Factoriel(0) 1 Remarques :

(i) Comme on le constate, le résultat n’est pas séquentiel : pour y arriver on était obligé d’empiler jusqu’à atteindre la condition d’arrêt (n=0 alors le factoriel est égal à 1). C’est à ce moment qu’on a commencé à remonter et constituer des résultats intermédiaires jusqu’à trouver le résultat final (n !=120).

(ii) On parle d’une exécution en Forward pour arriver à la condition d’arrêt puis en Backward pour trouver le résultat final.

Le PGCD Fonction PGCD(x : entier, y : entier) : entier Début Si (x=y) Alors PGCD x Sinon Si (x > y) Alors PGCD PGCD(x-y,y) Sinon PGCD PGCD(x,y-x) FinSi FinSi Fin

- Page : 78/104 -

LA PROGRAMMATION PROCEDURALE – Exercices Proposés –

Fonctions, Procédures, Initiation à la Récursivité

Exercice 1

Écrivez une procédure som_prod qui calcule la somme et le produit de deux réels.

Procédure som_prod(…………………………………...) (* en utilisant deux paramètres *) Variable …………………………………….. ……………………………………………….. Début ………………………………………………..

………………………………………………..

………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Procédure som_prod(…………………………………... ……………………………………………….) (* en utilisant quatre paramètres *) Variable …………………………………….. ……………………………………………….. Début ………………………………………………..

………………………………………………..

………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Exercice 2

2.1. En utilisant som_prod de l’exercice 1, Exécutez l’algorithme suivant en remplissant le tableau proposé ? Algorithme p_essai Variable z, u, x, p : réel Début

z 0.

u 5.2

x -3. som_prod(u,x,z,p) écrire (u,x,z,p) som_prod(p,z,u,x) écrire (u,x,z,p) Fin

2.2. Que se passe-t-il si on exécute som_prod(p,z,u,x) avant som_prod(u,x,z,p) ? ………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………

z n x p

z0

u5.2

x-3

som_prod(u,x,z,p)

écrire (u,x,z,p)

som_prod(p,z,u,x)

écrire (u,x,z,p)

- Page : 79/104 -

Exercice 3

3.1. Écrivez une procédure permut2, qui permute le contenu de deux variables réelles.

Procédure Permut2 (……………………………………...) (* en utilisant deux paramètres *) Variable …………………………………….. ……………………………………………….. Début ………………………………………………..

………………………………………………..

………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Procédure Permut2(…………………………………... ……………………………………………….) (* en utilisant trois paramètres *) Variable …………………………………….. ……………………………………………….. Début ………………………………………………..

………………………………………………..

………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

3.2. Quelle conclusion pouvez-vous tirer ? …………………………………………………………………………………………………

…………………………………………………………………………………………………

…………………………………………………………………………………………………

3.3. Écrivez un algorithme qui lit deux valeurs réelles au clavier et les affiche puis permute ces deux réels et réaffiche les deux valeurs.

Algorithme Affiche Variable …………………………………….. ……………………………………………….. Procédure Permut2 (………………………. ………………………………………………..) Début ………………………………………………..

………………………………………………..

………………………………………………..

…………………………………………………..

………………………………………………….. Fin (*fin de la procédure*)

Début (* algorithme Affiche*)

………………………………………………..

………………………………………………..

………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

- Page : 80/104 -

Exercice 4

On suppose donnée une procédure Son qui génère un son de fréquence f ; elle se présente comme suit : Procédure son (DON f: entier)

Écrivez un algorithme qui permet de simuler le fonctionnement d'un instrument de musique : l'appui sur les touches A, Z, E, R, T, Y, U, I devant produire un son correspondant à l'une des notes musicales Do, Ré, Mi, Fa, Sol, La, Si, Do les fréquences correspondants aux notes sont: 500, 561, 630, 667, 749, 841, 944 et 1000. L'algorithme s'arrête si l'utilisateur appui sur une autre touche.

Algorithme Musique Variable …………………………………….. ……………………………………………….. Procédure Son (…………………………….) Début

Supposée donnée Fin (*fin de la procédure*)

Début (* algorithme Musique *)

…………………………………………………..

…………………………………………………..

…………………………………………………..

………………………………………………..

………………………………………………..

………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Exercice 5

Écrivez une procédure décomposer, qui à partir d’une somme d’argent donnée, donne le nombre minimal de pièces de 20 DT, 10 DT, 5 DT, 1 DT et 0.5 DT qui la compose.

Procédure décomposer (…………………………………………….….) Variable ………………………………………………..

………………………………………………..

Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

………………………………………………..

………………………………………………..

………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

- Page : 81/104 -

Exercice 6

Écrivez une procédure Tri_Trois, qui prend en entrée trois entiers et qui les retourne triés par ordre croissant. Procédure Tri_Trois

(…………………………………………….….) Variable ………………………………………………..

………………………………………………..

Début …………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

………………………………………………..

………………………………………………..

………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

…………………………………………………..

Fin

Exercice 7

Créez une fonction qui calcule le carré d'un nombre réel.

Exercice 8

Créez une fonction min2 qui donne le minimum de deux réels en utilisant la formule suivante : Min(x,y)=(x+y-|x-y|)/2. Utilisez la fonction valeur_absolue déjà définie en cours.

Exercice 9

Écrivez une fonction min3 qui retourne le minimum de 3 réels en utilisant la formule suivante: Min(x,y,z)=Min(Min(x,y),z). Utilisez la fonction min2.

Exercice 10

Écrivez un algorithme qui lit 3 réels au clavier et qui affiche le minimum, utiliser la fonction min3.

Exercice 11

Créez la fonction factorielle : 0!=1, n!=nx(n-1)x….x1

Exercice 12

Créez une fonction qui calcule le cardinal (n, p). Utilisez la fonction factorielle.

Exercice 13

Écrivez une fonction qui retourne le PGCD de 3 entiers strictement positifs, en utilisant la formule suivante: PGCD(a,b,c)=PGCD(PGCD(a,b),c).

- Page : 82/104 -

1

1

1

n

nnU

UU

11

1

n

p

n

p

n

p CCC

Exercice 14

Écrivez une fonction récursive qui permet de calculer xn avec x>0. et n un entier positif.

Exercice 15

Soit la suite Un définie comme suit : U0=1 et Écrivez une fonction récursive qui permet de calculer Un.

Exercice 16

Soit la suite Fibonacci définie comme suit : Un=Un-1 + Un-2, U0=0 et U1=1 Écrivez une fonction récursive qui calcule les termes de la suite de Fibonacci.

Exercice 17

Écrivez une fonction récursive qui calcule la somme des éléments d'un tableau de réels de borne inf et de borne sup.

Exercice 18

Écrivez une fonction récursive qui calcule la factorielle d'un nombre n : n! = n (n-1)! 0! = 1

Exercice 19

Écrivez une fonction récursive qui calcule le cardinal de (n, p).

Exercice 20

Écrivez une fonction récursive qui cherche un élément x dans un tableau trié de réels de borne inf et de borne sup. Utilisez la recherche dichotomique.

- Page : 83/104 -

LES TRAITEMENTS SUR LES FICHIERS – L’Essentiel du Cours –

Enregistrement Fixe, Enregistrement Variable, Générateur, Fichier, Organisation Séquentielle, Organisation Indexée, Primitives, etc.

Objectif Général 4 : Acquérir les compétences nécessaires pour présenter des solutions algorithmiques basées sur les structures enregistrement et fichier. Objectifs Spécifiques :

OS 1 : Comprendre le type Enregistrement.

OS 2 : Comprendre le type Fichier.

OS 3 : Appliquer les types enregistrement et fichier pour réaliser des traitements sur des données stockées.

Rappel du Cours : DEFINITION Le type Enregistrement est une structure de données permettant de regrouper un ensemble de données de types différents sous une même variable. Remarques

(i) Un enregistrement est composé d’une ou plusieurs variables non nécessairement de même type, appelées Champs ou Rubriques.

(ii) Le type Enregistrement est dit également le type Structure. REPRESENTATION ALGORITHMIQUE Un type enregistrement doit être déclaré dans la partie réservée aux types, selon la syntaxe suivante : TYPE Nom_type = ENREGISTREMENT Nom_rubrique1 : type_rubrique1 Nom_rubrique2 : type_rubrique2 Nom_rubrique3 : type_rubrique3 …………. …………. Nom_rubriqueN : type_rubriqueN FinEnregistrement VARIABLE Nom_variable : Nom_type Remarque : Si certaines rubriques ont le même type, on peut les déclarer ensemble en les séparant par des virgules et en mentionnant une seule fois le type.

- Page : 84/104 -

Exemple 1 : déclaration de l’enregistrement étudiant. TYPE Étudiant = ENREGISTREMENT Nom : Chaîne (20) Prénom (30) CIN : entier Age : entier FinEnregistrement VARIABLE E : Étudiant En mémoire, en déclarant une variable E, l’espace réservé aura l’allure suivante : Nom Prénom CIN Age

E Exemple 2 : déclaration d’un nombre complexe TYPE Complexe = ENREGISTREMEN Préel : réel Pimaginaire : réel FinEnregistrement VARIABLE C : Complexe En mémoire, on va réserver un espace ayant la forme suivante : Préel Pimaginaire

C

ACCES AUX RUBRIQUES

Pour accéder aux rubriques d’un enregistrement, on doit effectuer tout d’abord une opération lecture, écriture, affectation, etc. en outre, cet accès peut être total ou partiel :

- Dans le cas où l’accès est total, on utilise Nom_variable. - Dans le cas où l’accès se fait à une rubrique, on utilise

Nom_variable.Nom_rubrique Lecture

a-) Totale : Lire(E) cette primitive va lire en un seul coup et à partir du clavier les différentes rubriques de l’enregistrement Etudiant.

La saisie s’effectuera comme suit : Ben Mohamed Mohamed 123456 35. On remarque qu’une telle saisie n’est pas très appréciée ; par contre pour certains problèmes on peut l’utiliser : lire un enregistrement et le stocker dans une autre variable.

- Page : 85/104 -

b-) Partielle : la lecture se fait rubrique par rubrique. On l’utilise généralement pour une saisie conviviale à l’écran. Dans notre exemple, la saisie de l’enregistrement Etudiant se fera alors :

Nom_variable = E Nom_rubrique = Nom ou Prénom ou CIN ou Age

Lire(E.Nom) (* on lira alors le nom Ben Mohamed *) Lire(E.Prénom) (* on lira alors le prénom Mohamed *) Lire(E.CIN) (* on lira alors le numéro CIN 123456 *) Lire(E.Age) (* on lira alors l’age 35 *)

Ecriture a-) Totale : Ecrire(E) est une primitive qui affiche les valeurs des différentes rubriques d’une manière assemblée ; elle peut être utilisée si jamais on veut écrire dans un fichier (voir chapitre suivant). b-) Partielle : l’écriture se fait rubrique par rubrique ; elle est conseillée s’il s’agit d’un dialogue entre l’utilisateur et le programme. Dans notre exemple, on peut afficher l’enregistrement étudiant après l’avoir saisi, rubrique par rubrique selon la syntaxe suivante :

Ecrire (Nom_variable.Nom_rubrique)

Nom_variable = E Nom_rubrique = Nom ou Prénom ou CIN ou Age

Ecrire (E.Nom) (* on affichera alors le nom Ben Mohamed *) Ecrire (E.Prénom) (* on affichera alors le prénom Mohamed *) Ecrire (E.CIN) (* on affichera alors le numéro CIN 123456 *) Ecrire (E.Age) (* on affichera alors l’age 35 *)

Affectation a-) Totale : il s’agit dans ce cas d’affecter les valeurs prises par les rubriques dans une autre variable qui doit avoir obligatoirement le même type que Nom_variable. Dans notre exemple, on suppose que E et E1 sont de variables de type Étudiant, et dans ce cas on peut effectuer une affectation totale, bien sûr si le contexte de l’exercice le demande : E1 E ; on aura alors,

E1= Ben Mohamed Mohamed 123456 35 b-) Partielle : selon le contexte de l’exercice, l’affectation peut se faire partiellement c’est à dire rubrique par rubrique, selon la syntaxe suivante :

Nom_variable.Nom_rubrique = Nom_variable1.Nom_rubrique Dans notre exemple, supposons que l’on souhaite copier un enregistrement dans une autre variable ; on aura alors : Sachant que E et E1 sont de variables de type Étudiant ; on peut écrire :

- Page : 86/104 -

E1.Nom E.Nom E1.Prénom E.Prénom E1.CIN E.CIN E1.Age E.Age Ce qui donne E1.Nom ‘Ben Mohamed’ E1.Prénom ‘Mohamed’ E1.CIN 123456 E1.Age 35 NOTION DE GENERATEUR Quand on affecte des valeurs aux rubriques d’un enregistrement, on dit qu’on a obtenu un Générateur. Un générateur est mathématiquement une classe de la relation enregistrement : c’est l’ensemble de valeurs que peuvent avoir à un instant donné, les différentes rubriques d’un enregistrement. Si on revient à l’exemple de l’enregistrement Etudiant, les informations suivantes : Ben Mohamed,Mohamed,123456,35 constituent un générateur de l’enregistrement Etudiant. Les valeurs d’un générateur sont délimitées par deux parenthèses :

G1 = (‘Ben Mohamed’,’Mohamed’,123456,35) Dans un enregistrement, on peut représenter plusieurs générateurs; mais à un instant donné, il ne peut contenir qu’un seul générateur. ENREGISTREMENT DE TAILLE VARIABLE

Problématique : On souhaite gérer les informations concernant les salariés d’une entreprise qui

diffèrent d’une catégorie à une autre. En voici les informations à implémenter : Matricule du salarié, Nom du salarié, Prénom du salarié, Date de naissance du salarié, Etat civil du salarié. Si le salarié est permanent, on indique le salaire de base et le montant des indemnités. Si le salarié est occasionnel, on indique le coût horaire, le nombre d’heures travaillées. Si le salarié est marié, on indique le nom et le prénom du conjoint ainsi que le nombre d’enfants. Si le salarié est célibataire, on indique s’il est en règle avec le service militaire. Question : Proposer une structure de données ? Solution : on va déclarer un type enregistrement appelé Salarié qui comportera les rubriques suivantes :

- Page : 87/104 -

CONSTANTE N = 200 TYPE Tab_Salarié = Tableau[1..N] de Salarié Salarié = ENREGISTREMENT Matricule : entier Nom, Prénom : chaine Date_naissane : chaine État_civil : (marié, célibataire) Catégorie : (permanent, occasionnel) Salaire_base : réel Indemnités : réel Nom_conjoint, Prénom_conjoint : chaine Nombre_enfant : entier Coût_horaire : réel Nombre_heures : réel Service_militaire : Booléen FinEnregistrement

On vient de déclarer un tableau de 200 salariés et chaque élément du tableau est censé comporter les informations relatives à un salarié. Matric Nom Préno Datn Eciv. Cat. SBas Indem NomC PrénC Nenf Chor Nbh SM

1 123 Ali Med 1164 M P 500 250 Med Alia 1 -- -- --

2 456 Med Sobhi 1155 C O -- -- -- -- -- 3.200 70 Oui

3

200

On vient de représenter deux générateurs de l’enregistrement Salarié. On remarque à première vue, que les rubriques de part et d’autre ne sont pas totalement remplies : cela s’explique par le fait, qu’en fonction des spécificités de chaque salarié on ne remplit que les cases permises. On est alors en présence de cases mémoires vides et ne pouvant plus être exploitées !!. on parle alors de ‘trous’ en mémoire. Comme la mémoire est une ressource à ne pas gaspiller, une telle situation n’est pas appréciable. L’idéal est que chaque générateur occupe uniquement les cases qui lui sont allouées. Pour ce faire, il faut alors utiliser une structure qui peut varier en fonction des spécificités de chaque générateur. Une telle structure existe et elle est appelée : Enregistrement Variable.

- Page : 88/104 -

DEFINITION

Un type enregistrement est dit variable si lors de sa définition certaines

rubriques ne peuvent apparaître que sous condition(s).

REPRESENTATION ALGORITHMIQUE TYPE Nom_type = ENREGISTREMENT

Nom_rubrique1 : type_rubrique1 Nom_rubrique2 : type_rubrique2 Nom_rubrique3 : type_rubrique3 …………….. …………….. Nom_rubrique_variable : type_rubrique_variable SELON (type_rubrique_variable) FAIRE Val1_type_rubrique_variable : Nom_rubrique_v1 : type_rubrique_v1

Nom_rubrique_v2 : type_rubrique_v2 Nom_rubrique_v3 : type_rubrique_v3 Val2_type_rubrique_variable : Nom_rubrique_v1 : type_rubrique_v1

Nom_rubrique_v2 : type_rubrique_v2 Nom_rubrique_v3 : type_rubrique_v3 ……… ……… FINSELON FINENREGISTREMENT Exemple de l’enregistrement Salarié CONSTANTE N = 200 TYPE Tab_Salarié = Tableau[1..N] de Salarié Situation = (marié, célibataire) Cat = (permanent, occasionnel) Salarié = ENREGISTREMENT

Matricule : entier Nom, Prénom : chaine Date_naissane : chaine Catégorie : Cat État_civil : Situation SELON (Situation) FAIRE Marié : Nom_conjoint, Prénom_conjoint : chaine Nombre_enfant : entier Célibataire : Service_militaire : Booléen FINSELON

- Page : 89/104 -

SELON (Cat) FAIRE Permanent : Salaire_base : réel Indemnités : réel Occasionnel : Coût_horaire : réel Nombre_heures : réel FINSELON FINENREGISTREMENT

Représentation des deux générateurs Avant : G1(123,’Ali’,’Med’,’1164’,Marié,Permanent,’Med’,’Alia’,1, ,500 ,250) G2(456,’Med’,’Sobhi’,’1155’,Célibataire,Occasionnel, , , , , ,3.200,70,Oui) En utilisant, l’enregistrement variable, on aura : G1(123,’Ali’,’Med’,’1164’,Marié,Permanent,’Med’,’Alia’,1,500,250) G2(456,’Med’,’Sobhi’,’1155’,Célibataire,Occasionnel,3.200,70,Oui) Remarques

(i) On voit maintenant que les deux générateurs ne comportent plus de cases vides et par conséquent plus de trous en mémoire.

(ii) On voit également clair que les deux générateurs G1 et G2 sont de tailles variables.

(iii) Dans un enregistrement variable, on doit tout d’abord déclarer la partie fixe puis on définit la partie variable.

(iv) Attention, il ne faut pas confondre entre le SELON vu dans le chapitre Structures Conditionnelles et le SELON vu dans ce chapitre : le premier concerne des instructions ; quant au deuxième il concerne des variables. C’est une erreur fréquente de la part des étudiants !?

ACCES AUX RUBRIQUES

En prenant les deux générateurs de l’exemple, on va essayer d’accéder à chacune

de leur rubrique : G1(123,’Ali’,’Med’,’1164’,Marié,Permanent,’Med’,’Alia’,1) G2(456,’Med’,’Sobhi’,’1155’,Célibataire,Occasionnel,3.200,70,Oui) TYPE Salarié = ENREGISTREMENT

Matricule : entier Nom, Prénom : chaine Date_naissane : chaine Catégorie : Cat État_civil : Situation SELON (Situation) FAIRE Marié : Nom_conjoint, Prénom_conjoint : chaine Nombre_enfant : entier Célibataire : Service_militaire : Booléen

- Page : 90/104 -

FINSELON SELON (Cat) FAIRE Permanent : Salaire_base : réel Indemnités : réel Occasionnel : Coût_horaire : réel Nombre_heures : réel FINSELON FINENREGISTREMENT

VARIABLE S : Salarié

G1(123,’Ali’,’Med’,’1164’,Marié,Permanent,’Med’,’Alia’,1,500,250) G2(456,’Med’,’Sobhi’,’1155’,Célibataire,Occasionnel,3.200,70,Oui) Pour un salarié permanent et marié, on aura : S.Matricule 123 S.Nom ‘Ali’ S.Prénom ‘Med’ S.Date_naissane ‘1164’ S.Etat_civil Marié

S.Catégorie Permanent S.Nom_conjoint ‘Med’ S.Prénom_conjoint ‘Alia’ S.Nombre_enfant 1 S.Salaire_base 500 S.Indemnités 250 Pour un salarié occasionnel et célibataire, on aura : S.Matricule 456

S.Nom ‘Med’ S.Prénom ‘Sobhi’ S.Date_naissane ‘1155’ S.Etat_civil Célibataire

S.Catégorie Occasionnel S.Service_militaire Oui S.Coût_horaire 3.200

S.Nombre_heures 70

NOTIONS DE FICHIER Un fichier est un ensemble d’informations stockées en mémoire secondaire et structuré en enregistrements.

- Page : 91/104 -

On dit également qu’un fichier est un ensemble d’enregistrements. Exemples

- Fichier des salariés d’une société. - Fichier des comptes clients en banque. - Fichier d’abonnés de la STEG ou de la SONEDE. - Fichier des étudiants d’une institution universitaire. - Fichier Stock d’une entreprise commerciale. - Etc.

LE SYSTEME DE GESTION DE FICHIERS : SGF Les mémoires secondaires tels que le disque dur, la disquette, la bande magnétique, etc., ne sont pas coûteux, possèdent de grandes capacités de stockage et sont non volatiles. L’acheminement des informations dans des fichiers existants sur ces supports se fait à l’aide de primitives incluses dans le système d’exploitation et plus exactement dans la couche qui est responsable de la gestion des fichier ; elle s’appelle SGF ou encore le Système de Gestion de Fichiers. Les principales fonctions d’un tel système sont : l’ajout d’un élément dans un fichier, la suppression d’un élément, la mise à jour d’un élément et la recherche d’un élément dans un fichier. ORGANISATION DES FICHIERS ET METHODES D’ACCES

Problématique :

Comment trouver dans un fichier un enregistrement dont on connaît une référence ? Cela va dépendre de la façon dont sont organisés les enregistrements entre eux. En fait, ça dépend du type d’organisation du fichier. On distingue :

- l’organisation séquentielle - l’organisation indexée - l’organisation relative - l’organisation sélective.

Pour accéder à un enregistrement, il faut avant tout voir le type d’organisation, puis voir est ce que le type d’accès désiré est permis dans une telle organisation ou non ! Par exemple, si on dispose d’une bande magnétique (l’équivalent d’une K7), il est facile de deviner que l’organisation est séquentielle. Pour atteindre le nième enregistrement, on doit obligatoirement parcourir les (n-1) enregistrements précédents et il n’y a pas d’autres solutions (imaginer que vous voulez écouter la 3ème chanson d’une K7, obligatoirement vous devez défiler les 2 chansons précédentes).

- Page : 92/104 -

Maintenant, si le support est un disque magnétique, son organisation n’est pas uniquement séquentielle mais elle peut être indexée : pour atteindre le nième enregistrement, on peut soit parcourir les (n-1) enregistrement précédents ou si on a une référence, on l’introduit et on accède directement à l’enregistrement y afférent (prenons l’exemple d’un disque musical, on peut accéder directement à la chanson préférée ou écouter séquentiellement les chansons jusqu’à ce que votre chanson préférée se manifeste). Donc, une méthode d’accès est une façon d’atteindre un enregistrement ; il y a essentiellement deux méthodes d’accès :

- accès séquentiel - accès direct

Organisation Séquentielle :

a-) Définition L’organisation séquentielle consiste à mettre les enregistrements dans le fichiers les uns après les autres selon l’ordre de leur arrivée. Elle peut être définie sur tout type de support de mémoire secondaire. Cette organisation ne permet que l’accès séquentiel. b-) Les Primitives

Ouverture d’un fichier : avant tout traitement sur les fichiers, il faut ouvrir les fichiers y afférents.

Ouvrir (nom_fichier, mode_ouverture)

Le mode d’ouverture est soit Lecture(L) ou (exclusif) Ecriture(E)

Fermeture d’un fichier : une fois le traitement achevé, il ne faut pas oublier de fermer tout fichier ouvert.

Fermer (nom_fichier)

Lecture d’un Enregistrement à partir d’un fichier Lire (nom_fichier, nom_enregistrement)

Écriture d’un enregistrement dans un fichier : c’est la même chose de dire ajouter un enregistrement dans un fichier.

Écrire (nom_fichier, nom_enregistrement) Remarques :

(i) L’ajout se fait toujours en fin de fichier. (ii) Tout fichier possède un booléen indiquant si la fin de fichier est atteinte ou

non ; on peut la noter EOF : End Of File et on peut appliquer les opérateurs logiques sur cette variable booléenne : par exemple on peut dire

- Page : 93/104 -

si NON (EOF) pour indiquer si la fin de fichier n’est pas atteinte alors on va exécuter tel traitement. Cette variable va obligatoirement avec le nom du fichier : EOF (nom_fichier)

(iii) Dans certains langages, après l’ouverture d’un fichier, il faut l’initialiser : en Pascal c’est la primitive RESET (nom_fichier).

Organisation Indexée

a-) Définition Un fichier dispose d’une organisation indexée, si chaque enregistrement est identifié

par son index dans une table d’index. Cet index est une rubrique du fichier (ou plusieurs) qui identifie d’une manière unique un et un seul enregistrement. b-) Les Primitives

Ouverture du fichier Ouvrir (nom_fichier, Mode_ouverture)

Le mode d’ouverture peut être soit lecture, soit écriture soit lecture/écriture.

Fermeture d’un fichier Fermer (nom_fichier)

Lecture séquentielle d’un enregistrement Lire (nom_fichier, nom_enregistrement)

Lecture indexée d’un enregistrement Lire (nom_fichier, clé, nom_enregistrement, zone_tampon)

Écriture d’un enregistrement dans un fichier à sa bonne place Écrire (nom_fichier, clé, nom_enregistrement, zone_tampon)

Suppression d’un enregistrement Supprimer (nom_fichier, clé)

Remarques :

(i) L’ajout se fait en fonction de la valeur de la clé. (ii) Tout fichier possède un booléen indiquant si la fin de fichier est atteinte ou

non ; on peut la noter EOF : End Of File et on peut appliquer les opérateurs logiques sur cette variable booléenne : par exemple on peut dire si NON (EOF) pour indiquer si la fin de fichier n’est pas atteinte alors on va exécuter tel traitement. Cette variable va obligatoirement avec le nom du fichier : EOF (nom_fichier)

(iii) Dans certains langages, après l’ouverture d’un fichier, il faut l’initialiser : en Pascal c’est la primitive RESET (nom_fichier).

On dit Index et parfois clé

- Page : 94/104 -

LES TRAITEMENTS SUR LES FICHIERS – Exercices Proposés –

Enregistrement Fixe, Enregistrement Variable, Générateur, Fichier, Organisation Séquentielle, Organisation Indexée, Primitives, etc.

Exercice 1 Déclarez un type enregistrement Agenda contenant les informations suivantes:

Nom

Prénom

Téléphone

Poste de travail Exercice 2 Déclarez une structure enregistrement Point contenant les informations suivantes:

Abscisse

Ordonnée Et déclarez un tableau de 10 points. Exercice 3 Écrivez un algorithme qui permet de saisir l'état civil d'une personne ayant les informations suivantes:

Nom

Année de naissance

Ville Exercice 4 Déclarez une variable P ayant les informations suivantes:

Nom

Prénom

Date de naissance:

Jour

Mois

Année

Matricule Exercice 5 Proposez une structure permettant de saisir les notes de certaines matières pour un étudiant, sachant qu'une matière a une note inférieure à 20 et un coefficient entier. Exercice 6 On souhaite enregistrer les notes des étudiants pour 6 matières pour une classe de 27 étudiants dans un tableau. Puis on désire afficher la moyenne de chacun avec son nom et son prénom. Construisez un algorithme permettant d'effectuer ces traitements ?

- Page : 95/104 -

Exercice 7 Écrivez une procédure permettant d'afficher les informations concernant les voitures

Matricule

Modèle

Couleur

Puissance

Date d'acquisition (jour, mois, année)

Date fin visite (jour, mois, année) Ces informations sont enregistrées dans un tableau de taille n. Exercice 8 Écrivez une procédure permettant de créer à partir d'un tableau de borne inf et de borne sup, contenant les informations concernant les étudiants de l'ISET de Radès (NCE, Nom, Prénom, Année naissance, Classe) un tableau de taille n contenant les étudiants de l'informatique. Exercice 9 Soient 2 tableaux de taille n1 et n2 contenant la liste des produits de deux ateliers appartenant à une même entreprise. Ces tableaux contiennent les informations suivantes:

Référence pièce

Catégorie

Libellé

Quantité en stock Ces deux tableaux sont triés selon Référence pièce dans l'ordre croissant. Écrivez une procédure permettant de fusionner ces deux tableaux en un tableau trié selon Référence pièce dans l'ordre croissant. Exercice 10 Écrivez un algorithme qui permet de saisir des enregistrements Dessin contenant les informations suivantes :

Abscisse

Ordonnée

Forme (cercle, carré, rectangle)

Rayon

Côté

Largeur

Longueur Déclarez 3 variables de ce type et leur affecter un cercle de centre o(5.3,3.2) et de rayon 2.1, un rectangle de centre (2.,5.) et de largeur 7.1 et de longueur 15.2. Exercice 11 Soit un fichier f_etudiant contenant les informations suivantes:

NCE

Nom

- Page : 96/104 -

Prénom

Ville

Code ville

Année de naissance

Année de bac

Nature du bac

Année 1er inscription

Classe Écrivez un algorithme permettant de lister le contenu du fichier f_etudiant. Exercice 12 Écrivez un algorithme qui affiche les étudiants de Tunis à partir du fichier f_etudiant Exercice 13 Écrivez un algorithme qui permet de saisir des étudiants à partir du clavier et de les enregistrer dans le fichier f_etudiant. Exercice 14 Écrivez une fonction qui retourne le nombre d'enregistrements dans le fichier f_etudiant. Exercice 15 Créez à partir du fichier étudiant un fichier finfo12 (ou finfo13) contenant respectivement les étudiants des classes Info11 respectivement Info12. Exercice 16 Soit fcompagence1 et fcompagence2 deux fichiers contenant les comptes des clients de l'agence 1 et de l'agence 2 ayant les informations suivantes:

Num compte

Nom client

Type client (morale ou physique)

Etat (débiteur ou créditeur)

Solde

Date de création (jour, mois, année) Ces fichiers sont triés par num compte et sont non volumineux ; écrivez un algorithme permettant de fusionner les deux fichiers en un nouveau fichier fcompte (trié par num compte). Exercice 17 Écrivez un algorithme qui permet d'éclater un fichier f_etudiant en 2 fichiers:

Fichier EtudRades

Fichier EtudCharguia Sachant que le fichier f_etudiant contient les informations suivantes:

NCE

Nom

Prénom

- Page : 97/104 -

Date de naissance (jour, mois, année)

Classe

Département (AC, Gestion, TJ, GM, GE, GC, Info) Le fichier EtudCharguia contiendra les étudiants des départements AC et TJ et le fichier EtudRades le reste. Exercice 18 Écrivez une procédure permettant d'afficher un enregistrement Personnel en lui fournissant la matricule de l'employé. Sachant que le fichier personnel contient les informations suivantes:

Matricule

Nom

Prénom

Date de naissance (jour, mois, année)

Ville

Situation familiale (célibataire, marié, veuf, divorcé)

Nombre d'enfants (marié)

Prénomc (marié)

Nombre enfants à charge (divorcé ou veuf) Exercice 19 On dispose de trois fichiers contenant des informations concernant des personnes.

Fichier 1 : "age.dat" contient le nom et l'âge (nom : chaîne, age : entier) Fichier 2 : "coordonnees.dat" contient le nom, le prénom et l'adresse (nom, prenom, adresse : chaîne) Fichier 3 : "secu.dat" contient le nom et le numéro de sécurité sociale (nom : chaîne, secu : entier)

On considère que chacun des trois fichiers possède un enregistrement sur chacune des personnes. On se propose de créer un seul fichier regroupant les informations des trois autres fichiers. 1-) Écrivez une fonction Rech_Age qui renvoie l'âge d'une personne à partir de son nom. 2-) Écrivez une procédure Rech_Pren_Adr qui recherche le prénom et l'adresse d'une personne donnée. 3-) A l'aide de Rech_Age et Rech_Pren_Adr, écrivez le programme principal qui fusionne toutes les informations des trois fichiers en un seul : "personne.dat" . Exercice 20 Je désire gérer ma cave de boissons. Une bouteille de boisson est caractérisée par :

son nom, son type (gazeuse, alcoolisée, minérale)

son année (1800.. 2005), sa note (0.. 20) 1-) Définissez le type Boisson. 2-) Écrivez une procédure Cree_Cave(nom-du-fichier), qui créé le fichier nom-du-fichier et enregistre dans celui-ci l'ensemble des boissons constituant la cave.

- Page : 98/104 -

LES ALGORITHMES DE TRI – L’Essentiel du Cours –

Tri par Sélection, Tri par Insertion, Tri à Bulles.

Objectif Général 5 : Comprendre les algorithmes de tri. Objectifs Spécifiques :

OS 1 : Tri par Sélection

OS 2 : Tri par Insertion

OS 3 : Tri à Bulles

OS 4 : Comparer ces algorithmes en terme de performance. Rappel du Cours : INTRODUCTION On a vu dans le chapitre « Le Type Tableau » un seul algorithme de Tri et on a alors définit qu’est ce qu’une action de tri. On rappelle qu’une opération de tri consiste à ordonner une suite de valeurs mémorisées selon un critère bien déterminé qu’on appelle clé et suivant une relation d’ordre (croissant ou décroissant). Il existe deux types de tris :

- Le Tri Interne : il s’effectue sur des données présentes en mémoire centrale, en général dans des tableaux.

- Le Tri Externe : il s’effectue sur des données stockées en mémoires secondaire, en général dans des fichiers.

Dans ce qui suit, on va s’intéresser aux tris internes et on va évoquer trois techniques de tri qui sont :

- Tri par Sélection - Tri par Insertion - Tri à Bulles

TRI PAR SELECTION

Principe Le principe consiste à sélectionner l’élément dont la valeur est la plus basse

(minimum), puis échanger la valeur de cet élément avec le premier élément du tableau. Le traitement doit se poursuivre en cherchant le minimum parmi ceux qui restent : à partir du deuxième élément du tableau, puis faire l’échange avec le deuxième élément jusqu’à atteindre T[n-1] et T[n].

Algorithme Algorithme Tri_Sélection Constante

- Page : 99/104 -

n : entier Type Tab_Entier = Tableau[1..n] de Entier Variable Min, ind, temp, i : entier T : Tab_Entier Début

Pour i allant de 1 à (n-1) Faire min ind Pour i allant de (ind+1) à n Faire Si (T(i) < T(min)) Alors min i FinSi FinPour Temp T(ind) T(ind) T(min) T(min) temp FinPour

Fin TRI PAR INSERTION Principe

On insère les éléments un par un en les plaçant correctement : on insère le second élément à sa place dans le sous tableau constitué du premier élément, on insère ensuite le troisième élément du tableau à sa place dans le sous tableau constitué du premier et du deuxième élément et ainsi de suite jusqu’au dernier élément. Algorithme Algorithme Tri_Insertion Constante n : entier Type Tab_Entier = Tableau[1..n] de Entier Variable i, j, aux : entier T : Tab_Entier Début Pour i allant de 2 à n Faire aux T(i) j (i-1) Tant que ( j > 0 ) et ( T(j) > aux ) Faire T(j+1) T(j) J j-1 Fin Tant que T(j+1) aux Fin pour Fin

- Page : 100/104 -

TRI A BULLES

Principe

Cette technique de tri consiste à balayer tout le tableau en comparant les éléments adjacents et en les échangeant s’ils ne sont pas dans le bon ordre. Un seul passage ne déplacera un élément donné que d’une position, mais en répétant le processus jusqu’à ce qu’aucun échange ne soit nécessaire. Algorithme Algorithme Tri_Bulles Constante n : entier Type Tab_Entier = Tableau[1..n] de Entier Variable Permute : Booléen i, temp : entier T : Tab_Entier Début Répéter permute faux Pour i allant de 2 à n Faire Si (T(I-1) > T(i)) Alors Permute vrai Temp T(i-1) T(i-1) T(i) T(i) temp FinSi FinPour Jusqu’à (Non(permute)) Fin EVALUATION DES PERFORMANCES

- Le Tri par Sélection : le nombre de boucles internes est estimé à n(n-1)/2 et le nombre maximal de déplacements d’éléments est de l’ordre de 2(n-1). Cette technique est intéressante dans le cas où le tableau est en désordre total mais elle n’est pas optimale si la première partie du tableau est triée.

- Le Tri par Insertion : le nombre de boucles interne est estimé à n(n-1)/2. Cette

technique est intéressante pour des tableaux ayant été déjà triés mais auxquels on a rajouté de nouveaux éléments en fin du tableau.

- Le Tri à Bulles : Cette technique nécessite un grand nombre de déplacements

d’éléments. Il va nécessiter (n-1) boucles principales dans le cas où le dernier élément devrait être placé en premier. Le nombre maximal de boucles internes est de l’ordre de (n-1)2 . Elle peut être intéressante quand le tableau initial est déjà pré-trié c’est à dire que les éléments ne sont pas disposés trop loin de leur position finale.

- Page : 101/104 -

LES ALGORITHMES DE TRI – Exercices Proposés –

Tri par Sélection, Tri par Insertion, Tri à Bulles.

Exercice 1 Écrivez un algorithme qui permet de saisir un nombre quelconque de valeurs, et qui les range au fur et à mesure dans un tableau. Une fois la saisie terminée, il doit dire si les éléments du tableau sont tous consécutifs ou non. Par exemple, si le tableau est :

12 13 14 15 16 17 18

ses éléments sont tous consécutifs. En revanche, si le tableau est :

9 10 11 15 16 17 18

ses éléments ne sont pas tous consécutifs. Exercice 2 Écrivez un algorithme qui trie un tableau dans l’ordre décroissant. Vous écrirez bien entendu deux versions de cet algorithme, l'une employant le tri par insertion, l'autre le tri à bulles. Exercice 3 Écrivez un algorithme qui inverse l’ordre des éléments d’un tableau dont on suppose qu'il a été préalablement saisi (« les premiers seront les derniers… ») Exercice 4 Écrivez un algorithme qui permet à l’utilisateur de supprimer une valeur d’un tableau préalablement saisi. L’utilisateur donnera l’indice de la valeur qu’il souhaite supprimer. Attention, il ne s’agit pas de remettre une valeur à zéro, mais bel et bien de la supprimer du tableau lui-même ! Si le tableau de départ était :

12 8 4 45 64 9 2

Et que l’utilisateur souhaite supprimer la valeur d’indice 4, le nouveau tableau sera :

12 8 4 45 9 2

Exercice 5 Écrivez l'algorithme qui recherche un mot saisi au clavier dans un dictionnaire. Le dictionnaire est supposé être codé dans un tableau préalablement rempli et trié.

- Page : 102/104 -

LES ALGORITHMES DE TRI – Corrigé –

Tri par Sélection, Tri par Insertion, Tri à Bulles.

Exercice 1 Algorithme Tab_Cons Constante N=7 Type Tab_Ent=Tableau[1..N] de Entier Variable T : Tab_Ent I : Entier X : Booléen Début Écrire ("Entrez les valeurs :") Pour I← 1 à N Faire Lire (T(I)) Fin Pour XVrai Pour I ← 1 à N – 1 Faire Si T(I) <> T(I – 1) + 1 Alors X ← Faux Fin Si Fin Pour Si X Alors Écrire ("Les nombres sont consécutifs") Sinon Écrire ("Les nombres ne sont pas consécutifs") Fin Si Fin Exercice 2 (* Tri Insertion *) Début Pour i ← 1à N – 1 Faire posmaxi I Pour J ← I + 1 à N – 1 Faire Si (t(J) > t(posmaxi)) Alors posmaxi ← j Fin si Fin Pour temp ← t(posmaxi) t(posmaxi) ← t(I) t(I) ← temp Fin Pour Fin

- Page : 103/104 -

(* Tri à Bulles *) Début Yapermut ← Vrai Tant que Yapermut Faire Yapermut ← Faux Pour i ← 1 à N – 1 Faire Si t(i) < t(i + 1) Alors temp ← t(i) t(i) ← t(i + 1) t(i + 1) ← temp Yapermut ← Vrai Fin si Fin Pour Fin Tant que Fin Exercice 3 On suppose que n est le nombre d’éléments du tableau préalablement saisi Début Pour i ← 1 à N/2 Faire Temp ← T(i) T(i) ← T(N-i) T(N-i) ← Temp Fin Pour Fin Exercice 4 Début Écrire ("Rang de la valeur à supprimer ?") Lire (S) Pour i ← S à N-2 T(i) ← T(i+1) Fin Pour Fin Exercice 5 N est le nombre d'éléments du tableau Dico(), contenant les mots du dictionnaire, tableau préalablement rempli. Algorithme Dictio Variable Sup, Inf, Comp : Entier Fini en Booléen Début Ecrire "Entrez le mot à vérifier" Lire (Mot) On définit les bornes de la partie du tableau à considérer

- Page : 104/104 -

Sup ← N - 1 Inf ← 0 Fini ← Faux Tant Que Non Fini Comp désigne l'indice de l'élément à comparer. En bonne rigueur, il faudra veiller à ce que Comp soit bien un nombre entier, ce qui pourra s'effectuer de différentes manières selon les langages. Comp ← (Sup + Inf)/2 Si le mot se situe avant le point de comparaison, alors la borne supérieure change, la borne inférieure ne bouge pas. Si Mot < Dico(Comp) Alors Sup ← Comp - 1 (* Sinon, c'est l'inverse *) Sinon Inf ← Comp + 1 Fin Si Fini ← Mot = Dico(Comp) ou Sup < Inf Fin Tant Que Si Mot = Dico(Comp) Alors Écrire ("le mot existe") Sinon Écrire ("Il n'’existe pas") Fin si Fin