Creeaza.com - informatii profesionale despre
TehnologieAfaceriScoalaDidacticaLegislatieFamilie


Evidentiem nevoile sociale din educatie - Referate profesionale unice
Acasa » scoala » informatica
INTERCLASARE + CAUTARE BINARA

INTERCLASARE + CAUTARE BINARA


INTERCLASARE + CAUTARE BINARA

1. Interclasare a doi vectori

Avem doi vectori ordonati crescator A si B. Trebuie sa obtinem un al treilea vector C format din elementele vectorilor A si B , C sa fie la randul lui ordonat crescator: O rezolvare imediata ar fi concatenarea (alipirea) celor doi vectori A si B si apoi ordonarea rezultatului prin oricare dintre metodele cunoscute.

Vom descrie algoritmul de interclasare a doi vectori.

Ne pozitionam la inceputul celor doi vectori A si B (i: si j:=1). Vom avansa in paralel in cei doi vectori. Comparam elementele din A si din B (de pe pozitiile in care suntem) Pe cel mai mic il depunem in C (k:=k+1) si inaintam in vectorul din care am pus elementul. Cand unul din cei doi vectori A si B s-a terminat, din celalalt "golim" in vectorul C .



2 Cautare binara a unui element intr-un vector

Daca tabloul unidimensional (vector) este ordonat crescator cautarea unui element dat in vector se poate rezolva mai rapid (decat cautarea secventiala)cu ajutorul algoritmului de cautare binara

Vom nota cu li - marginea din stanga a vectorului si cu lf marginea din dreapta. Intre cele doua margini trebuie sa caut un element dat e. Gasesc elementul din vector de la jumatate, mif. Verific daca elementul cautat e este egal cu elementul aflat in vector pe pozisia din mijloc. Daca nu se afla verificam cum este elementul cautat e fata de elementul din mijloc. In functie de raspuns urmeaza sa caut elementul e in stanga sau in dreapta elementului din mijloc. Voi schimba corespunzator valorile celor doua margini (stanga respectiv dreapta) a intervalului din vector unde urmeaza sa caut elementul e.

1. Interclasare

program interclasare;

var a,b,c:array[1..10] of integer;

n,m,k,i,j:integer;

begin

k:=0;

i:=1;

j:=1;

while (i<=n) and(j<=m) do

begin

k:=k+1;

if a[i] < b[j]

then

begin

c[k]:=a[i];

i:=i+1;

end

else

begin

c[k]:=b[j];

j:=j+1;

end

end;

while i<=n do

begin

k:=k+1;

c[k]:=a[i];

i:=i+1;

end;

while j<=m do

begin

k:=k+1;

c[k]:=b[j];

j:=j+1;

end;

for i:=1 to k do

write(c[i],' ');

end

2. cautare binara

Program cautarebinara:

var e,p,li,lf,m:integer;

begin

write('Dati elementul cautat:'); readln(e);

p:=0;

li:=1;

lf:=n;

repeat

m:=(lf+li) div 2;

if x[m]=e

then p:=m

else if x[m]>e

then lf:=m-1

else li:=m+1;

until (p<>0) or (li>lf);

if p=0

then

writeln('El nu exista in vector!')

else

writeln('El ',e,' este pe pozitia ',p,' in vector');

end

8. Aritmetica numerelor mari

In probleme pot apare de multe ori necesitatea prelucrarii unor numere mari - cu multe cifre - care nu pot fi reprezentate cu toate cifrele lor folosind tipurile intregi cunoscute in limbajul de programare. Nici reprezentarea lor ca numere reale nu este o solutie deoarece nici la numerele reale nu putem lucra cu numar mare de cifre exacte. Vom rezolva aceasta problema - deocamdata - lucrand cu cifrele numerelor - in vector de cifre -

program numeremari;

var a,b,c:array[0..20] of byte;

m,n,k,i,j:integer;

max,d,t,s,aux,cod:integer;

s:string;

begin

write('numar = '); readln(s);

for i:=1 to length(s) do

val(s[i],a[i],cod);

write('nr.cifre pt. primul numar n = ');

readln(n);

for i:=1 to n do

begin

write('a[',i,']= ');

readln(a[i]);

end;

write('cifre al doilea numar m = ');

readln(m);

for i:=1 to m do

begin

write('b[',i,']= ');

readln(b[i]);

end;

if n > m

then

begin

max:=n;

d:=n-m;

for i:=m downto 1 do

b[i+d]:=b[i];

for i:=1 to d do

b[i]:=0;

end

else

begin

max:=m;

d:=m-n;

for i:=n downto 1 do

a[i+d]:=a[i];

for i:=1 to d do

a[i]:=0;

end;

t:=0;

for i:=max downto 1 do

begin

s:=a[i]+b[i]+t;

if s>9

then

begin

c[i]:=s mod 10;

t:=s div 10;

end

else

begin

c[i]:=s;

t:=0;

end;

end;

writeln;

c[0]:=t;

if c[0]<>0

then

write(c[0],' ');

for I:=1 to max do

write (c[i],' ');

for i:=max downto d+1 do

if a[i] >=b[i]

then

c[i]:=a[i]-b[i]

else

begin

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

c[i]:=10+a[i]-b[i];

end;

for i:=1 to d do

c[i]:=a[i];

writeln;

K:=1;

while c[k]=0 do

k:=k+1;

if k>max

then

writeln('cele 2 numere au fost egale - rez = 0 ')

else

for i:=k to max do

write(c[i],' ');

end

Inmultirea




Politica de confidentialitate

creeaza logo.com Copyright © 2024 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.