déplacement minimum d'un point à un autre avec des étapes incrémentielles
C'est la première fois que je pose une question ici. J'ai un curieux problème d'algorithme, au centre du plan cartésien (0,0) je dois aller à un autre point (x,y) -x et y appartiennent à des nombres Z - mais je ne peux utiliser que des étapes horizontales et verticales et ce pas augmente d'une unité, une unité est une distance de (0,0) à (0,1), (1,0), (-1,0) ou (0,-1).
Par exemple, je dois aller au point (1,1) et les étapes sont :
- Aller à (1,0), un pas de 1 unité.
- Passez en (1,-2) un pas de 2 unités.
- Enfin, passez en (1,1) un pas de 3 unités.
Et pour cet exemple, la réponse est j'ai besoin de 3 étapes avec 6 unités de distance.
Évidemment, il y a plusieurs façons d'aller à un point du centre mais le problème a besoin du minimum.
Existe-t-il une formule ou un algorithme pour trouver le nombre minimum de pas et la distance de ce chemin ?
Eh bien, si vous trouvez l'un d'entre eux (pas ou distance), l'autre est facile à trouver car la distance est une somme de N (nombre de pas) premiers nombres naturels.
Merci d'avoir lu ceci et pour vos réponses et suggestions.
Réponses
Question interessante. Il est surprenant que la réponse ne dépende que de$|x|+|y|$. Par exemple, le même nombre d'étapes est nécessaire pour atteindre$(1,1)$ou$(0,2)$.
Le pas minimum est le plus petit entier non négatif$n$tel que$n(n+1)/2-(|x|+|y|)$est pair et non négatif.
Voici un$O(1)$-time algorithme qui renvoie la valeur décrite ci-dessus, où least_n
, c'est-à-dire,$\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$, est le plus petit entier non négatif$n$tel que$n(n+1)/2-(|x|+|y|)\ge0$.
def minimum_steps(x,y):
distance_to_origin := absolute_value(x) + absolute_value(y)
least_n := ceiling((-1 + square_root(8 * distance_to_origin + 1)) / 2)
gap := n * (n + 1) / 2 - distance_to_origin
# 0 <= gap <= n - 1
if gap is even:
return least_n
else if n is even:
return least_n + 1
else:
return least_n + 2
Vu le nombre d'étapes$s$, la distance parcourue est$1+2+\cdots+s=s(s+1)/2$.
L'exactitude de la formule et de l'algorithme ci-dessus provient de la caractérisation suivante.
Proposition. Le nombre minimum d'étapes à partir de$(0,0)$à$(x,y)$est le plus petit entier non négatif$n$tel que$n(n+1)/2-(|x|+|y|)$est non négatif et pair.
Preuve . Si nous pouvons aller à$(x,y)$dans$n$étapes, la somme de certains nombres entre 1 et$n$ou leurs négations doivent être$x$et la somme des nombres restants ou leurs négations doit être$y$, c'est à dire,$$\pm1\pm2\pm\cdots\pm n = |x| + |y|$$pour un choix de tous$\pm$'s. Cela signifie,$$1+2+\cdots+ n - (|x| + |y|)$$est non négatif et pair.
Maintenant, il suffit de prouver que$(x,y)$est accessible dans$n$étapes si$n(n+1)/2-(|x|+|y|)$est non négatif et pair. Démontrons-le par induction sur$n$.
Les cas de base,$n=0$ou$1$moyens$(x,y)=(0,0), (0,1), (1,0)$. Ces cas sont immédiats à vérifier.
Supposons, comme hypothèse d'induction, qu'elle soit correcte pour les plus petits$n$'s. Considérons maintenant le cas de$n\ge2$avec$n(n+1)/2-(|x|+|y|)$non négatif et pair. Nous pouvons supposer$x$et$y$sont non négatifs ; sinon, par exemple, si$x$est négatif, nous pouvons changer$x$à sa valeur absolue et inverser le sens de tous les pas parallèles à$X$-axe.
Il y a trois cas.
- $x \ge n$. Laisser$x'= x-n$. Alors$$(n-1)n/2-(|x'|+|y|)=n(n+1)/2-(|x|+|y|)$$est non négatif et pair. Par hypothèse d'induction, on peut passer à$(x',y)$dans$n-1$pas. Atteindre$(x,y)$dans$n$étapes, nous continuons$n$unités dans la direction X.
- $y\ge n$. Ceci est symétrique au cas ci-dessus.
- $0\le x\lt n$et$0\le y\lt n$. Il y a deux sous-cas.
- $x\ge 2$et$y\ge 2$. Laisser$x'=(n-1)-x$et$y'=n-y$. Alors$|x'|\le n-3$et$|y'|\le n-2$.$$(n-2)(n-1)/2-(|x'|+|y'|)\ge(n-3)(n-4)/2\ge0.$$La parité de$(n-1)(n-1)/2-(|x'|+|y'|)$est le même que$n(n+1)/2-(|x|+|y|)$, c'est-à-dire pair. Par hypothèse d'induction, on peut passer à$(x',y')$dans$n-2$pas . En inversant toutes les étapes, on peut passer à$(-x', -y')$dans$n-2$étapes également. Atteindre$(x,y)$dans$n$étapes, nous pouvons continuer avec deux autres étapes,$n$unités dans la direction X et$n+1$unités dans la direction Y.
- Un des$x$et$y$est$0$ou$1$. Laisser$g(k)=k(k+1)/2-(|x|+|y|)$. Le plus petit entier non négatif tel que$g(k)\ge0$est$m=\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$. Puisque les deux$x$et$y$sommes$\lt n$et l'un d'eux est$0$ou$1$,$$m\le \frac{1+\sqrt{8n+1}}2.$$Lorsque$g(m)$est même,$n=m$par définition. Lorsque$g$est étrange, puisque soit$g(m+1)=g(m)+(m+1)$ou$g(m+2)=g(m)+(m+1)+(m+2)$doit être pair, soit$m+1$ou$m+2$doit être$n$. Alors, que ce soit$g(m)$est pair ou impair, on a$$n\le m+2.$$En combinant les deux inégalités ci-dessus, on a$$n\le \frac{5+\sqrt{8n+1}}2,$$ce qui implique$n\le 6$. Puisque la direction X et la direction Y sont symétriques, supposons$y=0,1$. Depuis$x\lt n$,$x\lt 6$. Il suffit donc de vérifier les cas où$(x,y)$ $\in $ $\{(0,0),(0,1),$ $(1,0),(1,1),$ $(2,0), (2,1),$ $(3,0), (3,1),$ $(4,0), (4,1),$ $(5,0), (5,1)\}.$Il est facile de vérifier chacun d'eux.
$\ \checkmark$