Creeaza.com - informatii profesionale despre


Evidentiem nevoile sociale din educatie - Referate profesionale unice



Acasa » referate » informatica » calculatoare
Atestat la informatica - METODA BACKTRACKING

Atestat la informatica - METODA BACKTRACKING



COLEGIUL ECONOMIC “ANGHEL RUGINA”

VASLUI

Atestat  la  informatica

 

 

 


 

= METODA =

=BACKTRACKING=

            

METODA BACKTRACKING

 

1.1.   Stiva

   Stiva este acea forma de organizare a datelor (structura de date) cu proprietatea ca operatiile de introducere si scoatere a datelor se fac in varful ei.

   Pentru a intelege modul de lucru cu stiva, ne imaginam un numar n de farfurii identice, asezate una peste alta (o “stiva” de farfurii). Adaugarea sau scoaterea unei farfurii se face, cu usurinta, numai in varful stivei. Daca cele n farfurii sunt asezate una peste alta, spunem ca stiva este vida. Dupa ce am scos toate farfuriile din stiva, spunem ca aceasta este vida. Oricat ar parea de simplu, principiul stivei, el are consecinte uriase in programare.

   Stivele se pot utiliza folosind vectori.

   Fie ST(i) un vector.  ST(1),ST(2),…,ST(n) pot retine numai litere sau cifre. O variabila K indica in permanenta varful stivei.

Exemplificam, in continuare, modul de lucru cu stiva:


in stiva initial vida se introduce litera A, varful stivei va fi la nivelul 1 (k=1);


introducem in stiva litera B, deci k va lua valoarea 2;


scoatem din stiva pe  B (A nu poate fi scos);


scoatem din stiva pe A; stiva ramane vida

Observatii:

·     in mod practic, la scoterea unei variabile din stiva, scade cu 1 valorea variabilei ce indica varful stivei, iar atunci cand scriem ceva in stiva, o eventuala valoare reziduala se pierde;

·         pe un anumit nivel se retine, de regula, o singura informatie (litera sau cifra), insa este posibil, asa cum va rezulta din exemplele prezentate in lucrare, sa avem mai multe informatii, caz in care avem de a face cu stive duble, triple, etc;

·         intreaga teorie se bazeaza pe structura de tip stiva.

1.2.   Prezentarea tehnicii backtracking

   Aceasta tehnica se foloseste in rezolvarea problemelor ce indeplinesc simultan urmatoarele conditii:

·         solutia lor poate fi pusa sub forma unui vector S=x1, x2, …, xn, cu x1IA1, x2IA2, …, xnIAn;

·         multimile A1, A2, …, An sunt multimi finite, iar elementele lor se considera ca se afla intr-o relatie de ordine bine stabilita;

·         nu se dispune de o alta metoda de rezolvare;

Observatii:

·         nu pentru toate problemele n este cunoscut de la inceput;

·         x1, x2, …, xn pot fi la randul lor vectori;

·         in multe probleme, multimile A1, A2, …, An coincid.

La intalnirea unei astfel de probleme, daca nu cunoastem aceasta tehnica, suntem tentati sa generam toate elementele produsului cartezian A1* A2* …* An si fiecare element sa fie testat daca este solutie. Rezolvand problema in acest mod, timpul de executie este atat de mare, incat poate fi considerat infinit, algoritmul neavand nici o valoare practica.

   De exemplu, daca dorim sa generam toate permutarile unei multimi finite A,nu are rost sa generam produsul cartezian A*A*…*A, pentru ca apoi, sa testam, pentru fiecare element al acestuia, daca este sau nu permutare (nu are rost sa generam 1,1,1……,1, pentru ca apoi sa constatam ca nu am obtinut o permutare, cand de la a doua cifra 1 ne putem da seama ca cifrele nu sunt distincte).

Tehnica backtracking are la baza un principiu extrem de simplu:

·         se construieste solutia pas cu pas: x1, x2, …, xn;

·         daca se constata ca, pentru o valoare aleasa, nu avem cum sa ajungem la solutie, se renunta la acea valoare si se reia cautarea din punctul in care am ramas.

Concret:

·         se alege primul element x1, ce apartine lui A1;

·         presupunad generate elementele x1, x2, …, xn, apartinand multimilor A1, A2, …, Ak, se alege (daca exista) xk+1 primul element disponibil din multimea Ak+1, apar doua posibilitati:

1.      nu sa gasit un atfel de element, caz in care se reia cautarea considerand generate elementele x1, x2, …, xk, iar aceasta se reia de la urmatorul element al multimii Ak, ramas netastat;

2.      a fost gasit, caz in care se tasteaza daca acesta indeplineste anumite conditii de continuare, aparand astfel doua posibilitati:

A)   le indeplineste, caz in care se tasteaza daca s-a ajuns la solutie si apar, din nou, doua posibilitati:

a)          s-a ajuns la solutie, se tipareste solutia si se reia algoritmul considerand generate elementele x1, x2, …xk (se cauta, in continure, un alt element al multimii Ak+1 ramas netastat);

b)          nu s-a ajuns la solutie, caz in care se reia algoritmul considerand generate elementele x1, x2, …, xk si se cauta un prim element xk+2IAk+2.

B)          nu le indeplineste, caz in care se reia algoritmul considerand generate elementele x1, x2, …, xk, iar elementul xk+1 se cauta intre elementele multimii Ak+1 ramase netastate.

   Algoritmul se termina atunci cand nu mai exista nici un element x1IA1, netastat.

   Observatie: tehnica Backtracking are ca rezultat obtinerea tuturor solutiilor problemei. In cazul in care se cere o singura solutie, se poate forta oprirea, atunci cand a fost gasita.

   Pentru usurarea intelegerii metodei, vom prezenta o rutina unica, aplicabila oricarei probleme, rutina care utilizeaza notiunea de stiva. Rutina va apela proceduri si functii care au intotdeauna acelasi nume si parametri si care, din punct de vedere al metodei, realizeaza acelasi lucru. Sarcina rezolvitorului este de a scrie explicit, pentru fiecare problema in parte, procedurile si functiile apelate de rutina backtracking. Evident, o astfel de abordare conduce la programe lungi. Nimeni nu ne opreste, ca dupa intelegerea metodei, sa scriem programe scurte, specifice fiecareI probleme in parte (de exemplu, scurtam substantial textul doar daca renuntam la utilizarea procedurilor si functiilor).

   Am aratat ca orice solutie se genereaza sub forme de vector. Vom considera ca generarea solutiilor se face intr-o stiva. Astfel, x1IA1, se va gasi pe primul nivel al stivei, x2I A2 se va gasi pe al doilea nivel al stivei, … xk IAk  se va gasi pe nivelul k al stvei. In acest fel, stiva (notata ST) va arata ca mai jos:

                                                        ST

   Nivelul k+1 al stivei trebuie initializat (pentru a alege, in ordine, elementele multimii k+1). Initializarea trebuie facuta cu o valoare aflata (in relatia de ordine considerata pentru multimea Ak+1 ), inaintea tuturor valorilor posibile din multime. De exemplu, pentru generarea permutarilor multimii , orice nivel al stivei va lua valori de la 1 la n. Initializarea unui nivl (oarecare) se face cu valoarea 0. Procedura  de initializare o vom numi INIT si va avea doi parametri: k (nivelul care trebuie initializat si ST stiva).

   Gasirea urmatorului element al multimii Ak  (element care nu a fost tastat) se face cu ajutorul procedurii SUCCESOR (AS,ST,K). Parametrul AS (am succesor) esteb o variabila booleana. Insituatia in care am gasit elementul, acesta este pus in stiva si AS ia valoarea TRUE, contrar (nu a ramas un element netastat) AS ia valoarea FALSE.

   Odata ales un element, trebuie vazut daca acesta indeplineste conditiile de continuare (altfel spus, daca elementul este valid). Acest test se face cu alutorul procedurii VALID (EV,ST,K).

   Testul daca s-a ajuns sau nu la solutia finala se face cu ajutorul  functiei SOLUTIE(K), iar o solutie se tipareste cu ajutorul procedurii TIPAR.

Prezentam in continuare rutina backtracking:

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

 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(k,st)

                  end

         else k:=k-1

      end;

Observatie:

   Problemele rezolvate prin aceasta metoda necesita un timp indelungat. Din acest motiv, este bine sa utilizam metoda numai atunci cand nu avem la dispozitie un alt algoritm mai eficient. Cu toate ca exista probleme pentru care nu se pot elabota alti algoritmi mai eficienti, tehnica Backtracking trebuie aplicata numai in ultima instanta.

   In continuare prezentam mai multe probleme rezolvate prin aceasta metoda.

1.3.   Backtracking elementar

   Denumirea din titlu este folosita pentru a desemna utilizarea tehnicii backtrackingpentru nprobleme la care solutia este sub forma de vector, altfel spus, probleme pentru care stiva are latimea 1. Tot asa, exista probleme pentru care se foloseste stiva dubla, tripla (numite in programa probleme de backtracking in plan). In ce ne priveste, daca tot trebuie sa le ‘botezam’, le vom numi probleme de backtracking generalizat.

1.3.1.   Generarea permutarilor

Se citeste un numar natural n. Sa se genereze toate permutarile multimii .

Definitie. Vom numi permutare a multimii A= o functie bijectiva definita pe A cu valori in A.

   Exemplu: A=,  o permutare este (2,1,3).

Generarea permutarilor se va face tinand cont ca orice pemutare va fi alcatuita din elemente distincte ale multimii A. Din acest motiv, la generarea unei permutari, vom urmari ca numerele sa fie distincte.

Prezentam algoritmul corespunzator cazului n=3:


        se incarca in stiva pe nivelul 1 valoarea 1;

        incarcarea valorii 1 pe nivelul al 2-lea nu este posibila, intrucat aceasta valoare se gaseste si pe nivelul 1 al stivei;

        incarcarea valorii 2 pe nivelul al 2-lea este posibila, deoarece aceasta valoare nu mai este intalnita;

        valoarea 1 din nivelul al 3-lea se regaseste pe nivelul 1;

        valoarea 2 din nivelul al 3-lea se regaseste pe nivelul al 2-lea;

        valoarea 3 pe nivelul al 3-lea nu e intalnita pe nivelurile anterioare;

Intrucat nivelul 3 este completat corect. tiparim: 1 2 3   

Algoritmul continua pana cand stiva devine vida.

program permutari;

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

var st:stiva;

    n,k:integer;

    as,ev:boolean;

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

begin

 st[k]:=0;

end;

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

begin

if st[k]<n

 then

  begin

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

     as:=true

  end

 else as:=false

end;

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

var i:integer;

begin

 ev:=true;

 for i:=1 to k-1 do if st[k]=st[i] then ev:=false

end;

function solutie(k:integer):boolean;

begin

 solutie:=(k=n)

end;

procedure tipar;

var i:integer;

begin

 for i:=1 to n do write(st[i]);

 writeln

end;

begin

 write('N= ');readln(n);

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

 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(k,st)

                  end

         else k:=k-1

      end

end.

 1.3.2.   Problema celor n dame

 Fiind data o tabla de sah, de dimensiune n*n, se cer toate solutiile de aranjare a n dame, astfel incat sa nu se afle doua dame pe aceeasi linie, coloana sau diagonala (damele sa nu se atace reciproc).

  Exemplu: presupunand ca dispunem de o tabla de dimensiune 4*4, o solutie ar fi urmatoarea:

D

D

D

D

   Cum procedam? Observam ca o dama trebuie sa fie plasata singura pe linie. Plasam prima dama pe linia 1, coloana 1.

D

   A doua dama nu poate fi asezata decat in    coloanaa-3-a.

D

D

   Observam ca a treia dama nu poate fi plasata in linia a-3-a. Incercam atunci plasarea celei de-a doua dame in coloana a-4-a.

D

D

   A treia dama nu poate fi plasata decat in coloana a-2-a.

D

D

D

  

     In aceasta situatie dama a patra nu mai poate fi asezata.

   Incercand sa avansam cu dama a treia, observam ca nu este posibil sa o plasam nici in coloana a-3-a, nici in coloana a-4-a, deci o vom scoate de pe tabla. Dama a doua nu mai poate avansa, deci si ea este scoasa de pe tabla. Avansam cu prima dama in coloana a-2-a.

D

 A doua dama nu poate fi asezata decat in colana a-4-a.

D

D

   Dama a treia se aseaza in prima coloana.

D

D

D

Acum este posibil sa plasam a patra dama in coloana a-3-a si astfel am obtinut o solutie a problemei.

D

D

D



   Algoritmul continua in acest mod pana cand trebuie scoasa de pe tabla prima dama.

   Pentru reprezentarea unei solutii putem folosi un vector cu n componente (avand in vedere ca pe fiecare linie se gaseste o singura dama).



   Intrucat doua dame nu se pot gasi in aceeasi coloana, rezulta ca o solutie este sub forma de permutare. O prima idee ne conduce la generarea tuturor permutarilor si la extragerea solutiilor pentru problema (ca doua dame sa nu fie plasate in aceeasi diagonala). A proceda astfel, inseamna ca lucram conform strategiei backtracking. Aceasta presupune ca imediat ce am gasit doua dame care se ataca, sa reluam cautarea. fata de programul de generare a tuturor solutiilor problemei celor n dame, are o singura conditie suplimentara, in procedura VALID.

Semnificatia procedurilor este urmatoarea:

      INIT – nivelul k al stivei este initilizat cu 0;

      SUCCESOR – mareste cu 1 valoarea aflata pe nivelul k al stivei in situatia un care aceasta este mai mica decat n si atribuie variabilei EV valoarea TRUE; in caz contrar, atribuie variabilei EV valoarea FALSE;

     VALID – valideaza valoarea pusa pe nivelul k al stivei, verificand daca nu avem doua dame pe aceeasi linie (|st(k)-st(i)|=|k-i|), caz in care variabilei EV i se atribuie FALSE, in caz contrar, variabilei EV i se atribuie TRUE;

     SOLUTIE – verifica daca stiva a fost completata pana la nivelul n inclusiv;

     TIPAR – tipareste o solutie.

program dame;

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

var st:stiva;

    n,k:integer;

    as,ev:boolean;

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

begin

 st[k]:=0;

end;

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

begin

if st[k]<n

 then

  begin

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

     as:=true

  end

 else as:=false

end;

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

var i:integer;

begin

 ev:=true;

 for i:=1 to k-1 do

    if (st[k]=st[i]) or(abs(st[k]-st[i])=abs(k-i)) then

 ev:=false

end;

function solutie(k:integer):boolean;

begin

 solutie:=(k=n)

end;

procedure tipar;

var i:integer;

begin

 for i:=1 to n do write(st[i]);

 writeln

end;

begin

 write('N= ');readln(n);

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

 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(k,st)

                  end

         else k:=k-1

      end

end.

1.3.3.   Produsul cartezian a n multimi

Se dau multimile:

     A1=,

     A2=,

     …………………

    An=.

Se cere produsul catezian a celor n multimi.

    

   Exemplu: A1=, A2=, A3=.

A1*A2*A3=

   Pentru rezolvare se foloseste stiva ST si un vector A ce retine numerele k1,k2,…,kn. Utilizam metoda backtracking , usor modificata, din urmatoarele motive:

a) orice element aflat pe nivelul k al stivei este valid, motiv pentru care procedura VALID nu face altceva decat sa atribuie variabilei EV valoaree TRUE;

b) limita superioara pe nivelul k al stivei este data de A(k).

Observatie:

    - problema admite o rezolvare fara a cunoaste metoda backtracking, dar am preferat aceasta metoda din dorinta de a o rezolva standardizat. 

program produs-cartez;

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

var st:stiva;

    i,n,k:integer;

    as,ev:boolean;

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

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

begin

 st[k]:=0;

end;

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

begin

if st[k]<a[k]

 then

  begin

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

     as:=true

  end

 else as:=false

end;

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

begin

 ev:=true;

end;

function solutie(k:integer):boolean;

begin

 solutie:=(k=n)

end;

procedure tipar;

var i:integer;

begin

 for i:=1 to n do write(st[i]);

 writeln

end;

begin

 write('Numarul de multimi= ');readln(n);

 for i:=1 to n do

   begin

    write('a[',i,']=');

    readln(a[i])

   end;

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

 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(k,st)

                  end

         else k:=k-1

      end

end.

1.3.4.   Problema colorarii hartilor

   Fiind data o harta cu n tari, se cer toate solutiile de colorare a hartii, utilizand cel mult 4 culori, astfel incat doua tari cu frontiera comuna sa fie colorate diferit. Este demonstrat faptul ca sunt suficiente numai 4 culori pentru ca orice harta sa poata fi colorata.

   Pentru exemplificare, vom considera urmatoarea harta unde tarile sunt numerotate cu cifre cuprinse intre 1 si 5:

1,3,2,5,4


   O solutie a acestei probleme, este urmatoarea:

·         tara 1 – culoarea 1;

·         tara 2 – culoarea 2;

·         tara 3 – culoarea 1;

·         tara 4 – culoarea 3;

·         tara 5 – culoarea 4;

   Harta este furnizata programului cu ajutorul unei matrici An,n.

                 1, daca tara i se invecineaza cu tara j,

    A(i,j)=

                 0, in caz contrar.

   Matricea A este simetrica. Pentru rezolvarea problemei se utilizeaza stiva st, unde nivelul k al stivei simbolizeaza tara k, iar st[k] culoarea atasata tarii k. Stiva are inaltimea n si pe fiecare nivel ia valori intre 1 si 4.

      Prezentam algoritmul pe exemplul dat:

           

1

 
 tara 1 capata culoarea 1;

1

 
          

1

 
 tara 2 nu poate avea culoarea 1, intrucat se invecineaza cu tara 1,re are aceeasi culoare;

           

2

 
pentru tara 2, culoarea 2 este potrivita, caz in care se urca in stiva;

1

 

1

 


2

 
            tara trei poate avea culoarea 1 (nu se invecineazacu tara 1 ce are   aceeasi culoare), deci se va urca in stiva;

1

 


   Algoritmul continua pana cand stiva este vida. La validarea unui succesor pe nivelul k (tara k), se verifica daca exista o tara situata pe un nivel inferior, cu aceeasi culoare. In rest, se aplica algoritmul clasic backtracking.

program colorare;

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

var st:stiva;

    i,j,n,k:integer;

    as,ev:boolean;

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

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

begin

 st[k]:=0;

end;

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

begin

if st[k]<4

 then

  begin

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

     as:=true

  end

 else as:=false

end;

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

begin

 ev:=true;

 for i:=1 to k-1 do if (st[i]=st[k]) and (a[i,k]=1) then ev:=false

end;

function solutie(k:integer):boolean;

begin

 solutie:=(k=n)

end;

procedure tipar;

var i:integer;

begin

 for i:=1 to n do writeln('Tara=',i,'; culoarea=',st[i]);

 writeln('--------------')

end;

begin

 write('Numarul de tari= ');readln(n);

 for i:=1 to n do

     for j:=1 to i-1 do

       begin     write('a[',i,',',j,']=');readln(a[i,j]);

         a[j,i]:=a[i,j]

       end;

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

 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(k,st)

                  end

         else k:=k-1

      end

end.

1.3.5   Problema comis-voiajorului

   Un comis-voiajor trebuie sa viziteze un numar n de orase. Initial, acesta se afla intr-unul dintre ele, notat cu 1. Comis-voiajorul doreste sa nu treaca de doua ori prin acelasi oras, iar la intoarcere sa revina in orasul 1. Cunoscand legaturile existente intre  orase, se cere sa se tipareasca toate drumurile posibile pe care le poate efectua comis-voiajorul.

     Exemplu: in figura alaturata sunt simbolizate cele 6 orase, precum si drumurile existente intre ele.


Comis-voiajorul are urmatoarele posibilitati de parcurgere:



·         1,2,3,4,5,6,1;

·         1,2,5,4,3,6,1;

·         1,6,3,4,5,2,1;

·         1,6,5,4,3,2,1.

Legaturile existente intre orase sunt date in matricea An,n..

Elementele matricei A pot fi 0 sau 1 (matricea este binara).

             1, daca exista drum intre orasul I si j,

A(i,j)=

             0, in caz contrar.

   Se observa ca A(i,j)=A(j,i), oricare ar fi i si j apartinand multimii (matricea este simetrica)

  

   Pentru rezolvarea problemei folosim o stiva ST. La baza stivei (nivelul 1) se incarca numarul 1. Prezentam in continiare modul de rezolvare a problemei:

2

 


1

 
         dela orasul 1 la orasul 2 exista drum, deci se va urca in     stiva;

2

 


  

2

 
         orasul 2 se mai gaseste in stiva, deci nu este acceptat;

1

 
 

3

 


1

 

2

 
         de la orasul 2 la orasul 3 exista drum, prin orasul 3 nu s-a   mai trecut, deci orasul 3 este acceptat;

Algoritmul continua in acest mod pana se ajunge din nou la nivelul 1, caz in care algoritmul se incheie.

Un succesor, intre 2 si n, aflat pe nivelul k al stivei, este considerat valid , daca sunt indeplinite urmatoarele conditii:

·         nu s-a mai trecut prin orasul simbolizat de succesor , deci acesta nu se regaseste in stiva;

·         exista drum intre orasul aflat pe nivelul k-1 si cel aflat pe nivelul k;

·         daca succesorul se gaseste pe nivelul n, sa existe drum de la el la orasul 1.

program comis-voiajor;

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

var st:stiva;

    i,j,n,k:integer;

    as,ev:boolean;

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

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

begin

 st[k]:=1;

end;

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

begin

if st[k]<n

 then

  begin

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

     as:=true

  end

 else as:=false

end;

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

var i:integer;

begin

 ev:=true;

 if a[st[k-1],st[k]]=0

   then ev:=false

   else

     for i:=1 to k-1 do

             if st[i]=st[k] then ev:=false;

     if (k=n) and (a[1,st[k]]=0) then ev:=false

end;

function solutie(k:integer):boolean;

begin

 solutie:=(k=n)

end;

procedure tipar;

var i:integer;

begin

 for i:=1 to n do writeln('Nodul=',st[i]);

 writeln('--------------')

end;

begin

 write('Numarul de noduri= ');readln(n);

 for i:=1 to n do

     for j:=1 to i-1 do

       begin      write('a[',i,',',j,']=');readln(a[i,j]);

         a[j,i]:=a[i,j]

       end;

st[1]:=1;k:=2;

 init(k,st);

 while k>1 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(k,st)

                  end

         else k:=k-1

      end

end.

1.3.6   Partitiile unui numar natural

   Se citeste un numar natural n. Se cere sa se tipareasca toate modurile de drscompunere a sa ca suma de numere naturale.

   Exemplu: n=4.   Avem: 111, 112, 121, 13, 211, 22, 31, 4.

   Observatie:   Ordinea numerelor din suma este importanta. Astfel, se tipareste 112 dar si 211, 121.

   Pentru rezolvare, vom observa ca nivelul 1 al stivei ia valori intre 1 si n, nivelul 2 ia valori intre 1 si n-1, in general nivelul k ia valori intre 1 si n-k-1 (SUCCESOR). O solutie partiala este valida daca suma elementelor pe care le contine este mai mica sau egala cu n (VALID) si am obtinut o solutie atunci cand aceasta suma este egala cu n.

program partitii_n;

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

var st:stiva;

    n,k,s:integer;

    as,ev:boolean;

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

begin

 st[k]:=0;

end;

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

begin

if st[k]<n-k+1

 then

  begin

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

     as:=true

  end

 else as:=false

end;

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

var i:integer;

begin

 s:=0;

 for i:=1 to k do s:=s+st[i];

 if s<=n then ev:=true

         else ev:=false;

end;

function solutie(k:integer):boolean;

begin

 solutie:=(s=n)

end;

procedure tipar;

var i:integer;

begin

 for i:=1 to k do write(st[i]);

 writeln

end;

begin

 write('N= ');readln(n);

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

 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(k,st)

                  end

         else k:=k-1

      end

end.

1.3.6                Generarea partitiilor unei multimi

 

   Se considera multimea . Se cer toate partitiile acestei multimi.

   Amintim ca submultimile A1,A2,…,Ak, ale unei multimi A constituie o partitie a acesteia, daca sunt disjuncte  intre ele (nu au elemente comune) si multimea rezultata in urma reuniunii lor este A.

   O partitie a multimii se poate reprezenta sub forma unui vector ST cu n componente. ST(i)=k are semnificatia ca elementul i al multimii considerate apartine submultimii k a partitiei.

     Exemplu: A=, ST=, reprezinta partitia: , . O partitie a unei multimi cu n elemente este unic formata din cel mult n multimi distincte, caz in care fiecare element al multimii este unic in submultimea sa. Rezulta, de aici, ca ST(i) apartine multimii .

   In realitate, pentru a evita repetitia partitiilor, facem conventia:

   ST(1) – ia numai valoarea 1;

   ST(2) – ia valorile 1,2;

   …………………….

   ST(n) – ia valorile 1,2,…,n.

 

   Aceasta inseamna ca elementul 1 va apartine numai submultimii 1 a partitiei, elementul 2 va apartine submultimii 1 sau 2 a partitiei, etc. O alta cerinta este cceea ca oricare ar fi i ce apartine multimii , sa existe j apartinand aceleiasi multimi, astfel incat modulul diferentei dintre ST[i] si ST[j] sa fie cel mult egtal cu 1. aceasta corespunde faptului ca submultimile unei partitii se numeroteaza cu numere consecutive.

 

   Contraexemplu: A=, ST= ar avea semnificatia ca prima multime a partitiei este , iar a treia multime est , in acest caz neexistand multimea a doua.

   Demonstram ca intre multimea vectorilor ST generati in acest mod si multimea partitiilor multimii exista o corespondenta biunivoca.

Fie o partitie oarecare a multimii considerate. Construim vectorul ST astfel:

·          pentru toate elementele i care se gasesc in aceeasi multime cu elementul 1, ST(i) capata valoarea 1;

·          pornind de la elementul 2 si considerand elementele in ordine crescatoare, se cauta primul element care nu apartine submultimii unde3 se gaseste elementul 1;

·          pentru aceasta, ca si pentru toate elementele care sunt in submultime cu el, ST(i) va lua valoarea 2;

·         incepand cu elementul 3 si considerand elementele in ordine crescatoare, se cauta primul element care nu apartine primelor doua submultimi;

   Procedeul continua in acest mod, pana cand sunt analizate toate elementele multimii considerate. In acest mod, am demonstrat ca aceasta corespondenta este surjectiva. Pe de alta parte, la doua valori diferite ale vectorului ST corespund partitii diferite, deci corespondenta este injectiva.

   Suntem asadar in masura sa generam toate partitiile unei multimi , generand toate valorile posibile vectorului ST, in procedura TIPAR se tiparesc succesiv partitiile obtinute.

   Pentru generarea valorilor vectorului ST, se foloseste metoda backtracking. Din acest motiv vectorul ST este privit ca stiva. Elementul aflat pe nivelul k al stivei se poate majora pana la maximul dintre precedentele, plus 1. Avem solutie cand am gasit succesorul pe nivelul n.

  

program partitii;

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

var st:stiva;

    n,k:integer;

    as,ev:boolean;

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

begin

 st[k]:=0;

end;

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

var max,i:integer;

begin

if k=1

   then max:=1

   else

     begin

      max:=st[1];

      for i:=2 to k-1 do

        if max<st[i] then max:=st[i]

     end;

if (st[k]<max+1) and (st[k]<k)

   then

    begin

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

     as:=true

    end

   else as:=false

end;

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

begin

 ev:=true;

end;

function solutie(k:integer):boolean;

begin

 solutie:=(k=n)

end;

procedure tipar;

var i,max,j:integer;

begin

 max:=st[1];

 for i:=2 to n do if max<st[i] then max:=st[i];

 writeln('------  PARTITIE-------');

 for j:=1 to max do

   begin

    for i:=1 to n do

     if st[i]=j then write(i);

    writeln

    end

end;

begin

 write('N= ');readln(n);

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

 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(k,st)

                  end

         else k:=k-1

      end

end.

      








Politica de confidentialitate

.com Copyright © 2019 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 PROIECT DE LECTIE Clasa: I Matematica - Adunarea si scaderea numerelor naturale de la 0 la 30, fara trecere peste ordin
 Proiect didactic Grupa: mijlocie - Consolidarea mersului in echilibru pe o linie trasata pe sol (30 cm)
 Redresor electronic automat pentru incarcarea bateriilor auto - proiect atestat
 Proiectarea instalatiilor de alimentare ale motoarelor cu aprindere prin scanteie cu carburator

Lucrari de diploma

vezi toate lucrarile de diploma
 Lucrare de diploma - eritrodermia psoriazica
 ACTIUNEA DIPLOMATICA A ROMANIEI LA CONFERINTA DE PACE DE LA PARIS (1946-1947)
 Proiect diploma Finante Banci - REALIZAREA INSPECTIEI FISCALE LA O SOCIETATE COMERCIALA
 Lucrare de diploma managementul firmei “diagnosticul si evaluarea firmei”

Lucrari licenta

vezi toate lucrarile de licenta
 CONTABILITATEA FINANCIARA TESTE GRILA LICENTA
 LUCRARE DE LICENTA - FACULTATEA DE EDUCATIE FIZICA SI SPORT
 Lucrare de licenta stiintele naturii siecologie - 'surse de poluare a clisurii dunarii”
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine

Proiecte de atestat

vezi toate proiectele de atestat
 Proiect atestat informatica- Tehnician operator tehnica de calcul - Unitati de Stocare
 LUCRARE DE ATESTAT ELECTRONIST - TEHNICA DE CALCUL - Placa de baza
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 Proiect atestat tehnician in turism - carnaval la venezia






Termeni si conditii
Contact
Creeaza si tu