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