Aplicatii ale cautarii binare

(Categoria Tehnici de programare, Autor Andrei Teodorescu)

Voi prezenta in articolul care urmeaza cateva aplicatii ale cautarii binare. Algoritmii descrisi nu sunt intotdeauna optimi insa prezinta avantajul implementarii mult mai rapide, lucru care constituie un avantaj pe timp de concurs.

1. Sa se gaseasca (daca exista) cel mai mic numar natural N astfel incat N! sa se termine in exact p cifre de 0, p ≤ 10¹⁸
2. Se considera un teren de forma dreptunghiulara reprezentat de o matrice NxN care contine in pozitia (i,j) 1 daca aceasta este accesibila sau 0, altfel. Se dau 2 puncte (x₁,y₁) si (x₂,y₂). Sa se afisize latura maxima a unui patrat care poate fi deplasat intre cele 2 puncte astfel incat acesta sa se afle in orice moment al deplasarii numai pe teren bun (numai cu cifre de 1).
3. Sa se calculeze cel mai lung subsir crescator al unui sir de N numere.
4. Sa se calculeze cu precizie de Z zecimale:
   1. radicalul unui numar mare
   2. catul a 2 numerere mari (consideram un numar mare un numar cu cel putin 20 de cifre, care nu poate fi stocat in tipuri de date conventionale)

In prima problema trebuie sa observam prima oara ca numarul de zerouri in care se termina N! creste odata cu N, observatie evidenta datorita definitiei lui N!. Atunci, putem cauta binar valoarea lui N pentru care se verifca relatia din enunt. Recomand problema "Factorial" din arhiva de probleme InfoArena celor interesati de implementarea algoritmului.

Pentru a doua problema este usor de aratat ca daca daca se poate deplasa intre cele 2 puncte un patrat de latura l(l ≥ 2), atunci sigur se va putea deplasa si unul de latura l-1,l-2...1 iar daca nu putem deplasa un patrat de latura l, atunci nu putem deplasa nici unul de latura l+1,l+2...n. Astfel avem de cautat o valoare l astfel incat putem deplasa un patrat de latura l insa nu si unul de latura l+1. Numarul l va fi chiar rezultatul cautat. Pentru a face verificarea daca putem deplasa un patrat de o latura data putem folosi algoritmul lui Lee, care implementat atent va avea o complexitate de O(n²).

Nu voi insista prea mult asupra algoritmului de aflare a celui mai lung subsir crescator al unui sir, problema fiind cunoscuta, de asemenea se gaseste si in cartea "Psihologia concursurilor de informatica" de Catalin Francu. Idee de baza este sa se caute binar de fiecare data pozitia fiecarui element intr-un subsir crescator cat mai lung.

Pentru calcularea radicalului unui numar sau calcularea catului a doua numere se cunosc inca din gimnaziu algoritmi! :) Insa acesti algoritmi sunt destul de greu de implemantat(si oricum ajung la un moment dat la folosirea cautarii binare). Asadar in loc de a calcula rezultatul il putem cauta. De exemplu, in primul caz vom cauta o valoare a lui n pentru care n*n sa nu depaseasca numarul dat, insa (n+1)*(n+1) sa depaseasca. Asemanator se procedeaza si in cazul impartirii.

Pentru utilizarea acestor doi algoritmi trebuie ca cel care ii scrie sa stapaneasa foarte bine inmultirea, adunarea, compararea si, eventual, impartirea la 10 a numerelor mari (vezi articolul de pe site :D). Pentru a obtine o precizie de z zecimale se inmulteste numarul dat(in primul caz)cu 10^2*z si deimpartitul(in al doilea caz) cu 10^z iar in rezultatul obtinut ultimle z cifre vor fi zecimalele iar restul, partea intreaga.

Ca observatie, trebuie sa aveti grija intotdeauna cand alegeti intervalul in care se face cautarea pentru a fi siguri ca algoritmul va produce rezultatlul dorit!

In final invit cititorii sa rezolve cateva probleme cu ajutorul cautarii binare:

• problema Proc, ONI 2003, clasele XI-XII
• problema Stramosi din arhiva de probleme InfoArena ( indicatie: se realizeaza o parcurgere Euler si o parcurgere in latime a arborelui iar apoi se cauta ficare nod cerut pe nivelul pe care se afla)
• problema Loto din arhiva de probleme InfoArena
• problema Secventa 3 din arhiva de probleme InfoArena
• problema Tabara
• problema Multiplu
• problema Impartire in trei (Algoritmus, Runda 2, Problema 1)
• problema Suma (Algoritmus, Runda 5, Problema 5)