h1. Aplicatii ale cautarii binare
(Creat de '_andreitheo87_':user/andreitheo87 la data de _2004-12-20_ categoria _Elementari_, autor(i) _Teodorescu Andrei_)
*Continut scurt:*
In acest articol vor fi prezentate aplicatii interesante ale cautarii binare, extinzand aria de aplicabilitate a acestei metode de rezolvare care se poate dovedi deosebit de puternica intr-un concurs.
*Continut lung:*
==Include(page="template/raw")==
(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.
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^2).
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^2^)$}.
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!
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.
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 [1]http://www.liis.ro/~campion/problems/2/96/tabara.htm
* problema Multiplu [2]http://www.liis.ro/~campion/problems/1/172/multiplu.htm
* problema Impartire in trei (Algoritmus, Runda 2, Problema 1)
[3]http://www.algoritmus.org/probleme/Probleme_Runda02.php
* problema Suma (Algoritmus, Runda 5, Problema 5)
[4]http://www.algoritmus.org/probleme/Probleme_Runda05.php
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:
References
Visible links
1. http://www.liis.ro/~campion/problems/2/96/tabara.htm
2. http://www.liis.ro/~campion/problems/1/172/multiplu.htm
3. http://www.algoritmus.org/probleme/probleme_runda02.php
4. http://www.algoritmus.org/probleme/probleme_runda05.php
* problema "Proc":http://www.infoarena.ro/problema/proc, ONI 2003, clasele XI-XII
* problema "Stramosi":http://www.infoarena.ro/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":http://www.infoarena.ro/problema/loto din arhiva de probleme InfoArena
* problema "Secventa 3":http://www.infoarena.ro/problema/secv3 din arhiva de probleme InfoArena
* problema "Tabara":http://www.liis.ro/~campion/problems/2/96/tabara.htm
* problema "Multiplu":http://www.liis.ro/~campion/problems/1/172/multiplu.htm
* problema "Impartire in trei":http://www.algoritmus.org/probleme/Probleme_Runda02.php (Algoritmus, Runda 2, Problema 1)
* problema "Suma":http://www.algoritmus.org/probleme/Probleme_Runda05.php (Algoritmus, Runda 5, Problema 5)
