Notatii:
C1 codul lui P1
C2 codul lui P2
C1-C2 (valabil numai daca C2 este prefix pentru C1) codul care se
obtine eliminand codul lui C2 de la inceputul lui C1
(a) Identice
C1=C2
(b) P1 inclus in P2, cu care nu are nici un punct de contact
C2 este prefix pentru C1, iar C1-C2 contine atat cifra 1 cat si cifra
4, SAU C1-C2 contine atat cifra 2 cat si cifra 3.
(c) P2 inclus in P1, cu care nu are nici un punct de contact
C1 este prefix pentru C2, iar C2-C1 contine atat cifra 1 cat si cifra
4, SAU C2-C1 contine atat cifra 2 cat si cifra 3.
(d) P1 inclus in P2, cu care are cel putin un punct comun
C2 este prefix pentru C1, dar nu suntem in cazul (b)
(e) P2 inclus in P1, cu care are cel putin un punct comun
C1 este prefix pentru C2, dar nu suntem in cazul (c)
(f) Exterioare unul altuia, cu cel putin doua puncte comune
(g) Exterioare unul altuia, cu un singur punct comun
(h) Complet disjuncte
Pentru aceste cazuri procedam astfel: intai taiem din ambele siruri
cel mai lung prefix comun lor. Fie deci C1 si C2 noile coduri, in care
stim ca C1[0]<>C2[0]. Comparam acum C1[0] cu C2[0]. Sa presupunem ca
C1[0]=1, C2[0]=2. Cu alte cuvinte, P1 aluneca spre stanga, iar P2 spre
dreapta.
Atunci este obligatoriu ca urmatoarele cifre din C1 sa fie in multimea
{2, 4} (sferturile din dreapta), iar urmatoarele cifre din C2 sa fie
in multimea {1, 3} (sferturile din stanga). Altfel, P1 si P2 sunt
complet disjuncte. Aceasta este o restrictie referitoare la axa Oy: P1
trebuie sa alunece pe viitor mereu spre dreapta, iar P2 spre stanga.
Exista si alte combinatii pentru C1[0] si C2[0] care induc restrictii
pe Oy. Practic, singurele perechi care nu induc restrictii pe Ox sunt
C1[0]=1, C2[0]=3 (sau invers) si C1[0]=2, C2[0]=4 (sau invers).
Similar, exista perechi care induc restrictii fata de Ox. De exemplu,
daca C1[0]=1 si C2[0]=3, atunci neaparat pe viitor P1 trebuie sa
alunece in jos, iar P2 in sus.
Atunci distingem trei cazuri:
h) Daca la un moment i C1[i] sau C2[i] nu respecta restrictiile ce li
s-au impus, P1 si P2 sunt disjuncte. Exemplu: C1=14, C2=44. C2[0]=4,
deci pe viitor C2 trebuie sa alunece spre stanga. Dar deoarece C2[1]=4
(C2 continua sa alunece spre dreapta), inseamna ca P1 si P2 sunt
disjuncte.
g) Daca pana la sfarsit restrictiile sunt respectate, iar in final
exista restrictii si pe Ox si pe Oy, atunci P1 si P2 sunt vecine pe
colt. Exemplu: C1=14, C2=213. Atunci C1[0] si C2[0] introduc
restrictia fata de Oy, iar C1[1] si C2[1] introduc restrictia fata de
Ox. C2[2] respecta aceste restrictii.
h) Daca nu exista restrictie decat pe Ox sau pe Oy, atunci patratele
sunt vecine pe latura. Exemplu: C1=1242424242424, C2=2131313131313
La orice moment, C1[i] si C2[i] se afla in aceeasi emisfera (nordica
sau sudica), deci nu apar restrictii referitoare la axa Ox.
|
|