Discussion :

[beegees]

Bonjour tout le monde,

J'ai un exercice à faire (en C) mais je ne suis pas bien sûr de l'avoir compris (les formules sont très simples, à ce niveau là, il n'y a pas de problème mais c'est plutôt l'énoncé que je ne suis pas sûr davoir comppris :

Le programme doit permettre à l’utilisateur de trouver, dans le plan, le point d’une série prédéterminée (voir plan.txt) le plus proche d’un point de référence encodé par l’utilisateur.
Pour rappel, un point dans le plan est défini par deux coordonnées (x est la coordonnée
horizontale, et y est la coordonnée verticale).
Le fichier (plan.txt) contient la série de points dans laquelle s’effectuera les recherches ; il est structuré comme suit :
<coordonnée x du premier point> \t <coordonnée y du premier point>
<coordonnée x du second point> \t <coordonnée y du second point>
<coordonnée x du troisième point> \t <coordonnée y du troisième point>
…
<coordonnée x du dernier point> \t <coordonnée y du dernier point>
La formule permettant de calculer la distance entre deux points (x1,y1) et (x2,y2) est la suivante : distance = sqrt( dx² + dy² )
où dx = x2 – x1 et dy = y2 – y1
En bref, le programme doit :
* charger les données du fichier plan.txt en mémoire
* tant que l’utilisateur désire effectuer une recherche :
* permettre à l’utilisateur d’encoder les coordonnées d’un point de référence
(xref,yref)
* rechercher le point le plus proche du point de référence parmi les points chargés
à partir du fichier texte ; c’est à dire celui pour lequel la distance entre lui et le
le point de référence est minimal :
distance « entre (x,y) et (xref,yref) » = sqrt( (x-xref)² + (y-yref)² )
* afficher les coordonnées et l’indice du point de la série qui est le plus proche
du point de référence et distance

Voici mes questions :

J'ai encodé 3 positions dans un fichier txt, donc 6 points (3x et 3y).

Voici mon fichier txt :

2.3 4.5
3.6 9.7
8.5 4.7

Dois-je d'abord calculer la distance entre ces 3 points avec distance = sqrt( dx² + dy² ) ?

Ce que j'ai fais, c'est laisser le visiteur entrer deux points, j'ai ensuite calculer la distance entre ces deux points et chaque points de mon txt avec sqrt( (x-xref)² + (y-yref)² ).

Mais je me demande si il ne faut pas d'abord calculer la distance entre les points de mon txt ?

Si tel est le cas, je dois utiliser les distances obtenues avec sqrt( dx² + dy² ) pour le second calcul ? (sqrt( (x-xref)² + (y-yref)² ))

C'est un exercice intéressant pour la manipulation des fichiers et des tableaux.

Merci d'avance pour votre aide.

beegees

[souviron34]

euh... tu sais pas lire ???

En bref, le programme doit :
* charger les données du fichier plan.txt en mémoire
* tant que l’utilisateur désire effectuer une recherche :
* permettre à l’utilisateur d’encoder les coordonnées d’un point de référence
(xref,yref)
* rechercher le point le plus proche du point de référence parmi les points chargés
à partir du fichier texte ; c’est à dire celui pour lequel la distance entre lui et le
le point de référence est minimal :
distance « entre (x,y) et (xref,yref) » = sqrt( (x-xref)² + (y-yref)² )

[paradize3]

Bonjour,

A prioris ce que tu dois faire c'est uniquement calculer la distance entre le point entre par l'utilisateur et tous les autres points du fichier, et trouver le minimum (petite optimisation, pas besoin d'utiliser les couteuses racines carrees).

Maintenant si tu as N points dans le fichiers, et M requetes, la complexite sera en O(M*N), peut-on faire mieux (en terme de complexite)? La reponse est oui, et c'est du reste un sujet qui a ete/est passablement etudie, en particulier les algorithmes plus performants mettent au profit l'inegalite du triangle (et la je ne saurais que t'inviter a consulter google, avec nearest neigbor algorithm comme mot cle par exemple).

Bonne chance et meilleures salutations,

Gregoire