Functie pentru diviziuni consecutive

[crs12decoder]

Problema mi-a venit in minte cand am postat asta: http://rstcenter.com/forum/46078-intrebari-ciudate-interviews.rst

Mai exact referitor la:

"Date fiind 20 de becuri destructibile, care se sparg la o anumita inaltime, si 100 de etaje, cum determini inaltimea la care becurile crapa?" - Qualcomm, post de inginer

Am propus rezolvarea problemei prin diviziuni succesive.

Prima oara incepand de la etajul 50, aruncam un bec, daca se sparge coboram la 25. Daca nu, urcam la 75.

Si tot asa parcurgem cate jumatate din drum pana cand aflam la ce etaj maxim se sparge becul.

Problema pe care o propun ca si challenge aici:

Sa se gaseasca o functie matematica(formula) ce ne poate spune pentru orice numar de etaje dat, de cate aruncari MAXIM avem nevoie pentru a determina etajul.

Pentru 10 etaje sunt 4 aruncari maxime.

Pentru 100 etaje sunt 7 aruncari maxime.

Pentru n etaje cate aruncari maxime sunt?

Edited January 2, 2012 by crs12decoder

[em]

Haide s? ne gândim la complexitatea la divide et impera.

R?spunsul este ceil(log2(nrEtaje)).

Pentru 10: ceil(log2(10))=ceil(3.32)=4.

Pentru 100:ceil(log2(100))=ceil(6.64)=7.

[crs12decoder]

Yep.

ceil(log base 2 din n)

Cum ai determinat?

//edited ty totti

Edited January 2, 2012 by crs12decoder

[totti93]

@crs12decoder nu cred ca e log2(n) + 1. Eu consider ca em a zi bine. De ce?

Calculeaza pentru 2^k etaje (k E N*). iti va da fix log2(n).

Deci varianta corecta:

{ log2(n);       n = 2 ^ k, k E N
{ [log2(n)] + 1; n != 2 ^ k, k E N

Edited January 2, 2012 by totti93

[n1cky]

Divide et Impera ? (vrajitorii!?!) Nu stim noi chestii complicate, asa ca incercam o varianta mai simpla(fun).

Noi o luam incetisor pe foaie, si ajungem la o schema de genul :

Luam unul din exemple, n=10;

Prima data, aruncam de la etajul 5, daca s-a spart, atunci sunt 2 posibilitati : etajul cu pricina e chiar 5, sau etajul cu pricina e mai jos.

Continuam, presupunem ca s-a spart, aruncam de la etajul 2 si presupunem din nou ca se sparge, iarasi avem 2 posibilitati : etajul cu pricina e 2, sau etajul cu pricina este 1, aruncam de la 1 si aflam rezultatul. Daca nu se sparge aruncam de la 3, daca s-a spart la 3, atunci 3 e etajul cu pricina, daca nu, aruncam de la 4 sa vedem daca este 4 sau 5.

Prin analogie se trateaza cazul in care de la etajul 5 nu s-a spart.

Observam ca numarul maxim de pasi pe care ii urmam este 4. Tinand cont ca stiam de dinainte ca pentru 10 etaje, raspunsul este 4, ne dam seama ca nu am gresit.

Dupa reprezentarea mai multor asemenea scheme (nu neaparat) ne cam dam seama de o posibila regula.

Vedem ca tot impartim la 2 :

1. 10 : 2 = 5

2. 5 : 2 = 2,5

3. 2,5 : 2 = 1,25

Dar noi stim ca avem 4 pasi, nu 3. Ce facem ? Inventam noi o modalitate de a scoate inca un pas.

Observam ca:

1,25 : 2 = 0,625

Rotunjim 0,625 la 1 si adunam la pasii nostri. Ne ies 4 pasi. Super nu ?

Tragem alta concluzie :

Hai sa impartim numarul nostru la 2, pana la primul rezultat subunitar, si numaram pasii.

1. 10 : 2 = 5

2. 5 : 2 = 2,5

3. 2,5 : 2 = 1,25

4. 1,25 : 2 = 0,625

Ne gandim, daca merge pentru un caz, asta nu inseamna ca merge pentru toate. Din fericire, mai avem un rezultat cunoscut, putin mai indepartat totusi, si anume pentru n=100, numarul de pasi = 7 ;

Ne apucam sa testam algoritmul nostru :

1. 100 : 2 = 50

2. 50 : 2 = 25

3. 25 : 2 = 12,5

4. 12,5 : 2 = 6,25

5. 6,25 : 2 = 3,125

6. 3,125 : 2 = 1,5625

7. 1,5625 : 2 = 0,78125

Voila, ne ies 7 pasi, exact ca si rezultatul pe care il stiam de dinainte.

Stam putin si ne gandim, la cat am impartit la 2 , ne vine asa o idee de un posibil logaritm in baza 2, poate ne-o usura munca. Cine stie ?

Si ne apucam iar de calculat.

log2(10) = 3,32193 ;

Aha, da cam urat logaritmul, dar stai asa. Noi cati pasi aveam la n=10 ? Parca 4.

Observam o posibila scurtatura :

Daca rotunjim 3,32193 ne iese fix 4, adica rezultatul corect.

Bun, pai atunci ia sa umblam noi la algoritmul nostru sa il imbunatatim. Decat sa stam sa tot impartim la 2, de ce nu am face un logaritm in baza 2 si apoi am rotunji rezultatul ?

Scoatem varianta imbunatatia a algoritmului : ceil(log2(n)).

Ca sa vezi, ne iese acelasi lucru ca si baietilor mari care stiu Divide et Impera.

Sau varianta a 2a, admitem ca stim Divide et Impera si spunem direct cat face.

Edited January 2, 2012 by n1cky

[cmiN]

Sau poti spune ca evenimentele se pot aseza intr-un arbore binar perfect echilibrat si ca inaltimea lui este logN.