Tablouri unidimensionale

15
Tablouri unidimensionale Neacsu Tiberiu Clasa a X-a A

Transcript of Tablouri unidimensionale

Page 1: Tablouri unidimensionale

Tablouri unidimensionale

Neacsu TiberiuClasa a X-a A

Page 2: Tablouri unidimensionale

Definitia, declaratia si lungimea unui tablou unidimension... Minimul, maximul si numarul de aparitii intr-un vector Cautarea secventiala – toate aparitiile Cautarea secventiala – prima aparitie Cautarea secventiala – ultima aparitie Cautarea secventiala – verificarea aparitiei Permutarea circulara spre stanga si spre dreapta cu o poziti

e Permutarea circulara spre stanga si spre dreapta cu k poz... Stergerea si inserarea unei valori dintr-un vector Sortarea vectorilor Interclasarea vectorilor Cautarea binara Vectorul caracteristic

Cuprins

Page 3: Tablouri unidimensionale

Se numeste vector o variabila capabila sa retina o colectie de valori de acelasi tip.

Declaratia unui vector : x:array [1..20] of byte; Se numeste lungimea unui vector o variabila care va retine

numarul efectiv de celule pe care programul le prelucreaza la un moment dat (ex: n:byte; pentru variabila x).

Definitia, declaratia si lungimea unui tablou unidimensional (vector)

Page 4: Tablouri unidimensionale

Minimul, maximul si numarul de aparitii intr-un vectorex: n=6x1=1.75x2=2.25x3=1.75x4=3.75x5=3.75x6=1--------1.0003.75 2

Secventa min:=x[1]; nr:=1;For i:=2 to n do if x[i]<min then

min:=x[i];writeln (min:1:3);For i:= 2 to n do if x[i]>max then

beginmax:=x[i]; nr:=1; endelse if x[i]=max then

nr:=nr+1;Writeln (max:1:3,’ ‘,nr);

Page 5: Tablouri unidimensionale

Cautarea secventiala – toate aparitiileEnunt: Sa se afiseze, separate prin

spatiu, toate aparitiile valorilor pare.

Secventa: for i:=1 to n do

if x[i] mod 2=0 thenwrite (i,’ ‘);

Page 6: Tablouri unidimensionale

Cautarea secventiala – prima aparitieEnunt:Sa se afiseze prima aparitie a

unei valori cu o singura cifra. Atentie! Nu avem siguranta gasirii acesteia.

Secventa:p:=0;For i:=1 to n do

if x[i]<=9 then beginp:=i; break;

end;If p>0 then writeln (‘Prima

aparitie a unei cifre este pe pozitia ‘,p)

else writeln (‘Nu exista’);

Page 7: Tablouri unidimensionale

Cautarea secventiala – ultima aparitieEnunt:Sa se afiseze ultima aparitie a

unui numar ce are prima cifra para.

Secventa:u:=0;For i:=n downto 1 do begin

aux:=x[i];while aux>9 do

aux:=aux div 10;if aux mod 2=0 then begin

u:=i; break; end;end;

if u<>0 then writeln (‘Ultima aparitie a unui numar cu prima cifra para,’ ‘,u)

else writeln (‘Nu exista’);

Page 8: Tablouri unidimensionale

Cautarea secventiala – verificarea aparitieiEnunt:Sa se precizeze daca in tablou

exista numere impare.

Secventa:ok:=false;For i:=1 to n do

if x[i] mod 2=1 then beginok:=true; break; end;

if ok=true then writeln (‘Exista numere impare’)

else writeln (‘Nu exista numere impare’);

Page 9: Tablouri unidimensionale

Permutarea circulara spre stanga si spre dreapta cu o pozitieSpre stangaaux:=x[1];For i:=2 to n do

x[i-1]:=x[i];x[n]:=aux;

Spre dreaptaaux:=x[n];For i:=n-1 downto 1 do

x[i+1]:=x[i];x[1]:=aux;

Page 10: Tablouri unidimensionale

Permutarea circulara spre stanga si spre dreapta cu k pozitiiSpre stanga

Varianta 1: - de k ori cu o pozitie

k:=k mod n;

For i:=1 to k do begin

aux:=x[1];

for j:=2 to n do

x[j-1]:=x[j];

x[n]:=aux; end;

Varianta 2: - cu k pozitii

k:=k mod n;

For i:=1 to k do

x[n+i]:=x[i];

For i:=1 to n do

x[i]:=x[k+i];

Spre dreapta

Varianta 1: - de k ori cu o pozitiek:=k mod n;For i:=1 to k do begin

aux:=x[n];for j:=n-1 downto 1 do

x[j+1]:=x[j];x[1]:=aux; end;

Varianta 2: - cu k pozitiik:=k mod n;For i:=1 to (n-k) do

x[n+1]:=x[i];For i:=1 to n do

x[i]:=x[n-k+i];

Page 11: Tablouri unidimensionale

Stergerea si inserarea unei valori dintr-un vectorStergerea unei valori dintr-

un vectorFor i:=p to n-1 do

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

Inserarea unei valori dintr-un vector

For i:=n downto p doa[i+1]:=a[i];

n:=n+1;a[p]:=v;

Page 12: Tablouri unidimensionale

Sortarea vectorilorVarianta 1For i:=1 to n-1 do begin

r:=I;for j:=i+1 to n do

if x[j]<x[r] then r:=j;aux:=x[r];x[r]:=x[i];x[i]:=aux; end;

Varianta 2For i:=1 to n-1 do

for j:=i+1 to n doif x[j]<x[i] then begin

aux:=x[i];x[i]:=x[j];x[j]:=aux;

end;

Page 13: Tablouri unidimensionale

Interclasarea vectorilorSecventai:=1; j:=1;While (i<=n) and (j<=m) do

if x[i]<y[j] then begin write (x[i],’ ‘);i:=i+1;end

else beginwrite (y[j],’ ‘);j:=j+1;end;

For k:=i to n do write (x[k],’ ‘);For k:=j to m do write (y[k],’ ‘);

Page 14: Tablouri unidimensionale

Cautarea binaraSecventagasit:=false;i:=p; j:=q;While i<=j do begin

m:=(i+j) div 2;If v=x[m] then begin

gasit:=true; break; endelseif v<x[m] then j:=m-1

else i:=m+1;end;

Page 15: Tablouri unidimensionale

Vectorul caracteristicConsideram ca vectorul x1, x2, … , xn

contine doar cifre (n<=10000)

Se foloseste vectorul auxiliar

v0, v1, v2, … , v9 deoarece {0,1,2, … ,9} este intervalul ordinal in care sunt incadrate valorile din vector

v[i] = - 0, daca valoarea i nu apare in vectorul x

- de cate ori apare valoarea I in vectorul x

Secventa I. Initializare vector caracteristicFor i:=0 to 9 do v[i]:=0;

II. Actualizare vector caracteristicFor i:=1 to n do

v[x[i]]:=v[x[i]]+1;

III. Utilizarea vectorului caracteristicFor i:=0 to 9 do

if v[i]>0 then write (I,’ ‘);