Différentes distances⚓︎
Il existe en mathématiques et en informatique de nombreuses façons de calculer la distance entre deux points.
On étudie ici les trois distances suivantes :
C'est la distance parcourue « en suivant les rues » dans le quartier de Manhattan. Elle vaut \(12\) dans la figure ci-dessous, quel que soit le chemin suivi :
On la définit comme la somme des « écarts » entre chaque paires de coordonnées des points :
\(\mathrm{manhattan}(x_A, y_A, x_B, y_B) = \lvert x_B - x_A \rvert + \lvert y_B - y_A \rvert\)
Aide
Avec Python, on calcule la valeur absolue de \(a\) en faisant abs(a).
C'est la distance classique du cours de mathématiques (dans le cas où les axes sont perpendiculaires et de même échelle).
On la calcule à l'aide du théorème de Pythagore :
\(\mathrm{euclidienne}(x_A, y_A, x_B, y_B) = \sqrt{(x_B - x_A)^2+(y_B - y_A)^2}\)
Afin de simplifier les calculs, on utilisera ici le carré de la distance euclidienne :
\(\mathrm{euclidienne\_carrée}(x_A, y_A, x_B, y_B) = (x_B - x_A)^2+(y_B - y_A)^2\)
Aide
Avec Python, on calcule le carré de \(a\) en faisant a**2.
Aux échecs, le roi peut se déplacer d'une case à la fois dans toutes les directions.
Combien de coups lui faut-il pour atteindre une case donnée ? La réponse est donnée par la distance de Tchebytchev.
Sur la figure ci-dessous, les cases marquées sont toutes accessibles en \(2\) coups.
Cette distance est égale à l'« écart » maximal entre les coordonnées de chaque point :
\(\mathrm{tchebytchev}(x_A, y_A, x_B, y_B) = \max (\lvert x_B - x_A \rvert , \lvert y_B - y_A \rvert)\)
Aide
Avec Python, on calcule le maximum de deux nombres a et b en faisant max(a, b).
Exemples
En prenant \(A(2\,;\,-5)\) et \(B(-3\,;\,1)\) :
>>> xA, yA = 2, -5
>>> xB, yB = -3, 1
>>> manhattan(xA, yA, xB, yB)
11
>>> euclidienne_carre(xA, yA, xB, yB)
61
>>> tchebychev(xA, yA, xB, yB)
6
En prenant \(A(2\,;\,2)\) et \(B(2\,;\,2)\) :
>>> xA, yA = 2, 2
>>> xB, yB = 2, 2
>>> manhattan(xA, yA, xB, yB)
0
>>> euclidienne_carre(xA, yA, xB, yB)
0
>>> tchebychev(xA, yA, xB, yB)
0
Compléter les fonctions ci-dessous :
def manhattan(..., ..., ..., ...):bksl-nl return ...bksl-nlbksl-nlbksl-nldef euclidiennepy-undcarre(..., ..., ..., ...):bksl-nl ...bksl-nlbksl-nlbksl-nldef ...:bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlxA, yA = 2, -5bksl-nlxB, yB = -3, 1bksl-nlassert manhattan(xA, yA, xB, yB) == 11bksl-nlassert euclidiennepy-undcarre(xA, yA, xB, yB) == 61bksl-nlassert tchebychev(xA, yA, xB, yB) == 6bksl-nlbksl-nlxA, yA = 2, 2bksl-nlxB, yB = 2, 2bksl-nlassert manhattan(xA, yA, xB, yB) == 0bksl-nlassert euclidiennepy-undcarre(xA, yA, xB, yB) == 0bksl-nlassert tchebychev(xA, yA, xB, yB) == 0bksl-nlbksl-nldef manhattan(xA, yA, xB, yB):bksl-nl return abs(xB - xA) + abs(yB - yA)bksl-nlbksl-nlbksl-nldef euclidiennepy-undcarre(xA, yA, xB, yB):bksl-nl return (xB - xA) py-strpy-str 2 + (yB - yA) py-strpy-str 2bksl-nlbksl-nlbksl-nldef tchebychev(xA, yA, xB, yB):bksl-nl return max(abs(xB - xA), abs(yB - yA))bksl-nlbksl-nlbksl-nl# Testsbksl-nlxA, yA = 2, -5bksl-nlxB, yB = -3, 1bksl-nlassert manhattan(xA, yA, xB, yB) == 11bksl-nlassert euclidiennepy-undcarre(xA, yA, xB, yB) == 61bksl-nlassert tchebychev(xA, yA, xB, yB) == 6bksl-nlbksl-nlxA, yA = 2, 2bksl-nlxB, yB = 2, 2bksl-nlassert manhattan(xA, yA, xB, yB) == 0bksl-nlassert euclidiennepy-undcarre(xA, yA, xB, yB) == 0bksl-nlassert tchebychev(xA, yA, xB, yB) == 0bksl-nlbksl-nl
A
Z