Capitolul 7

 


TABLOURI UNIDIMENSIONALE


 

DECLARAREA TABLOURILOR

 

Numim tablou o colectie (grup, multime ordonata) de date, de acelasi tip, situate intr-o zona de memorie continua (elementele tabloului se afla la adrese succesive). Tablourile sunt variabile compuse (structurate),  deoarece grupeaza mai multe elemente. Variabilele tablou au nume, iar tipul tabloului este dat de tipul elementelor sale. Elementele tabloului pot fi referite prin numele tabloului si indicii (numere intregi) care reprezinta pozitia elementului in cadrul tabloului.

 

In functie de numarul indicilor utilizati pentru a referi elementele tabloului, putem intalni tablouri unidimensionale (vectorii) sau multidimensionale (matricile sunt tablouri bidimensionale).

 

Ca si variabilele simple, variabilele tablou trebuie declarate inainte de utilizare.

Modul de declarare:

     tip   nume_tablou[dim_1][dim_2]…[dim_n];

unde: tip reprezinta tipul elementelor tabloului; dim_1,dim_2,...,dim_n sunt numere intregi sau expresii constante intregi (a caror valoare este evaluata la compilare) care reprezinta limitele superioare ale indicilor tabloului.

           

TABLOURI UNIDIMENSIONALE

 

Tablourile unidimensionale sunt tablouri cu un singur indice (vectori).

Daca tabloul contine dim elemente, indicii elementelor au valori intregi din intervalul [0, dim-1].

Un element al unui tablou poate fi utilizat ca orice alta variabila. Adresarea unei componente se face proin indicele ei, trecut intre paranteze drepte. Se pot efectua operatii asupra fiecarui element al tabloului, nu asupra intregului tablou.

 

Exemple:

 

int vect[20]; /* declararea tabloului vect, de maximum 20 de elemente, de tipul int. Elementele tabloului vect sunt : vect[0], vect[1], …, vect[19] – date de tip int*/

           

double p,q,tab[10];  // declararea variabilelor simple p, q si a vectorului tab, de maximum 10 elemente, tip double

 

#define MAX 10

char tab[MAX];             /*declararea tabloului tab, de maximum MAX (10) elemente de tip char*/

 

 

Consideram declaratia tabloului v cu maxim 6 elemente de tip int

 

int v[6];              

 

Elementele tabloului pot fi initializate prin atribuire:

v[0]=100;

v[1]=101;

v[2]=102;

v[3]=103;

v[4]=104;

v[5]=105;

 

100

101

102

103

104

105

v[0]

v[1]

v[2]

v[3]

v[4]

v[5]

 

 

Exemplu:

double alpha[5], beta[5], gama[5];

int i=2;

alpha[2*i-1] = 5.78;

alpha[0]=2*beta[i]+3.5;

gama[i]=aplha[i]+beta[i];       //permis

gama=alpha+beta;                                //nepermis

 

Variabilele tablou pot fi initializate in momentul declararii:

declaratie_tablou=lista_valori;

 

Valorile din lista de valori sunt separate prin virgula, iar intreaga lista este inclusa intre acolade:

 

Exemple:

            int v[6]={100,101,102,103,104,105};

double x=9.8;

double a[5]={1.2, 3.5, x, x-1, 7.5};

 

La declararea unui vector cu initializarea elementelor sale, numarul maxim de elemente ale tabloului poate fi omis, caz in care compilatorul determina automat marimea tabloului, in functie de numarul elementelor initializate.

Exemplu:

char tab[]={ ’A’, ’C’, ’D’, ’C’};

 

 


                            [0]                            [3]

 

            float data[5]={ 1.2, 2.3, 3.4 };

 

                                   

                         

    [0]                                       [4]

 

Citirea elementelor unui vector:

     double a[5];

     int i;

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

     {    cout<<”a["<<i<<”]=”;    //afisarea unui mesaj prealabil citirii fiecarui element

          cin>>a[i];              //citirea valorii elementului de indice i

     }

Sau, pentru un vector cu n componente (n£20):

double a[20]; int i, n;

     cout<<”Dim. Max. =”; cin>>n;

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

     {    cout<<”a[“<<i<<”]=”;

          cin>>a[i];

     }

Pentru simplitate, se pot considera elementele vectorului incepand cu pozitia 1. In acest caz, primul element al tabloului ramane neutilizat, iar valoarea sa este cea alocata implicit la compilare.

double a[20]; int i, n;

     cout<<”Dim. Max. =”; cin>>n;

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

     {    cout<<”a[“<<i<<”]=”;

          cin>>a[i];

     }

 

Afisarea elementelor unui vector:

     cout<<”Vectorul introdus este:\n”;

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

          cout<<a[i]<<’ ’;

Probleme propuse:

1.            Se citeste un vector cu n componente numere intregi. Sa se calculeze media aritmetica a componentelor vectorului.

2.            Se citeste un sir de n numere intregi, n dat. Sa se numere elementele pozitive si pare. Calculati produsul elementelor negative. Sa se calculeze media aritmetica a elementelor pozitive din vector.

3.            Fie n numere naturale date. Sa se afiseze acelea dintre ele care sunt prime.

4.            Sa se afiseze si sa se numere elementele pare de pe pozitiile impare ale unui vector.

5.            Fie doi vectori x si y, de marime n. Sa se calculeze:

a)      E=(x1+y1)* (x2+y2)* ......*(xn+yn)

b)      E=x1y1+ x2y2 +......+xnyn

c)      E=min(x1,y1)+min(x2,y2)+ ......min(xn,yn)

d)      E=min(x1,yn)+min(x2,yn-1)+ ......min(xn,y1)

6.            Sa se ordoneze crescator / descrescator un vector.

7.            Determinarea maximului / minimului unui vector si afisarea pozitiilor pe care apar.

8.            Sa se roteasca un vector cu o pozitie la dreapta / stanga (ultimul element devine primul, respectiv primul element devine ultimul).

9.            Rotirea unui vector cu k pozitii la stanga (dreapta).

10.        Sa se mute la sfarsitul unui tablou toate elementele nule.

11.        Construiti un vector care sa contina primele n numere prime.

12.        Sa se puna intr-un vector toate numerele prime pana la n care, inversate, sunt tot prime.

13.        Suma si produsul a doua polinoame. Valoarea unui polinom intr-un punct.

14.        Sa se verifice daca un vector este ordonat (crescator sau descrescator).

15.        Dandu-se un vector neordonat cu n componente diferite, sa se determine elementul cu numarul de ordine k din tabloul ordonat crescator, fara a se ordona tabloul.

16.        Dandu-se un vector neordonat cu n componente diferite, sa se determine pozitia elementului a[k] in tabloul ordonat crescator, fara a se ordona tabloul.

17.        Sa se gaseasca un element k printre elementele unui vector. Daca se gaseste, sa se afiseze pozitiile pe care apare. Daca nu, sa se dea un mesaj.

18.        Sa se verifice daca un vector contine elementele in ordinea pozitiv – negativ – pozitiv – negativ etc. Se va afisa DA sau NU.

19.        Sa se verifice daca un vector contine elementele in ordinea pozitiv – negativ – pozitiv – pozitiv – negativ – negativ – pozitiv – pozitiv – pozitiv etc. Se va afisa DA sau NU.

20.        Un vector se numeste alternativ daca pentru orice i, a[i]*a[i+1]=0. Scrieti un program care decide daca un vector este alternativ sau nu.

21.        Interclasarea a doi vectori ordonati

22.        Sa se numere de cate ori se intampla ca intr-un vector, un element sa fie egal cu suma (produsul, media aritmetica, geometrica) vecinilor sai.

23.        Sa se determine media aritmetica a elementelor unui vector, in care elementele egale se  vor lua o singura data.

24.        Sa se verifice daca elementele unui sir pot forma o progresie aritmetica (geometrica). Daca da, sa se afiseze ratia.

25.        Sa se inverseze un vector in el insusi.

26.         

27.        Sa se insereze un element intr-un vector, la pozitia k. Sa se repete operatia de mai multe ori.

28.        Sa se stearga un elementul din pozitia k dintr-un vector.

29.        Sa se calculeze cmmdc a n numere naturale.

30.        Sa se afiseze cifrele distincte ale unui numar, si frecventa lor de aparitie.

31.        Se citeste un vector cu n componente numere intregi. Sa se construiasca vectorul format din suma (produsul) cifrelor elementelor din primul vector.

32.        Fie doi vectori a si b cu m, respectiv n elemente numere reale. Sa se afiseze cate din componentele vectorului a sunt strict mai mici decat toate componentele vectorului b.

33.        Sa se afiseze primele n elemente din sirul lui Fibonacci (F[0]=1, F[1]=1, F[n]=F[n-1]+F[n-2], n>1).

34.        Sa se decida daca elementele unui vector sunt distincte.

35.        Sa se afiseze diferenta, intersectia, reuniunea si produsul cartezian a doua multimi de numere reale.

36.        Fie un vector de numere intregi. Sa se determine, daca exista, un numar p care sa fie cel mai mare element prim din vector. Daca nu exista, atunci p sa fie 0. Daca p este nenul, sa se imparta toate componentele vectorului la suma cifrelor lui p.

37.        Sa se inmulteasca un numar foarte mare cu  un numar format dintr-o singura cifra.

38.        Suma a doua numere mari.

39.        Sa se transforme un numar din baza 10 in baza 2. Generalizare pentru baza b, 2<=b<=16.

40.        Sa se elimine zerourile dintr-un vector, fara a schimba ordinea elementelor nenule.

41.        Mos Craciun a primit scrisori de la toti copiii cuminti, scrisori pe care le-a numerotat in ordinea sosirii, incepand de la 1. Plecand la drum, si-a dat seama ca, in graba, a uitat cateva scrisori. Scoate din sac cate o scrisoare, notand pe o foaie numarul fiecareia. Stiind ca a primit n scrisori, scrieti un program care le afiseaza pe cele pe care le-a uitat acasa. Se da numarul de scrisori n si numerele scrisorilor existente in sac. Enumerarea lor se va termina cu 0

42.        Un grup de teroristi ce pregatesc o lovitura de stat isi propun sa ocupe un aeroport strategic. Ei detin harta zborurilor intre cele n aeroporturi, adica m perechi (i,j) ce indica faptul ca exista zbor din aeroportul i in aeroportul j. Ei vor ocupa acel aeroport din care se poate ajunge in fiecare din celelalte aeroporturi, dar in care nu se poate ajunge. Scrieti un program care gaseste aeroportul care trebuie ocupat

43.        Intr-un zoo-magazin sunt n colivii cu papagali, toate inchise. O maimuta jucausa pleaca de la prima colivie si, din 2 in 2, deschide usile coliviilor. Apoi porneste iar de la prima colivie si, din 3 in 3, deschide usile inchise si inchide usile deschise. Face acelasi lucru din 4 in 4, samd..., din k in k (k<n). Scrieti un program care afiseaza coliviile care in final vor ramane deschise

44.        Numerele de la 1 la n sunt asezate pe circumferinta unui  unui cerc, astfel incat n ajunge langa 1. Incepand cu numarul s, se elimina numerele din k in k, dupa fiecare eliminare cercul strangandu-se. Care va fi numarul ramas?

45.        Aceeasi problema, dar numerele nu se elimina, ci se marcheaza, pana cand un numar va fi marcat de 2 ori. Cate numere au ramas nemarcate ?

46.        Sa se determine cea mai lunga secventa de numere crescatoare consecutive intr-un vector.

47.        Sa se determine cel mai lung sir de numere crescatoare dintr-un sir. Numerele nu vor fi neaparat consecutive, dar se va pastra ordinea lor.

48.        Sa se determine cea mai lunga secventa palindromica dintr-un sir. (elemente consecutive)

49.        Se citeste un numar intreg foarte mare(care depaseste orice domeniu), cifra cu cifra. Sa se verifice daca numarul citit poate reprezenta factorialul vreunui numar natural. Daca da, sa se afiseze acel numar. Daca nu, sa se dea un mesaj.

Ex: (n!=1*2*3*...*n – factorialul lui n)

40320=8!  

1307674368000=15!         

1=1!        

12 – Nu este factorialul nici unui numar natural

50.        Un alpinist parcurge un munte si masoara cotele de altitudine in diverse puncte prin care trece. Seara, in popas, vrea sa afle:

a)      numarul piscurilor traversate (cotele alaturate piscului sunt strict mai mici decat acesta)

b)      numarul vailor traversate

c)      numarul platformelor traversate

d)      cea mai mare panta urcata, ca diferenta de altitudine

e)      cea ai mare panta coborata, tot ca diferenta de altitudine

Exemplu:

Pentru n=13 si 4,8,6,7,7,3,2,1,3,8,8,8,7 se va afisa :

piscuri 1

vai 2

platforme 2

cea mai lunga panta in urcare 1 3 8

cea mai lunga panta in coborare 7 3 2 1

51.        Sa se genereze toate submultimile multimii {1,2,3…n}

52.        Sa se genereze toate submultimile multimii {a[1],a[2],a[3]…a[n]}

53.        Fie un sir de n numere naturale. Sa se determine cel mai lung subsir cu proprietatea ca elementele sunt in ordine crescatoare. Daca exista mai multe astfel de siruri, se va afisa macar unul. Elementele din subsir nu trebuie sa fie consecutive in sirul dat.

54.        Fie un numar de n cifre, citit cifra cu cifra. Sa se elimine k cifre astfel incat numarul ramas sa fie maxim, fara a schimba ordinea cifrelor ramase.