loupi a écrit :Essaie d'obtenir un énoncé plus clair même sans aucune indication d'aide, si tu veux arriver à faire quelque chose...
Là, je l'ai encore relu ce matin, c'est imbitable, on ne comprend ni l'objectif, ni le rapport avec les indications données.
L'énoncé n'est en effet pas très pédagogique et on comprend qu'il puisse poser problème. Voici mon interprétation des objectifs de cette séquence d'exercices avec un énoncé qui me semble plus clair et plus progressif :
On cherche dans cet exercice à savoir si une liste est injective. Une liste est injective si elle ne contient pas deux fois ou plus le même élément, autrement dit elle ne contient aucun doublon.
Partie A
Une première idée est de comparer les éléments de la liste deux à deux. Si l'on en trouve deux égaux, la liste contient un doublon et l'on peut arrêter la recherche. On pourra par exemple comparer le premier élément avec tous les suivants, puis le deuxième avec tous les suivants et ainsi de suite.
Question 1) Que donne cette idée sur la liste [1, 2, 3, 2, 4] ?
Question 2) Écrire le pseudo-code de cet algorithme et le vérifier sur la liste précédente
Question 3) Écrire en Python une fonction
est_injective(liste) qui renvoie
True si la liste est injective et
False sinon.
Question 4) Combien de comparaisons entre deux éléments sont effectuées par votre programme sur la liste [1, 2, 3, 2, 4] ? Dans le pire des cas, combien de comparaisons peuvent être effectuées sur une liste de taille
n et donner une telle liste ? Quelle est donc la complexité de cette méthode ?
Partie B
La complexité de la méthode précédente n'est pas satisfaisante. On va donner ici une solution de complexité linéaire en la taille de la liste. L'idée est de se souvenir des éléments de la liste que l'on a déjà rencontrés auparavant. On peut par exemple créer un tableau
deja_vu dont la case
i vaut
True si l'on a déjà rencontré un élément de valeur
i et
False sinon. Lorsque l'on découvre un nouvel élément de valeur
i deux cas peuvent se présenter : (a)
deja_vu est vrai, dans ce cas on peut arrêter la recherche et la liste n'est pas injective; (b) deja_vu n'est pas vrai, dans ce cas on met deja_vu à jour et on continu.
Question 1) Quelle doit être la taille du tableau deja_vu?
Question 2) Écrire en Python une fonction maximum(liste) qui renvoie le maximum d'une liste et la tester.
Question 3) Écrire en Python une fonction initialise(taille, valeur) qui créée un tableau (une liste en Python) de taille taille avec tous les éléments initialisés à valeur.
Question 4) Écrire le pseudo-code d'un algorithme mettant en place l'idée exposée dans cette partie. Le vérifier sur les listes [1, 2, 3, 2, 4] et [1, 2, 3, 5, 4].
Question 5) Écrire en Python une fonction est_injective_rapide(liste) qui implémente ce pseudo-code.
Question 6) Quelle est la complexité de cette méthode (rem: ne pas oublier la complexité des fonctions maximum et initialise) ?