Să optimizăm algoritmul căutării secvenţiale a unui element în vector. Algoritmul se va executa mai rapid cu cât corpul ciclului este mai simplu şi cu cât condiţia ciclului este mai simplă. În algoritm corpul ciclului este destul de simplu, el este format dintr-o singură instrucţiune (I:=I+1), iar condiţia ciclului este compusă din două subcondiţii:
1) mai sunt elemente în vector (I<=n)
2) elementul căutat nu s-a găsit (A[I] # X]
În căutarea cu baraj vectorul se declară cu un element mai mult,deci cu n+1 elemente. Şi în elementul de pe poziţia (n+1) se va pune valoare căutată X - barajul. Deci din condiţia ciclului poate fi scoasă prima subcondiţie, deoarece un element egal cu cel căutat va fi găsit. El va fi sau elementul efectiv al vectorului (dacă I<=n) sau barajul. Algoritmul căutării cu baraj este următorul:
Type
Vector=array[1..n+1] of integer
Var
A: vector
I: natural
X: integer
Begin
A[n+1]:= X
I:=1
While A[I] # X do
I:=I+1
End
If I<=n then
WriteString(‘Există’)
Else
WriteString(‘Nu există’)
end
Dacă căutarea se face în direcţie opusă, atunci barajul se pune la începutul vectorului.
Type
Vector=array[0..n] of integer
Var
A: vector
I: cardinal
X: integer
Begin
A[0]:= X
I:=n
While A[I] # X do
I:=I - 1
End
If I >= 1 then
WriteString(‘Există’)
Else
WriteString(‘Nu există’)
End
6.1.2.9. Căutarea binară
În ipoteza în care elementele vectorului în care se face căutarea sunt ordonate, se poate aplica o metodă de căutare mai rapidă ( accelerarea operaţiei de căutare este importantă mai ales dacă vectorul prelucrat sunt de dimensiuni mari). O astfel de metodă este căutarea binară.
Să considerăm un vector A ordonat crescător în care se caută valoarea X. Dacă valoarea căutată este mai mare decât cea aflată în mijlocul vectorului, înseamnă că ea este mai mică sau egală cu una din valorile care se găsesc în jumătatea superioară a vectorului. Deci zona de memorie poate fi restrânsă la această jumătate. În caz contrar, căutarea se continuă în jumătatea inferioară a vectorului. Dacă am ficsa poziţia primului element în indicele limita_jos, iar poziţia ultimului element în indicele limita_sus, atunci restrângerea zonei de căutare se realizează prin schimbarea valorii uneia dintre cele două limite. În pasul următor căutarea se va relua în jumătatea de vector corespunzătoare, comparând elementul căutat cu cel din mijlocul noii zone de căutare. Operaţia se repetă până când se detectează egalitate între un element din vector şi valoare căutată sau zona în care trebuie să se facă căutarea devine vidă (indicii limita_jos şi limita_sus sunt adiacenţi). Metoda de căutare binare se realizează cu următorul algoritm:
Var
A:vector
I: natural
Limita_jos: natural
Limita_sus: naturall
Mijloc: natural
Gasit:Boolean
Begin
Gasit:=false
Limita_jos:=1
Limita_sus:=n
While (limita_jos<=limita_sus ) and (not Gasit) do
Mijloc:=(limia_jos+limita_sus) div 2
If A[mijloc]=x then
Gasit:=true
Else
If A[mijloc]< x then
Limita_sus:=mijloc-1
Else
Limita_jos:=mijloc+1
End
End
End
If gasit then
WriteString(‘Există’)
Else
WriteString(‘Nu există’)
end
Deşi nu este cel mai eficient algoritm de căutare în structuri ordonate, căutarea binară este cea mai folosită, deoarece oferă o bună stabilitate (timpul de căutare în toate cazurile este apropiat de timpul mediu) şi nu execută decât comparaţii între valorile din tablou, fără a implica alte operaţii asupra lor.
6.1.2.10.Căutarea prin interpolare
Este un algoritm asemănător ca principiu cu algoritmul de căutare binară şi se aplică tablourilor ce conţin valori numerice. La fiecare pas de căutare, pe baza interpolării, algoritmul încearcă să “ghcească” unde s-ar putea găsi cheia căutată în cadrul tabloului. Pe baza comparaţiei între cheia de căutare şi valoarea estimată( probei) obţinută pe baza interpolării, se deduce care subtablou poate conţine cheia, şi aceasta se supune din nou metodei, celălalt subtablou fiind abandonat.
Left:=1
Rithg:=n
While (A[Rithg]>=key) and (key >A[Left] do
I:=trunc((key – A[left]) / (A[Rithg]-A[Left]) * (rithg-Left)) + Left
If key >A[I] then
Left:=I+1
Else
If key
Else
Left:=I
End
End
If key=A[left] then
Poz:=left
Else
Poz:=-1
End
End
Algoritmul se comportă bine pentru tablouri cu chei numerice a căror distribuţie este uniformă şi în care nu apar valori dublate.
6.1.2.11.Deplasare elementelor vectorilor
Elementele unui vector pot fi deplasate la stânga sau dreapta cu una sau mai multe poziţii.
Deplasare la stânga cu o poziţie
Fie dat vectorul A cu următoarele elemente: 1 2 3 4 5. Să se formeze vectorul A cu următoarele elemente: 2 3 4 5 0. Elementul A[2] trece pe locul elementului A[1], elementul A[3] -> A[2] ş.a.m.d. primul element părăseşte vectorul, iar ultimul element devine vid. Dacă vectorul are n elemente, atunci se vor realiza (n-1) deplasări, unde elementului current A[I] i se va atribui valoarea elementului vecin din dreapta A[I+1]
For I:=1 to n-1 step 1
A[I]:= A[I+1]
End
A[n]:=0
Deplasare la stânga cu k poziţii
Pentru a deplasa elementele vectorului la stânga cu k poziţii e necesar de repetat de k ori algoritmul de deplasare la stânga cu o poziţie:
For j:=1 to k step 1
For I:=1 to n-1 step 1
A[I]:= A[I+1]
End
A[n]:=0
End
Deplasare la dreapta cu o poziţie
Fie dat vectorul A cu următoarele elemente: 1 2 3 4 5. Să se formeze vectorul A cu următoarele elemente: 0 1 2 3 4 5 . Elementul A[1] trece pe locul elementului A[2], elementul A[3] -A[4] ş.a.m.d. Ultimul element părăseşte vectorul, iar primul element devine vid. Dacă vectorul are n elemente, atunci se vor realiza (n-1) deplasări, unde elementului current A[I] i se va atribui valoarea elementului vecin din stânga A[I-1]. Parcurgerea vectorului va fi realizată începând cu ulimul element al vectorului.
For I:=n to 2 step 1
A[I]:= A[I-1]
End
A[1]:=0
Deplasare la dreapta cu k poziţie
Pentru a deplasa elementele vectorului la dreapta cu k poziţii e necesar de repetat de k ori algoritmul de deplasare la dreapta cu o poziţie:
For j:=1 to k step 1
For I:=n to 2 step -1
A[I]:= A[I-1]
End
A[1]:=0
End
6.1.2.12. Algoritmi de rotire a elementelor unui vector
La rotire toate elementele vectorului se deplasează cu una sau mai multe poziţii la stânga sau dreapta. Elemental care părăsesc vectorul apar în partea opusă a lui.
Rotire cu o poziţie la stânga
Fie vectorul iniţial A cu următoarele elemente 1 2 3 4 5. după rotire la stânga cu o poziţie vectorul A va avea următorul conţinut: 2 3 4 5 1. După cum se observă elementele se deplaseză cu o poziţie la stânga, iar în ultimul element A[n] se scrie valoarea primului A[1]. Pâna la deplasare e necesar ca valoarea primului elemement să fie salvată în X. După deplasare în ultimul element al vectorului se va scrie valoarea fostului prim element salvată în X.
X:=A[1]
For I:=1 to n-1 step 1
A[I]:= A[I+1]
End
A[n]:=X
Rotire cu k poziţii la stânga
Se va repeta algoritmul de rotire la stânga cu o poziţie de k ori.
For j:=1 to k step 1
X:=A[1]
For I:=1 to n-1 step 1
A[I]:= A[I+1]
End
A[n]:=X
End
Rotire la dreapta cu o poziţie
Fie dat vectorul A cu următoarele elemente: 1 2 3 4 5. Să se formeze vectorul A cu următoarele elemente: 5 1 2 3 4 . Elementul A[1] trece pe locul elementului A[2], elementul A[3] -A[4] ş.a.m.d. Ultimul element trece pe locul primului element. Dacă vectorul are n elemente, atunci se vor realiza (n-1) deplasări, unde elementului current A[I] i se va atribui valoarea elementului vecin din stânga A[I-1]. Parcurgerea vectorului va fi realizată începând cu ulimul element al vectorului. Înainte de deplasare se va salva valoarea ultimului element în X pentru a o scrie după deplasre în primul element al vectorului.
X:=A[n]
For I:=n to 2 step 1
A[I]:= A[I-1]
End
A[1]:=X
Rotire cu k poziţii la dreapta
Se va repeta algoritmul de rotire la dreapta cu o poziţie de k ori.
For j:=1 to k step 1
X:=A[n]
For I:=n to 2 step -1
A[I]:= A[I-1]
End
A[1]:=X
End
6.1.2.13.Copierea valorilor care îndeplinesc o condiţie dintr-un vector sursă într-un vector destinaţie
În cazul cel mai defavorabil vectorul sursă poate să nu conţină nici un element care să îndeplinească condiţia impusă. În acest caz, vectorul destinaţie nu va avea nici un element. Celălalt caz limită este cel în care toate valorile din vectorul sursă sunt copiate în vectorul destinaţie.
Rezultă că numărul de valori din vectorul destinaţie (NrValD) trebuie iniţializat cu valoarea 0.
În continuare trebuie analizate, unul câte unul, elementele vectorului sursă, copiindu-le în vectorul destinaţie pe cele care îndeplinesc condiţia impusă.
Copierea unui element sursă presupune două operaţii: creşterea numărului de elemente din vectorul destinaţie şi copierea valorii sursă ca ultima valoare în vectorul destinaţie.
Algoritmul care realizează aceste prelucrări este următoarea:
NrValD:=0
For I:=1 to NrValS step 1 do
If Vs[I]={proprietatea} then
NrValD:= NrValD+1
Vd[NrValD]:=Vs[I]
End
End
6.1.2.14. Construirea listei indicilor elementelor care îndeplinesc o anumită condiţie
Această prelucrare este tipică pentru problemele de tipul “Care sunt elementele care au proprietatea x?” Ea este o variantă a celei prezentate anterior, principala diferenţă constând în faptul că în locul valorii se copiază indicele acesteia, după cum urmează:
NrIndici:=0
For I:=1 to NrValS step 1 do
If Vs[I = proprietate then
NrIndic:= NrIndici+1
VI[NrIndici]:=I
End
End
6.1.2.15 Algoritmi de interclasare a doi vectori
1. Fie vectorul A cu n elemente şi vectorul B cu m elemente. Să se formeze vectorul C cu (n+m) elemente. Primele n elemente ale vectorului C sunt luate din elementele corespunzătoare ale vectorului A, iar următoarele m elemente sunt luate din vectorul B.
Rezolvare:
Vom folosi 2 cicluri. Primul ciclu va forma primele n elemente ale vectorului C, unde C[I]:=A[I]. Ciclul al doilea va forma celelalte m elemente ale vectorului C, luându-le din B.
For I:=1 to n step 1
C[I]:=A[I]
End
For I:=1 to m step 1
C[n+I]:=B[I]
End
2.Fie vectorul A cu n elemente şi vectorul B cu m elemente. Să se formeze vectorul C. În C se trec toate elementele din A, iar din B – numai cele care nu sunt în A.
Rezolvare:
În primul ciclu elementele vectorului A se trec în primele n elemente ale vectorului C. În cel de-al doilea ciclu se trec în vectorul C numai acele elemente din B care nu sunt în A. Se foloseşte algoritmul de căutare a unui element egal cu X. Variabila k va reprezenta poziţia elementului vectorului B, care trebuie inclus în vectorul C. Dacă se va decide că elementul vectorului B trebuie inclus în C, variabila k se va incrementa cu unu.
For I:=1 to n step 1
C[I]:=A[I]
End
K:=0
; ciclu parcurge toate elementele vectorului B
For j:=1 to m step 1
x:=B[j]
; se caută în A elementul X
I:=1
While (I<=n) and (A[I]#X) do
I:=I+1
End
If I>n then
; elementul X nu există în A; el se include în C
k:=k+1
C[n+k]:=X
End
End
3. Fie A[1..n] şi B[1..m]. să se formeze vectorul C în felul următor: a[1] b[1] a[2] b[2] ..a[n] b[n]. Vectorul C va avea 2*n elemente.
Rezolvare:
Elementele vectorului A se vor scrie în vectorul C pe poziţii impare (I*2-1), iar elementele vectorului B se vor scrie în C pe poziţii pare (I*2).
Ciclul prezentat în continuare transcrie în C elementele vectorului A pe poziţii impare.
For I:=1 to n step 1
C[I*2-1]:= A[I]
End
Iar următorul ciclu transcrie în C elementele vectorului B pe poziţii pare.
For I:=1 to n step 1
C[I*2]:= B[I]
End
Deoarece ambele cicluri se repetă de n oricorpurile ciclurilor pot fi unite într-un singur ciclu:
For I:=1 to n step 1
C[I*2-1]:= A[I]
C[I*2]:= B[I]
End
4. Fie A[1..n] şi B[1..m] ordonate crescător. Să se formeze vectorul C ordonat crescător, fără a folosi metode de sortare.
Rezolvare:
Vom proceda în felul următor:
- vom compara primul element din vectorul A cu primul element din vectorul B şi pe cel mai mic îl vom pune în C, eliminându-l din vectorul de unde provine;
- procesul se repetă până când se epuizează unul din vectori;
- apoi se copiază la sfârşitul vectorului C toate elementele din vectorul rămas neterminat.
Type
Vector1=array[1..n] of integer
Vector2=array[1..m] of integer
Vector3=array[1..n+m] of integer
Var
A:vector1
B:vector2
C:vector3
I: natural ; adresează elementele vectorului A
j: naturall ; adresează elementele vectorului B
k: natural ; adresează elementele vectorului C
begin
I:=1
J:=1
K:=0
; până când sunt elemente în A (I<=n) şi sunt elemente în B
While (i<=n) and (j<=m) do (j<=m)
if A[I]
c[k]:=A[I]
I:=I+1 ; se trece la următorul element din A
Else
k:=k+1
c[k]:=B[j]
j:=j+1 ; se trece la următorul element din A
end
end
; se copiază sfârşitul vectorului A în vectorul C
While I<=n do
k:=k+1
c[k]:=A[I]
I:=I+1
End
; se copiază sfârşitul vectorului B în vectorul C
While j<=n do
k:=k+1
c[k]:=B[j]
j:=j+1
End
6.1.2.16. Sortarea vectorilor
Prin sortare se înţelege o operaţie de aranjare a unei mulţimi de elemente într-o anumită ordine: în creştere sau descreştere.
Vom afirma , că elementele vectorului A[1..n] sunt aranjate în ordine crescândă, dacă între elementele vectorului se respectă relaţia A[1]<=A[2]<=A[3] …A[n] şi în ordine descrescătoare, dacă între elementele vectorului are loc relaţia: A[1]>=A[2]>=A[3] …A[n]
Sortarere prin inserţie
Înainte de a examina elementul A[I] (I=2,3,4, …n) al vectorului A[1..n] vom considera, că elementele precedente A[1], A[2], … A[I-1] au fost în prealabil aranjate în ordine crescândă şi se cere inserarea elementului A[I] în locul, care îi revine între elementele sortate anterior. În urma operaţiei de includere se va obţine un sector din i elemente ordonate. Următorul element A[I+1] va fi inclus între cele ordonate în mod analog ş.a.m.d., până când va fi aranjat tot vectorul.
Rezolvare:
Pentru a include elementul A[I] intre primele (I-1) elemente ordonate vom compara pe rând elementul A[I] cu A[I-1], A[I-2], … până când se va găsi poziţia j (1<=j<=I), în care va fi scris elementul A[I]. Concomitent cu compararea vom efectua şi deplasarea elementelor A[I-1], A[I-2], …A[j] cu o poziţie la dreapta.
Pentru a ilustra metoda vom cosidera următorul vector A[1.. 9] cu următoarele elemente:
18 13 22 10 24 9 4 23 11
1-ul pas: I=2. Se caută locul lui 13. Deorece porţiunea vectorului ordonat costă dintr-un singur element 18, atunci elementul 13 se inserează înaintea elementului 18. Deci după această inserţie vectorul va avea următorul conţinut:
13 18 22 10 24 09 04 23 11.
Primele 2 elemente sunt ordonate. Examinăm elementul A[3]=22 şi-I căutăm locul lui printer primele 2 elemente 13, 18. Deoarece 22 este mai mare decât valoare primelor 2 elemente el rămâne pe locul 3. vectorul va avea următorul conţinut:
13 18 22 10 24 09 04 23 11.
În aşa mod se procedează cu celelalte elemente ale vectorului.
I=4 A[4]=10 10 13 18 22 24 09 04 23 11
I=5 A[5]=24 10 13 18 22 24 09 04 23 11
I=6 A[6]=9 09 10 13 18 22 24 04 23 11
I=7 A[7]=4 04 09 10 13 18 22 24 23 11
I=8 A[8]=23 04 09 10 13 18 22 23 24 11
I=9 A[9]=11 04 09 10 11 13 18 22 23 24
Algoritmul este următorul:
For I:=2 to n step 1
Includerea elementului A[I] între primele (i-1) elemente
End
Detaliem corpul ciclului :
For I:=2 to n step 1
X:=A[I]
J:=I-1 ; se caută locul lui X printre primele (I-1) elemente
While (j>=1) and (A[I]>x) do
A[j+1]:=A[j]
J:=j –1
End
A[j+1]:=x
End
Sortarea prin selecţie
Ideia acestei metode de sortare este foarte simplă: se selectează elementul minim din vector şi se interschimbă cu primul element; în continuare se caută elementul minim, începând cu elementul al doilea al vectorului şi se interschimbă cu elementul al doilea al vectorului ş.a.m.d.
Rezolvare:
For I:=1 to n-1 step 1
Căutarea elementului minim din intervalul I ..n
Interschimbare elementului minim găsit cu elementul A[I]
End
Detaliem corpul ciclului:
For I:=1 to n-1 step 1
Min:=A[I]
I_min:=I
For j:=I+1 to n step 1
If A[I] < min then
Min:=A[I]
I_min:=I
End
End
A[I_min]:=A[I]
A[I]:=min
End
Sortarea prin interschimbare directă
Se analizează succesiv perechile de elemente vecine, inversând între ele valorile elementelor care nu îndeplinesc condiţia de ordine. Pentru ordonarea vectorului nu este suficientă o singură parcurgere. Parcurgerea vectorului trebuie repetată până când se obţine ordinea dorită, deci nu mai sunt perechi de elemente care contrazic relaţia de ordine. În cazul cel mai nefavorabil vectorul trebuie parcurs de (n-1) ori.
Metoda de sotare prezentată este denumită metoda bulelor (BubbleSort) deoarece valorile mici “migrează” spre începutul vectorului, la fel ca bulele de gaz care se ridică spre suprafaţa unui lichid.
For I:=1 to n-1 step 1
For j:=n-1 to 1 step –1
If A[j]>A[j] then
Temp:=A[j]
A[j]:=A[j+1]
A[j+1]:=temp
End
End
Această metodă este considerată drept una din cele puţin efective.Analiza evoluării procesului de sortare ne permite să facem unele propuneri de optimizare a algoritmului.
În primul rând poate fi scurtată porţiunea de parcurgere a tabelului, deoarece după fiecare parcurgere un număr oarecare de elemente de la începutul tabelului devin ordonate. Deci parcurgerea vectorului o vom fece nu pâna la 1,ci pănă la i.
For I:=1 to n-1 step 1
For j:=n-1 to i step –1
If A[j]>A[j] then
Temp:=A[j]
A[j]:=A[j+1]
A[j+1]:=temp
End
End
Algoritmul poate fi optimizat,dacă am memoriza dacă au fost sau nu interschimbări la o parcurgere a vectorului. Dacă n-a fost nici o interschimbare, rezultă că vectorul e ordonat de acum.
Vom folosi variabila logică Schimb, care va ficsa schimbul. Deci primul ciclu se va repeat nu de (n-1) ori, dar până când nu au fost făcute interschimbări.
Var
Schimb:Boolean
Begin
I:=1
Repeat
Schimb:=false
For j:=n to I step –1 do
If A[j-1]>A[j] then
Temp:=A[j-1]
A[j-1]:=A[j]
A[j]:=temp
Schimb:=true
Endif
Endfor
I:=I+1
Until I>n or Scimb=true
Algoritmul poate fi optimizat, dacă am ficsa şi poziţia ultimului interschim. Evident că toate perechile de elemente de după acest indice sunt deja ordonate. Deaceia parcurgerea poate fi terminată la acest indice şi nu la indicele i.
Begin
I:=1
L:=1
Repeat
Schimb:=false
K:=L
For j:=n to k step –1 do
If A[j-1]>A[j] then
Temp:=A[j-1]
A[j-1]:=A[j]
A[j]:=temp
L:=j
Schimb:=true
End
End
I:=I+1
Until I>n or Schimb=true
Sortarea prin metoda ShakerSort
Dacă parcurgem vectorul de la sfârşit spre început şi realizăm interschimbările necesare, atuci la o parcurgere cel mai mic element se deplasează spre începutul vectorului, iar dacă am schimba direcţia parcurgerii, atuci cel mai mare element se va deplase spre sfârşitul vectorului. Această idée se foloseşte în metoda ShakerSort.
Var
L: natural ; indicele elementului din stânga
R: natural ; indicele elementului din dreapta
K:=n
Begin
L:=2
R:=n
K:=n
Repeat
For j:=r to l step –1 do
If A[j-1] >A[j] then
Temp:=A[j-1]
A[j-1]:=A[j]
A[j]:=temp
K:=j
End
End
L:=k+1
For j:=L to R step 1 do
If A[j-1] >A[j] then
Temp:=A[j-1]
A[j-1]:=A[j]
A[j]:=temp
K:=j
End
End
R:=k-1
Until L>R
6.1.2.17. Eliminarea elimentului din vector
Să se elimine din vector elementul cu numărul k. Pentru rezolvarea problemei e necesar ca elementele k+1 .. n să fie deplasate cu o poziţie la stânga.
For I:=k+1 to n step 1 do
A[I]:=A[I+1]
End
N:=n-1 ; se micşorează numărul de elemente din vector
Exemplu:
Să se elimine din vector elementul cu valoare maximă.
Rezolvare:
Determinăm indicele elementului maxim
; considerăm că elementul maxim este pe primul loc în vector
Max:=A[1]
I_max:=1
For I:=2 to n step 1
If A[I] >max then
; dacă s-a găsit alt maxim, atunci memorizăm şi poziţia lui
Max:=A[I]
I_max:= I
End
End
Pentru a elimina din vector elementul cu indicele k vom elabora procedura Delete. La intrare procedura are 3 parametri : vectorul X , k –indicele elementului care trebuie eliminate şi n –numărul de elemente efective ale vectorului. La ieşire va fi vectorul X modificat – fără elementul de pe poziţia k. Deci k se va transmite prin valoare, iar vectorul X şi n –prin referinţă.
Procedure Delete(k: natural, var X: vector,var n:natural)
Var
I: natural
Begin
For I:=k to n-1 step 1 do
X[I]:=X[I+1]
End
n:=n-1
End
Pentru a elimina elementul maxim procedura Delete se va apela Delete(I_max,A,10).
Dacă din vector trebuie eliminate mai multe elemente, e mai bine ca prelucrarea vectorului să se înceapă de la sfârşit.
Exemplu:
Să se elimine din vectorul A toate elementele egale cu X
Rezolvare:
N_el:=n
For I:=n to 1 step –1 do
If A[I]=X then
Delete(A,I,n_el)
End
End
6.1.2.18. Includerea elementelor în vector
Includerea elementului X după elementul cu numărul k
Se consideră că în vector există loc pentru elementele care se vor include.
Includerea se va face în felul următor:
- primele k elemente nu se modifică;
- toate elementele din intervalul k+1 .. n trebuie să fie deplasate la dreapta cu o poziţie;
- elementului cu numărul k i se atribuie X.
Să elaborăm procedura Insert, care va face includerea. La intrare procedura va avea vectorul A, X – valoarea elementului inclus, k – poziţia după care va fi inclus elemental şi n –numărul de elemente efective ale vectorului. La ieşire va fi vectorul A modificat şi n modificat. Deci parametrii X şi k se vor transmite prin valoare, iar vectorul A şi n – prin referinţă.
Procedure Insert (k:cardinal, X:cardinal, var A:vector,var n:natural)
Var
I:natural
Begin
For I:=n to k step –1 do
A[I+1]:=A[I]
End
A[k]:=x
N:=n+1
End
Includerea elementului X înaintea elementul cu numărul k
Această problemă este asemănătoare cu precedenta. În procedura precedentă se deplasau la dreapta toate elementele după elementul k, începând cu (k+1), iar pe locul elementului k se includea noul element X. În această problemă se vor deplasa la dreapta toate elementele începând cu k, iar pe locul lui se va include elementul X.
Procedure Insert2(k:cardinal,x:integer,var A:vector,var n:natural)
Var
I: natural
Begin
For I:=n to k step –1
A[I+1]:=A[I]
End
A[k]:=X
N:=n+1
End
Includerea în vector a câtorva elemente
De exemplu:
Să se includă în vector după fiecare element divizibil prin 3 elementul cu valoarea X.
Rezolvare:
În acest caz vectorul trebuie să fie declarat cu (2*n) elemente. Dacă am prelucra vectorul de începând cu primul element, făcând includerea elementului X după elementul care posedă proprietatea, atunci elementul inclus ne face probleme, deoarece la fiecare iteraţie se va schimba indicele ultimului element şi ar trebui “ sărit “ elementul inclus. Iar dacă parcurgerea vectorului ar începe cu ultimul element, atunci elementul inclus nu ridică probleme. În variabila n_el vom acumula numărul elementelor incluse. Dacă elementul se include în vector atunci variabila n_el se incrementează cu 1. Variabila n_el se declară ca variabilă globală. Vom modifica procedura de includere.
Procedure Insert2(k:cardinal,x:integer, var A:vector)
Var
I:cardinal
Begin
; deplasarea elementelor cu o poziţie la dreapta
; (n+n_el) indicele ultimului element
For I:=n+n_el to k+1 step –1
A[I+1]:=A[I]
End
A[k+1]:=X
N_el:=n_el+1 ; contorul elementelor incluse
End
Folosind această procedură algoritmul ar fi următorul:
N_el:=0
For I:=n to 1 step –1
If A[I]=proprietate then
Insert (I,X,A)
End
End
Includerea unui element într-un table ordonat
Începând cu ultimul element se va parcurge vectorul de la dreapta spre stânga, vereficând treptat condiţia A[I]>X şi permutând fiecare A[I] >X în poziţia vecină din dreapta. Astfel, căutând locul noului element, asigurăm şi eliberarea lui.
Begin
I:=n
While (I >=1) and (A[I]>X) do
A[I+1]:=A[I]
I:=I-1
End
A[I+1]:=X
6.1.3 Operaţii cu mulţimi, memorate sub formă de vectori
Mulţimile pot fi memorate sub forma unor vectori, făcând, însă convenţia de a nu se repeat elementele în cadrul vectorului.
Să presupunem că avem doi vectori A (cu n elemente distincte) şi B ( cu m elemente distincte). Să realizăm reuniunea şi respective intersecţia lor.
Reuniunea
Pentru reuniune, vom copia în vectorul rezultat (reuniune) toate elementele din A, după care vom adăuga acele elemente din B care nu se găsesc în A.
For I:=1 to n step 1
Reuniune[I]=A[I]
End
; se adaugă acele elemente di n B care nu sunt în A
k:=0
for I:=1 to m step 1
j:=1
while (j<=n) and (B[I]# A[j] do
j:=j+1
end
if j>n then
k:=k+1
reuniune[n+k]:=B[I]
end
end
Intersecţie
; se parcurge A, şi se pun în Intersec toate acele elemente ce se regăsesc în B
k:=0
for I:=1 to n step 1
j:=1
gasit:=false
while j<=m and not Gasit do
if A[I]=B[j] then
gasit:=true
end
j:=j+1
end
if gasit then
k:=k+1
intersec[k]:=A[I]
end
6.1.4. Operaţii ci polinoame
O expresie de forma anXn + an-1Xn-1 + … a2X2 + a1X + a0, în care an, an-1, … a2, a1, a0 sunt numere reale date, numite coeficienţi, se numeşte polinom de gradul n. X este variabila polinomului.
Problema care apare, în primul rând este de a calcula valoarea polinomului pentru o valoare a variabilei X dată. Un polinom poate fi memorat prin coeficienţii săi. Apoi apar probleme de genul: suma şi diferenţa a două polinome( care se reduce la a aduna, respective a scădea, componentele corespunzătoare din vectorii în care memorăm cele două polinoame ş. a.
Calcularea valorii unui polinom
Var
S:real
P:real
X:real
I: natural
Begin
S:=0
P:=1
For I:=0 to n step 1
S:=s+a[I]*p
P:=p*x
End
6.1.4.Probleme rezolvate cu ajutorul vectorilor
1. Numărrul punctelor din cerc.
Se dau n puncte în plan şi un cerc. Să se determine numărul punctelor care se află în interiorul cercului.
Rezolvare:
Punctele se dau prin coordonatele (xi,yi),I=1,2,…,n. Variabila Nr va conţine numărul punctelor din interiorul cercului, care se dă prin centrul O(a,b) şi raza r. Pentru a calcula valoarea lui nr se iniţializează cu 0 şi se verifică care dintre punctele (xi,yi) au distanţa faţă de (a,b) mai mică decât r, deci se află în cerc. Pentru fiecare răspuns afirmativ valoarea variabilei nr se măreşte cu 1.
Algoritmul pentru rezolvarea problemei este următorul:
Algoritm puncte;
Type
Vector=array[1..n] of real
Var
X: vector
Y: vector
A,b:real
R: real
Nr:=natural
I: natural
Begin
Nr:=0
For I:=1 to n step 1 do
If sqr((x[I]-a)) + sqr((y[I]-b))
End
End
WriteNat(nr)
End
Niciun comentariu:
Trimiteți un comentariu