Kurbağaları yakala

Bir kurbağa sayı çizgisinde atlar ve onu yakalamaya çalışırsınız. Atlama ve yakalama her zaman alternatiftir. Kurbağa \(s \in \mathbb{Z}\) ve her hareketle \(z \in \mathbb{Z}\) mesafesini atlar ( \(z>0\) sağa, aksi takdirde sola). \(z\) her sıçrama için aynıdır. Yapışma bir tamsayı konumu belirtmekten oluşur. \(z\) veya \(s\) bilmiyorsunuz. Her zaman kurbağayı yakalamanın bir yolu olduğunu gösteriyoruz.


İlk olarak, \(a_1 = s\) ve \(a_{n+1} = a_n + z = s + n \cdot z\) ile \(s,z \in \mathbb{Z}\) .

Şimdi seçiyoruz

$$h:\mathbb{N} \to \mathbb{Z}^2: h(2^k r) = \left ( (-1)^{k+1} \left \lfloor \frac{k+1}{2} \right \rfloor, (-1)^{\frac{r+1}{2}} \left \lfloor \frac{r+1}{4} \right \rfloor \right ) $$

işlev olarak (tam olarak) her doğal sayıya bir tamsayı dizisi atar. Bu işlevin seçimi \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , \(\mathbb{N}\) \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) \(\mathbb{Z}\) ve \(g(2^kr) = (k+1, \frac{r+1}{2})\) , \(\mathbb{N}\) \(\mathbb{N}^2\) yönlü, motive edilmiş olarak tasvir eder.

Şimdi \(h\) ( \(h\) nin hassasiyetini de yerinde gösteriyoruz, ancak bu özelliğe ihtiyacımız yok).

\((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Ama sonra

$$h \left ( 2^{2 \cdot 2^{k_1} r_1 - 1} \cdot (4 \cdot 2^{k_2} r_2 - 1) \right ) = (2^{k_1} r_1, 2^{k_2} r_2) = (x,y).$$

Bu nedenle: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) ile \(h(m) = (x_m,y_m) = (s, z)\) .

Örneğin, \(n = 88\) de bizim sıramsa, \(h(88)=(2,3)\) hesaplar ve \(2 + 88 \cdot 3 = 266\) konumunu \(2 + 88 \cdot 3 = 266\) .

Sonra \(m\) tam olarak \(m\) \(x_m + m \cdot y_m = s + m \cdot z = a_m\) sonra seçim kurbağaya düşer.

\(h\) ye ek olarak, Cantor'un eşleştirme işlevi veya iki yönlü spiral gibi birçok işlev de mümkündür.

JavaScript'te basit bir uygulama aşağıdaki gibidir:

See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.

Geri