Algoritmi si structuri de date (10-11.12.2014) Informatica&Matematic, anul 1 ASD21AlgMatrLab

1

Algoritmi cu matrice (continuare)

R1. Enunul problemei: S se descrie un algoritm pentru a determina cte linii au cel puin un element negativ ntr-o matrice dat? Metoda de rezolvare: Se parcurge fiecare linie a matricei i n cazul n care exist un element negativ se contorizeaz linia. De exemplu, pentru matricea:

-------

---

=

654321514321432101102121654321

A

sunt 4 linii (liniile 2, 3, 4, 5) care au cel puin un element negativ.

Descrierea algoritmului n pseudocod: citete m,n,a11,,amn contor 0 *initializarea contorului de linii pentru i = 1,m repeta *pentru fiecare linie i pentru j = 1,n repeta *parcurgem linia daca aij < 0 atunci *elementul curent este negativ

contor contor + 1 *contorizam linia curenta break *se trece la urmatoarea linie

scrie contor Descrierea algoritmului n C++ (CodeBlocks):

#include using namespace std; int main() { int m,n,i,j,contor; float a[10][10]; //citim dimensiunile si elementele matricei coutm; coutn; cout

Algoritmi si structuri de date (10-11.12.2014) Informatica&Matematic, anul 1 ASD21AlgMatrLab

2

R2. Enunul problemei: S se descrie un algoritm pentru a afia indicele liniilor ce conin cel puin k elemente negative. n cazul n care nu exist astfel de linii se va afia un mesaj. Metoda de rezolvare: De exemplu, pentru matricea

A =

-----

-----

4321321003212210

4321

i k=2 sunt 3 linii cu cel puin k elemente negative. O variant simpl a algorimului ar fi s se parcurg liniile matricei i s se contorizeze elementele negative, iar n cazul n care acest numr depete valoarea k s se afieze indicele liniei respective. Pentru a verifica dac nu exist astfel de linii, se poate lua o variabila boolean care-i schimb valoarea n cazul n care s-a afiat indicele unei linii corespunztoare. La final, dup parcurgerea tuturor liniilor, dac aceast variabil nu i-a schimbat valoarea iniial, atunci se va afia un mesaj. O descriere a algoritmului n pseudocod:

citete m,n,a11,,amn,k exist fals *presupunem ca nu exista linii corespunzatoare pentru i = 1,m repeta *pentru fiecare linie contor_neg 0 *initializare contor pentru linia i pentru j = 1,n repeta *parcurgem linia daca aij < 0 atunci *elementul curent este negativ

contor_neg contor_neg + 1*contorizam elem. neg. curent daca contor_neg >= k atunci *sunt cel putin k elem. neg. exista adevarat *schimbam valoarea var. exista scrie i *afisam indicele liniei

daca exista = fals atunci scrie "Nu exista linii cu cel putin k elem. negative" O descriere a algoritmului n C++ (CodeBlocks):

#include using namespace std; int main() { int m,n,i,j,k,exista,contor_neg; float a[10][10]; coutm; coutn; cout

Algoritmi si structuri de date (10-11.12.2014) Informatica&Matematic, anul 1 ASD21AlgMatrLab

3

O optimizare a acestui algoritm poate fi aceea n care parcurgerea liniei se continu doar dac nu s-au gsit deja k elemente negative, iar linia este corespunztoare dac numrul de elemente negative este egal cu k:

exista = 0; //presupunem ca nu exista linii corespunzatoare for (i=0;i

Algoritmi si structuri de date (10-11.12.2014) Informatica&Matematic, anul 1 ASD21AlgMatrLab

4

O descriere a algoritmului n C++ (CodeBlocks): #include using namespace std; int main() { int m,n,i,j,contor,OK; float a[10][10]; //citim dimensiunile si elementele matricei coutm; coutn; cout

Algoritmi si structuri de date (10-11.12.2014) Informatica&Matematic, anul 1 ASD21AlgMatrLab

5

for (int i=2; i*i

Algoritmi si structuri de date (10-11.12.2014) Informatica&Matematic, anul 1 ASD21AlgMatrLab

6

int main() { int m,n,i,j,p,q; float a[10][10]; coutm; coutn; cout

Algoritmi si structuri de date (10-11.12.2014) Informatica&Matematic, anul 1 ASD21AlgMatrLab

7

float SumaLinie(int p, float a[10][10],int n) { //calculeaza suma pe linia p intr-o matrice patrata de dim.n float S=0; for (int j=0;j

Algoritmi si structuri de date (10-11.12.2014) Informatica&Matematic, anul 1 ASD21AlgMatrLab

8

R7. Enunul problemei: Pe o tabl de ah (cu liniile numerotate de la 1 la 8 i coloanele de la A la H) se dau coordonatele a doi nebuni, unul alb i unul negru. S se descrie un algoritm pentru a stabili dac cei doi nebuni se atac sau nu. Metoda de rezolvare: De exemplu, dac un nebun este pe poziia D3 i al doilea n poziia G6, acetia se atac, ns dac acetia sunt n poziiile D3 i G5 nu se atac. Algoritmul const n a stabili dac cele dou piese sunt pe o paralel cu diagonala principal, adic formeaz un triunghi dreptunghic isoscel cu paralele la axele orizontal i vertical ( |c1-c2| = |n1-n2| ).

O descriere a algoritmului n C++ (CodeBlocks):

#include #include //pt abs altfel in C++: apel ambiguu using namespace std; int main() { char c1,c2; int n1,n2; coutc1>>n1; coutc2>>n2; if (abs(c1-c2) == abs(n1-n2)) //coordonatele coloanelor se convertesc in //codurile ASCII corespunzatoare ('A'->65, ..., 'H'->72) //apoi se calculeaza diferenta dintre ele => lungime latura cout