Kodhok mlumpat-mlumpat ing garis angka, lan tujuane yaiku kanggo nyekel. Mlumpat lan nyekel kanthi gentian. Kodhok miwiti saka posisi \(s \in \mathbb{Z}\) lan saben obah, mlumpat kanthi jarak \(z \in \mathbb{Z}\) (yen \(z>0\) , mlumpat menyang tengen; yen ora, menyang kiwa). \(z\) padha kanggo saben lompatan. Nyekel kodhok kalebu nemtokake posisi integer. Ora ana \(z\) utawa \(s\) sing dingerteni. Kita bakal nuduhake manawa ana prosedur sing mesthi ngidini kita nyekel kodhok.
Kaping pisanan, \(a_1 = s\) lan \(a_{n+1} = a_n + z = s + n \cdot z\) nganggo \(s,z \in \mathbb{Z}\) .
Saiki kita milih
$$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 ) $$
minangka fungsi sing nemtokake (persis) tuple nomer kabeh nomer kanggo saben nomer alam. Pilihan fungsi iki yaiku liwat fungsi \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , \(\mathbb{N}\) ing \(\mathbb{Z}\) lan \(g(2^kr) = (k+1, \frac{r+1}{2})\) , sing \(\mathbb{N}\) ing \(\mathbb{N}^2\) peta kanthi subjektif, motivasi.
Saiki kita nuduhake surjectivity \(h\) ( \(h\) uga injeksi, nanging kita ora butuh properti iki).
Ayo \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Nanging banjur
$$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).$$
Mula: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) kanthi \(h(m) = (x_m,y_m) = (s, z)\) .
Contone, yen giliran kita pindhah ing \(n = 88\) , kita ngetung \(h(88)=(2,3)\) lan milih \(2 + 88 \cdot 3 = 266\) minangka posisi kasebut.
Banjur sawise persis \(m\) obah nganggo \(x_m + m \cdot y_m = s + m \cdot z = a_m\) pilihan kasebut tiba ing kodhok.
Saliyane \(h\) , akeh fungsi liyane kayata fungsi pasangan Cantor utawa spiral bijective bisa uga ditindakake.
Iki minangka implementasine sing gampang ing JavaScript:
See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.