Algoritmi legati de lucrul cu tablouri unidimensionale (vectori)
proba
Tablourile sunt colecţii de date de acelaşi tip reunite sub un singur nume, care ne permit să programăm mai uşor operaţii asupra grupurilor de valori de acelaşi tip.
Declararea tabloului este similară cu declaraţia unei variabile simple, cu o singură excepţie: trebuie declarată şi dimensiunea tabloului. Numărul de componente se declară între paranteze pătrate [ ].
Declaraţia
float date[50];
crează un vector (numit "date") cu 50 de elemente tip float.Primul element are indicele 0, al doilea are indicele 1, …, iar ultimul are indicele 49.
Un tablou unidimensional (numit de foarte multe ori vector) este deci o colecţie structurată de elemente care pot fi accesate individual, specificând poziţia componentei printr-un indice (variabilă de tip întreg).
Sintaxa unei declaraţii de tablou unidimensional (vector):
TipDată NumeTablou[ExpresieConstInt];
Elementele unui tablou pot fi aproape de orice tip de dată.
Expresia dintre parantezele drepte este o constantă întreagă, ce trebuie să fie strict mai mare decât 0 şi determină numărul de componente ale tabloului.
Dacă valoarea este n, domeniul indicilor va fi între 0 şi n-1, deci vectorul are n elemente.
Pentru a avea acces la componentele individuale ale unui vector, scriem numele vectorului urmat de o expresie indice între [ ].
Expresia specifică numărul componentei accesate şi poate fi o constantă întreagă, o variabilă întreagă, sau o expresie care este evaluată la o valoare întreagă. Oricare ar fi însă forma indicelui, acesta trebuie să fie o valoare întreagă.
Fiecare componentă a unui tablou poate fi tratată exact ca o variabilă simplă.
Elementele unui tablou pot fi iniţializate în instrucţiunea de declarare prin adăugarea unei liste de valori separate prin virgulă, plasate între acolade.
Exemplu
O variantă on-line poate fi experimentată la 
sau la vectoriInitializare
Dacă se înscriu mai multe valori în listă, compilatorul semnalează o eroare. Dacă sunt mai puţine valori în listă, restul sunt iniţializate cu valoarea 0.
Up Home Structura Site Algoritmi elementari
A. Citirea elementelor unui vector de la tastatură; prelucrarea elementelor; afişarea
O variantă on-line poate fi experimentată la 
sau la vectoriCitTast
Up Home Structura Site Algoritmi elementari
B. Citirea unui vector dintr-un fisier
B1. Cazul în care se cunoaşte numărul elementelor
vectoriCitFis1
6
3 -8 11 3 17 2
B2. Cazul în care NU se cunoaşte numărul elementelor
vectoriCitFis2.in
3 -8 11 3 17 2
EXEMPLE DE ALGORITMI
A. Căutarea unei valori intr-un vector neordonat
vectoriCautValoare.in
40
17 3 22 23 15 17 4 11 47 28 5 9 41 21 37 5 18 33 12 17 4 81 33 14 29 5 44 62 11 76 1 52 48 79 6 35 32 33 8 28
O variantă on-line poate fi experimentată la 
sau la vectoriCautValoare
Up Home Structura Site Algoritmi elementari
B. Maxime şi minime în vectori
vectoriMaxMin.in
40
17 3 22 23 15 17 4 11 47 28 5 9 41 21 37 5 18 33 12 17 4 81 33 14 29 5 44 62 11 76 1 52 48 79 6 35 32 33 8 28
O variantă on-line poate fi experimentată la 
sau la vectoriMaxMin
Up Home Structura Site Algoritmi elementari
C. Ordonarea crescătoare a elementelor unui vector, prin interschimbare
Comparăm primul element din vector cu toate elementele care urmează după el. Dacă găsim un element mai mic decât primul, atunci le interschimbăm pe cele două. Apoi continuăm cu al doilea element al şirului, pe care, de asemenea îl comparăm cu toate elementele care urmează după el şi în cazul în care găsim un element mai mic decăt al doilea,interschimbăm cele două elemente. Apoi procedăm la fel cu al treilea element al şirului iar procesul continuă astfel pâna la penultimul element al şirului care va fi comparat doar cu ultimul element din şir.
vectoriMaxMin.in
40
17 3 22 23 15 17 4 11 47 28 5 9 41 21 37 5 18 33 12 17 4 81 33 14 29 5 44 62 11 76 1 52 48 79 6 35 32 33 8 28
O variantă on-line poate fi experimentată la 
sau la vectoriOrdonareDirecta
Up Home Structura Site Algoritmi elementari
D. Ordonarea crescătoare a elementelor unui vector, prin metoda bulelor
În acest algoritm, se compară fiecare din primele n-1 elemente cu elementul următor, cu interschimbarea celor care nu respectă condiţia (v[j] < v[j+1], pentru ordonarea crescătoare, sau v[j] > v[j+1], pentru ordonarea descrescătoare). Algoritmul se repetă de n-1 ori.
Două frumoase prezentari ale acestei metode se găsesc pe internet:
Prima prezentare respectiv A doua prezentare
vectoriOrdonareBule.in
40
17 3 22 23 15 17 4 11 47 28 5 9 41 21 37 5 18 33 12 17 4 81 33 14 29 5 44 62 11 76 1 52 48 79 6 35 32 33 8 28
O variantă on-line poate fi experimentată la 
sau la vectoriOrdonareBule
Up Home Structura Site Algoritmi elementari
E. Deplasarea la dreapta a unui vector, cu insertia pe prima poziţie a unei valori k şi mărirea dimensiunii vectorului
20
17 22 15 47 41 37 33 12 81 33 29 44 62 76 52 48 79 35 32 28
O variantă on-line poate fi experimentată la 
sau la vectoriDeplasareDreapta
Observaţie: în mod asemănător, se poate insera o valoare k pe orice poziţie p
Up Home Structura Site Algoritmi elementari
F. Deplasarea la dreapta a unui vector, cu recirculare (rotirea la dreapta)
20
17 22 15 47 41 37 33 12 81 33 29 44 62 76 52 48 79 35 32 28
O variantă on-line poate fi experimentată la 
sau la vectoriRotireDreapta
Up Home Structura Site Algoritmi elementari
G. Deplasarea la stânga a unui vector, cu pierderea primei valori şi micşorarea dimensiunii vectorului
20
17 22 15 47 41 37 33 12 81 33 29 44 62 76 52 48 79 35 32 28
O variantă on-line poate fi experimentată la 
sau la vectoriDeplasareStanga
Observaţie: în mod asemănător, se poate elimina orice element de pe orice poziţie p
Up Home Structura Site Algoritmi elementari
H. Deplasarea la stânga a unui vector, cu recirculare (rotirea la stânga)
20
17 22 15 47 41 37 33 12 81 33 29 44 62 76 52 48 79 35 32 28
O variantă on-line poate fi experimentată la 
sau la vectoriRotireStanga
Up Home Structura Site Algoritmi elementari
I. Crearea unor vectori diferiţi ca dimensiune şi conţinut dintr-un vector dat
I.1. Crearea
Din vectorul v se crează vectorii v1 (cuprinzând elementele de pe poziţiile impare din v) şi v2 (cuprinzând elementele de pe poziţiile pare din v)
20
17 22 15 47 41 37 33 12 81 33 29 44 62 76 52 48 79 35 32 28
O variantă on-line poate fi experimentată la 
sau la vectoriCreari1
Up Home Structura Site Algoritmi elementari
I.2. Crearea
Din vectorul v se crează vectorii v1 (cuprinzând elementele impare din v) şi v2 (cuprinzând elementele pare din v)
20
17 22 15 47 41 37 33 12 81 33 29 44 62 76 52 48 79 35 32 28
O variantă on-line poate fi experimentată la 
sau la vectoriCreari2
J. Elementele distincte într-un vector
Să se verifice dacă un vector are sau nu elementele distincte
Pentru vectorul de intrare
40 17 3 22 23 15 17 4 11 47 28 5 9 41 21 37 5 18 33 12 17 4 81 33 14 29 5 44 62 11 76 1 52 48 79 6 35 32 33 8 28
Se obţin rezultatele:
O variantă on-line poate fi experimentată la Elementele distincte vector
K. Vectori de consistenţă - Vectori caracteristici
(Vectori de fanioane)
Presupunând că fişierul de intrare cuprinde numerele
17 3 22 23 15 17 4418 4 11 47 28 5 9 251 41 21 5666 37 5 18 33 12 17 94584 4 81 33 99 14 702 39037 29 5 44 62 11 8543 76 1 52 111 48 79 6 35 32 33 8 28
rezultatele sunt:
O variantă on-line poate fi experimentată la Vectori de consistenta
L. Vectori de frecvenţă
(Vectori de contoare)
Presupunând că fişierul de intrare cuprinde numerele
17 3 22 23 15 17 4418 4 11 47 28 5 9 251 41 21 5666 37 5 18 33 12 17 94584 4 81 33 99 14 702 39037 29 5 44 62 11 8543 76 1 52 111 48 79 6 35 32 33 8 28
rezultatele sunt:
O variantă on-line poate fi experimentată la Vectori de frecventa
M. Elemente comune in doi vectori
Presupunând că primul fişier de intrare cuprinde numerele
17 3 22 23 15 4 11 47 28 5 9 41 21 37 18 33 12 81 14 29 5 44 62 76 1 52 48 79 6 35 32 33 8 28
iar al doilea fişier de intrare cuprinde numerele
3 11 27 32 35 37 44 45 46 54 61 63 71 73 77 76 78 81 82 85 88 89 90 92 95 96 99
rezultatele sunt:
O variantă on-line poate fi experimentată la Elemente comune in doi vectori
N. Descompunerea în factori primi
O variantă on-line poate fi experimentată la Desc fact primi
Up Home Structura Site Algoritmi elementari
TEME DE LABORATOR
- Se citeşte de la tastatură numărul n de componente, apoi elementele (numere naturale), ale vectorului unidimensional v. Să se afişeze maximul, minimul şi poziţiile pe care acestea le ocupă în vector (numărul n şi elementele v[i] vor fi definite unsigned long)
- Pentru vectorul de la punctul 1, să se afişeze suma tuturor elemetelor pare de pe poziţii impare
- Utilizând vectorul v de la punctul 1, să se creeze vectorul w, care conţine toate elementele din v, iar între fiecare două elemente successive media aritmetică a acestor elemente
- Utilizând vectorul v de la punctul 1, să se creeze vectorul w, care conţine numerele prime din v
- Se citeşte de la tastatură un număr n (unsigned long); să se creeze şi afişeze vectorul w, care conţine cifrele numărului n
- Se citeşte de la tastatură un număr n (unsigned long); să se afişeze cel mai mare număr natural care se poate obţine utilizând cifrele numărului n
BONUS:
- Să se rotească circular spre stânga vectorul v de la punctual 1 cu exact k poziţii (k număr natural introdus de la tastatură)
- Implementaţi o metodă eficientă pentru problema de la punctual 9, în cazul în care n şi k pot fi numere foarte mari
- În vectorul v, de la punctul 1, să se intercaleze pe poziţia k valoarea m (k şi m citite de la tastatură)
- Să se şteargă elementul de pe poziţia k din vectorul v (k citit de la tastatură)
SUPERBONUS
- Elementele vectorului v de la punctul 1 reprezintă elementele unei mulţimi A; să se construiasă vectorul w care conţine elementele celei mai largi (cu cel mai mare număr de elemnte posibil) submulţimi B, care satisfice condiţia că suma elementlor este divizibilă prin 3.