Remerciez-le!

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

Td note 2006 correction TD noté L ? exercice devra être imprimé à la ?n du TD et rendu au chargé de TD Il ne faut pas oublier de mentionner son nom en commentaires au début du programme L ? objectif de cet exercice est de programmer une recherche dans une

TD noté L ? exercice devra être imprimé à la ?n du TD et rendu au chargé de TD Il ne faut pas oublier de mentionner son nom en commentaires au début du programme L ? objectif de cet exercice est de programmer une recherche dans une liste triée Il faut d ? abord récupérer un ?chier texte disponible sur Intranet Ce ?chier contient un mot par ligne Il faut lire ce ?chier et construire une liste avec tous ces mots points Construire une fonction qui véri ?e que la liste chargée à la question précédente est triée points Construire une fonction qui recherche un mot X dans la liste et qui retourne sa position ou - si ce mot n ? y est pas Cette fonction prend deux paramètres la liste et le mot à chercher Elle retourne un entier On précise que pour savoir si deux cha? nes de caractères sont égales il faut utiliser l ? opérateur points Quels sont les positions des mots UN et DEUX La réponse doit ?gurer en commentaire dans le programme Il faudra écrire aussi le nombre de comparaisons e ?ectuées pour trouver ces deux positions points Lorsqu ? une liste est triée rechercher un élément est beaucoup plus rapide Si on cherche le mot X dans la liste il su ?t de le comparer au mot du milieu pour savoir si ce mot est situé dans la partie basse X inférieur au mot du milieu la partie haute X supérieur au mot du milieu S ? il est égal le mot a été trouvé Si le mot n ? a pas été trouvé on recommence avec la sous-liste inférieure ou supérieure selon les cas jusqu ? à ce qu ? on ait trouvé le mot ou qu ? on soit sûr que le mot cherché n ? y est pas Le résultat de la recherche est la position du mot dans la liste ou - si ce mot n ? a pas été trouvé Cette recherche s ? appelle une recherche dichotomique Ecrire la fonction qui e ?ectue la recherche dichotomique d ? un mot dans une liste triée de mots Véri ?ez que les deux fonctions retournent bien les mêmes résultats Cette fonction peut être récursive ou non Elle prend au moins les deux mêmes paramètres que ceux de la question si elle en a d ? autres il faudra leur donner une valeur par défaut On précise que les comparaisons entre cha? nes de caractères utilisent aussi les opérateurs points Normalement les positions des mots UN et DEUX n ? ont pas changé mais il faut de nouveau déterminer le nombre d ? itérations e ?ectuées pour trouver ces deux positions avec la recherche dichotomique points Quel est au pire le coût d ? une recherche non dichotomique La réponse doit ?gurer en commentaire dans le programme point Quel est au pire le coût d ? une recherche dichotomique La réponse doit ?gurer en commentaire dans le programme point