Remerciez-le!

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

Master Sciences, Technologies, Santé Mention Mathématiques, spécialité Enseigne

Master Sciences, Technologies, Santé Mention Mathématiques, spécialité Enseignement des mathématiques Algorithmique et graphes, thèmes du second degré Feuille TD n°2 – Exercices d’algorithmique … éléments de correction … Exercice 1. Lecture et affichage d’une liste Écrire un algorithme permettant de construire une liste d’entiers naturels strictement positifs à partir d’une suite entrée au clavier et terminée par 0, puis de l’afficher une fois construite. Réponse. On construit la liste à l’aide de la structure tantque (pour détecter la fin de saisie), et on affiche son contenu en la parcourant à l’aide d’une boucle pour. L’algorithme est le suivant : Algorithme lectureEtAffichageListeEntiers Algorithme lectureEtAffichageListeEntiers Algorithme lectureEtAffichageListeEntiers Algorithme lectureEtAffichageListeEntiers # cet algorithme permet de construire une liste d’entiers naturels # strictement positifs à partir d’une suite entrée au clavier et # terminée par 0, puis de l’afficher une fois construite variables liste : liste d’entiers naturels n, i : entiers naturels début # initialisation liste [ ] # boucle de lecture des valeurs et de création de la liste Entrer ( n ) tantque ( n ≠ 0 ) # on rajoute l’entier n en fin de liste liste liste + [ n ] # on lit la valeur suivante Entrer ( n ) fin_tantque # boucle de parcours pour affichage pour i de 0 à NombreEléments ( liste ) - 1 faire Afficher ( liste [ i ] ) fin_pour fin Exercice 2. Retournement d’une liste Écrire un algorithme permettant de retourner une liste (son premier élément deviendra dernier, son deuxième avant-dernier, etc.) et d’afficher la liste ainsi retournée. Réponse. On retourne la liste en échangeant successivement les premier et dernier éléments, les second et avant-dernier éléments, etc. Attention, il faut arrêter cette série d’échange à la moitié de la longueur de la liste, sinon on la retourne deux fois !... L’algorithme, sous forme d’action, est le suivant : Action retournementListeEntiers ( Action retournementListeEntiers ( Action retournementListeEntiers ( Action retournementListeEntiers ( ES ES ES ES liste liste liste liste : liste d’entiers ) : liste d’entiers ) : liste d’entiers ) : liste d’entiers ) # cette action permet de retourner une liste d’entiers variables i, nbEléments : entiers naturels début # initialisation nbEléments NombreEléments ( liste ) # retournement de la liste pour i de 0 à ( nbEléments div 2 ) - 1 faire # on échange les éléments n° i et nbEléments - 1 - i liste liste [ 0 : i ] + liste [ nbEléments - i - 1] + liste [ i + 1 : nbEléments - i – 1 ] + liste [ i ] + liste [ nbEléments – i : nbEléments ] fin_pour fin On notera l’utilisation d’un paramètre d’entrée-sortie (ES), à la fois en entrée et en sortie : il s’agit d’un paramètre dont la valeur va être modifiée par l’action. Exercice 3. Nombre d’occurrences d’un élément Écrire un algorithme permettant de compter le nombre d’occurrences (d’apparitions) d’un élément donné dans une liste. Réponse. Il suffit de parcourir la liste en comptant le nombre d’apparitions de l’entier recherché. L’algorithme, sous forme de fonction, est le suivant : Fonction Fonction Fonction Fonction nombreOccurrencesDansListe nombreOccurrencesDansListe nombreOccurrencesDansListe nombreOccurrencesDansListe ( liste ( liste ( liste ( liste : liste d’entiers, élément : liste d’entiers, élément : liste d’entiers, élément : liste d’entiers, élément : entier ) : entier ) : entier ) : entier ) : entier : entier : entier : entier # cette fonction permet de déterminer le nombre d’occurrences de # élément dans liste variables liste : liste d’entiers naturels n, i, élément, nbOccurrences : entiers naturels début # initialisations nbEléments NombreEléments ( liste ) nbOccurrences 0 # parcours de la liste et comptage pour i de 0 à nbEléments – 1 faire si ( élément = liste [ i ] ) alors nbOccurrences nbOccurrences + 1 fin_si fin_pour # retour résultat Retourner ( nbOccurrences ) fin Exercice 4. La liste est-elle triée ? Écrire un algorithme permettant de déterminer si la liste obtenue est ou non triée par ordre croissant (au sens large). Réponse. Ondoit parcourir la liste en comparant chaque élément à son suivant dans la liste. Pour cela, le booléen estTriée, initialisé à vrai, basculera à faux lorsque deux éléments consécutifs de la liste ne sont pas rangés dans l’ordre. La structure tantque permet d’arrêter le parcours dès que le booléen passe à faux ou que l’on atteint l’avant-dernier élément de la liste. L’algorithme, sous forme de fonction, est le suivant : Fonction Fonction Fonction Fonction listeTriée listeTriée listeTriée listeTriée ( liste ( liste ( liste ( liste : liste d’entiers ) : liste d’entiers ) : liste d’entiers ) : liste d’entiers ) : booléen : booléen : booléen : booléen # cet algorithme permet de déterminer la liste # est ou non triée par ordre croissant au sens large variables n, i, nbEléments : entiers naturels estTriée : booléen début # initialisations estTriée vrai i 0 nbEléments NombreEléments ( liste ) # parcours et test de la liste : est-elle triée ? tantque ( ( i ≤ nbEléments – 2 ) et estTriée ) faire si ( L [i] > L [i+1] ) alors estTriée faux sinon i i + 1 fin_si fin_tantque # retour du résultat Retourner ( estTriée ) fin Exercice 5. La liste est-elle monotone ? Écrire un algorithme permettant de déterminer si une liste est ou non triée par ordre croissant ou décroissant au sens large (une telle liste est dite monotone, croissante ou décroissante respectivement). Réponse. Une fois la liste construite, on doit la parcourir, dans un premier temps, pour déterminer si elle est croissante ou décroissante (on utilisera un booléen estCroissante pour mémoriser cela) en cherchant les deux premiers éléments consécutifs distincts (si tous les éléments sont égaux, la liste est monotone). Ensuite, on procède comme dans l’exercice précédent, en adaptant le test des éléments consécutifs, et en continuant le parcours à l’endroit où l’on a détecté la première différence…. L’algorithme est le suivant : Algorithme listeMonotone Algorithme listeMonotone Algorithme listeMonotone Algorithme listeMonotone # cet algorithme permet de déterminer si une liste lue au clavier # est monotone (croissante ou décroissante au sens large) variables liste : liste d’entiers naturels n, i, nbEléments : entiers naturels trouvé, estCroissante, estMonotone : booléen début # initialisation liste liste [ ] # boucle de lecture des valeurs et de création de la liste Entrer ( n ) tantque ( n ≠ 0 ) # on rajoute l’entier n en fin de liste liste liste + [ n ] # on lit la valeur suivante Entrer ( n ) fin_tantque # croissante ou décroissante ? # initialisations trouvé faux estCroissante vrai i 0 nbEléments NombreEléments ( liste ) # parcours cherche deux éléments consécutifs distincts tantque ( ( i ≤ nbEléments – 2 ) et ( non trouvé ) ) faire si ( L [i] < L [i+1] ) alors trouvé vrai sinon si ( L [i] > L [i+1] ) alors estCroissante faux trouvé vrai sinon i i + 1 fin_si fin_si fin_tantque # initialisations parcours suivant listeMonotone vrai # parcours et test de la liste : est-elle monotone ? tantque ( ( i ≤ nbEléments – 2 ) et estMonotone ) faire si ( ( estCroissante et ( L [i] > L [i+1] ) ) ou ( ( non estCroissante ) et ( L [i] < L [i+1] ) ) ) alors estMonotone faux sinon i i + 1 fin_si fin_tantque # affichage résultat si ( estMonotone ) alors Afficher ( "La liste est monotone" ) si ( estCroissante ) alors Afficher ( "croissante." ) sinon Afficher ( "décroissante." ) fin_si sinon Afficher ( "La liste n’est pas monotone" ) fin_si fin Remarque. Notons que si tous les éléments de la liste sont égaux (ou si celle-ci contient 0 ou 1 élément), le booléen estCroissante est à vrai après le premier parcours ; le second parcours n’est pas effectué, et le message "La liste est monotone croissante." est affiché. Exercice 6. Tri par insertion Écrire un algorithme permettant de construire une liste triée par ordre croissant d’entiers naturels strictement positifs à partir d’une suite entrée au clavier et terminée par 0. Ainsi, chaque nouvel élément devra être inséré en bonne position dans la liste en cours de construction. Réponse. Chaque élément lu doit être inséré en bonne position dans la liste en cours de construction. Pour cela, il faut chercher le premier élément de la liste plus grand ou égal à l’élément à insérer. L’algorithme est le suivant : Algorithme triParInsertion Algorithme triParInsertion Algorithme triParInsertion Algorithme triParInsertion # cet algorithme permet de construire une liste triée par ordre croissant # à partir d’une suite entrée au clavier et terminée par 0, en utilisant # le principe du tri par insertion variables liste : liste d’entiers naturels n, i, nbEléments : entiers naturels trouvé : booléen début # initialisation uploads/Finance/ ensm-correction-feuille-td2.pdf