perjalanan minimum dari satu titik ke titik lain dengan langkah bertahap
Ini pertama kalinya saya membuat pertanyaan di sini. Saya punya masalah penasaran tentang algoritme, di tengah bidang Cartesian (0,0) saya perlu pindah ke titik lain (x, y) -x dan y adalah milik bilangan Z - tetapi saya hanya dapat menggunakan langkah horizontal dan vertikal dan langkah-langkah ini bertambah satu per satu unit, satu unit adalah jarak dari (0,0) ke (0,1), (1,0), (-1,0) atau (0, -1).
Misalnya, saya perlu menuju ke (1,1) poin dan langkah-langkahnya adalah:
- Pergi ke (1,0), langkah 1 unit.
- Lanjutkan ke (1, -2) langkah dari 2 unit.
- Terakhir, lanjutkan ke (1,1) langkah dari 3 unit.
Dan untuk contoh ini jawabannya saya butuh 3 langkah dengan 6 satuan jarak.
Jelas, ada beberapa cara untuk pergi ke satu titik dari tengah, tetapi masalahnya harus minimal.
Apakah ada rumus atau algoritma untuk menemukan jumlah langkah minimum dan jarak dari cara ini?
Nah, jika Anda menemukan salah satunya (langkah atau jarak), yang lain mudah ditemukan karena jarak adalah penjumlahan dari N (hitungan langkah) bilangan asli pertama.
Terima kasih telah membaca ini dan atas jawaban serta saran Anda.
Jawaban
Pertanyaan menarik. Mengejutkan bahwa jawabannya hanya bergantung pada$|x|+|y|$. Misalnya, jumlah langkah yang dibutuhkan untuk mencapainya sama$(1,1)$ atau $(0,2)$.
Langkah minimum adalah bilangan bulat non-negatif terkecil $n$ seperti yang $n(n+1)/2-(|x|+|y|)$ adalah genap dan tidak negatif.
Ini dia $O(1)$algoritma -time yang mengembalikan nilai yang dijelaskan di atas, di mana least_n
, yaitu,$\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$, adalah bilangan bulat nonnegatif terkecil $n$ seperti yang $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
Mengingat jumlah langkahnya $s$, jarak yang ditempuh $1+2+\cdots+s=s(s+1)/2$.
Ketepatan rumus dan algoritma di atas berasal dari karakterisasi berikut.
Dalil. Jumlah minimum langkah dari$(0,0)$ untuk $(x,y)$ adalah bilangan bulat non-negatif terkecil $n$ seperti yang $n(n+1)/2-(|x|+|y|)$ tidak negatif dan genap.
Bukti . Jika kita bisa pergi ke$(x,y)$ di $n$ langkah, jumlah beberapa angka antara 1 dan $n$ atau negasi mereka harus $x$ dan jumlah angka yang tersisa atau negasinya harus $y$, yaitu, $$\pm1\pm2\pm\cdots\pm n = |x| + |y|$$ untuk beberapa pilihan $\pm$'s. Itu berarti,$$1+2+\cdots+ n - (|x| + |y|)$$ tidak negatif dan genap.
Sekarang sudah cukup untuk membuktikannya $(x,y)$ dapat dijangkau dalam $n$ langkah jika $n(n+1)/2-(|x|+|y|)$tidak negatif dan genap. Mari kita buktikan dengan induksi$n$.
Kasus dasar, $n=0$ atau $1$ cara $(x,y)=(0,0), (0,1), (1,0)$. Kasus-kasus ini akan segera diverifikasi.
Misalkan, sebagai hipotesis induksi, itu benar untuk yang lebih kecil $n$'s. Sekarang pertimbangkan kasus$n\ge2$ dengan $n(n+1)/2-(|x|+|y|)$nonnegatif dan genap. Kita bisa berasumsi$x$ dan $y$tidak negatif; sebaliknya, misalnya, jika$x$ negatif, kita bisa berubah $x$ ke nilai absolutnya dan membalikkan arah semua langkah yang sejajar $X$-sumbu.
Ada tiga kasus.
- $x \ge n$. Membiarkan$x'= x-n$. Kemudian$$(n-1)n/2-(|x'|+|y|)=n(n+1)/2-(|x|+|y|)$$tidak negatif dan genap. Dengan hipotesis induksi, kita bisa pergi ke$(x',y)$ di $n-1$ steps. To reach $(x,y)$ in $n$ steps, we continue $n$ units in X-direction.
- $y\ge n$. This is symmetric to the case above.
- $0\le x\lt n$ and $0\le y\lt n$. There are two subcases.
- $x\ge 2$ and $y\ge 2$. Let $x'=(n-1)-x$ and $y'=n-y$. Then $|x'|\le n-3$ and $|y'|\le n-2$. $$(n-2)(n-1)/2-(|x'|+|y'|)\ge(n-3)(n-4)/2\ge0.$$ The parity of $(n-1)(n-1)/2-(|x'|+|y'|)$ is the same as $n(n+1)/2-(|x|+|y|)$, i.e, even. By induction hypothesis, we can go to $(x',y')$ in $n-2$ steps . Reversing all the steps, we can go to $(-x', -y')$ in $n-2$ steps as well. To reach $(x,y)$ in $n$ steps, we can continue with two more steps, $n$ units in X-direction and $n+1$ units in Y-direction.
- One of $x$ and $y$ is $0$ or $1$. Let $g(k)=k(k+1)/2-(|x|+|y|)$. The smallest nonnegative integer such that $g(k)\ge0$ is $m=\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$. Since both $x$ and $y$ are $\lt n$ and one of them is $0$ or $1$, $$m\le \frac{1+\sqrt{8n+1}}2.$$ When $g(m)$ is even, $n=m$ by definition. When $g$ is odd, since either $g(m+1)=g(m)+(m+1)$ or $g(m+2)=g(m)+(m+1)+(m+2)$ must be even, either $m+1$ or $m+2$ must be $n$. So, whether $g(m)$ is even or odd, we have $$n\le m+2.$$ Combing the two inequalities above, we have $$n\le \frac{5+\sqrt{8n+1}}2,$$ which implies $n\le 6$. Since X-direction and Y-direction are symmetric, let us assume $y=0,1$. Since $x\lt n$, $x\lt 6$. So it is enough to verify the cases where $(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)\}.$ It is easy to verify each of them.
$\ \checkmark$