증분 단계로 지점 간 최소 이동
여기에서 질문을 한 것은 처음입니다. 알고리즘에 대해 궁금한 문제가 있습니다. 데카르트 평면 (0,0)의 중심에서 다른 지점으로 이동해야합니다 (x, y) -x 및 y는 Z 번호에 속하지만 수평 및 수직 단계 만 사용할 수 있습니다. 이 단계는 한 단위 씩 증가하고 단위는 (0,0)에서 (0,1), (1,0), (-1,0) 또는 (0, -1)까지의 거리입니다.
예를 들어 (1,1) 지점으로 이동해야하며 단계는 다음과 같습니다.
- 1 단위 단계 인 (1,0)으로 이동합니다.
- 2 단위 씩 (1, -2) 단계로 이동합니다.
- 마지막으로 (1,1) 3 단위 단계로 이동합니다.
이 예에서 답은 6 단위의 거리에 3 단계가 필요하다는 것입니다.
분명히 중심에서 한 지점으로 이동하는 방법에는 여러 가지가 있지만 문제는 최소한으로 필요합니다.
최소 걸음 수와이 방법의 거리를 찾는 공식이나 알고리즘이 있습니까?
음, 그중 하나 (걸음 또는 거리)를 찾으면 거리가 N (걸음 수) 첫 번째 자연수의 합이기 때문에 다른 하나를 쉽게 찾을 수 있습니다.
이것을 읽고 귀하의 답변과 제안에 감사드립니다.
답변
흥미로운 질문입니다. 대답이$|x|+|y|$. 예를 들어, 도달하려면 동일한 수의 단계가 필요합니다.$(1,1)$ 또는 $(0,2)$.
최소 단계는 음이 아닌 최소 정수입니다. $n$ 그런 $n(n+1)/2-(|x|+|y|)$ 짝수이고 음이 아닙니다.
여기에 $O(1)$위에서 설명한 값을 반환하는 -time 알고리즘입니다. 여기서 least_n, 즉,$\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$는 음이 아닌 최소 정수입니다. $n$ 그런 $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
단계 수를 감안할 때 $s$, 이동 거리는 $1+2+\cdots+s=s(s+1)/2$.
위의 공식과 알고리즘의 정확성은 다음 특성에서 비롯됩니다.
제안. 최소 단계 수$(0,0)$ ...에 $(x,y)$ 음이 아닌 최소 정수입니다. $n$ 그런 $n(n+1)/2-(|x|+|y|)$ 음이 아니고 짝수입니다.
증거 . 우리가 갈 수 있다면$(x,y)$ 에 $n$ 단계, 1과 1 사이의 일부 숫자의 합 $n$ 또는 그들의 부정은 $x$ 나머지 숫자 또는 그 부정의 합은 $y$즉, $$\pm1\pm2\pm\cdots\pm n = |x| + |y|$$ 모두의 선택을 위해 $\pm$'에스. 그 의미는,$$1+2+\cdots+ n - (|x| + |y|)$$ 음이 아니고 짝수입니다.
이제 증명하는 것으로 충분합니다. $(x,y)$ 도달 가능 $n$ 경우 단계 $n(n+1)/2-(|x|+|y|)$음이 아니고 짝수입니다. 귀납법으로 증명하자$n$.
기본 케이스, $n=0$ 또는 $1$ 방법 $(x,y)=(0,0), (0,1), (1,0)$. 이러한 경우는 즉시 확인됩니다.
귀납 가설로 더 작은 경우에 옳다고 가정하십시오. $n$'에스. 이제 경우를 고려하십시오$n\ge2$ 와 $n(n+1)/2-(|x|+|y|)$음수가 아니고 심지어. 우리는 가정 할 수 있습니다$x$ 과 $y$음수가 아닙니다. 그렇지 않으면 예를 들어$x$ 부정적입니다, 우리는 바꿀 수 있습니다 $x$ 절대 값으로 바꾸고 평행 한 모든 단계의 방향을 반대로합니다. $X$-중심선.
세 가지 경우가 있습니다.
- $x \ge n$. 허락하다$x'= x-n$. 그때$$(n-1)n/2-(|x'|+|y|)=n(n+1)/2-(|x|+|y|)$$음이 아니고 짝수입니다. 귀납 가설에 의해 우리는$(x',y)$ 에 $n-1$단계. 닿다$(x,y)$ 에 $n$ 단계, 우리는 계속 $n$ X 방향의 단위.
- $y\ge n$. 이것은 위의 경우와 대칭입니다.
- $0\le x\lt n$ 과 $0\le y\lt n$. 두 개의 하위 사례가 있습니다.
- $x\ge 2$ 과 $y\ge 2$. 허락하다$x'=(n-1)-x$ 과 $y'=n-y$. 그때$|x'|\le n-3$ 과 $|y'|\le n-2$. $$(n-2)(n-1)/2-(|x'|+|y'|)\ge(n-3)(n-4)/2\ge0.$$ 패리티 $(n-1)(n-1)/2-(|x'|+|y'|)$ 와 같다 $n(n+1)/2-(|x|+|y|)$, 즉, 심지어. 귀납 가설에 의해 우리는$(x',y')$ 에 $n-2$단계. 모든 단계를 반대로하면$(-x', -y')$ 에 $n-2$단계도 있습니다. 닿다$(x,y)$ 에 $n$ 두 단계를 더 계속할 수 있습니다. $n$ X 방향 단위 및 $n+1$ Y 방향 단위.
- 다음 중 하나 $x$ 과 $y$ 이다 $0$ 또는 $1$. 허락하다$g(k)=k(k+1)/2-(|x|+|y|)$. 음이 아닌 가장 작은 정수$g(k)\ge0$ 이다 $m=\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$. 둘 다 이후$x$ 과 $y$ 아르 $\lt n$ 그리고 그들 중 하나는 $0$ 또는 $1$, $$m\le \frac{1+\sqrt{8n+1}}2.$$ 언제 $g(m)$ 짝수이다, $n=m$정의에 따라. 언제$g$ 둘 중 하나이기 때문에 이상합니다 $g(m+1)=g(m)+(m+1)$ 또는 $g(m+2)=g(m)+(m+1)+(m+2)$ 짝수 여야합니다. $m+1$ 또는 $m+2$ 반드시 $n$. 그래서$g(m)$ 짝수 또는 홀수, 우리는 $$n\le m+2.$$ 위의 두 부등식을 결합하면 $$n\le \frac{5+\sqrt{8n+1}}2,$$ 의미하는 $n\le 6$. X 방향과 Y 방향은 대칭이므로$y=0,1$. 이후$x\lt n$, $x\lt 6$. 따라서 다음과 같은 경우를 확인하는 것으로 충분합니다.$(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)\}.$ 각각을 확인하는 것은 쉽습니다.
$\ \checkmark$