informatica -

ATESTAT INFORMATICA

PROIECT

1.. Notiuni teroretice

Strategia generala backtracking

Recursivitate

Strategia generala in var backtracking

5.Ex: probleama labirint ,program fotografie

CAPITOLUL I. NOTIUNI TEORETICE

In cautarea unor principii fundamentale ale elaborarii algoritmilor, backtraking este una dintre cele mai generale tehnici. Multe probleme care necesita cautarea unui set de solutii sau o solutie optima care sa satisfaca anumite restrictii pot fi rezolvate utilizand aceasta metoda. Denumirea backtraking (cautarea cu revenire) a fost utilizata pentru prima oara in anii '50 de catre D. H. Lehmer. Cei care au studiat procesul inaintea sa au fost: R. J. Walker (care i-a dat o interpretare algoritmica in 1960), S. Golomb si L. Bammert (care au prezentat o descriere generala a metodei, precum si varietatea de aplicabilitate a acesteia).

1. Prezentarea metodei

Aceasta metoda se aplica problemelor a caror solutie poate fi pusa sub forma unui vector x₁, x₂, . , x_n in care x₁A₁, . , x_n A_n sunt multimi finite si nevide si ale caror elemente se afla intr-o relatie de ordine bine stabilita. De multe ori multimile A , . , A_n coincid.

Metoda backtraking construieste solutia problemei progresiv, obtinand pe rand elementele x , x₂, . , x_n, netrecand la componenta x_k pana cand nu s-au stabilit celelate componente, x₁, . , x_k-1.

Presupunem ca am generat deja elementele x , . , x_k. Urmatorul pas este generarea lui x_k+1 A_k+1. In acest scop se cauta in multimea A_k+1 urmatorul element disponibil. Exista doua posibilitati:

1.Sa nu existe un astfel de element in multimea A_k+1. In aceasta situatie se renunta

la ultimul x_k ales, deci s-a facut un pas inapoi si in continuare se cauta generarea unui alt element x_k din multimea A_k

1.1Exista un x_k+1 disponibil in multimea A_k+1. In aceasta situatie se verifica daca

acest element indeplineste conditiile ( conditii de continuare) cerute de enuntul problemei de a face parte din solutie.

Apar alte posibilitati

Daca x_k+1 ales indeplineste conditiile de continuare si poate face parte din solutie, atunci apar alte doua situatii:

2.1. Sa se fi ajuns la solutia finala a problemei si aceasta trebuie tiparita;

Sa nu se fi ajuns la solutia finala si atunci se considera generat x_k+1, facand un

pas inainte la x_k+2 A_k+2.

Daca x_k+1 nu indeplineste conditiile de continuare atunci se cauta urmatorul element disponibil in multimea A_k. Daca si ea se epuizeaza se face un pas inapoi renunzandu-se la x_k

Observatie Problema se termina, cu tiparirea tuturor solutiilor, cand a fost epuizata multimea A

Pentru a implementa aceasta metoda intr-un limbaj de programare, respectiv in C++ , se foloseste o structura de date de tip special (LIFO - last in first out), numita stiva, caracterizata prin faptul ca operatiile permise asupra ei se pot realiza la un singur capat numit varful stivei. Stiva se asimileaza cu un vector pe verticala si in ea se construieste solutia problemei.

Analiza: Documente specifice operatiilor cu numerar Eseu: Forma de contabilitate utilizata la o societate comerciala

Aceasta structura are nevoie de o variabila k care precizeaza in permanenta nivelul stivei.

Daca k = 0 se spune ca stiva este vida.

Daca k = n se spune ca stiva este plina.

Orice adaugare a unui element in stiva presupune cresterea nivelului stivei: k=k+1.

Orice eliminare a unui element din stiva presupune scaderea nivelului stivei :

k = k - 1.

Stiva pe care o folosim este o stiva simpla, avand capacitatea de a memora pe un anumit nivel o litera sau o cifra.

Metoda de programare backtracking admite atat o implementare interativa cat si una recursiva, folosind o serie de subprograme cu rol bine determinat, corpul lor de instructiuni depinzand de natura si complexitatea problemei.

2. Strategia generala backtraking in varianta iterativa

Se folosesc urmatoarele functii:

►Functia       init (), de tip void - cu rolul de a initializa fiecare nivel k al stivei, cu o valoare neutra, care nu face parte din solutie, dar care permite, pentru fiecare componenta a solutiei, trecerea la primul element al domeniului sau de valori, ca si in cazul celorlalte, conform relatiei de ordine in care acestea se afla.

►Functia       succesor (), de tip int - cu rolul de a gasi un succesor, adica de a cauta un nou element disponibil in multimea de valori a unei componete din solutie. Aceata functie va returna valoarea 1 daca exista succesor si valoarea 0 in caz contrar.

► Functia valid (), de tip int - cu rolul de a verifica daca succesorul ales indeplineste conditiile de continuare. Aceata functie va returna valoarea 1 daca succesorul este valid ( respecta conditiile de continuare) si valoarea 0 in caz contrar.

► Functia    tipar(), de tip void - cu rolul de a tipari o solutie determinata.

► Functia solutie(), de tip int - cu rolul de a verifica, la nivelul k al stivei, daca s-a ajuns la solutie sau nu, returnand, in mod corespunzator valoarea 1 sau 0.

Strategia generala backtraking se implementeaza in C, intr-o functie de tip void, in felul urmator:

void back()

if (as)

if solutie( ) tipar();

else

;

else k:=k-1;

}

}

Se folosesc variabilele intregi as si ev, cu semnificatia "am succesor", respectiv "este valid".

3. Recursivitatea

Recursivitatea este una din notiunile fundamentale ale informaticii. Utilizarea frecventa a recursivitatii s-a facut dupa anii '80. Multe din limbajele de programare evoluate si mult utilizate nu permiteau scrierea programelor recursive. In linii mari, recursivitatea este un mecanism general de elaborare a programelor. Ea a aparut din necesitati practice (transcrierea directa a formulelor matematice recursive) si reprezinta acel mecanism prin care un subprogram se autoapeleaza.

Un algoritm recursiv are la baza un mecanism de gandire diferit de cel cu care ne-am obisnuit deja. Atunci cand scriem un algoritm recursiv este suficient sa gandim ce se intampla la un anumit nivel pentru ca la orice nivel se intampla exact acelasi lucru.

Un algoritm recursiv corect trebuie sa se termine, contrar programul se va termina cu eroare si nu vom primi rezultatul asteptat. Conditia de terminare va fi pusa de programator.

Un rezultat matematic de exceptie afirma ca pentru orice algoritm iterativ exista si unul recursiv echivalent (rezolva aceasi problema) si invers, pentru orice algoritm recursiv exista si unul iterativ echivalent.

In continuare, raspundem la intrebarea: care este mecanismul intern al limbajului care permite ca un algoritm recursiv sa poata fi implementat? Pentru a putea implementa recursivitatea, se foloseste structura de date numita stiva.

Mecanismul unui astfel de program poate fi generalizat cu usurinta pentru obtinerea recursivitatii. Atunci cand o functie se autoapeleaza se depun in stiva:

● valorile parametrilor transmisi prin valoare;

● adresele parametrilor transmisi prin referinta;

● valorile tuturor variabilelor locale (declarate la nivelul functiei);

adresa de revenire la instructinea imediat urmatoare autoapelului.

4. Strategia generala backtraking in varianta recursiva

Metoda de programare backtraking are si o varianta recursiva. Prelucrarile care se fac pentru elementul k al solutiei se fac si pentru elementul k+1 al solutiei si aceste prelucrari se pot face prin apel recursiv. In algoritmul backtracking implementat iterativ, revenirea la nivelul k-1 trebuie sa se faca atunci cand pe nivelul k nu se gaseste o valoare care sa indeplineasca conditiile interne. In cazul implementarii recursive, conditia de baza este ca pe nivelul k sa nu se gaseasca o valoare care sa indeplineasca conditiile interne. Cand se ajunge la conditia de baza, inceteaza apelul recursiv si se revine la subprogramul apelant, adica la la subprogramul care prelucreaza elementul k-1 al solutieie, iar in stiva se vor regasi valorile prelucrate anterior in acest subprogram.

Intreaga rutina care implementeaza algoritmul backtracking recursiv se va transforma intr-o functie de tip void (procedurala) ce se va apela din programul principal prin back(1), avand ca parametru nivelul k al stivei; aceasta se va autoapela pe nivelele urmatoare ale stivei.

void back (int k)

Aceasta procedura functioneaza in felul urmator:

- se testeaza daca s-a ajuns la solutie; daca da, aceasta se tipareste si se revine la nivelul anterior;

-in caz contrar, se initiaza nivelul stivei si se cauta un succesor;

daca am gasit un succesor, se verifica daca este valid si daca da se autoapeleaza procedura pentru (k+1); in caz contrar, se continua cautarea succesorului;

daca nu exista succesor se revine la nivelul anterior (k+1) prin iesirea din procedura back.

Ex problema:

Program labirint;

type stiva=array[1..100,1..3] of integer;

var st:stiva;

       m,n,k,i,j,l,c,l1,c1:integer;

       as,ev:boolean;

       a:array[1..100,1..100] of integer;

procedure init(var st:stiva;k:integer);

begin

      st[k,1]:=0;

      if k=1 then begin

        st[k,2]:=l;st[k,3]:=c;

        end else begin

            st[k,2]:=l1;st[k,3]:=c1;

            end;

end;

procedure succesor(var as:boolean;var st:stiva;k:integer);

begin

       if  st[k,1]<4 then begin

          st[k,1]:=st[k,1]+1;

          as:=true;

      end else as:=false;

end;

procedure valid(var ev:boolean;st:stiva;k:integer);

begin

        l1:=st[k,2];c1:=st[k,3];

        case st[k,1] of

        1: l1:=l1-1;

            2: c1:=c1+1;

            3: l1:=l1+1;

            4: c1:=c1-1;

           end;

       ev:=true;

       case st[k,1] of

       1: if a[st[k,2],st[k,3]] and 8<>0 then ev:=false;

           2: if a[st[k,2],st[k,3]] and 4<>0 then ev:=false;

           3: if a[st[k,2],st[k,3]] and 2<>0 then ev:=false;

           4: if a[st[k,2],st[k,3]] and 1<>0 then ev:=false;

           end;

       for i:=1 to k-1 do if  (l1=st[i,2]) and (c1=st[i,3]) then ev:=false;

end;

function solutie(k:integer):boolean;

begin

       solutie:=(l1<1) or (l1>m) or (c1<1) or (c1>n);

end;

procedure tipar;

       for i:=1 to k do write(st[i,2],' ',st[i,3],'    ');

       writeln;

end;

begin

       write('m,n:');readln(m,n);

       for i:=1 to m do

      for j:=1 to n do read(a[i,j]);

       write('l,c:');readln(l,c);

       k:=1;init(st,k);

       while k>0 do begin

      repeat

             succesor(as,st,k);

             if as then valid(ev,st,k);

      until (not as) or (as and ev);

      if as then if solutie(k) then tipar else begin

             k:=k+1;

             init(st,k);

             end else k:=k-1;

          end;

end.

Program fotografie;

Const   DimMax = 50;

    Dx: array[1 . . 4]  of   integer=(-1, 0, 1, 0) ;

    Dy: array[1 . . 4]  of   integer=(0, 1, 0, -1) ;

Type    Indice = 0  .  .  DimMax+1 ;

Var      a: array[Indice,  Indice]  of  0 . . 1 ;

            m, n, i, j, NrObiecte : Indice ;

Procedure Citire;

var fin: text ;

begin

assign(fin,  'foto.in'); reset(fin) ;

readln(fin, n, m);

for i :=1 to n do

                     begin

               for j :=1 to m do  read(fin, a[i, j]);

               end;

close(fin);

end;

Procedure Sterge_Obiect(x, y: Indice) ;

var dir: 1 .  . 4 ;

begin

if a[x,y] = 1 then

            begin

            a[x,y] := 0 ;

            for dir := 1 to 4 do  Sterge_Obiect(x + Dx[dir] , y + Dy[dir]) ;

            end;

end;

begin

Citire;

for i := 1 to n do

              for j := 1 to m do

                      if  a[i, j] = 1 then

                          begin

                          inc(NrObiecte);

                          Sterge_Obiect(i j);

                          end;

writeln(Nr. Obiecte =   ',  NrObiecte) ; readln ;

end.