Bonjour a tous,
je voudrais éclaircir un peu le problème (qui me plait bien)
Le problème ici est : "Ne pas avoir de doublons dans les
nombres pris au hazard" (je ne parle pas des cas
particuliers qui offriraient des solutions certainements
éllégantes voire simples)
Pour çà deux solutions :
Soit on cherche à chaque itération si le nombre pris est un
doublon. => on reporte le problème sur "Trouvé un
élément dans un ensemble".
Soit on cherche à retirer les éléments déjà pris et le
problème devient "Trouvé une structure d'informations
permettant de sélectionné uniquement les éléments
restants".
je suis assez content de partager la même réponse que
vous sur la complexité en O(N) (ou O(random(N)) = 0(1))
avec équiprobabilité garantit
Je peux vous dire qu'il existe mieux pour ce qui est de la
complexité temporelle, je crois dire sans me tromper en
O(random(N)) uniquement.
Pensez-vous trouver l'idée ?
Elle n'est pas trés compliquée et demande de connaître
une technique algorithmique.
Je ne vous donnerez pas la solution, car ce qui est
intéressant n'est pas d'avoir la solution d'un problème mais
comprendre comment on y est arrivé. (Généralement en ce
posant de bonnes questions, ce qui reste évident à dire
malheureusement pour nous !)
Il nous resterait à améliorer la fonction random(N) pour
être certain qu'elle soit en O(1)
Partager