artımlı adımlarla noktadan noktaya minimum seyahat
Burada ilk kez bir soru soruyorum. Algoritma ile ilgili ilginç bir problemim var, Kartezyen düzlemin merkezinde (0,0) başka bir noktaya gitmem gerekiyor (x, y) -x ve y Z sayılarına ait - ancak sadece yatay ve dikey adımlar kullanabilirim ve bu adımlar birer birer artar, birim (0,0) 'dan (0,1), (1,0), (-1,0) veya (0, -1)' e bir uzaklıktır.
Örneğin, (1,1) noktasına gitmem gerekiyor ve adımlar:
- 1 birimlik bir adım olan (1,0) 'a gidin.
- (1, -2) 'ye 2 birimlik bir adıma gidin.
- Son olarak, (1,1) 'e 3 birimlik bir adıma gidin.
Ve bu örnek için cevap, 6 birim mesafe ile 3 adıma ihtiyacım var.
Açıkçası, merkezden bir noktaya gitmenin birkaç yolu var ama problemin asgari düzeyde olması gerekiyor.
Minimum adım sayısını ve bu yolun mesafesini bulmak için bir formül veya algoritma var mı?
Birini bulursanız (adımlar veya mesafe), diğerini bulmak kolaydır çünkü mesafe N (adım sayısı) ilk doğal sayıların toplamıdır.
Bunu okuduğunuz, cevaplarınız ve önerileriniz için teşekkür ederiz.
Yanıtlar
İlginç soru. Cevabın yalnızca şuna bağlı olması şaşırtıcı$|x|+|y|$. Örneğin, ulaşmak için aynı sayıda adım gerekir.$(1,1)$ veya $(0,2)$.
Minimum adım, en az negatif olmayan tam sayıdır $n$ öyle ki $n(n+1)/2-(|x|+|y|)$ eşittir ve negatif değildir.
İşte bir $O(1)$-yukarıda açıklanan değeri döndüren zaman algoritması, burada least_n
, yani,$\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$en az negatif olmayan tam sayıdır $n$ öyle ki $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
Adımların sayısı göz önüne alındığında $s$, katedilen mesafe $1+2+\cdots+s=s(s+1)/2$.
Yukarıdaki formül ve algoritmanın doğruluğu aşağıdaki karakterizasyondan gelir.
Önerme. Minimum adım sayısı$(0,0)$ -e $(x,y)$ en az negatif olmayan tam sayıdır $n$ öyle ki $n(n+1)/2-(|x|+|y|)$ negatif değildir ve hatta.
Kanıt . Eğer gidebilirsek$(x,y)$ içinde $n$ adımlar, 1 ile 1 arasındaki bazı sayıların toplamı $n$ veya onların olumsuzlukları $x$ ve kalan sayıların toplamı veya olumsuzlukları olmalıdır $y$yani $$\pm1\pm2\pm\cdots\pm n = |x| + |y|$$ hepsinden bazı seçenekler için $\pm$'s. Bunun anlamı,$$1+2+\cdots+ n - (|x| + |y|)$$ negatif değildir ve hatta.
Şimdi bunu kanıtlamak yeterli $(x,y)$ ulaşılabilir $n$ adımlar eğer $n(n+1)/2-(|x|+|y|)$negatif değildir ve hatta. Bunu tümevarımla kanıtlayalım$n$.
Temel durumlar, $n=0$ veya $1$ anlamına geliyor $(x,y)=(0,0), (0,1), (1,0)$. Bu vakalar hemen doğrulanmalıdır.
Tümevarım hipotezi olarak daha küçük için doğru olduğunu varsayalım. $n$'s. Şimdi durumunu düşünün$n\ge2$ ile $n(n+1)/2-(|x|+|y|)$negatif olmayan ve hatta. Varsayabiliriz$x$ ve $y$negatif değildir; aksi takdirde, örneğin, eğer$x$ olumsuz, değiştirebiliriz $x$ mutlak değerine getirin ve paralel olan tüm adımların yönünü tersine çevirin $X$eksen.
Üç durum var.
- $x \ge n$. İzin Vermek$x'= x-n$. Sonra$$(n-1)n/2-(|x'|+|y|)=n(n+1)/2-(|x|+|y|)$$negatif değildir ve hatta. Tümevarım hipoteziyle şu adrese gidebiliriz:$(x',y)$ içinde $n-1$adımlar. Ulaşmak için$(x,y)$ içinde $n$ adımlar, devam ediyoruz $n$ X yönündeki birimler.
- $y\ge n$. Bu, yukarıdaki duruma simetriktir.
- $0\le x\lt n$ ve $0\le y\lt n$. İki alt durum var.
- $x\ge 2$ ve $y\ge 2$. İzin Vermek$x'=(n-1)-x$ ve $y'=n-y$. Sonra$|x'|\le n-3$ ve $|y'|\le n-2$. $$(n-2)(n-1)/2-(|x'|+|y'|)\ge(n-3)(n-4)/2\ge0.$$ Eşitliği $(n-1)(n-1)/2-(|x'|+|y'|)$ aynıdır $n(n+1)/2-(|x|+|y|)$, yani, hatta. Tümevarım hipoteziyle şu adrese gidebiliriz:$(x',y')$ içinde $n-2$adımlar. Tüm adımları tersine çevirerek gidebiliriz$(-x', -y')$ içinde $n-2$adımlar da. Ulaşmak için$(x,y)$ içinde $n$ adım, iki adım daha devam edebiliriz, $n$ X yönündeki birimler ve $n+1$ Y yönündeki birimler.
- Biri $x$ ve $y$ dır-dir $0$ veya $1$. İzin Vermek$g(k)=k(k+1)/2-(|x|+|y|)$. Negatif olmayan en küçük tam sayı, öyle ki$g(k)\ge0$ dır-dir $m=\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$. İkisinden beri$x$ ve $y$ vardır $\lt n$ ve onlardan biri $0$ veya $1$, $$m\le \frac{1+\sqrt{8n+1}}2.$$ Ne zaman $g(m)$ eşit $n=m$tanım olarak. Ne zaman$g$ tuhaf, çünkü her ikisi de $g(m+1)=g(m)+(m+1)$ veya $g(m+2)=g(m)+(m+1)+(m+2)$ ya eşit olmalı $m+1$ veya $m+2$ olmalıdır $n$. Öyleyse,$g(m)$ çift mi tuhaf mı, bizde var $$n\le m+2.$$ Yukarıdaki iki eşitsizliği birleştirdiğimizde, $$n\le \frac{5+\sqrt{8n+1}}2,$$ Hangi ima $n\le 6$. X yönü ve Y yönü simetrik olduğundan, varsayalım$y=0,1$. Dan beri$x\lt n$, $x\lt 6$. Bu yüzden durumları doğrulamak yeterlidir.$(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)\}.$ Her birini doğrulamak kolaydır.
$\ \checkmark$