Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

REPUBLIQUE TUNISIENNE MINISTERE DE L’EDUCATION ET DE LA FORMATION ALGORITHMIQUE

REPUBLIQUE TUNISIENNE MINISTERE DE L’EDUCATION ET DE LA FORMATION ALGORITHMIQUE ET PROGRAMMATION 4ème année de l’enseignement secondaire Sciences de l'informatique Centre National Pédagogique Les auteurs Abdelhafidh ABIDI Inspecteur Principal Nadia AGREBI DEKHIL Professeur Principal d’Enseignement Secondaire Noureddine ZOUARI Professeur Principal Hors Classe Les évaluateurs Habib SMEI Maître Technologue Rached DOUARI Inspecteur Principal © Tous droits réservés au Centre National Pédagogique Préface La matière « Algorithmique et programmation » repose essentiellement sur l'algorithmique et la résolution de problèmes. La maîtrise de l'algorithmique requiert deux qualités : - avoir une certaine intuition, car il est impossible de savoir a priori quelles instructions permettront d'obtenir le résultat voulu. C'est là, si l'on y tient, qu'intervient la forme « d'intelligence » requise pour l'algorithmique. Cette qualité se développe avec l'expérience et la multiplication des problèmes à résoudre. Le raisonnement, au départ laborieux, finira par devenir « spontané ». - être méthodique et rigoureux. En effet, chaque fois qu'on résout un problème, il faut systématiquement se mettre mentalement à la place de la machine qui va exécuter le programme de la solution. Ce manuel est conçu pour aider à développer chez les élèves, entre autres, les qualités d'intuition et de rigueur dans leurs raisonnements. Conforme aux nouveaux programmes, ce manuel est destiné aux élèves de la quatrième année secondaire de la section « Sciences de l'informatique ». L'intention de l'ouvrage est donc, d'aider l'élève à : - apprendre à résoudre des problèmes et à écrire des algorithmes. - acquérir les algorithmes les plus courants dans des domaines variés tel que la récurrence, l'arithmétique, l'approximation, les tris, … - Pascal. Chacun des sept chapitres de ce manuel est précédé par : 1- La liste des objectifs qui précisent les savoirs et les savoir-faire permettant ainsi de délimiter la portée de chaque notion étudiée. 2- Le plan du chapitre. Comme pour le manuel d'algorithmique et de programmation de la troisième année de la section « Sciences de l'informatique », chaque chapitre de ce manuel comporte : - des activités préliminaires - l'étude de la notion (définition, syntaxe au niveau algorithmique et au niveau du langage de programmation Pascal) - des applications sous forme d'exercices résolus - une série d'exercices en fin de chapitre - une partie lecture pour renforcer le volet culture informatique chez les apprenants. Le premier chapitre intitulé « Les enregistrements et les fichiers » est conçu pour introduire deux nouvelles structures de données que les élèves n'ont pas vu en 3ème année. Le deuxième chapitre présente la technique de raisonnement par récurrence qui sera utilisée dans beaucoup d'applications des chapitres suivants. Comme dans le programme de 3ème année, les cinq derniers chapitres présentent les grandes familles d'algorithmes à savoir : - les algorithmes de tri - les algorithmes récurrents - les algorithmes arithmétiques - les algorithmes d'approximation - les algorithmes avancés Nous invitons les utilisateurs de ce manuel à nous faire part de leurs critiques et de leurs suggestions et nous les remercions d'avance. Les auteurs Nadia.Dekhil@edunet.tn Noureddine.Zouari@edunet.tn Abdelhafidh.Abidi@edunet.tn L e s l o g o s L e s l o g o s Une remarque importante Une idée - Une solution d'une application ou d'une activité posée, - Une réponse à une ou à plusieurs questions Une série d'exercices non corrigés Lecture Des points importants à retenir du chapitre Question, activité, application ou exercice de degré de difficulté simple Question, activité, application ou exercice de degré de difficulté moyen Question, activité, application ou exercice de degré de difficulté assez élevé Question, activité, application ou exercice de degré de difficulté élevé Chapitre 1 Les enregistrements et les fichiers 7 Chapitre 2 La récursivité 73 Chapitre 3 Les algorithmes de tri 95 Chapitre 4 Les algorithmes récurrents 123 Chapitre 5 Les algorithmes d’arithmétique 151 Chapitre 6 Les algorithmes d’approximation 187 Chapitre 7 Les algorithmes avancés 213 Bibliographie 246 Sommaire S Sommaire Webographie 247 Objectifs • Définir la structure enregistrement • Définir les fichiers et les modes d'accès • Mettre à profit les structures enregistrement et fichiers pour résoudre des problèmes. Plan du chapitre A) Les enregistrements I- Introduction II- Définition et déclaration III- Utilisation des enregistrements B) Les fichiers I- Introduction II- Organisation des fichiers III- Types d'accès IV- Fichiers à accès séquentiel V- Fichiers à accès direct VI- Fichiers texte Retenons Exercices Lecture Chapitre 1 pitre 1 Les enregistrements et les fichiers Chapitre 1 Question : Les enregistrements et les fichiers 8 A. Les enregistrements Activité 1 N° Code Nom & Prénom Moyenne Observations 1 C0120 Cherni Selim 14.25 Néant 2 K0235 Kefi Marwa 13.12 Redoublante … … … … …. … … … … … 30 B3017 Bennour Raouf 11.75 Dispensé du sport Le directeur de l’établissement veut créer un programme permettant la saisie et le traitement de ces listes sachant que chaque classe comporte au maximum 40 élèves. a. Donnez la structure de données nécessaire pour les objets à utiliser. b. Donnez une déclaration algorithmique de ces objets. Un établissement scolaire organise les informations concernant ses classes dans une liste identique à la suivante : a. Nous remarquons que cette liste comporte une information alphanumérique (Code), des informations numériques (N°, Moyenne) et d’autres alphabétiques (Nom & Prénom, Observations). D’après les connaissances que nous avons acquises les deux dernières années, nous pouvons utiliser 5 variables déclarées comme suit : I. Introduction Les enregistrements et les fichiers 9 Question : b. Tableau de déclaration des objets : Objet Type / Nature Rôle Num Tableau de 40 entiers Tableau des numéros des élèves Code Tableau de 40 chaînes Tableau des codes Nom Tableau de 40 chaînes Tableau contenant les noms & prénoms Moy Tableau de 40 réels Tableau des moyennes Obser Tableau de 40 chaînes Tableau des observations Est-il possible de regrouper ces variables au sein d'un même tableau ? Bien sûr que NON car un tableau ne peut contenir que des éléments de même type. Mais nous pouvons utiliser 5 tableaux différents déclarés comme suit : Tableau de déclaration des nouveaux types : Tableau de déclaration des objets : Type Tab = Tableau de 40 Chaîne de caractères Objet Type / Nature Rôle Num Tableau de 40 entiers Tableau contenant les numéros des élèves Code Tab Tableau contenant les codes Nom Tab Tableau contenant les noms & prénoms Moy Tableau de 40 réels Tableau regroupant les moyennes Obser Tab Tableau rangeant les observations Nous venons de voir que les variables simples ou les tableaux ne permettent pas de ranger des données de types différents. Si nous voulons établir par exemple une structure comportant en même temps des informations alphanumériques, numériques et alphabétiques, nous devons créer un nouveau TYPE qui permet de les regrouper. Nous allons voir une nouvelle structure appelée ENREGISTREMENT ou ARTICLE (RECORD en Pascal) qui permet de réaliser cette tâche. Chapitre 1 10 II. Définition et déclaration Définition Un enregistrement est un type de données défini par l'utilisateur et qui permet de grouper un nombre fini d'éléments (ou champs) de types éventuellement différents. Schématisons cette structure : Champ 1 Type 1 Champ 2 Type 2 Champ 3 Type 1 Champ 4 Type 4 Champ 5 Type 5 Une seule entité d'une variable enregistrement Tableau de déclaration des nouveaux types Déclaration d’une structure ENREGISTREMENT En algorithmique Type Nom_type = Enregistrement champ 1 : Type 1 - - - - champ n : Type n Fin Nom_Type Tableau de déclaration des objets Objet Type / Nature Rôle Identificateur_objet Nom_type Enregistrement pour … Les enregistrements et les fichiers 11 En Pascal TYPE Nom_type = Record champ_1 : type_1 ; - - - - champ_n : type_n ; End; VAR identificateur_objet : Nom_type ; a. Les types (type 1, type 2, .. , type n) peuvent être soit prédéfinis, soit définis par l'utilisateur. b. Dans ce qui suit, nous utiliserons les mots variable ou objet au lieu de iden- tificateur_objet. Activité 2 Déclarez (en algorithmique et en Pascal) une variable enregistrement représentant un nombre complexe composé d'une partie réelle et d'une partie imaginaire. Tableau de déclaration des nouveaux types En algorithmique Type complexe = Enregistrement p_réelle : Réel p_imaginaire : Réel Fin complexe Tableau de déclaration des objets Objet Type / Nature Rôle z complexe Variable de type complexe, représentant un nombre complexe Chapitre 1 12 En Pascal TYPE complexe = Record p_reelle : Real ; p_imaginaire : Real ; End ; VAR z : complexe ; Activité 3 Déclarez en algorithmique et en Pascal, une varaiable enregistrement qui comporte : – le numéro du jour (jj) de 1 à 31, – le mois (mm) en utilisant le type mois qui est un nouveau type défini par l'utilisateur et qui énumère les 12 mois de l'année, – l'an (aa) qui est un entier. Déclarez une variable nommée "calendrier" qui permettra l'utilisation de cet enregistrement. Tableau de déclaration des nouveaux types En algorithmique Type mois = (Janvier, Février, Mars, Avril, Mai, Juin, Juillet, Août, Septembre, Octobre, Novembre, Décembre) date = Enregistrement jj : 1..31 mm : mois aa : Entier Fin date Tableau de déclaration des objets Objet Type / Nature Rôle calendrier date Variable de uploads/Science et Technologie/ 4-si-algoritmique 1 .pdf