Distance minimum entre 2 occurrences

thepigou · June 2018

Bonjour à tous,
Je suis un élève de terminale S voulant s'entrainer pour la demi-final du concours Algoréa.
Ainsi lors de ma préparation, je bloque sur un exercice :
Le but de cet exercice est de trouver la distance minimale entre 2 apparitions d'un même nombre dans une liste de nombre en codant un programme informatique. (vous pouvez trouver l'intégralité de l'énoncé dans les pièces jointes).
J'ai essayé plusieurs idées comme comptabiliser chaque nombre de la suite et de l'associer à son rang mais mon programme possède une limite de temps pour être exécuté et une limite d'espace.

Ainsi si vous avez des pistes de recherches ou des idées n'hésitez pas.
Merci d'avance pour vos réponses. 76722

fm_31 · June 2018

Bonjour ,

je retiendrais la stratégie suivante :

pour chaque nombre de la liste , ne traiter que la distance qui le sépare du premier nombre identique suivant trouvé .

Cordialement

fm_31 · June 2018

De plus dans la recherche du premier nombre identique , on peut s'arrêter dès qu'on dépasse un minimum déjà obtenu .
Ainsi on parcours la liste entière une fois et 40000 autres fois mais partiellement .

GaBuZoMeu · June 2018

Ça fait dans le pire des cas quelque chose comme $n(n-1)/2$ comparaisons, il me semble. ($n$ = longueur de la liste).
En commençant avec un tri de la liste (gardant l'information du rang), on peut faire en $n\log(n)$.

pascalortiz · June 2018

Plusieurs façons. Soit L la liste des entiers.

1) Brute force (quadratique) : tu passes en revue chaque élément z de L et à chaque étape tu regardes les éléments de L qui suivent à la recherche d'un élément identique à z (en fait le premier venu suffit) et tu mémorises l'écart en mettant à jour dès qu'un écart plus petit est rencontré. Sans doute que tu ne passeras pas les tests de performance avec cet algo.

2) Méthode GaBuZoMeu. Tu tries en une liste M la liste des (L[k], k) (tri lexicographique) et tu parcours M à la recherche des doublons de L (ils sont voisins dans M) puis tu cherches l'écart minimal entre un indice et son suivant par examen des doublons.

3) Ils donnent des entiers entre 0 et 40000 (pas très grand), ce n'est peut-être pas pour rien. Tu construis une liste D=[ None]*40001 (en Python pour fixer les idées) et tu parcours L. A chaque étape z=L[k], tu places l'indice k de l'élément z dans D[z] s'il y a None et sinon tu mesures l'écart de ce qui s'y trouve et de k, tout en maintenant à jour un minimum des écarts. Je pense que ce sera en pratique la méthode la plus rapide. Si les entrées n'étaient pas des entiers entre 0 et 40000, par exemple des entiers sur une plage beaucoup plus large, tu aurais utilisé une table de hachage ou assimilé (dictionnaire en Python, map en C++).

Je sais que les descriptions ci-dessus peuvent paraître laconiques, donc n'hésite pas à y revenir si ce n'est pas clair.

EDIT. L'exo est accessible ICI mais il faut d'abord valider l'exercice précédent.
Sinon, je confirme que le premier algo ne passe que les 6 premiers tests. Les deux autres passent les 14 tests mais l'interface n'indique pas les temps réalisés.
Le 2e algo est le plus simple à coder, trois lignes de Python.

EDIT2
Finalement, après un nouvel essai (et avoir créé un compte sur le site) j'ai pu voir les temps pour les 14 tests : l'algo 3 est environ trois plus rapide que le 2.

sebsheep · June 2018

Merci Pascal pour ces tests. La différence de timing que tu donnes est en Python ou en C ?

pascalortiz · June 2018

C'était en Python.

Distance minimum entre 2 occurrences

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 5