Metode evoluate de programare Limbajele c şi C++

14. Probleme diverse

De multe ori suntem puşi în faţa unor probleme pe care le înţelegem uşor dar nu ştim cum să le rezolvăm cât mai simplu şi elegant. Vă propunem câteva metode care bine însuşite pot duce, uneori, la o rapidă rezolvare a problemelor dificile. Evident că, nu toate problemele pot fi încadrate în aceste tipare propuse dar fiecare programator poate să-şi formeze un astfel de "portofoliu" de metode cu care să poate aborda orice problemă. Metodele prezentate în continuare pot constitui un început.

14.1. Generarea combinărilor

Fie o mulţime oarecare de n elemente care poate fi pusă într-o corespondenţă biunivocă cu mulţimea A={1,...,n}. Ne propunem să determinăm toate m-combinările (mn) ale mulţimii A (submulţimi de m elemente ale mulţimii A). Vom rezolva problema, nerecursiv, pornind de la m-combinarea V=(1,2,...,m) determinând succesiv toate m-combinările ordonate lexicografic crescător.

Fie V=(v₁,v₂,...,v_m) o m-combinare oarecare, atunci m-combinarea următoare în ordine lexicografică crescătoare se obţine astfel:

1. 
   se determină cel mai mare indice i satisfăcând relaţiile:
   

v_ii+1=n-m+i+1,..., v_m-1=n-1, v_m=n. (1)

1. 
   se trece la vectorul următor:
   

(v₁, ..., v_i-1,v_i+1,v_i+2, ..., v_i+n-i+1);

1. 
   dacă nu există un astfel de indice i (care să satisfacă relaţiile (1)) înseamnă că vectorul V conţine ultima m-combinare şi anume: (n-m+1,n-m+2, ...,n).
   

Dăm în continuare o funcţie C care generează o m-combinare cu n elemente având ca parametru cod o variabilă booleană care pentru valoarea 0 generează prima m-combinare iar pentru valoarea 1 generează următoarea m-combinare. Funcţia comb reîntoarce valoarea 1 dacă s-a generat o m-combinare oarecare şi valoarea 0 dacă s-a generat ultima m-combinare (în acest caz cod are valoarea 0). Se va folosi un vector global v în care se generează m-combinările.

#define dim 50

#include

int v[dim+1], n, m;

// functia generatoare a m-combinarilor

int comb(cod)

int cod;

{

int i,j; // generarea primei m-combinari 1,...,m

if (cod == 0)

{

for (i=1; i<=m; v[i]=i++);

return (1);

}

i=m+1;

do { i   } // cautarea indicelui i pentru satisfacerea relatiilor (1)

while (v[i] >= n m+i);

if (i)

{

v[i]=v[i]+1;

for (j=i+1; j<=m; v[j]=v[j 1]+1,j++);

return (1);

}

else return (0);

}
void main(void)

{

int kod,i;

printf("\ndati n: ");

scanf ("%d",&n);

printf("\ndati m: ");

scanf ("%d",&m);

comb(0);

kod=1;

while (kod)

{ printf("\n");

for (i=1;i<=m;printf ("%3d",v[i++]));

kod = comb(kod);

}

getche();

}

14.2. Metoda greedy

Se aplică problemelor în care se dă o mulţime A conţinând n date (de orice natură şi structură) de intrare cerându-se să se determine o submulţime B (BA) care să îndeplinească anumite condiţii pentru a fi acceptată. Cum, în general, există mai multe astfel de submulţimi (numite soluţii posibile) se mai dă şi un criteriu conform căruia dintre aceste submulţimi să alegem una singură (numită soluţie optimă) ca rezultat final. Foarte multe probleme de căutare se înscriu în acest tip.

Menţionăm că, în general, soluţiile posibile au următoarele proprietăţi:

- se presupune că  este soluţie posibilă;

- dacă B este soluţie posibilăţi CB atunci şi C este soluţie posibilă;

Vom da în continuare o variantă a tehnicii greedy (denumire care în traducere înseamnnă lăcomie, înghiţire) în care se porneşte de la mulţimea vidă. Apoi se alege pe rând, într-un anumit fel, un element din A neales încă. Dacă adăugarea lui la soluţia parţial anterior construită conduce la o soluţie posibilă, atunci se adaugă, altfel se alege un nou element. Tot acest procedeu se repetă pentru toate elementele din A. Dăm în continuare în pseudocod o procedură:

procedure GREEDY (n,A,B)

B:=;

for i=1,n do

call ALEGE (A,i,x);

call POSIBIL (B,x,cod);

if cod=1 then

call ADAUG (B,x);

endif;

endfor;

return;

end procedure

Despre procedurile apelate din GREEDY precizăm următoarele:

1. 
   procedura ALEGE furnizează în x un element din A a_j{a_i,...,a_n} şi interschimbă a_i cu a_j; dacă la fiecare pas se cercetează a_i atunci procedura se simplifică;
   
2. 
   procedura POSIBIL verifică dacă elementul x poate fi adăugat sau nu mulţimii parţiale construită până la pasul curent furnizând o valoare booleană cod cu semnificaţia:
   

cod = 1, dacă B U {x}, este soluţie posibilă

cod = 0, altfel

1. 
   procedura ADAUG înlocuieşte pe B cu B{x}.
   

Obs. Procedurile de mai sus nu sunt necesare întotdeauna, acest fapt depinzând de complexitatea problemei. Oricum trebuie reţinut cadrul de rezolvare al acestui tip de problemă.

Problemă rezolvată
Se dă o mulţime de valori reale X={x₁, . . .,x_n}. Se cere submulţimea YX astfel ca  y /yY, să fie maximă.
Evident că problema este foarte simplă (în Y trebuie introduse elementele strict pozitive din X; evităm să mai construim procedurile ALEGE, POSIBIL, ADAUG) şi vom da rezolvarea ei în pseudocod:
procedure SUMA (n,X,Y,k)

integer n,X(n),Y(n),k

k:=0;

for i=1,n do

if x(i) > 0 then k:=k+1;

y(k):=x(i)

endif;

endfor;

return;

end procedure

Probleme propuse
14.2.1.

Se dau n şiruri S₁,S₂,...,S_n ordonate crescător, de lungimi L₁,L₂, ...,L_n. Să se obţină un şir S de lungime L₁+L₂+...+L_n cu toate elementele celor n şiruri ordonate crescător (problemă de interclasare).

Indicaţie: Vom interclasa succesiv câte două şiruri în final obţinând şirul ordonat crescător. Complexitatea interclasării a două şiruri A şi B de lungimi a şi b depinde direct proporţional de a+b (pentru că se fac a+b deplasări de elemente). Se pune problema găsirii ordinii optime în care trebuie efectuate aceste interclasări astfel ca numărul total de deplasări să fie minim.

Vom da un exemplu pentru a lămuri mai bine lucrurile:

fie 3 şiruri de lungimi (90,40,10). Interclasăm şirul S₁ cu S₂ apoi şirul rezultat cu S₃; putem nota acest lucru formal prin (S₁+S₂)+S₃. Se obţin (90+40) + (130+10)=270 deplasări. Dacă vom interclasa şirurile în ordinea (S₂+S₃)+S₁ vom obţine (40+10)+ (50+90)=190 de deplasări. De aici concluzia că întotdeauna vom interclasa şirurile de lungimi minime din şirurile rămase.


14.2.2.

Găsiţi tripletele de numere pitagorice din N_n x N_n x N_n (prin N_n notat mulţimea {0,1,2,...,n}). Încercaţi optimizarea timpului de execuţie a programului.

14.2.3.

Fie mulţimea m-combinărilor luate din n elemente şi fie k<m un număr natural. Să se dea un algoritm şi apoi să se scrie un program C astfel încât să se determine o submulţime de m-combinări cu proprietatea că oricare două m-combinări au cel mult k elemente comune.

14.2.4.

Să se determine mulţimile interior stabile (MIS) ale unui graf oarecare dat prin matricea sa de adiacenţă.