Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune.stiinta, numere naturale, teoreme, multimi, calcule, ecuatii, sisteme



Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Informatica


Index » educatie » Informatica
Solutia problemei Banda


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 2n.

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 2n

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 2pas=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).




loading...




Politica de confidentialitate


Copyright © 2020 - Toate drepturile rezervate