Solutia problemei Banda

Solutia problemei Banda

Avem doua probleme "divide et impera", doua variatiuni pe aceeasi tema:

Fie intervalul [st,dr] si mijlocul lui mijl=(st+dr) div 2.

Cerinta 1:     Unde va ajunge pozitia s1?

Pornim cu un singur strat de elemente cu lungime 2ⁿ.

La fiecare pliere putem avea doua cazuri:

a. s1 ramane pe loc

b. s1 isi schimba linia si coloana. Intervalul studiat se injumatateste, insa inaltimea lui se dubleaza (strat)

lin:=strat+1-lin;

col:=st+dr-col;

strat:=2*strat;

Cerinta 2:De unde se ajunge pe f2?

Pornim cu o coloana de lungime 1 si inaltime 2ⁿ

Desfacem plierile obtinute. Vom avea in vedere o proprietate importanta: in fiecare pas al deplierii, valoarea dr al intervalului [st,dr], dr este divizibil cu 2^pas=putere si va fi [dr-putere+1,dr] sau [st,st+putere-1], in functie ca se desface spre stanga sau spre dreapta.

Daca linia si coloana patratului special este sub mijlocul coloanei, atunci aceste valori nu se vor schimba, altfel se vor schimba in simetricele fata de extremitati:

lin=1+inaltime-lin

col=st+dr-col (unde st si dr sunt noile dimensiuni ale intervalului)

Dupa n pasi se va obtine lin=1 si col va fi rezultatul cerut. (s2=col).