Metode evoluate de programare Limbajele c şi C++

14.4. Metoda divide et impera (divide şi stăpâneşte)

Această modalitate de elaborare a programelor constă în împărţirea repetată a unei probleme de dimensiune mai mare în două sau mai multe subprobleme de acelaşi tip urmată de combinarea soluţiilor subproblemelor rezolvate pentru a obţine soluţia problemei iniţiale.

Se dă un vector A=(a₁,...,a_n) şi trebuie efectuată o prelucrare oarecare asupra elementelor sale.

Presupunem că:

 p,q{1,...,n} cu 1 p < q   m{p,p+1,...,q-1} a.î. prelucrarea secvenţei {a_p,...,a_q} se poate face prelucrând subsecvenţele:

{a_p,...,a_m} şi {a_m+1,...,a_q} şi apoi combinând rezultatele pentru a obţine prelucrarea întregii secvenţe {a_p,...,a_q}.

Dacă se reuşeşte o astfel de formalizare a problemei atunci ea poate fi rezolvată cu ajutorul acestei metode.

Vom da în continuare o procedură recursivă în pseudocod:

procedure DI (p,q,α)

if q-p  eps then

call PREL (p,q,α)

else

call IMPARTE (p,q,m) ;

call DI (p,m,β);

call DI (m+1,q,γ);

call COMB (β,γ,α);

endif;

return;

end procedure

Câteva precizări se impun:

1. 
   procedura trebuie apelată prin call DI (1,n,α) în α obţinându-se rezultatul final;
   
2. 
   eps este lungimea maxim a unei secvene {a_p,...,a_q} notată prin (p,q) pentru care se face prelucrarea directă fără a mai fi necesară împărţirea în subprobleme;
   
3. 
   procedura PREL realizează prelucrarea directă a secvenţelor (p,q);
   
4. 
   procedura COMB realizează combinarea rezultatelor β şi γ ale prelucrării a două secvenţe vecine (p,m) şi (m+1,q) obţinând rezultatul α al prelucrării întregii secvenţe (p,q);
   
5. 
   prin procedura IMPARTE se obţine valoarea lui m.
   

Vom da ca exemplu problema sortării crescătoare a unui şir de întregi prin interclasare.

1. 
   deoarece secvenţele (i,i+1) sunt uşor de ordonat acestea vor constitui secvenţele ce se vor prelucra, deci eps = 1;
   

- m se va calcula ca (p+q)/2, deci nu mai e nevoie de procedura specială IMPARTE;

1. 
   procedura COMB va interclasa întotdeauna două secvenţe (p,m) şi (m+1,q) ordonate crescător;
   
2. 
   vom folosi un vector x drept structură globală şi vom face toate prelucrările pe elementele sale nemaiavând nevoie de zonele α,β;
   
3. 
   pentru zona γ vom folosi un vector local y în procedura COMB acesta conţinând elementele corespondente din x dar ordonate crescător; tot în procedura COMB se vor copia apoi elementele lui y din porţiunea (p,q) în x;
   
4. 
   evident că procedurile din schema generală a algoritmului sunt funcţii C cititorul făcând analogiile necesare.
   

#include

#include

#define nrelem 100

int x[nrelem];

int n;
void PREL (int p, int q)

{int aux;

if ((p x[q])) {

aux=x[p];

x[p]=x[q];

x[q]=aux;

}

}

void COMB (int inf, int mijloc, int sup)

{int i,j,k,l;

int y[nrelem];

i=k=inf;

j=mijloc+1;

while (i<=mijloc && j<=sup)

{ if (x[i] <= x[j])

y[k++]=x[i++];

else

y[k++]=x[j++];

}

for(l=i; l<=mijloc; y[k++]=x[l++]);

for(l=j; l<=sup; y[k++]=x[l++]);

for(k=inf; k<=sup; x[k++]=y[k]);

}

void DI (int p, int q)

{ int m;

if ((q p) <= 1)

PREL (p,q);

else

{m=(p+q)/2;

DI (p,m);

DI (m+1,q);

COMB (p,m,q);

}

return;

}
void main(void)

{int i;

clrscr();

printf ("dati nr de elemente\n");

scanf ("%d",&n);

for (i=1; i<=n; i++)

{printf("x[%d]=",i);

scanf("%d",&x[i]);

}

DI (1,n);

printf("\nsirul sortat crescator este:\n");

for (i=1; i<=n; i++) printf("x[%d]=%d\n",i,x[i]);

getch();

}

14.5. Metoda programării dinamice

Această metodă este aplicabilă problemelor de optim în care soluţia poate fi privită ca rezultatul unui şir de decizii d₁, . . . ,d_n. Fiecare decizie depinde de deciziile deja luate şi nu este unic determinată (spre deosebire de tehnica greedy unde fiecare decizie care se ia trebuie să fie unică). Totodată este necesar să fie satisfăcută una din variantele principiului optimalităţii pentru a putea fi aplicată această metodă.

Vom formaliza acest principiu al optimalităţii:

1. 
   fie d₁,...,d_n un şir optim de decizii (SOD) care transformă starea s_o în starea s_n, trecând prin stările intermediare s₁, . . . ,s_n-1; vom nota acest fapt prin (d₁,d_n) este SOD pentru perechea de stări (s_o,s_n);
   
2. 
   grafic procesul este descris ca în figura următoare:
   

d₁ d₂ d_n

*----->*---->*------>* . . . *------>*

s_o s₁ s₂ s_n-1 s_n

Vom da acum mai multe variante ale principiului optimalităţii:

1. 
   dacă (d₁,d_n) este SOD pentru (s_o,s_n) atunci (d₂,d_n) este SOD pentru (s₁,s_n);
   

2) dacă (d₁,d_n) este SOD pentru (s_o,s_n) atunci  i din {1, . . . ,n-1} avem

a) (d₁,d_i) este SOD pentru (s_o,s_i) SAU

b) (d_i+1,d_n) este SOD pentru (s_i,s_n).

3) dacă (d₁,d_n) este SOD pentru (s_o,s_n) atunci  i din {1, . . . ,n-1} avem

a) (d₁,d_i) este SOD pentru (s_o,s_i) ŞI

b) (d_i+1,d_n) este SOD pentru (s_i,s_n).
Ultima variantă este cea mai generală şi mai completă. Odată verificat o formă a principiului optimalităţii, metoda programării dinamice constă în a scrie relaţiile de recurenţă şi apoi de a le rezolva. În general relaţiile de recurenţă sunt de 2 tipuri :

1. 
   fiecare decizie d_i depinde de d_i+1,...,d_n - relaţii de recurenţă înainte, deciziile vor fi luate în ordinea d_n, d_n-1, . . . ,d₁;
   
2. 
   fiecare decizie d_i depinde de d₁, . . . ,d_i-1 - relaţii de recurenţă înapoi, deciziile vor fi luate în ordinea d₁, d₂, . . . , d_n.
   

Problemă rezolvată
Fie G=(X,Γ) un 1-graf orientat căruia îi ataşăm matricea costurilor, (fiecare arc (i,j)Γ este etichetat cu o valoare reală strict pozitivă). Se pune problema găsirii drumului de valoare minim (DVM) între oricare 2 vârfuri i şi j.
Rezolvare
Verificăm prima variantă a principiului optimalităţii:

- fie i, i₁, i₂, . . . , i_m, j DVM între i şi j atunci evident că i₁, . . . , i_m, j este DVM între i₁ şi

j;

- notăm prin L(i,k) lungimea DVM dintre i şi k,  kX;

- notăm deasemenea d_kj valoarea arcului (k,j);

- ecuaţiile de recurenţă sunt:

L(i,j) = min {L(i,k) + d_kj)}

(k,j)Γ
#include

#include

#define nn 10

int d[nn+1][nn+1],i,j,n;
int L(int i,int j)

{

int m=MAXINT;

int k,x=0;

if (i= =j) m=0;

else

for (k=1;k<=n;k++)

if (d[k][j] < MAXINT)

{ x=L(i,k)+d[k][j];

if (x

}

return m;

}
void citestematrice(void)

{int i,j;

printf("\ndati dimensiunea matricii distantelor : ");

scanf("%d",&n);

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{ printf("d[%d,%d]= ",i,j);

scanf ("%d",&d[i][j]);

}

for(i=1;i<=n;i++)

for(j=1;j<=n;j++) if (d[i][j]= =  1) d[i][j]=MAXINT;

}

void citeste(void)

{ printf("\ndati varful initial : ");

scanf("%d",&i);

printf("\ndati varful final : ");

scanf("%d",&j);

}
void afiseaza(int val)

{ printf("\nvdlm intre varful %d si %d este %d",i,j,val);

}
void main(void)

{ int vdlm;

clrscr();

citestematrice();

citeste();

vdlm=L(i,j);

afiseaza(vdlm);

getch();

}
Probleme propuse
14.5.1.

Se dă o matrice A=(a_ij), i=1,...,n; j=1,...,m cu elementele din mulţimea {0,1,2}. Două elemente din A a_ij şi a_kl se numesc 4-vecine dacă i-k+j-l = 1.

Notăm cu S_o, S₁ şi S₂ submulţimile formate din elementele matricii egale cu 0, 1 respectiv 2. Submulţimea S₁ se împarte în grupuri astfel: a_ij şi a_kl fac parte din acelaşi grup dacă sunt 4-vecine sau dacă  a_pq  S₁ : a_ij şi a_pq sunt 4-vecine iar a_pk şi a_kl sunt din acelasi grup. Un element a_kl  S_o îl vom numi spion al grupului G  S₁ dac  a_ij  G a.î. a_kl şi a_ij s fie vecine. Un spion este perfect dac are toţi vecinii din G.

Se cere:

a) cel mai numeros grup (S₁) care are un singur spion (dacă există).

b) toate grupurile care au cel puţin doi spioni perfecţi.

14.5.2.

Se dă o matrice cu elemente care au valori din {d,o}, care reprezintă un teren cu drumuri {d} şi obstacole {o}. În acest teren se află un tanc şi o ţintă. Acest tanc poate primi comenzi pentru rotirea ţevii (cu 90^o în ambele sensuri), pentru deplasare (în direcţia ţevii cu o linie sau cu o coloană) sau pentru tragere (în direcţia ţevii pentru a nimeri ţinta) în cazul în care între tanc şi ţintă nu există nici un obstacol. Considerând că deplasarea nu se poate efectua prin obstacole, se cere cel mai scurt drum necesar tancului pentru a putea distruge ţinta şi şirul comenzilor efectuate în cazul în care exist un astfel de drum.

14.5.3.

Se d o matrice cu elemente din {0,1,2,3}, reprezentând o pădure cu capcane (0) şi cărări (1). În această pădure se află o vulpe (2) şi mai mulţi lupi (3). Fiecare lup încearcă să se apropie de vulpe fără a şti unde se află capcanele, iar în cazul în care cade într-o capcană, moare. Vulpea încearcă să se îndepărteze de cel mai apropiat lup, având însă posibilitatea să descopere şi capcanele şi să le ocolească. Atât vulpea cât şi lupii îi pot modifica poziţia doar cu o linie sau cu o coloană în fiecare moment. Să se spună dacă vulpea reuşeşte să scape de lupi.

14.5.4.

Se consideră un teren dreptunghiular sub forma unei matrici A de m linii şi n coloane. Elementele a_ij ale matricii conţin cotele (înălţimile) diferitelor porţiuni astfel obţinute. Se presupune că o bilă se găseşte pe o porţiune (i_o,j_o) având cota a(i_o,j_o).

Se cere un program care să precizeze toate traseele (începând cu (i_o,j_o) ) posibile pe care le poate urma bila spre a ieşi din teren, ştiind că bila se poate deplasa în orice porţiune de teren 4-învecinat cu o cotă strict inferioară cotei terenului pe care se găseşte bila.
14.5.5.

Se cere un program care rezolvă problema labirintului (nerecursiv).

O matrice de m linii şi n coloane reprezintă un labirint dacă:

 a(i,j) = o - semnificând culoar;

 a(i,j) = 1 - semnificând zid.

Un traseu de ieşire pornind de la o porţiune (i_o,j_o) trebuie să fie o succesiune de perechi (i_o, j_o), (i₁, j₁) . . . (i_k, j_k) astfel încât 2 perechi învecinate să fie 4-vecine şi a(i_p,j_p)=0

 p=0, . . . ,k.


TEMĂ:
Să se scrie programe C care rezolvă 5 probleme propuse din capitolul 14.

PARTEA II
Limbajul C++