Comment calculer la distance entre 2 points dans une matrice 2D
Je suis nouveau sur ce site, et de nouveau à C. j'ai besoin d'un programme pour trouver la moyenne des "sauts" il faut partir de tous les points.
L'idée est la suivante: Trouver un "saut" distance de 1 à 2, 1 à 3, 1 à 4 ... 1 à 9, ou de 2 à 1, 2 à 3, 2 à 4 de 2 à 5 etc.
De les faire sur la première ligne est simple, il suffit de (2-1) ou (3-1) et vous obtenez le nombre correct. Mais si je veux trouver la distance entre 1 et 4 ou 1 à 8 puis je n'ai absolument aucune idée.
Les dimensions de la matrice peuvent éventuellement être variable. Mais je veux juste aider avec une matrice de 3x3.
Quelqu'un pourrait me montrer comment le trouver?
Sauter signifie la verticale ou à l'horizontale se déplacer d'un point à un autre. de 1 à 2 = 1, de 1 à 9 = 4 (plus court chemin)
- Le théorème de pythagore:
dist = sqrt((x2 - x1) ^ 2 + (y2 - y1) ^ 2)
- Que diable faites-vous avec toutes ces modifications? Si vous écrivez un illisible, mauvaise question, au moins respecter le travail des autres qui ont pris la peine de fixation pour vous!
- Que voulez-vous faire avec le "saut" de la distance?
- désolé pour les modifications, je suis nouveau ici. Toujours à essayer de comprendre le site @H2CO3
Vous devez vous connecter pour publier un commentaire.
Quelle est la définition de "sauter distance" ?
Si vous dire combien de sauts qu'un homme a besoin d'aller de la place de M à N, si il ne peut sauts à la verticale et à l'horizontale, une seule possibilité:
Par exemple sauter-distance entre 1 et 9:
|3-1|+|3-1| = 4
La définition de "distance" sur ce genre de problèmes est toujours délicat.
Imaginer que les points sont les marques sur un champ, et l'on peut marcher partout. Ensuite, vous pouvez prendre n'importe quel chemin d'un point à l'autre. L'itinéraire le plus court serait alors une ligne droite; sa longueur serait la longueur du vecteur qui joint les points, qui se trouve être le vecteur de la différence entre les deux points les positions. Cette durée peut être calculée à l'aide de Pythagore le théorème de:
dist = sqrt((x2-x1)^2 + (y2-y1)^2)
. Ceci est connu comme la distance Euclidienne entre les points.Maintenant, imaginez que vous êtes dans une ville, et chaque point est un bâtiment. Vous ne pouvez pas marcher plus d'un bâtiment, de sorte que les seules options sont à aller vers le haut/bas ou gauche/droite. Ensuite, la distance la plus courte est donnée par la somme des composantes du vecteur de la différence; ce qui est mathématique, manière de dire que "descendre à 2 pâtés de maisons, puis un bloc vers la gauche", c'est marcher 3 blocs de distance:
dist = abs(x2-x1) + abs(y2-y1)
. Ceci est connu comme la distance de Manhattan entre les points.Dans votre problème, cependant, il semble que le seul mouvement possible est de sauter à côté d'un point, en une seule étape, les diagonales permis. Ensuite, le problème devient un peu plus délicat, car le chemin est très irrégulière. Vous avez besoin d'une Théorie des graphes ici, très utile lors de la modélisation de problèmes avec des éléments liés, ou "nœuds". Chaque point serait un nœud connecté à ses voisins, et le problème serait de trouver le plus court chemin d'accès à un autre point donné. Si les sauts avaient un poids différent (par exemple, est de sauter en diagonale a été plus difficile), un moyen facile de résoudre ce problème est serait avec l'Algorithme de Dijkstra; plus de détails sur la mise en œuvre au Wikipédia.
Si le coût est toujours le même, alors le problème est réduit à compter le nombre de sauts en Largeur d'Abord la Recherche du point de destination à partir de la source.
Il faut définir le "saut " distance": "le nombre de sauts nécessaires pour atteindre le Point A [Ax,a] à un Point B [Bx,Ba]."
Maintenant, il peut y avoir deux façons de le houblon sont autorisés :
Horizontalement/Verticalement
Dans ce cas, vous pouvez aller vers le haut/bas ou gauche/droite. Comme vous devez vous déplacer les axes X et Y indépendamment, votre sna est:
jumpDistance = abs(Bx - Ax) + abs(By - Ay);
Horizontalement/Verticalement et aussi en Diagonale
Dans ce cas, vous pouvez aller vers le haut/bas ou gauche/droite et en diagonale aussi bien. En quoi elle diffère de
Case 1
est que maintenant, vous avez la capacité de changer les axes X et Y ensemble, au prix d'un seul saut . Votre réponse est:jumpDistance = Max(abs(Bx - Ax),abs(By - Ay));