Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Sirul si tabloul

c

+ Font mai mare | - Font mai mic





DOCUMENTE SIMILARE

Trimite pe Messenger
Tipuri abstracte de date
Liste - Lista simplu si dublu inlantuite
FUNCTII SI STRUCTURA PROGRAMULUI
Caractere speciale si de punctuatie
APLICATII IN LIMBAJ C++, UTILE IN PROIECTAREA ASISTATA
Clase si functii template in C++
Tipuri de date predefinite
Algoritmi divide et impera
Modifica informatia nodului cu info=para din lista
Pointeri spre functii

TERMENI importanti pentru acest document

Sirul si tabloul




Definitia 3.2

Un sir este o multime ordonata de elemente, care apartin unei clase de simboluri elementare.

Lungimea unui sir este egala cu numarul de elemente care compun sirul. Tipul unui sir este tipul caracter. Pot exista siruri de biti, siruri de cifre, siruri de litere, siruri de cifre si litere, siruri de caractere. Cele mai importante operatii definite pe siruri sunt operatia de concatenare si operatia de comparare.

Definitia 3.3

Un tablou este o multime ordonata de elemente de acelasi tip.

Ordonarea elementelor intr-un tablou este folosita pentru a identifica elementele in cadrul tabloului, in care scop se utilizeaza un ansamblu de indici. Numarul de indici folositi pentru a identifica elementele unui tablou constituie numarul de dimensiuni al tabloului. Astfel, exista tablouri cu o dimensiune (vectori), tablouri cu doua dimensiuni (matrice) etc.

Fiecarui element al unui tablou i se va aloca o zona de memorie numita locatie, lungimea acestei locatii fiind functie de tipul tabloului. Elementele unui vector vor ocupa in ordine locatii succesive de memorie. Pentru reprezentarea unei matrice se pot folosi doua metode:

memorarea succesiva pe linii a elementelor;

memorarea succesiva pe coloane a elementelor.

Fie N1,,Np multimi total ordonate cu | Ni | = ni , i = 1,,p. Pentru simplificare, vom nota in acelasi mod (<, ≤) cele p relatii de ordine. Fie multimea N = N1 x x Np, si x, y I N , x = (x1, , xp), y = (y1, , yp), xi, yi Ni, i=1,,p. Pe multimea N se pot introduce urmatoarele doua relatii de ordine:

relatia de ordine lexicografica, conform careia avem x ≤ y daca x = y sau x < y ( adica k astfel incat xi = yi, i = 1, , k-1, xk < yk );

relatia de ordine invers lexicografica, conform careia x ≤ y daca x = y sau x < y ( adica k astfel incat xk < yk, xi = yi , i = k+1, , p).

Observam ca pentru o matrice cu m linii si n coloane ordinea de memorare pe linii corespunde ordinii lexicografice pe N = N1 x N2 = x , iar ordinea de memorare pe coloane corespunde relatiei de ordine invers lexicografice pe aceeasi multime.

Fie T(n1, n2, , np) un tablou p dimensional avand limitele maximale pentru indicii i1, i2, , ip respectiv pe n1, n2, , np. Fie Nk = , k = 1, , p, n = n1 n2 np , Nn = . Definim bijectia

r1 : N1 x x Np-1 x Np Nn



r1(i1, , ip-1, ip) = ip + (ip-1 - 1)np + (ip-2 - 1)npnp-1 + + (i1 - 1)npn2

Numarul r1(i1, , ip-1, ip) numit rangul elementului T(i1, , ip-1, ip) reprezinta numarul locatiei de memorie a elementului in memorarea tabloului conform relatiei de ordine invers lexicografice pe multimea N1 x x Np-1 x Np.

Analog definim bijectia

r2 : N1 x N2 x x Np Nn

r2(i1, i2, , ip) = i1 + (i2 - 1)n1 + (i3 - 1)n1n2 + + (ip - 1)n1n2np-1

Numarul r2(i1, i2, , ip) numit rangul elementului T(i1, i2, , ip) reprezinta numarul locatiei de memorie a elementului in memorarea tabloului conform relatiei de ordine invers lexicografice pe multimea N1 x N2 x x Np.

Exemplul 3.1

N1 = N2 =

p = 2, n1 = 3, n2 = 4, n = 12

N12 =

 

Memorarea pe linii

i 2 3 4 5 6 7 8 9 10 11 12

xi (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4)

Avem xi < xi , i = 1, ,11 in ordinea lexicografica; xi = (xi1, xi2)

r1 : N1 x N2 N12, r1(i1, i2) = i2 + (i11)n2

r1(2, 3) = 3 + (21)*4 = 7

Memorarea pe coloane

i 1 2 3 4 5 6 7 8 9 10 11 12

xi (1,1) (2,1) (3,1) (1,2) (2,2 ) (3,2) (1,3) (2,3) (3,3 ) (1,4) (2,4) (3,4)

Avem xi < xi , i = 1, , 11 in ordinea invers lexicografica; xi = (xi1, xi2)

r2 : N1 x N2 N12, r2(i1, i2) = i1 + (i21)n1

r2(2, 3) = 2 + (3 1) * 3 = 8






Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 447
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2021 . All rights reserved

Distribuie URL

Adauga cod HTML in site