Aeronautica Comunicatii Drept Informatica Nutritie Sociologie Tehnica mecanica Informatica Qdidactic » stiinta & tehnica » informatica Lucrare pentru atestarea competentelor profesionale la informatica - tablouri bidimensionale Lucrare pentru atestarea competentelor profesionale la informatica - tablouri bidimensionale Lucrare pentru atestarea competentelor profesionale la informatica - Tablouri bidimensionale - 1. Motivatia lucrarii Rezolvarea problemelor matematice de tip sisteme de ecuatii cat si probleme legate de teoria grafurilor au necesitat folosirea tablourilor bidimensionale. Toate concursurile si olimpiadele scolare necesita cunoasterea si folosirea tablourilor bidimensionale. Intr-o mare parte problemele informatice implica folosirea matricelor. Voi sustine Bacalaureatul la informatica, iar tema aleasa la atestat imi va consolida cunostiintele pentru obtinerea unor rezultate bune la aceasta proba si ma va ajuta si in viitoarea cariera. . Motivatia lucrarii..ntelor profesionale.. 2. Tabloul - GENERALITATI - Pentru a pastra in memoria calculatorului diverse informatii se folosesc variabile. Daca informatiile pe care vrem sa le pastram se pot reprezenta prin numere intregi atunci folosim variabile de tipul int, daca se pot reprezenta prin numere reale atunci folosim variabile de tipul float, etc. Spre exemplu pentru a calcula suma a trei numere reale, vom declara patru variabile de tip float: trei variabile vor memora cele trei numere, iar a patra variabila va memora suma lor. Putem avea situatii cand avem nevoie de un numar mare de variabile, sau de un numar de variabile care nu este cunoscut dinainte. Spre exemplu daca vrem sa facem calcule asupra a 100 de numere, este incomod sa declaram 100 variabile. Sau daca trebuie sa facem calcule asupra a N numere, unde N este introdus de la tastatura, atunci nici macar nu stim cate variabile sa declaram.      In asemenea situatii putem folosi tablouri. Un tablou reprezinta un sir de mai multe variabile de acelasi tip, grupate sub un acelasi nume. Tablourile sunt compuse din elemente. Fiecare element al unui tablou poate fi considerat ca fiind o variabila independenta, de acelasi tip ca si tabloul. Tablourile au o dimensiune, care reprezinta numarul de elemente din tablou. Tablourile se declara specificand tipul de date, numele si dimensiunea. Spre exemplu o declarare de forma: int a[100]; inseamna ca declaram un tablou de 100 de elemente de tip int. Elementele tabloului se acceseaza specificand numele tabloului si indicele dorit. Numerotarea indicilor incepe de la 0. Primul element al tabloului de mai sus va fi a[0], al doilea va fi a[1], iar ultimul va fi a[99]. In general prelucrearea tablourilor se face prin instructiuni repetitive: for, while sau dowhile. 3. Tabloul de memorie bidimensional (matricea) Tabloul in interpretare matematica Fie A = multimea primelor n numerelor naturale. Fie M = A × A × × A  produsul cartezian a k astfel de multimi. Se numeste tablou o functie f : M →T, unde T este o multime oarecare. Numarul k este dimensiunea tabloului. Daca k=1 tabloul se mai numeste I vector. Vectorul are n componente. Daca k=2 tabloul se mai numeste si matrice. Matricea are n × n elemente.    Exemple.     1. Vector cu 5 componente numere naturale V = (1,3,6,2,4)     Aici k=1 ; n=5, T=N, elementele vectorului sunt v=1, v=3, , v=4 2. Vector cu n componente numere reale Z= (z,z,z, . ,z), z R,  i    Aici k=1, n=n, T=R 3. Matrice cu n linii si m coloane cu elemente din R : Tabloul de mai sus se numeste A; Elementele sale sunt Prin  se intelege elemental care se gaseste in linia i si coloana j. Aici k=2,.           Atentie! Frecvent se confunda numarul componentelor cu dimensiunea tabloului. De exemplu, despre un vetor cu n componente se spune ca este de dimensiune n (cand de fapt, toti vectorii au dimensiunea 1).                                Organizarea in structuri de date a datelor prelucrate de algoritmi simplifica multe dintre operatiile de prelucrare. Atunci cand organizati datele intr-o structura de date trebuie sa identificati modul in care puteti avea acces la ele si operatiile pe care le puteti executa cu datele din colectie. Procesul de organizare a datelor in colectii este un proces care se desfasoara pe trei niveluri care interactioneaza intre ele, pornind de la nivelul conceptual : Scop : exemplificarea modului in care, pentru a rezolva problema, alegeti organizarea datelor intr-o structura de date de tip tablou de memorie. Enuntul problemei 1. O firma de transport are un parc de 10 masini, cu capacitati de transport diferite. Trebuie sa se determine cate dintre aceste masini au cea mai mare capacitate de transport. Pentru rezolvarea problemei, trebuie stabilita structura de date care se va folosi : La nivel conceptual - capacitatile de transport ale masinilor reprezinta un sir de numere intregi, aranjate intr-o ordine aleatorie, in care trebuie cautat numarul cel mai mare si de cate ori apare in sir.

La nivel logic - implementarea permisa de limbajul C++ a unei colectii de date omogene este vectorul, fiecare numar intreg fiind un element al structurii. Pentru rezolvarea problemei se vor folosi urmatorii algoritmi : algoritmul pentru parcurgerea vectorului la memorarea numerelor, algoritmul pentru determinarea valorii maxime dintr-un sir de numere si algoritmul de cautare in vector a elementelor cu o valoare precizata (valoarea maxima).

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]                         

Daca se doreste pastrarea datelor memorate (capacitatile de transport ale masinilor din parcul auto) pentru prelucrarea lor ulterior, se vor salva intr-un fisier text, de unde vor fi restaurate in memoria interna intr-un vector, la fiecare prelucrare (executie a programului).

Observatie. In structura de date folosita (vectorul), intre elementele structurii exista o relatie de ordine in care fiecare element are un succesor si un predecesor. Acest tip de structura este o structura liniara.

Enuntul problemei 2. Sunt cinci contoare pentru energia electrica, ce se citesc trimestrial, si se inregistreaza intr-un tabel consumul trimestrial (in mii de kWh). Trebuie sa se determine : media consumului trimestrial pe un singur contor si pe toate contoarele, cel mai mare consum trimestrial, cel mai mic consum trimestrial, contorul cu cel mai mic consum si contorul cu cel mai mare consum.

Pentru rezolvarea problemei, trebuie stabilita structura de date care se va folosi :

La nivel conceptual - contoarele sunt organizate intr-un tabel cu patru linii si cinci coloane in care sunt memorate numere intregi. Tabelul va avea 4 linii, corespunzatoare celor 4 trimestre, si 5 coloane, corespunzatoare celor cinci contoare.

La nivel logic - implementarea permisa de limbajul C++ a unei colectii de date omogene este tabloul de memorie. Pentru rezolvarea problemei se vor folosi urmatorii algoritmi : algoritmul pentru parcurgerea tabloului de memorie, pentru memorarea numerelor, algoritmul pentru determinarea mediei aritmetice si algoritmii de determinare a valorii minime, respectiv maxime. Daca pentru reprezentarea datelor s-ar folosi tabloul de memorie cu o singura dimensiune (vectorul), algoritmii de prelucrare ar fi foarte complicati. Solutia, in acest caz, este tabloul bidimensional (matrice) cu patru linii si cinci coloane. Identificarea unui element din tablou se va face de data aceasta nu printr-un numar de ordine, ci prin numarul liniei si numarul coloanei. Daca numele tabloului bidimensional este b, elementul  este elementul din linia 2 si coloana 3 si, in exemplu, are valoarea 32.

La nivel fizic - memoria interna nu are o structura matriceala. Ea este formata din locatii de memorare care au adrese consecutive. Din aceasta cauza, structura dreptunghiulara a tabelului trebuie simulata. Spatiul de memorare alocat tabelului va fi o zona continua, de 40 octeti, in care se vor memora datele din tabel, linie cu linie. Numarul de ordine m al elementului din linia i si coloana j dintr-un tablou cu n coloane este : m = n x (i-1)+j

                 elementul din linia 2 si coloana 3

Si in cazul acestui exemplu, daca se doreste pastrarea datelor memorate (valorile consumului trimestrial al fiecarui contor) pentru prelucrarea lor ulterior, se vor salva intr-un fisier text, de unde vor fi restaurate in memoria interna intr-un tablou bidimensional, la fiecare prelucrare (executie a programului).

Observatie. Metoda de memorare a elementelor tabloului, in ordine, unul dupa altul, intr-o zona continua de memorie, in locatii cu aceeasi dimensiune, este folosita pentru identificarea elementelor structurii si se realizeaza printr-un ansamblu de indici. Numarul de indici (k) folosit pentru identificarea elementelor determina dimensiunea tabloului. Astfel :

Pentru k=1, structura este un tablou unidimensional numit si vector ;

Pentru k=2, structura este un tablou bidimensional numit si matrice.

In primul exemplu, s-a folosit un tablou de memorie cu numerele a,cu o singura dimensiune si cu 10 elemente. In al doilea exemplu s-a folosit tabloul cu numele b, cu doua dimensiuni, cu 4 elemente pe o dimensiune (4 linii) si 5 elemente pe cealalta dimensiune (5 coloane). In cel de-al doilea caz, tabloul are tot 20 de elemente. Chiar daca, din punct de vedere al memoriei interne, spatiul de memorare alocat este tot sub forma unui bloc continuu de 20, respectiv 40 de octeti, cele doua tipuri de tablouri (cu o dimensiune sau cu doua dimensiuni) difera intre ele prin modul in care pot fi identificate elementele structurii. Identificarea unui element al tabloului se face prin numele tabloului si valorile indicilor dupa toate dimensiunile. De exemplu,  inseamna elementul 6 din tabloul a, iar  inseamna elementul de pe linia 2 si coloana 4 din tabloul b.

Intr-o matrice cu m linii si  n coloane, numarul de ordine al elementului de pe linia  nl si din coloana nc este :

Daca inregistrarea in memorie se face linie cu linie : nr_ord_l=(nl-l)xn+nc.

Daca inregistrarea in memorie se face coloana cu coloana: nr_ord_c=(nc-l)xm+nl.

  Daca matricea se inregistreaza incepand de la adresa adr, ir un element ocupa o zona de memorie cu dimensiunea dim, adresa la care se gaseste elementul care are numarul de ordine nr_ord este egala cu adr+dimx(nr_ord-1).

O structura de date care, la  nivel conceptual are imaginea unui tabel care contine date de acelasi tip, se implementeaza la nivel logic cu ajutorul unui tablou bidimensional.

4. Implementarea tabloului bidimensional in C++

Declararea unui tablou de memorie de tip matrice (cu doua dimensiuni) se face prin instructiunea :

unde <tip_data> precizeaza tipul elementelor matricei, <nume> este identificatorul matricei, iar <nr_1> si <nr_2> sunt doua constante intregi care specifica numarul de elemente ale matricei pentru fiecare dimensiune : <nr_1> - numarul de linii, iar <nr_2> - numarul de coloane. De exemplu, prin instructiunile declarative :

int a[2][4] ;

float b[3][5] ;

se declara doua matrice : a  cu 8 elemente de tip int, care are 2 linii si 4 coloane, si b, cu 15 elemente de tip float, care are 3 linii si 5 coloane.

se declara doua matrice : a cu 8 elemente de tip int, care are 2 linii si 4 coloane in care s-au atribuit valori initiale ale elementelor.

unde nume este numele matricei, <indice_1> este numarul de ordine al liniei, iar <indice_2> este numarul de ordine al coloanei.

	indicele coloanei        j

Deoarece adresa matricei este si adresa primului element, iar indicii reprezinta deplasarea elementului fata de adresa matricei, numerotarea indicilor se face                    pornind de la 0, iar 0<=indice_1<m si 0<=indice_2<n, unde m reprezinta numarul de linii, si n numarul de coloane ale matricei, precizate la declararea ei. In exemplu, a[1][2] reprezinta elementul din linia a 2-a si coloana a 3-a din matricea a, si are valoarea 7.

Tabloul de memorie fiind o structura de date statica, la declararea lui i se aloca o zona fixa de memorie. Lungimea tabloului de memorie reprezinta numarul de elemente ale tabloului. La declararea tabloului, este posibil sa nu se cunoasca numarul de elemente care vor fi prelucrate la fiecare executie a programului. In prelucrarea tabloului de memorie se folosesc doua lungimi :

Lungimea fizica. Reprezinta numarul de elemente stabilit la declararea tabloului. Este numarul maxim de elemente care pot fi stocate in spatiul de memorie rezervat tabloului. In cazul unei matrice, lungimea fizica este data de produsul dintre numarul de linii si numarul de coloane precizate la declararea matricei.

Lungimea logica.  Reprezinta numarul de elemente care vor fi prelucrate la executia programului. Este mai mic sau cel mult egal cu lungimea fizica (numarul maxim de elemente). Lungimea logica se comunica in timpul executiei programului (de la tastatura, sau se citeste dintr-un fisier text). In cazul matricei, ea reprezinta produsul dintre numarul de linii si numarul de coloane ale matricei (mxn).

Pentru elementul a[i][j], unde i  si j reprezinta indicele liniei, respectiv al coloanei, se definesc succesorul elementului si predecesorul lui, astfel :

Elementul a[0][0] nu are predecesor, iar elementul a[m-1][n-1] nu are succesor.

5. Algoritmi pentru prelucrarea tablourilor bidimensionale

5.1 Algoritmi pentru parcurgerea elementelor unei matrice

Parcurgerea elementelor unei matrice se poate face :

de la primul element pana la ultimul element, sau

de la ultimul element pana la primul element.

Secventa de instructiuni pentru parcurgerea elementelor unei matrice de la primul element la ultimul element este :

Secventa de instructiuni pentru parcurgerea elementelor unei matrice de la ultimul element la primul element este :

Exemplul 1 - Citirea de la tastatura a valorilor elementelor unei matrice. Secventa de instructiuni este :

Exemplul 2 - Afisarea pe ecran a valorilor elementelor unei matrice. Secventa de instructiuni este :

Parcurgerea unei matrice pe contur :

a[0][j]   j=0 n-1-;  j--

a[i][n-1] i=1 m-1; i++

a[m-1][j]  j=n-2 0;  j--

Secventa de instructiuni este :

In sens trigonometric.

a[i][n-1] i=m-2 1; i--

a[m-1][j]  j=1 n-1;  j++

5.2 Algoritmi pentru prelucrarea matricelor patrate

O matrice patratica este o matrice in care numarul liniilor este egal cu numarul coloanelor. Lungimea logica a unei matrice patratice este n X n (unde n = numarul de linii si de coloane). Ea este impartita in zone, de cele doua diagonale :

diagonala principala ;

diagonala secundara .

Diagonala principala :

Diagonala secundara :

Cele doua diagonale impart matricea patrata in patru regiuni : Nord, Vest, Sud si Est :

Matrice speciale (sunt matrice care au anumite proprietati, in functie de valorile elementelor). Pentru a se face economie de memorie, aceste matrice pot fi memorate ca vetori.

Matrice patrata simetrica fata de diagonala. Daca este simetrica fata de diagonala principala (a[i][j] = a[j][i]), se vor memora in vetorul b numai elemente de pe diagonala principala si cele de deasupra diagonalei principale : b[k] = a[i][j], unde i=0 n-1 si j=i n-1. Daca este simetrica fata de diagonala secundara (a[i][j] = a[n-i-1][n-j-1]), se vor memora in vectorul b numai elementele de pe diagonala secundara si cele de deasupra diagonalei principale : b[k] = a[i][j],unde i=0 n-1 si j=0 n-i-1. Numarul de elemente ale vectorului b va fi : nx(n+1)/2.

Matrice simetrica fata de axe. Daca este simetrica fata de axa verticala (a[i][j] = a[i][n-j-1]), se vor memora in vectorul b numai elementele de pe axa verticala (numai daca numarul de coloane este impar) si cele de la dreapta axei verticale :b[k] = a[i][j], unde i=0 m-1 si j=0 n/2 (pentru n par) sau j=0 n/2-1 (pentru n impar). Numarul de elemente ale vectorului b va fi : m x (n/2+1) pentru n par, respectiv m x n/2, pentru n impar. Daca este simetrica fata de axa orizontala (a[i][j] = a[m-i-1][j], se vor memora in vectorul b numai elementele de pe axa orizontala (numai daca numarul de linii este impar) si cele de deasupra axei orizontale : b[k] = a[i][j], unde i=0 m/2 (pentru n par) sau i=0 m/2-1 (pentru m impar) si j=0 n-1. Numarul de elemente ale vectorului b va fi : n x (m/2+1) pentru m par, respectiv n x m/2, pentru m impar.

Matrice patrata diagonala. Toate elementele care nu se gasesc pe diagonala principala, respectiv secundara, au valoarea 0. Se vor memora in vectorul b numai elementele de pe diagonala principala, respectiv secundara : b[k] = a[i][i], respectiv b[k] = a[i][n-i-1], unde i=0 n-1. Numarul de elemente ale vectorului b va fi :n.

Matrice patrata triunghiulara. Toate elementele care se gasesc deasupra sau sub o diagonala au valoarea 0. Se va memora la fel ca o matrice patrata simetrica fata de acea diagonala.

6. Aplicatii cu matrice

** ** ************Problema 1 ** ** ************

Se citesc de la tastatura doua numere naturale n si m (1<m<10), 1<n<10) si o matrice a cu n linii si m coloane formata din numere intregi de cel mult 4 cifre fiecare. Scrieti programull C++ ce sorteaza descrescator elementele fiecarei linii. Matricea sortata se va afisa pe ecran, fiecare linie a matricei pe cate o linie a ecranului, elementele unei linii fiind separate prin spatii.

#include<iostream.h>

void main()

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

cout<<endl ;

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

     cout<<a[i][j]<< ' ';

  ** ** ************Problema 2 ** ** ************

Se citesc de la tastatura un numar natural n (1<n<10) si o matrice patratica cu n linii si n coloane formata din numere intregi de maximum 4 cifre. Scrieti programul C++ ce sorteaza descrescator doar elementele situate pe diagonala principala. Matricea sortata se va afisa pe ecran, fiecare linie a matricei pe cate o linie a ecranului, elementele unei linii fiind separate prin cate un spatiu.

#include<iostream.h>

void main()

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

** ** ************Problema 3 ** ** ************

Se citesc de la tastatura 2 numere naturale m si n  (2<m,n<10). Sa se scrie programul C++ care construieste in memorie o matrice A cu linii (numerotate de la 1 la m) si n coloane (numerotate de la 1 la n) cu proprietatea ca a[i][j] este cel mai mic numar care se poate obtine prin concatenarea lui i cu j. Matricea se va afisa pe ecran, cate o linie a matricei pe cate o linie a ecranului, elementele fiecarei linii fiind separate prin spatii. De exemplu pentru m=3 si n=4 se va afisa matricea urmatoare :

#include<iostream.h>

#include<conio.h>

void main()

** ** ************Problema 4 ** ** ************

Se considera subprogramul max1 care are 3 parametri : un tablou patratic de numere reale a, numarul n de linii si de coloane ale tabloului si numarul unei linii lin (0<=lin<n<21). Subprogramul returneaza cea mai mare valoare aflata pe linia lin a tabloului. Scrieti declararile necesare si definitia completa a subprogramului max1. Scrieti Declararile de variabile si programul principal care citeste de la tastatura valoarea maxima din matrice utilizand apeluri ale subprogramului max1.

Rezolvare : Subprogramul propus determina in maniera clasica, printr-o parcurgere a elementelor liniei, valoarea maxima de pe linia respectiva, in timp ce programul principal va determina exact in aceeasi maniera valoarea maxima dintre maximele returnate de subprogram pentru fiecare dintre liniile tabloului.

float max1(float a[20][20], int n, int lin)

#include <iostream.h>

void main()

 cout<<max<<endl;

** ** ************Problema 5 ** ** ************

Scrieti programul C++ care construieste in memorie o matrice patratica cu n linii si n coloane formata numai din valori 1 si 2 astfel incat elementele de pe diagonala secundara si cea principala sa fie egale cu 1, iar restul elementelor din matrice sa fie egale cu 2. Valoarea lui n (numar natural, 2<n<23) se citeste de la tastatura, iar matricea se va afisa pe ecran, cate o linie a matricei pe cate o linie a ecranuuli, cu cate un spatiu intre elementele fiecarei linii (ca in exemplu).

De exemplu, pentru n=5 se construieste in memorie si se afiseaza matricea :

#include<iostream.h>

void main()

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

** ** ************Problema 6 ** ** ************

Scrieti programul C++ care construieste in memorie o matrice patratica cu n linii si n coloane formata numai din valori 0,1 si 2 astfel incat elementele de pe diagonala secundara si cea principala sa fie egale cu 0, elementele situate intre diagonalele matricei, intre partea superioara si inferioara a acesteia, sa fie egale cu 1, iar restul elementelor din matrice sa fie egale cu 2. Valoarea lui n (numar natural, 2<n<23) se citeste de la tastatura, iar matricea se va afisa pe ecran, cate o linie a matricei pe cate o linie a ecranului, cu spatii libere intre elementele fiecarei linii (ca in exemplu).

De exemplu, pentru n=5 se construieste in memorie si se afiseaza matricea :

#include<iostream.h>

void main()

               else 

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

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

** ** ************Problema 7 ** ** ************

Scrieti programul C++ care citeste de la tastatura un numar natural n (2<n<30) si construieste in memorie o matrice patratica cu n linii si n coloane ale carei elemente vor primi valori dupa cum urmeaza :

• elementele aflate pe diagonala secundara a matricei vor primi valoarea n+1 ;
• elementele de pe prima linie, cu exceptia celui aflat pe diagonala secundara vor primi valoarea 1 ;
• elementele de pe a doua linie, cu exceptia celui aflat pe diagonala secundara vor primi valoarea 2 etc.

Programul va afisa matricea astfel contruita pe ecran, cate o linie a matricei pe cate o linie a ecranului, cu spatii intre elementele fiecarei linii (ca in exemplu).

De exemplu : pentru n=4 matricea  va contine :

#include<iostream.h>

void main()

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

      cout<<endl;

** ** ************Problema 8 ** ** ************

Un tablou bidimensional a cu m linii (1<m<11) si n coloane (1<n<21) cu elemente numere intregi se numeste palindromic daca sirul format prin parcurgerea sa linie cu linie, are primul element al parcurgerii egal cu ultimul element al parcurgerii, al doilea egal cu penultimul, etc. Sa se scrie un program C++ care citeste doua numere m si n si apoi elementele tabloului bidimensional a de la tastatura si afiseaza pe ecran mesajul « DA » in cazul in care a este palindromic si « nu » in caz contrar.

#include<iostream.h>

void main()

 k=-1;

 for(i=0;i<m;i++)

 palindrom=1;

 k=0;

 while (k<n*m/2 && palindrom)

    if (v[k]!=v[m*n-k-1])

      palindrom=0;

    else k=k+1;

 if (palindrom) cout<<'DA!';

   else cout<<'NU!';

Bibliografie

Informatica. Manual pentru clasa a IX-a

Autor : Tudor Sorin

Informatica. Manual pentru clasa a X-a

Autor (i): Marinel Serban, Emanuela Cerchez

Informatica. Manual pentru clasa a XI-a

Autor(i): Mariana Milosescu

www.cs.utt.ro

https://www.ace.tuiasi.ro/ro/index.htm

Contact |- ia legatura cu noi -|
Adauga document |- pune-ti documente online -|
Termeni & conditii de utilizare |- politica de cookies si de confidentialitate -|
Copyright © |- 2024 - Toate drepturile rezervate -|

Informatica

Access Autocad Baze de date C Calculatoare Catia Excel Foxpro Grafica design Html Internet Java Linux Mathcad Matlab Oracle Outlook Photoshop Php Powerpoint Retele calculatoare Sql Windows Word

Analize pe aceeasi tema Aplicatii - nnmodel Elemente fundamentale ale limbajului JavaScript Lucrare pentru atestarea competentelor profesionale la informatica - tablouri bidimensionale Algoritmi fundamentali de sortare

Ramai informat Informatia de care ai nevoie Acces nelimitat la mii de documente. Online e mai simplu. Contribuie si tu! Adauga online documentul tau.