Remerciez-le!

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

ALGORITHMES ET STRUCTURES DE DONNEES ELEMENTAIRES (E.T. : 20heures, E.D. : 20 h

ALGORITHMES ET STRUCTURES DE DONNEES ELEMENTAIRES (E.T. : 20heures, E.D. : 20 heures, E.P. : 18 heures) Année Universitaire 2011/2012 Dr RAKOTOASIMBAHOAKA CYPRIEN ROBERT Enseignant-chercheur à l’Ecole Nationale d’Informatique UNIVERSITE DE FIANARANTSOA 1. ELEMENTS ELEMENTAIRES DES ALGORITHMES. 1.1. Les chaînes de caractères 1.2. Fonctions et variables entières 1.3. Itérations et conditions 1.4. Transmission des paramètres 1.5. Raisonnement par récurrence 2. VECTEURS 2.1. Introduction 2.2. Algorithmes traitant un seul vecteur 2.3. Tris d’un vecteur 2.4 Algorithmes de mise à jour d’un vecteur 3. FICHIERS 3.1. Définition et propriétés 3.2. Actions primitives d’accès 3.3. Algorithmes traitant un seul fichier 3.4. Algorithmes traitant plusieurs fichiers 1. ELEMENTS ELEMENTAIRES DES ALGORITHMES Un algorithme est une suite d’instructions que devra effectuer un automate (ordinateur) pour arriver en un temps fini, à un résultat déterminé (post-condition), à partir d’une situation donnée (pré-condition). 1.1. Les chaînes de caractères Afficher un message à l’écran, ou imprimer un message sur papier. 1.1.1. l’instruction « écrire » Nous voulons faire afficher un message de bienvenue. Algorithme 1 : écrire("Bonjour à tous") ; Un caractère peut être une lettre majuscule ou minuscule, un chiffre, un signe de ponctuation, ou un espace pris entre apostrophe, par exemple : ‘A’, ‘b’. Une chaîne de caractère, ou chaîne pour abréger, est une suite quelconque de caractères, entourée de guillemets, par exemple : "une classe". Si parmi ces caractères nous voulons imprimer une valeur on écrit le % suivi d’un caractère qui indique le type de cette valeur (algorithme 2). 1.1.2. les variables de type chaîne, l’instruction lire Nous pouvons .souhaiter « personnaliser » notre message d’accueil en affichant le nom de l’utilisateur. Bien entendu, l’ordinateur ne connaît ce nom à priori et devra donc commencer par le lui demander. Algorithme 2 : écrire("Comment vous appelez-vous ? ") ; lire(nom) ; écrire("Bonjour %s ! \n",nom) ; Chaque variable ou identificateur est une suite de caractères pris parmi les lettres, les chiffres et le caractère « souligné », mais doit commencer par une lettre. Ainsi : a, A3_b2, toto sont des identificateurs valables, alors que 35, 5A, A+B ne le sont pas. 1 Exemple d’exécution de l’algorithme2. 1.2. Fonctions et variables entières Une fonction est une suite d’instructions nommée, que l’on pourra appeler par ce nom chaque fois que l’on veut l’utiliser. Une fonction doit être déclarée afin de pouvoir ensuite l’appeler par son nom. Syntaxe de la déclaration : type_de_valeur_de _retour nom_fonction(arguments) { corps de le fonction } vide bonjour1(vide) { chaine nom ; écrire("Comment vous appelez-vous ? ") ; lire(nom) ; écrire("Bonjour %s ! \n",nom) ; } 1.2.1. Déclarations de variables Elles servent à indiquer à l’ordinateur les identificateurs utilisés dans la fonction, ainsi que leur type. Dans la fonction bonjour1, nous n’avons qu’une seule variable appelée nom et de type chaîne. Syntaxe de déclaration : type identificateur ; Exemple : chaine ch ; ch est une variable de type chaine. 1.2.2. Variables entières et expressions arithmétiques Notre fonction va indiquer à l’utilisateur son âge. C’est l’ordinateur qui calculera cet âge à partir de deux données : l’année actuelle et l’année de naissance de l’utilisateur. vide bonjour2(vide) { chaine nom ; entier annee, naissance ; écrire("A quelle annee sommes-nous ? ") ; lire(annee) ; écrire("Comment vous appelez-vous ? ") ; lire(nom) ; écrire("Votre annee de naissance ? ") ; lire(naissance) ; écrire("Bonjour %s ! \n",nom) ; écrire("Vous etes age de %d ans \n", annee-naissance) ; } Les entiers peuvent être positifs ou négatifs, et on peut leur appliquer les opérations arithmétiques classiques : addition, soustraction, multiplication, division notés +, -, *, et /, ainsi que l’opérateur modulo, noté %, tel que n % p donne le reste de la division entière de n par p ; Exemples : 3 + 5 donnera 8 2 * (-6) donnera -12 12 / 3 donnera 4 12 % 3 donnera 0 14 % 3 donnera 2 On appellera une expression entière toute expression formée à partir de variables entières, de nombres entiers, d’opérateurs, et éventuellement de parenthèses, selon les règles habituelles de l’algèbre. Exemple : Si les variables abc et xy ont respectivement pour valeurs 3 et -5, l’expression suivante : (abc + 25) / (4 * (7 + xy)) aura pour valeur : (3 + 25) / (4 * (7 + -5)), soit 28 / 8 c’est-à-dire 3. Dans la fonction bonjour2, nous utilisons une expression entière dans la dernière instruction écrire. Il s’agit de l’expression annee – naissance, dont la valeur est calculée par l’ordinateur. Exemple d’exécution de bonjour2 1.2.3. Paramètres, instruction d’affectation Avec la fonction bonjour2, nous devons demander à chaque utilisateur la valeur de l’année en cours. On peut supposer que cette valeur est déjà connue de l’ordinateur (par une saisie préliminaire). On pourra alors paramétrer la fonction avec cette valeur. vide bonjour3(entier annee) { chaine nom ; entier naissance, age ; écrire("A quelle annee sommes-nous ? ") ; lire(annee) ; 2 écrire("Comment vous appelez-vous ? ") ; lire(nom) ; écrire("Votre annee de naissance ? ") ; lire(naissance) ; écrire("Bonjour %s ! \n",nom) ; age = annee-naissance ; écrire("Vous etes age de %d ans \n", age) ; } Le paramètre annee est de type entier est appelé paramètre formel et il sera remplacé à l’appel de la fonction par une valeur entière. On dit qu’on fait le passage par valeur. Exemples d’instructions d’appel  bonjour3(1993) ;  Si la variable ancour contient une valeur entière : bonjour3(ancour) ; On dira que 1993 ou ancour sont des paramètres effectifs, dont la valeur remplace celle du paramètre formel lors de l’exécution. D’autre part, nous introduisons dans la fonction une instruction d’affectation : age = annee – naissance ; Cette instruction permet de ranger une valeur dans une variable, autrement que par saisie directe (lire). Exemple d’instructions d’affectation correctes a1 = 3 ; b = 3 * 5 ; c = a1 ; c = (b + 6) / 4 ; nb = nb + 1 ; nb = nb * (a1 + b) ; L’instruction d’affectation nb = nb + 1 est tout à fait différente d’une égalité mathématique. En effet, l’égalité nb = = nb + 1 serait évidemment toujours fausse, quelle que soit la valeur de nb alors que l’instruction nb = nb + 1 consiste simplement à modifier la valeur de la variable nb, en lui ajoutant 1. Exemples d’instructions d’affectation incorrectes a + 1 = 3 ; (a+ 1 n’est pas un identificateur de variable). a = 3b ; (3b n’est ni un identificateur, ni une expression correcte) Cette instruction d’affectation est aussi correcte : x = y = z = 0 ; l’associativité est effectuée de droite à gauche. Cependant l’écriture suivante n’est pas acceptée : double x = y = z = 0 ; // est rejeté. Rappel : toute variable utilisée dans un programme doit être déclarée au début de l’algorithme, une fois et une seule. Lorsqu’une variable apparaît en partie droite d’une instruction d’affectation, c’est que l’on suppose qu’elle contient une valeur. Cette valeur devra lui avoir été affectée auparavant (initialisation), sinon l’on dira que la valeur est indéfinie, et le résultat de l’affectation ne sera pas défini. Exemple d’algorithme correct : vide corr(vide) { entier a, b, c ; a = 12 ; b= 5 ; c = a – b ; a = a + c ; /* il s’agit ici de modifier la valeur de a, en lui ajoutant c */ b = a ; } Pour voir les contenus successifs des variables, nous allons en effectuer la trace : il s’agit tout simplement d’un tableau dans lequel pour chaque ligne de l’algorithme, nous noterons les valeurs des variables. Exemple d’algorithme incorrecte vide incorr(vide) { entier a, b, c ; a = 5 ; c = a + b ; d = c - 2 ; 3 int a, b, c ; a = 12;b = 5 ; c = a - b ; a = a + c ; b = a; a b c indéfini indéfini indéfini 12 5 indéfini 12 5 7 19 5 7 19 19 7 } 1.3. Itérations et conditions Ecrivez une fonction qui saisit le nom et l’année de naissance de toute une série de personnes et affiche pour chaque personne son âge. Une première méthode consiste à répéter les instructions de saisie et d’écriture un certain nombre de fois. vide etudiants1(entier annee) { chaine nom ; entier naissance, age ; écrire("Nom d’un etudiant ? ") ; lire(nom) ; écrire("Son annee de naissance ? ") ; lire(naissance) ; age = annee – naissance ; écrire("%s est age de %d ans\n",age) ; écrire("Nom d’un etudiant ? ") ; lire(nom) ; écrire("Son annee de naissance ? ") ; lire(naissance) ; age = annee – naissance ; écrire("%s est age de %d ans\n",age) ; écrire("Nom d’un etudiant ? ") ; lire(nom) ; écrire("Son annee de naissance ? ") ; lire(naissance) ; age = annee – naissance ; écrire("%s est age de %d ans\n",age) ; écrire("Nom d’un etudiant ? ") ; lire(nom) ; écrire("Son annee de naissance ? ") ; lire(naissance) uploads/s3/ algo-jiro-chap1-2012.pdf