Operația de căutare folosind tehnica de programare Divide et impera

-ARTICOL ȘTIINȚIFIC IN DOMENIUL INFORMATICII

 

     Operația de căutare este o operație uzuală într-un sistem informatic deoarece în orice moment trebuie să se cunoască situația datelor care sunt manipulate.

     Operația de căutare poate fi realizată în mai multe feluri: operație de căutare secvențială, operație de căutare cu acces direct, operație de căutare specială utilizând tehnica de programare Divide et impera.

     Acest curs pune accent pe tehnicile de programare folosite în cadrul sistemelor informatice în C# și de aceea în această lecție voi prezenta o căutare realizată cu ajutorul metodei Divide et impera. Pentru aceasta trebuie să se prezinte noțiunile teoretice ale acestei metode de programare.

Divide et impera este o tehnică de programare care poate fi aplicată anumitor clase de probleme ce pot fi împărțite în subprobleme de același fel, subprobleme care la rândul lor pot fi împărțite după același mecanism până când se ajunge la o problemă rezolvabilă și soluția problemei se obține concatenând soluțiile subproblemelor. Metoda presupune o implementare recursivă, iar o funcție care ar descrie (intuitiv) acest mecanism este:

 

int divide_et_impera(int a, int b) //se lucrează pe problema din intervalul [a,b]

{int c=(a+b)/2; // variabila c este mijlocul intervalului

if (abs(a-b)<=1) return rezultat; //dacă intervalul a ajuns la un element sau două, atunci problema poate fi rezolvată și se rezolvă

else {rez1=divide_et_impera(a,c); // când problema nu este rezolvabilă se împarte în două

         rez2= divide_et_impera(c+1,b); //subprobleme identice pe intervale [a,c] si [c+1,b] adică se înjumătațește intervalul

         rez3=rez1 concatenat rez2; //rezultatul final se obține concatenând soluțiile subproblemelor

         return rez3;

}}

 

Pentru a realiza o operație de căutare  a datelor folosind mecanismul Divide et impera se parcurg pașii:

1. Se construiește fereastra de dialog pentru a permite utilizatorului introducerea informației după care să se realizeze căutarea. Se acționează click secundar pe WindowsFormsApplication1 în fereastra poziționată în dreapta ecranului SolutionExplorer și se selectează opțiunea Add si opțiunea New Item:

 

2. Se selectează din fereastra Add New Item opțiunea Windows Form:

 

3. Se construiește ecranul de dialog folosind pentru text elementul Label, pentru câmpul de editare elementul TextBox și pentru declanșatorul OK Button, element care va permite introducerea datelor. Elementele vizuale se trag pe ecran, element cu element iar textul asociat se scrie în fereastra de proprietăți în secțiunea Text. 

 

4. În această etapă vom asocia câmpului de editare de pe ecran o variabilă pentru a putea prelua codul introdus de la tastatură,  pentru a realiza căutarea. Se realizează urmatoarele:

-se accesează codul ferestrei noi, pentru exemplul nostru în Form4 acționăm tasta F7,

-în clasa Form4 se va declara variabila camp1 și proprietatea corespunzătoare:

 

public partial class Form4 : Form

    {

        private string camp1;

        public string Camp1

        { get { return camp1; } }

5. Se revine în partea de Design al lui Form4 acționând Shift+F7, se apasă dublu click pe butonul ok pentru a-i defini acțiunea (metoda click). Deci vom scrie in metoda click :

   private void button1_Click(object sender, EventArgs e)

        {

            camp1 = textBox1.Text.Trim();         

            Close();        }

6. În această etapă se definește acțiunea propriu-zisă a butonului de căutare, adică se va activa dialogul modal care permite citirea datelor de la tastatură, se va folosi un algoritm de căutare în care se folosește tehnica de programare Divide et impera și în cazul în care se găsește informația, se va afișa într-o fereastră mesajul corespunzator. Deci vom parcurge pașii (pentru exemplul nostru):

-se implementează în formularul principal modulul de Divide et impera care va realiza căutarea:

        private bool divide_et_impera(int a, int b, string caut) // subprogramul recursiv de Divide et impera care cauta elementul caut in intervalul din matrice[a,b]

        {int c=(a+b)/2;

         if (a==b) {  //daca s-a ajuns la un element(conditia de oprire)

           if (caut==v[a,0]) return true; //se testeaza daca elementul coincide cu informatia cautata caut si daca da se returneaza valoarea adevarat

                        else return false; //daca nu se gaseste se returneaza fals}

             else return (divide_et_impera(a,c,caut) || divide_et_impera(c+1,b,caut));

//altfel se produce mecanismul de Divide et impera, adica problema este impartita in doua subprobleme, cautarea pe doua intervale de valori: de la a la jumatate [a,c] si de la jumatate plus unu la b [c+1,b]doua c. Solutia este obtinuta prin concatenarea cu operatorul || a rezultatelor celor doua cautari, deoarece rezultatul este boolean}

            -se face dublu click pe butonul Cautare produs în funcție de cod,

-se scrie în butonul al operației codul :

        private void button1_Click(object sender, EventArgs e)

        {    bool ok;      

            l = new Form4();

            l.ShowDialog(); //se activeaza dialogul modal

            if (l.Camp1 != "") //daca s-a introdus valoare in campul de editare

            {                ok=divide_et_impera(0, n - 1, l.Camp1); //se lanseaza subprogramul recursiv de Divide et impera pe intreaga matrice adica pe intervalul ce porneste de la 0 pana la numarul de elemente n-1              

                if (ok == true)  //functie de ce rezultat se preia in variabila ok se afiseaza measajul

                    MessageBox.Show("Produsul exista!");

                else MessageBox.Show("Produsul nu exista!");

            }        }

 

      Obs. Programul de exemplu este folosit pentru ca dumneavoastră să puteți lucra asemănător , doar adaptând operația care se potrivește temei alese.

7. Se declară în formularul principal variabila l care este identificatorul ferestrei de căutare Form4. Se va scrie în codul lui Form1, în secțiunea de declarații (după variabilele declarate de voi vector sau matrice) instrucțiunea:

 Form4 l;

Obs. Numele identificatorilor de clase sau variabile este pus de utilizator, deci puteți folosi orice nume doriți (l, h ,camp1, camp2 etc.), important este să păstrați corespondența operațiilor.

          În acest exemplu structura de date este de tip matrice și deci trebuie să ținem cont de codificarea stabilită inițial. În acest exemplu, noi am căutat dacă ceea ce am scris în camp1 se potrivește cuelementul de pe coloana 0, deoarece în camp1 am stabilit că voi introduce codul produsului și coloana 0 era codificarea pentru codul produsului.

Trebuie să amintesc că secvențele de cod, acolo unde nu sunt explicate, sunt logice operațiilor descrise șirespectă noțiunile de limbaj C# învățate anterior. Deasemenea operațiile sunt orientative, se pot alege și alte metode pentru realizarea lor.

Prin urmare tehnica de programare Divide et impera este o metodă care poate fi aplicată pentru rezolvarea unei vaste clase de probleme și poate fi utilizată cu succes în operații de căutare, în operații pentru realizarea de calcule, în operații de ordonare a datelor (ordonarea prin interclasare).

 

Autor articol:

Profesor Șălaru Antonia