воскресенье, 25 марта 2012 г.


SUBPROGRAME


SUBPROGRAMUL reprezinta parti identificabile prin nume care se pot activa la cerere prin intermediul acetui nume. O parte din subprogram se contruieste ca subprogram daca un algoritm cuprinde in mai multe locuri aceiasi secventa de operatii executabila pentru aceleasi date sau pentru date diferite. In loc ca subprogramul sa cuprinda in acelasi loc, acelasi  grup de instructiuni, concepand grupul de intructiuni ca subprogram, el va aparea in program o singura data si se va activa de mai multe ori. Partea respectiva de program rezolva o subproblema din cele in care se descompune problema complexa. In limbajul Pascal, avem doua tipuri de subprograme : procedurile si functiile. Deosebirea intre ele consta in numarul de valori calculate si returnate programului apelat. Procedurile calculeaza mai multe valori sau nici una, iar functiile returneaza o singura valoare asociata numelui functiei. Atat procedurile cat si functiile pot fi standard(predefinite in unitul sistem), cat si nestandard(definite de utilizator). Procedurile si functiile nestandard trebuie declarate obligatoriu inainte de a fi apelate.
O declaratie de subprograme cuprinde:
-un antet de supbrogram care precizeaza interfata subprogramului cu mediul sau, si
- blocul subprogramului care descrie functionarea lui interna.


 DOMENIUL DE VIZIBILITATE AL INDENTIFICATORILOR

         Prin domeniul de vizibilitate (valabilitate) se intelege zona de program in care e valabila declararea sau definirea unui identificator. Toti indentificatorii definiti sau declarati intr-un bloc sunt cunoscuti in blocul respectiv si se numesc variabile locale. Daca blocul cuprinde blocuri incluse in care identificatorii (variabile locale ale acestora) nu se definesc sau redenumesc, atunci acestea sunt cunoscute in blocurile incluse si se numesc variabile globale pentru acesta. Daca o variabila declarata intr-un bloc se redefineste atunci in blocul in care a fost redeclarata va fi variabila atribuita generata la redeclarare.


DECLARAREA SI APELUL PROCEDURILOR. PARAMETRII FORMALI SI PARAMETRII EFECTIVI

            O procedura e un sunbrogram care calculeaza mai multe valori accesibile sau nu programului apelant sau efectueaza anumite operatii fara sa calculeze vreo valoare. Valorile calculate accesibile programului apelant reprezinta parametrii de iesire ai subprogramului. Acestia pot depinde de anumite valori pe care subprogramul le primeste din programul apelant, valori reprezentand parametrii de intrare. Parametrii formali sunt variabile simbolice in care lucreaza subprogramul. Ele sunt declarate in antetul subprogramului si sunt cunoscute numai in interiorul subprogramului. La apelarea procedurii se specifica parametrii efectivi sau actuali prin intermediul instructiunii procedurale. Parametrii efectivi reprezinta variabilele cu care subprogramele lucreaza efectiv in momentul activarii.
Declararea procedurii se face folosind:
PROCEDURE  nume_procedura(lista parametrii)
-parametrii precizati la scrierea proedurii sunt parametrii formali si se separa prin ‘ ; ’
-pentru fiecare parametru se precizeaza numele si tipul acestuia.

Apelarea procedurii :
Pentru a executa o procedura aceasta trebuia apelata. La apel se da numele procedurii si valorile concrete ale parametrilor care se separa prin punct si virgula.

Ex :  procedure citire(n :integer ; k :char) ;
Begin
…..
end;

Cand se apeleaza o procedura, modulul apelant a abandonat temporar, si se executa procedura. In timpul executiei procedurii, parametrii formali sunt inlocuiti in tot corpul procedurii cu parametrii actuali (valori concrete). Dupa executarea procedurii se revine in modulul apelant la linia imediat urmatoare celei care a facut apelul. Parametrii formali si parametrii efectivi nu e obligatoriu sa aiba acelasi nume dar trebuie sa existe o concordanta de numar, tip si ordine.

 DECLARAREA SI APELUL FUNCTIILOR

           O functie e un subprogram care calculeaza si returneaza programului apelant o singula valoare. Aceasta valoare este asociata numelui functiei. Iar tipul poate fi simplu, string sau reper. Valoarea returnata de functie nu poate avea alt tip structurat decat string.
Declararea unei functii:
FUNCTION nume_functie(lista parametrii formali): identificator de tip;
-nume_functie reprezinta numele functiei, al carei tip este ‘identificator de tip’
-identificator de tip = nume de tip simplu: STRING sau REPER;
Blocul functiei trebuie sa contina obligatoriu o instructiune de atribuire prin care identificatorul functiei primeste valoarea unei expresii.
Identificatorul functiei nu are voie sa apara in partea dreapta a unor atribuiri decat daca functia este recursiva.

Apelul unei functii decurge astfel:
     - se intrerupe calculul expresiei in care a aparul apelul functiei ;
- se transmit parametrii, daca exista, exact ca la proceduri ;
- se executa functia;



METODA BACKTRACKING


Se aplica problemelor in care solutia poate fi reprezentata sub forma unui vector - x=(x1, x2, x3, …xk,… xn) € S, unde S este multimea solutiilor problemei si S=S1 x S2 x… x Sn, si Si sunt multimi finite avand s elemente si xi € si , (?)i = 1..n.
Pentru fiecare problema se dau relatii intre componentele vectorului x, care sunt numite conditii interne ; solutiile posibile care satisfac conditiile interne se numesc solutii rezultat. Metoda de generare a tuturor solutiilor posibile si apoi de determinare a solutiilor rezultat prin verificarea indeplinirii conditiilor interne necesita foarte mult timp.
Metoda backtracking evita aceasta generare si este mai eficienta. Elementele vectorului x, primesc pe rand valori in oridinea crescatoare a indicilor, x[k] va primi o valoare numai daca au fost atribuite valori elementelor x1.. x[k-1]. La atribuirea valorii lui x[k] se verifica indeplinirea unor conditii de continuare referitoare la x1…x[k-1]. Daca aceste conditii nu sunt indeplinite, la pasul k, acest lucru inseamna ca orice valori i-am atribui lui x[k+1], x[k+1], .. x[n] nu se va ajunge la o solutie rezultat.
Metoda backtracking construieste un vector solutie in mod progresiv incepand cu prima componenta a vectorului si mergand spre ultima cu eventuale reveniri asupra atribuirilor anterioare.
Metoda se aplica astfel :
1) se alege prima valoare sin S1 si I se atribuie lui x1 ;
2) se presupun generate elementele x1…x[k-1], cu valori din S1..S[k-1]; pentru generarea lui x[k] se alege primul element din S[k] disponibil si pentru valoarea aleasa se testeaza indeplinirea conditiilor de continuare.
Pot aparea urmatoarele situatii :
a) x[k] indeplineste conditiile de continuare. Daca s-a ajuns la solutia finala (k=n) atunci se afiseaza solutia obtinuta. Daca nu s-a ajuns la solutia finala se trece la generarea elementului urmator - x[k-1] ;
b) x[k] nu indeplineste conditiile de continuare. Se incearca urmatoarea valoare disponibila din S[k]. Daca nu se gaseste nici o valoare in S[k] care sa indelineasca conditiile de continuare, se revine la elementul x[k-1] si se reia algoritmul pentru o noua valoare a acestuia. Algoritmul se incheie cand au fost luate in considerare toate elementele lui S1.
Problemele rezolvate prin aceata metoda necesita timp mare de executie, de aceea este indicat sa se foloseasca metoda numai daca nu avem alt algoritm de rezolvare.
Daca multimile S1,S2,…Sn au acelasi numar k de elemente, timpul necesar de executie al algoritmului este k la n. Daca multimile S1, S2.. Sn nu au acelasi numar de elemente, atunci se noteaza cu ‘m’ minimul cardinalelor multimilor S1..Sn si cu ‘M’, maximul. Timpul de executie este situat in intervalul  [m la n .. M la n]. metoda backtracking are complexitatea exponetiala, in cele mai multe cazuri fiind ineficienta. Ea insa nu poate fi inlocuita cu alte variante de rzolvare mai rapide in situatia in care se cere determinarea tuturor solutiilor unei probleme.



RECURSIVITATE


Prin recursivitate se intelege faptul ca un subprogram se apeleaza pe el insusi, apelul aparand atunci cand subprogramul este inca activ. Exista doua tipuri de recursivitate:
1) recursivitate directa - cand un subprogram se autoapeleaza in corpul sau ;
2) recursivitate indirecta - cand avem doua subprograme (x si y), iar x face appel la y si invers ;

Se folosesc algoritmi recursivi  atunci cand calculele aferente sunt descrise in forma recursiva.
Recursivitatea este frecvent folosita in prelucrarea structurilor de date definite recursiv. Un subprogram recursiv trebuie scris astfel incat sa respecte regulile :
a) Subprogramul trebuie sa poata fi executat cel putin o data fara a se autoapela ;
b)Subprogramul recursiv se va autoapela intr-un mod in are se tinde spre ajungerea in situatia de executie fara autoapel.

Pentru a permite apelarea recursiva a subprogramelor, limbajul Pascal dispune de mecanime speciale de suspendare a executiei programului apelant, de salvare a informatiei necesare si de reactivare a programului suspendat .
Pentru implementarea recursivitatii se foloseste o zona de memorie in care se poate face salvarea temporala a unor valori. La fiecare appel recursiv al unui subprogram se salveaza in aceasta zona de memorie starea curenta a executiei sale.
Desi variabilele locale ale subprogramului apelant au aceleasi nume  cu cele ale subprogramului apelat, orice referire la acesti identificatori se asociaza ultimului set de valori alocate in zona de memorie. Zona de memorie ramane alocata pe tot parcursul executie subprogramului apelat si se dealoca in momentul revenirii in programul apelat. Zona de memorie nu este gestionata explicit de programator ci de catre limbaj.
La terminarea executiei subprogramului apelat recursiv, se reface contextul programului din care s-a facut apelul. Datorita faptului ca la fiecare autoapel se ocupa o zona de memorie, recursivitatea este eficienta numai daca numarul de autoapelari nu este prea mare pentru a nu se ajunge la umplerea zonei de memorie alocata.
Recursivitatea ofera avantajunl unor solutii mai clare pentru probleme si a unei lungimi mai mici a programului. Ea prezinta  insa dezavantajul unui timp mai mare de executie si a unui spatiu de memorie alocata ami mare. Este de preferat ca atunci cand programul recursiv poate fi transformat intr-unul iterativ sa se faca apel la cel din urma.


descompunerea problemei de rezolvat in subprobleme si rezolvarea fiecarei subprobleme printr-un subprogram separat;
-existenta unor subprograme predefinite;
-daca un program are anumite secvente care se repeta,atunci se poate asocia secventei un subprogram si in loc sa scriem secventa de mai multe ori vom folosi subprogramul;

In Pascal subprogramele sunt de 2 tipuri:-proceduri si functii.


Procedurile

Procedurile sunt subprograme care pot calcula si returna mai multe valori sau niciuna.
Sintaxa:-intre var si begin principal.

procedure nume_procedura(lista_paramatrii_formali_optional);
  {sectiune de declaratii locale:tipuri de variabile,constante,subprograme;}
 begin
{instructiuni(corpul procedurii)}
end;

Apelul unei proceduri se realizeaza intr-o instructiune procedurala astfel:
   nume_procedura(lista_parametrii_efectivi_sau_actuali);

Obs!Listele de parametrii formali si efectivi trebuie sa corespunda ca numar,pozitie,tip.



FUNCTII

O functie calculeaza si returneaza o valoare.
Sintaxa:

function nume_functie(lista,parametrii,formali):tip_rezultat_valoare_returnata;
   declaratii_locale(variabile,tipuri locale)
  begin
  {instructiuni}
  end;

Obs!O functie returneaza o valoare.Tipul rezultatului poate fi unul dintre tipurile simple(toate tipurile numerice:real,char,boolean),iar dintre tipurile structurate doar tipul string.

Obs!Functia returneaza o valoare prin intermediul numelui ei.Din acest motiv una dintre instructiunile functiei trebuie sa fie o instructiune de atribuire cu numele functiei in partea stanga.
Numele functiei nu poate apare deocamdata in partea dreapta a instructiunii(apel recursiv).

Obs!O functie se apeleaza intr-o expresie prin : nume_functie(lista,parametrii,actuali,sau,efectivi);

RECURSIVITATE


O definitie este recursiva daca in cadrul definitiei apare chiar notiunea care se defineste.
   Ex~!Un descendent al unei persoane este un copil al acesteia sau un descendent al unui copil al acesteia.
   Ex~1!
    S(n)=1,daca x=0
             S(n-1)+S(n-2),daca x<>0

O definitie recursiva trebuie sa indeplineasca urmatoarele doua conditii:
  -trebuie sa existe cazuri elementare in care valoarea sa se calculeze direct
  -si ca fiecare dintre cazuruile ne-elementare sa se reduca in cele din urma la un caz elementar
In informatica recursivitatea se realizeaza cu ajutorul subprogramelor;vom avea functii si proceduri recursive.
Un subprogram este recursiv daca se realizeaza un autoapel al lui direct sau indirect prin intermediul altor subprograme.
     Ex! n!=1*2*3*..*n;
   
   function factorial(n:byte):longint;
     begin
     if n=0 then factorial:=1
             else
                  factorial:=n*factorial(n-1);
     end;
-este mai neeficienta datorita apelului functiei;
OBS!Aceasta functie recursiva este putin mai eficienta decat o functie iterativa care ar calcula factorialul,aceasta datorita apelului din functie,transferului de parametrii si a revenirilor din apel.

OBS!Daca o functie se apeleaza la infinit,are loc recursivitatea infinita,si practic se ocupa stiva(zona de memorie alocata programului).


PROCEDURI RECURSIVE

         Secventa din subprogramele recursive aflate dupa instructiunea de autoapel se va executa in ordinea inversa a apelurilor.

Conversia unui numar  intr-o baza b

procedure conb(n:word);
    begin
     if n div b<>0 then conv(n div b);
     write(n mod b);
     end;
  conv(n);


PARAMETRII POT FI DE 2 TIPURI:-PRIN REFERINTA: "VAR"-PRIN VALOARE:FARA VAR;

Pentru parametrii prin referinta schimbarile asupra parametrilor se pastreaza la parasirea subprogramului,iar prin valoare in stiva se face o copie a valorii parametrului,iar schimbarile din subprogram se fac asupra copiei,nu asupra variabilei insasi.

OBS!Cand avem tipuri ce solicita o zona de memorie mai mare(vectori,inregistrari,matrice),atunci este de preferat sa utilizam nu o copie a parametrului,ci sa il declaram prin referinta,deoarece ocupa o zona de memorie mai mica astfel!..

METODA "DIVIDE  ET  IMPERA"

Prezentarea generala a metodei

  Metoda "Divide et impera " se poate aplica in rezolvarea unei probleme care indeplineste urmatoarele conditii:
 -se poate descompune (in doua sau mai multe) subprobleme;
 -aceste subprobleme sunt independente una fata de alta(o subproblema nu se rezolva pe baza alteia si nu foloseste rezultatele celeilalte)
 -aceste subprobleme sunt similare(asemanatoare) cu problema initiala;
 -aceste subprobleme sunt de dimensiuni mai mici fata de problema initiala;
 -la randul lor,subproblemele se pot descompune(daca este necesar) in alte subprobleme mai simple;
 -aceste subprobleme se pot rezolva(solutiona) imediat,prin algoritmi simpli;

Numele metodei Divide et impera este sugestiv:"dezbina si cucereste";(desparte si stapaneste).

Etapele rezolvarii unei probleme(numita problema initiala) prin metoda "Divide et impera"
-descompunerea problemei initiale in(doua sau mai multe) sibprobleme independente,similare problemei initiale,de dimensiuni mai mici;
-descompunerea treptata a subproblemelor in alte subprobleme din ce in ce mai simple,pana cand acestea se pot rezolva imediat,prin algoritmi simpli;
-rezolvarea imediata a subproblemelor simple;
-combinarea solutiilor subproblemelor de dimensiuni mai mici pentru construirea solutiilor  subproblemelor de dimensiuni din ce in ce mai mari;
-combinarea ultimelor solutii determina obtinerea solutiei problemei initiale;

Metoda "Divide et impera" admite o implementare recursiva,deoarece subproblemele sunt similare(asemanatoare) problemei initiale,dar de dimensiuni mai mici.
Principiul fundamental al recursivitatii:ceea ce se intampla la un nivel ,se intampla la orice nivel,avand  grija sa asiguram conditia(conditiile) de terminare ale apelurilor recursive repetate.
Asemanator se intampla si in cazul metodei "Divide et impera".La un anumit nivel sunt 2 posibilitati:
s-a ajuns la o (sub)problema simpla ce admite o rezolvare imediata,caz in care se rezolva (sub)problema, si se revine din apel(la [sub]problema anterioara,de dimensiune mai mare),sau se continua cu fragmentarea problemei pe subprobleme.

Minimul unui tablou unidimensional

var v:array[1..120]of integer;
function min(li,ls:byte):integer;
var m:byte;{mijlocul intervalului}
      min1,min2:integer;
begin
if ls-li<=1 then
     if v[li]<v[ls] then min:=v[li]
            else min:=v[ls]
    else begin
            m:=(li+ls)div 2;
            min1:=min(li,m);
            min2:=min(m+1,ls);
            if min1<min2 then min:=min1
                                else min:=min2;{impera}
 end;
end;
apel:write(min(1,n));

PROBLEMA CAUTARII BINARE


Avem un tablou sortat si un numar sau o valoare.Trebuie determinat daca valoarea respectiva exista in tablou,si in cazul in care exista,sa se afiseze pozitia pe care se afla.

var n,i,p:byte;
      v:array[1..120]of integer;
      x:integer;

function caut_bin(li,ls:byte):integer;
  var m:byte;
   begin
   if li>ls then caut_bin:=0
      else begin
        m:=(li+ls) div 2;
        if x=v[m] then caut_bin:=m
             else begin
                     if x<v[m] then caut_bin:=caut_bin(li,m-1)
                                                        else caut_bin:=caut_bin(m+1,ls);
                   end;
     end;
  end;
begin
write('n:=');readln(n);
{citire vector,valoarea x}
p:=caut_bin(1,n);
writeln(p);
readln;
end.
OBS!Complexitatea algoritmului:[log2n]+1 pasi.

SORTAREA PRIN INTERCLASARE

-exista doi vectori sortati din care trebuie obtinut al treilea cu elementele celor doi vectori si care este de asemenea sortat;

Ideea!-se imparte vectorul in doua,se sorteaza recursiv fiecare jumatate,apoi cele doua jumatati se interclaseaza rezultand vectorul sortat;

var a:array[1..120]of integer;
      n:byte;

procedure inter(li,m,ls:byte);
{interclaseaza secventele a[li],...,a[m],a[m+1],...,a[ls]}
var i,j,k:byte;
      v:array[1..20]of integer;
begin
{
i-indicele curent din prima secventa;
  j-indicele curent din a doua secventa;
  k-indicele din secventa principala;
}
i:=li;
j:=m+1;
k:=1;
while (i<=m) and (j<=ls) do begin
          if a[i]<a[j] then begin
                     v[k]:=a[i];
                       i:=i+1;
                    end
                else begin
                         v[k]:=a[j];
     j:=j+1;
end;
    k:=k+1;
end;
if i<=m then
     for j:=i to m do begin
             v[k]:=a[j];
              k:=k+1;
         end
    else
        for i:=j to ls do begin
                  v[k]:=a[i];
                  k:=k+1;
          end;
 for i:=li to ls do a[i]:=a[i-li+1];
end;

procedure sortinter(li,ls:byte);
{sorteaza tabloul cu indicii li si ls}
var m:byte;
begin
if li<ls then begin
       m:=(li+ls) div 2;
       sortinter(li,m);
       sortinter(m+1,ls);
       inter(li,m,ls);
    end;
end;

begin
{citire tablouri}
sortinter(1,n);
{afisare tablou}
readln;
end.

Fie n numere naturale.Calculati cmmmc-ul lor folosind un algoritm "divide et impera".

Algoritmul lui Euclid!
Se impart numerele cu cat si rest,se inlocuieste deimpartitul(a) cu impartitorul(b) si impartitorul cu restul.Se repeta pana cand restul este nul,iar cmmdc este ultimul rest nenul.

var v:array[1..120]of integer;
      n,i{li,ls}:byte;

function euclid(a,b:word):word;
var rest:word;{v:word}
begin
while b<>0 do begin
      r:=a-a mod b;
      a:=b;
      b:=r;
  end;
 euclid:=a;
end;

function cmmdc(li,ls:byte):word;
{calculeaza cmmdc pentru toate numerele v[li],...,v[ls]}
var m:byte;
begin
if ld<=ls+1 then cmmdc:=euclid(v[li],v[ls])
      else begin
           m:=(li+ls) div 2;
           cmmdc:=euclid(cmmdc(li,m),cmmdc(m+1,ld));
         end;
end;

begin
{citire vector}
write('n;=');readln(n);
write(cmmdc(1,n));
readln;
end.

METODA BACKTRACKING

Este o tehnica de programare care ne permite generarea tuturor solutiilor unor probleme.Metoda genereaza vectori care indeplinesc anumite conditii numite conditii interne.Acest tip de probleme    s-ar putea rezolva prin generarea tuturor vectorilor si apoi prin afisarea celor care indeplinesc conditile interne,insa ar fi neeficient.

Metoda Backtracking functioneaza astfel:se genereaza componentele vectorului stiva(st) incepand cu prima componenta.Avand generate componentele st[1],...,st[niv-1] ,{nivelul curent} din stiva componenta stiva de niv va lua pe rand toate valorile care indeplinesc conditiile de continuare(deduse din conditiile interne);aleasa o valoare pe nivelul curent niv,se va apela recursiv pentru a genera valori pe nivelul urmator,niv+1.In momentul cand s-au generat toate valorile de pe un nivel,se va reveni din recursivitate pe nivelul anterior.

PASI CE  TREBUIE URMARITI IN BACKTRACKING

P1:gasirea semnificatiei vectorului stiva(st){ce vom genera}
P2:determinarea valorilor ce pot fi puse pe fiecare nivel;
P3:determinarea conditiilor de continuare;
P4:conditia de solutie;

Exemplu!

{declaratii de variabile}

functia continuare(...):tip_boolean;
{returneaza daca secventa de numere ordonate sau selectate prin backtracking este valida}
{declaratii locale}
begin
{instructiuni}
{...}
{apelul sau reapelarea functiei}
end;

procedure back(nivel:byte);
var i:tip;
begin
if niv=n+1{s-a ajuns la finalul unei selectii}
   then
       begin
       {instructiuni de prelucrare,afisare,etc...}
       end
    else
      for i:=valoare_inceput to valoare_finala do begin
             v[niv]:=i;
              if cont(...) then back(niv+1);
          end;
  end;
begin
{citiri,etc...}
back(1);
readln;
end.