Discussion :

[atlantis123]

salut les amies
j'ai un exercie,
ecrire un algorithme qui calcul la distance entre n points est a la fin il compare ces distances et dire qu'elle la plus petite.
est ce que quelqu'un peut m'aider a résoudre ce probléme .
et merci d'avance.

[Mat.M]

Bonsoir c'est pas très compliqué.
1 la distance on peut la calculer avec le théorème de Pythagore
2 ensuite en ayant calculé la distance de chaque point il faut les mémoriser dans un tableau de n éléments.
3 puis avec une méthode de tri du tableau il suffit de ranger le tableau de la plus petite à la plus grande...

[ToTo13]

1 la distance on peut la calculer avec le théorème de Pythagore
2 ensuite en ayant calculé la distance de chaque point il faut les mémoriser dans un tableau de n éléments.
3 puis avec une méthode de tri du tableau il suffit de ranger le tableau de la plus petite à la plus grande...

Version 2
1 la distance on peut la calculer avec le théorème de Pythagore
2 tu stockes la plus petite au fur et à mesure dans une variable (min) qui tu (ça évite un tableau et un tri).

[Mat.M]

Bonjour après coup j'avais oublié de préciser qu'il faut faire une double imbriquée et tester pour chaque point
une version sophistiquée serait de prendre peut-être l'algorithme de Djykstra ?

[Vakhyw]

Si tu as juste besoin de trouver la distance la plus petite, tu calcules les n*n distances en gardant en mémoire la plus petite distance rencontrée. A la fin, tu retournes simplement cette distance. Cette algorithme ne peut pas être amélioré : tu es obligé de faire au minimum ces n*n (en fait n*(n-1)) itérations.

[prgasp77]

Si il est possible d'améliorer le schmilblick : il n'est pas nécessaire de calculer toutes les distances, leur carré suffit
On retournera la racine carrée du plus petit carré de distance

[Vakhyw]

Oui mais la complexité reste la même Ce que je veux dire c'est que n*n est la complexité minimale.

[Acrim]

Si on part du principe que les distances sont symétriques il n'y a alors que n*(n-1)/2 distances à calculer.

Est il possible de faire mieux ? Je pense que oui (vous me direz ce que ça vaut).

Etape-1 : Choisir un point A (parmi les n points)
Etape-2 : Calculer la distance entre A et les (n-1) autres points
Etape-3 : Trier les points par distance croissante (par rapport à A) dans un tableau allant de 0 à n-1 (le point A étant dans la première case).
Etape-4 : Pour chaque points i, calculer distance(i,j) avec j>i et j<n (en retenant la minDist au fur à mesure).

Bon jusqu'à là on a rien amélioré, sauf si on rajoute la condition d’arrêt:
j<n et distance(A,j)-distance(A,i)< minDist (distance(A,j)-distance(A,i) étant une borne min de la distance séparant i et j).

Ça ne réduit pas la complexité dans le pire des cas. Mais en moyenne on doit quand même éviter quelques calculs.

[Acrim]

http://en.wikipedia.org/wiki/Closest...points_problem

[Vakhyw]

Effectivement il existe des algos sympas en O(n*log n).

Je trouve ce PDF bien expliqué : http://people.cis.ksu.edu/~subbu/Pap...est%20pair.pdf

Et une implémentation Java + explications ici : http://www.baptiste-wicht.com/2010/0...eep-algorithm/

[FR119492]

Salut!

Oui mais la complexité reste la même

La complexité est une notion chère aux spécialistes de l'algorithmique théorique. Mais pour ceux qui font du calcul numérique concret, ça ne correspond souvent pas à grand chose.
Jean-Marc Blanc

[Vakhyw]

Oui enfin sur un forum d'algorithmique, il me semble que la notion de complexité en temps / espace a droit de cité.

Sinon qu'entends-tu quand tu dis que ça ne correspond souvent pas à grand chose ?

[prgasp77]

Prenons un algorithme quelconque. Divisons (quelque soit la taille du problème) le nombre d'instructions nécessaire par 1000 pour obtenir un nouvel algorithme. Et bien ces deux algos auront la même complexité.

Considérer la complexité dans le pire des cas est une chose, considérer celle dans le cas moyen et bencher le programme résultant en est une autre. Les deux sont nécessaires, et cracher sur l'un tout en vénérant l'autre c'est un peu comme tenir le Théâtre en sainte estime et laisser Molière être enterré dans la fosse commune.

J'espère que l'analogie vous fera sourire

[Vakhyw]

Heu oui d'accord. Bien sûr il s'agit de description asymptotique, mais elles donnent aussi une idée claire de l'évolution du temps d'exécution en fonction de la taille de l'entrée.

Sauf pour des entrées à taille quasiment fixe, je vois pas trop comment discuter d'une telle notation surtout que pour des tailles faibles, le temps humain consommé est généralement négligeable ...

[FR119492]

Salut!

Sinon qu'entends-tu quand tu dis que ça ne correspond souvent pas à grand chose ?

mais elles donnent aussi une idée claire de l'évolution du temps d'exécution en fonction de la taille de l'entrée.

Il y a quelques années, j'ai fait un petit test; j'ai mesuré le temps d'exécution pour la résolution de systèmes linéaires de taille 128, 256, 512, 1024, 2048, etc. En principe, le graphe des valeurs obtenues aurait dû être celui d'un polynôme du 3ème degré; en fait, la courbe présentait une discontinuité qui s'expliquait par le fait qu'au delà d'une certaine taille, Windows stockait des morceaux de la matrice sur le disque dur (sans avertir l'utilisateur) et que les transferts prenaient beaucoup de temps.
La théorie, c'est très beau, mais la réalité est dans la pratique.
Jean-Marc Blanc