Trier une liste

Rousseau-Wallon shared this question 3 years ago
Answered

Bonjour,

J'ai une liste de points du plan L = {P1, P2, ... , Pn}.

Elle a la propriété de posséder une permutation L' telle que la distance entre un point de L' et son suivant soit toujours la même (une longueur D connue d'avance).

Il faut trouver L'.

Je voulais prendre comme premier élément A pour L' celui de L dont l'abscisse est la plus petite et ensuite chercher celui (il y en a toujours un et un seul) qui soit distant de A de D. Mais je me suis rendu compte que le premier élément de L' n'est pas forcément celui de L dont l'abscisse est la plus petite. Du coup je suis bloqué.

Comments (4)

photo
1

oui, Koch en stock

en fait je me suis trompé : chaque point (sauf deux) possède deux voisins distants de D. Les deux restants (les extrémités de la chaîne) n'en possède qu'un seul.

photo
1

3 points ? ouch oui !

mais il n'y a a qu'une seule ligne brisée formée de segments de même longueur qui passe par tous ces points

photo
1

non je n'ai pas la ligne brisée,

j'ai juste la liste des points par lesquels elle doit passer,

et cette liste me parvient dans le mauvais ordre

photo
1

pour moi c'est un marathon..

vous pouvez expliquer votre méthode svp

PS : ma liste ne contient pas 5 points, mais bien davantage. C'est donc une "ligne de koch" (non, pas une ligne de coke!) qui les relie, et pas seulement le motif de base.

© 2022 International GeoGebra Institute