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.
