operatii cu vectori

Căutarea cu baraj
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 Ritgh:=I-1
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] k:=k+1
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)) Nr:=nr+1
End
End
WriteNat(nr)
End

STRUCTURI DE DATE in programare

6. STRUCTURI DE DATE
Structurile de date, spre deosebire de cele simple, sunt combinaţii de alte tipuri, definite prin descrierea tipurilor componentelor şi prin indicarea unor metode de structurare. Componentele tipurilor structurate pot fi elementare sau structurate.

6.1. Tablouri unidimensionale
În multe probleme apare necesitatea de a lucra cu grupuri de variabile de acelaşi tip. De exempu, pentru a memora notele studentului de la sesiunea de iarnă avem nevoie de un grup de numere naturale, iar pentru a memora temperaturile zilnice ale lunii noiemrie avem nevoie de un grup de numere întregi. Un grup de elemente de acelaşi tip se mai numeşte şi tablou unidimensional sau vector. Vectorul reprezintă un tip de date structurat.
Să alcătuim algoritmul rezolvării următoarei probleme: să se calculeze suma a 5 numere întregi.
Rezolvare: Vom declara 5 variabile de tip integer pentru a memora valorile celor 5 numer întregi.
Algoritm suma
Var
N1: integer
N2: integer
N3: integer
N4: integer
N5: integer
S : integer
Begin
Readint(n1)
Readint(n2)
Readint(n3)
Readint(n4)
Readint(n5)
S:=n1+n2+n3+n4+n5
Writeint(s)
End.
Să calculăm suma a 30 numere întregi. Dacă rezolvăm problema în mod analog, atunci avem nevoie de 30 variabile pentru păstrarea celor 30 numere şi algoritmul ar fi mult mai lung. Ar fi mai bine ca cele 30 de variabile să nu le declarăm separate, dar să declarăm un grup format din 30 elemente.
Tipul tablou unidimensional (vector) se declară în felul următor:
Type
< Nume_tip> = array of ,
unde
tip indece poate fi de orice tip scalar,
iar tip element – de orice tip de date.
Exemple:
Type
vector = array[1..20] of integer ar însemna un grup de elemente numere înteregi, numerotate de la 1 la 20.
Dacă am declara o variabilă de acest tip:
Var
X: vector
Pentru a accesa elementul cu numărul 7 vom specifica X[7], deci componenta de ordin I se va specifica prin X[I].
Pentru a referi un element al vectorului se foloseşte următoarea specificare
< Nume_variabila> [ ]
Se pot defini şi vectori cu elementele numerotate, de pildă, de la –5 la 5:
Type
vector1=array[-5 ..5] of integer
Var
X1:vector
În acest caz vectorul va avea 10 elemente, numerotate astfel:
[-5][-4][-3][-2][-1][0][ 1][ 2][ 3][ 4][ 5]
Primul element al acestui vector poate fi accesat astfel X1[-5], al 6-lea –X1[0]
Fie date următoarele declaraţii:
Type
Lucratori=(Ivanov,Petrov,Sidorov)
Vector2 = array[lucratori] of real
Var
Salar : vector2
Vectorul Salar are 3 elemente. Specificarea Salar[Ivanov] ar referi primul element, Salar[Petrov] – al 2-lea, iar Salar[Sidorov] – al 3-lea.

Type
Vector=array[‘a’ ..’z’] of real ar însemna un şir de numere reale, “numerotate” de la ‘a’ la ‘z’
Pentru vectorul
Var
X: vector
Componenta a 3-ia ar fi referită astfel X[‘c’]
Am putea defini chiar:
Type
Vector=array[char] of integer ceea ce ar însemna un grup de elemente numere întregi, numerotate de la caracterul cu codul ASCII 0 pănă la caracterul cu codul ASCII 255, care este ultimul.
Putem folosi şi tipul Boolean pentru a defini vectori, de exemplu:
Type
Vector=array[Boolean] of integer
Var
Y:vector
Vectorul Y are 2 elemente. Primul poate fi referit Y[false], iar ultimul –Y[true].
O variabilă de tip vector nu poate fi nici citită nici scrisă în întregime. De obicei se lucrează cu componentele vectorului. Cu componentele vectorului se pot face toate operaţiile ce se pot face cu orice variabilă de acel tip ( afişare, citire, atribuire etc.)

6.1.1. Prelucrarea secvenţială a elementelor vectorului
Deoarece o structură de tip vector cuprinde un număr fixat de elemente de acelaşi tip, pentru a prelucra toate elementele lui se va folosi un ciclu care se va repeta de n ori, unde n- numărul de componente ale vectorului.
For I := to step 1
< Prelucrarea elementului I>
Endfor
Acest algoritm parcurge elementele vectorului de la primul pănă la ultimul.
Pentru a parcurge elementele vectorului în ordine inversă se va folosi următorul algoritm:
For I := valoare finala indice to valoare initiala indice step -1
Prelucrarea elementului I
Endfor
6.1.2.Metode de lucru cu elementele vectorilor
Fie următoarea declaraţie:
Type
Vector=array[1 .. 10] of integer
Var
A: Vector
6.1.2.1.Formarea vectorului
Citirea vectorului de la tastatură
Trebuie să fie formate toate cele 10 componente ale vectorului. Deci folosim algoritmul de prelucrare consecutivă a elementelor, unde în fiecare iteraţie se va citi valoarea care se va memoriza în elementul corespunzător.
Pentru organizarea ciclului cu contor avem nevoie de variabila ciclului, fie I
Var
I:cardinal
Begin
For I:=1 to 10 step 1
ReadInt(A[I])
Endfor
End
Formarea vectorului
1. Sa se formeze un vector elementele căruia sunt primele n numere naturale
Var
I:natural
Begin
For I:=1 to 10 step 1
A[I] := I
End
End
2. Sa se formeze un vector elementele căruia sunt primele n numere Fibonacci
Primul număr Fibonacci este 1.deaceia vom atribui primului element al vectorului A[1] valoara 1. Şi cel de-al doilea număr Fibonacci este 1 şi vom atribui celui de-al doilea element al vectorului valoarea 1. Celelalte numere Fibonacci, începând cu al 3-lea sunt egale cu suma celor doi vecini din stânga, care vor fi referiţi A[I-1] şo A[I-2] respective.
Var
I: natural
Begin
A[1]:=1
A[2]:=1
For I:=3 to 10 step 1
A[I] := A[I-2}+A[I-1]
End
End
6.1.2.2. Afişarea unui vector
Afişarea poate fi făcută în două feluri:
- fiecare element pe un rând;
- toate elementele pe un rând.

Afişarea vectorului - fiecare element pe un rând
Var
I: natural
Begin
For I:=1 to 10 step 1
WriteInt(A[I] )
Writeln
End
End
Afişarea vectorului - toate elementele pe un rând
Var
I: natural
Begin
For I:=1 to 10 step 1
WriteInt(A[I] )
End
End
Afişarea vectorului - toate elementele pe un rând în ordine inversă
Vom folosi algoritmul care parcurge elementele vectorului în ordine inversă
Var
I: natural
Begin
For I:=10 to 1 step -1
WriteInt(A[I] )
End
End
Afişarea elementelor pare ale vectorului
Elementul current al vectorului A[I] va fi afişat numai dacă conţine un număr par (A[I] mod 2 =0)
Var
I: natural
Begin
For I:=1 to 10 step 1
If A[I] mod 2 =0
WriteInt(A[I] )
Endif
End
End
Afişarea elementelor impare de pe poziţii pare
Poziţia înseamnă indicele I, iar elementul de pe poziţia I va fi referit ca A[I]. Pentru a parcurge numai elementele de pe poziţii pare vom începe cu primul element de pe poziţie pară –al 2-lea, apoi cu pasul 2 var fi parcurse celelalte elemente.
Var
I: natural
Begin
For I:=2 to 10 step 2
If A[I] mod 2 #0 then
WriteInt(A[I] )
End
End
End

6.1.2.3. Modificarea valorilor elementelor vectorului
1. De exemplu: să se mărească cu 5 ultimul element al tabloului
Rezolvare:
În acest caz vom accesa direct elementul 5 al vetorului folosind referirea A[10]
A[10]:=A[10]+5

2. Toate elementele negative ale vectorului să fie micşorate de 3 ori
Rezolvare:
Vom parcurge toate elementele vectorului, dar vor fi modificate numai cele negative(A[I]<0)
Var
I: natural
Begin
For I:=1 to 10 step 1
If A[I]<0 then
A[I]:= A[I] div 3
End
End
End
6.1.2.4. Însumarea componentelor unui vector
Însumarea tuturor componentelor unui vector
Suma componentelor se calculează ca orice sumă, se pleacă de la suma nulă. Apoi la fiecare iteraţie i ( i de la 1 la n), suma creşte cu elementul curent, care este A[I]
Var
I: natural
S:integer
Begin
S:=0
For I:=1 to 10 step 1
S:=S+A[I]
End
End
Însumarea componentelor unui vector care posedă o proprietate
Dacă elementul curent posedă proprietatea atunci el este adăugat la sumă.
Exemplu:
Să se calculeze suma elementelor divizibile prin 3
Var
I: natural
S:integer
Begin
S:=0
For I:=1 to 10 step 1
If A[I] mod 3=0 then
S:=S+A[I]
End
End
End
6.1.2.5. Numărarea elementelor vectorului cu o proprietate dată
Proprietatea poate fi:
- Elementul conţine o valoare negativă (A[I]<0);
- Elementul conţine o valoare pozitivă (A[I]<0);
- Elementul conţine o valoare pară (A[I] mod 2 =0);
- Elementul conţine o valoare impară (A[I] mod 2 #0);
- Elementul conţine o valoare egală cu X;
- Elementul e număr prim;
- Elementul e număr perfect etc.
Vom folosi un contor pentru a număra elementele. Iniţial el trebuie să fie nul. De fiecare dată când găsim un element cu proprietatea dată contorul se incrementează cu 1.
Exemplu:
Să se determine câte elemente divizibile prin 5 sau 7 conţine vectorul.
Rezolvare:
Proprietatea se va scrie A[I] mod 5=0 sau A[I] mod 7=0
Var
I: natural
N_el: natural
Begin
N_el:=0
For I:=1 to 10 step 1
If (A[I] A[I]mod5=0) or ( A[I] mod 7=0) then
N_el:=N_el+1
End
End
End

Dacă proprietatatea reprezintă un algoritm mai complicat, se poate elaboara o funcţie logică care verifică dacă un element o posedă sau nu. Apoi în condiţia construcţiei If se va apela această funcţie pentru fiecare element al vectorului.
Să se calculeze căte elemente ale vectorului sunt numere perfecte.
Rezolvare:
Vom elabora funcţia logică Este_perfect
Function Este_perfect(n:natural):Boolean
Var
I: natural
S_div: natural
Begin
S_div:=0
For I:=1 to n-1 step 1
If n mod I=0 then
S_div:=s_div+I
End
End
If s_div=n then
Return True
Else
Return False
End
End
Se va parcurge vectorul şi se va verifica proprietatea apelând funcţia Este_perfect
Var
I: natural
N_el: natural
Begin
N_el:=0
For I:=1 to 10 step 1
If Este_perfect(A[I]) then
N_el:=N_el+1
End
End
End
61.2.6.. Determinarea minimului unui vector
Considerăm minim primul element; apoi parcurgem restul vectorului şi, ori de câte ori găsim un element mai mic, actualizăm minimul la valoarea acelui element.
Min:=A[1]
For I:=2 to n step 1
If A[I] < min then
Min:=A[I]
End
End
La sfârşitul ciclului, variabila min (de acelaşi tip ca şi componentele vectorului) conţine cel mai mic element al vectorului.
Pentru a găsi şi poziţia elementului minim în vector vom modifica algoritmul astfel:
Min:=A[1]
p_min:=1 ; considerăm că elementul minim este pe primul loc în vector
For I:=2 to n step 1
If A[I] < min then
Min:=A[I]
p_min:= I ; dacă s-a găsit alt minim, atunci memorizăm şi poziţia lui
End
End
6.1.27. Determinarea maximului unui vector
Considerăm minim primul element; apoi parcurgem restul vectorului şi, ori de câte ori găsim un element mai mare, actualizăm maximul la valoarea acelui element.
Max:=A[1]
For I:=2 to n step 1
If A[I] > max then
Max:=A[I]
End
End
La sfârşitul ciclului, variabila max (de acelaşi tip ca şi componentele vectorului) conţine cel mai mic element al vectorului.
Pentru a găsi şi poziţia elementului maxim în vector vom modifica algoritmul astfel:
Max:=A[1]
p_max:=1 ; considerăm că elementul maxim este pe primul loc în vector
For I:=2 to n step 1
If A[I] >max then
Max:=A[I]
p_max:= I ; dacă s-a găsit alt maxim, atunci memorizăm şi poziţia lui
End
End
6.1.2.8. Determinarea existenţei în vector a elementelor cu oproprietate dată
Se poate aplica algoritmul de numărare a elementelor cu o proprietate dată. Dacă N_el>0 rezultă că există aşa elemnte, altfel – nu există.
Var
I: natural
N_el: natural
Begin
N_el:=0
For I:=1 to 10 step 1
If Este_perfect(A[I]) then
N_el:=N_el+1
End
End
End
If N_el>0 then
WriteString(‘Există’)
Else
WriteString(‘Nu există’)
End
Acest algoritm ar putea fi optimizat. Parcurgerea vectorului se va face de la prima poziţie, până la sfârşit sau până s-a găsit primul element căutat. Această metodă, de comparare succesivă a valorii căutate cu cele din vector, considerate în ordinea apariţiei lor, este denumită căutare secvenţială.
Fie A vectorul cu n elemente în care este căutată valoarea X şi Gasit o variabilă de tip Boolean, a cărei valoare precizează dacă valoarea căutată a fost găsită sau nu. Înainte de a începe căutarea, variabila Găsit trebuie iniţializată cu valoarea false, deoarece nu s-a găsit valoarea căutată (X). Atunci când aceasta este găsită, variabilei Gasit i se atribuie valoarea True şi căutarea se termină. Dacă însă vectorul nu conţine valoarea X, valoarea variabilei Gasit rămâne neschimbată(False), căutarea terminându-se după analiza ultimului element din vector.
Algoritmul care realizează căutarea,conform celor expuse anterior, este următoarea:

Gasit:=false
I:=1
While (I<=n) and (not Gasit) do
If A[I]=X then
Gasit:=true
Endif
I:=I+1
End
If Gasit then
WriteString(‘Există’)
Else
WriteString(‘Nu există’)
End
Dacă am transfera verificarea condiţiei din corpul ciclului în condiţia ciclului, algoritmul ar fi următorul:
I:=1
While (I<=n) and (A[I] # X) do
I:=I+1
End
Ieşirea din ciclu se va face sau când elementul căutat s-a găsit ( A[I]#X = False) sau când în vector nu mai sunt elemente (I>n)
Deci,
If I<=n then
WriteString(‘Există’)
Else
WriteString(‘Nu există’)
End
Dacă se cere ca rezultatul căutării să fie reprezentat de indicele primului element din vector egal cu X, atunci ultimele două variante ale căutării se modifică după cum urmează:
1) Gasit:=false
I:=1
While (I<=n) and (not Gasit) do
If A[I]=X then
Gasit:=true
End
I:=I+1
End
If Gasit then
prim:=i-1
Else
WriteString(‘Nu există’)
End
2) I:=1
While (I<=n) and (A[I] # X) do
I:=I+1
End
If I<=n then
prim:=i
Else
WriteString(‘Nu există’)
End
Dacă se cere ca să fie căutat ultimul element al vectorului egal cu X, atunci se pot folosi aceiaşi algoritmi, numai că parcurgerea vectorului se va face în direcţie opusă, începând cu ultimul element.
I:=n
While (I>=1) and (A[I] # X) do
I:=I-1
End
If I<=1 then
ultim:=i
Else
WriteString(‘Nu există’)
End

abstartia datelor in programare

5. ABSTRACŢIA DATELOR
Ce este abstracţia? Abstracţia este o metodă, care presupune folosirea următooarei idei: evedenţierea unor proprietăţi importante ale obiectului analiza şi ignorarea celor neimportante în acest moment.
De fiecare dată, când ne îndereptăm atenţia la anumite proprietăţi ale obiectului şi le ignorăm pe celelalte, noi folosim abstracţia. Abstracţia este o parte importantă a gândirii. De asemenea abstracţia reprezintă o metodă importantă , folosită la dezvoltarea programelor.
Orice product-program poate fi analizat din 2 puncte de vedere:
- făcând abstracţie de la detaliile de realizare, algoritmul corespunde unei anumite probleme din lumea reală;
- din punctual de vedere al realizării algoritmului, el reprezintă o consecutivitate de operaţii, destinată să resolve problema.
O metodă importantă în proiectarea structurilor de date este abstracţia datelor, care reprezintă un şir de metode de programare.
Cea mai simplă metodă de abstracţie a datelor este atribuirea reuşită a identificatoarelor. De exemplu, identificatorul Temp e mai reuşit decât identificatorul X, care nu sugerează, că variabila dată păstrează valoarea unei temperaturi.
Limbajele de programare conţin mai multe posibilităţi de abstracţie a datelor. Vom studia următoarele metode de abstracţie a datelo:
- constante;
- tipuri de date utilizator;
- tipul de date enumerare;
- tipul de date interval.

5.1. Constante
Pentru păstrarea informaţiei în program se folosesc variabilele. Pe parcursul execuţiei programuluivaloarea variabilei se poate modifica de multe ori. Pe lângă variabile în program destul de frecvent se folosesc şi constantele. Spre deosebire de variabile valoarea constantei e cunoscută la scrierea algoritmului şi nu se modifică pe parcursul execuţiei programului. În limbajele de programare constantele la fel ca şi variabilele trebuie să fie declarate. Ele se declară în secţiunea Const. La descriere se indică două elemente: numele constantei şi valoarea ei.
Const
An=2000
Coef_tva=0.2
Pi=3.14
Cm_in_metru=100
Virsta=18
Folosirea constantelor măresc lizibilitatea algoritmului. De exemplu, pentru a calcula suma cumpărăturii se poate folosi operatorul:
Suma := Suma + Suma * Coef_tva, care este mai sugestiv decât operatorul cu effect identic Suma := Suma + Suma * 0.2.
Există diferite nivele de “constanţă” a constantelor. Unele din ele, ca Pi, Cm_in_metru sunt constante după definiţia lor. Dar alte constante nu întotdeauna au aceiaşi valoare. De exemplu, constanta An, Coef_tva, Virsta sunt constante pe parcursul unei execuţii a algoritmului, dar se pot modifica de la execuţie la alta. Dar şi folosirea acestor constante au avantaje. La modificarea valorii constantei, e mai simplu să se modifice o singură dată valoarea ei în secţiunea Const, unde ea este declarată, decât să se caute toate locurile în program unde se foloseşte constanta. Folosirea acestor tipuri de constante simplifică actualizarea periodică a lor.
5.2. Tipuri de date utilizator
În afară de tipurile de date standard, programatorul poate crea noi tipuri de date, numite tipuri de date utilizator. Toate tipurile de date utilizator se descriu în secţiunea Type. Sintaxa descrierii unui tip de date nou este:
< nume_tip_nou> =
Un tip nou de date poate fi construit dintr-un tip de date deja cunoscut (standard sau declarat anterior). În declaraţie se indică metoda de obţinere a noului tip din tipul cunoscut.
În cel mai simplu caz în Type se pot renumi tipurile de date existente. Numele oricărui tip de date standard poate fi înlocuit cu un identificator mai sugestiv ales de programator. De exemplu,
Type
Logic: Boolean
Pozitiv: natural
După ce au fost declarate tipurile noi, ele pot fi folosite la declararea variabilelor în secţiunea Var. De exemplu:
Var
Numar: pozitiv
Exista: logic

5.3. Tipul de date enumerare
Adesea programele se ramifică în funcţie de cazurile particulare care trebuie tratate, cazuri a căror exprimare nu este numerică. De exempu, un program de genul agendă de lucru va depinde de ziua din săptămână care se programează. Evident, programul va fi mult mai clar dacă, în loc să codificăm numeric zilele săptămânii, vom folosi denumirile loe uzuale. Sau să presupunem că vrem să lucrăm la un nivel mai abstrac, de exemplu cu semafoare electrice. Cele trei culori ale semaforului pot fi codificate numeric, dar programul ar fi mai clar, dacă vom folosi denumirile colorilor. Sau, dacă într-un program de grafică vom avea de prelucrat diferite figuri, ca de exemplu triunghiuri, dreptunghiuri, pătrate, hexagoane, prelucrarea va fi mai clară dacă vom idendifica fiecare situaţie de prelucrare prin numele figurii respective, decât codificând- o numeric. Pentru evitarea unor asemenea codificări şi pentru sporirea lizibilităţii programelor se foloseşte tipul de date enumerare.
Un tip de date enumerare defineşte o mulţime ordonată de valori prin enumerarea identificatorilor care desemnează valorile. Primul identificator desemnează cea mai mică valoare, ci numărul ordinal 0. Ceilalţi identificatori au, conform succesiunii lor, numerele ordinale următoare. În memorie, valorile acestui tip se reprezintă prin numerele lor de ordine, deci prelucrare se va face rapid. Aceşi identificatori se tratează în program identic cu constantele.
Tipul de date enumerare se defineşte printr-o listă de identificatori abstracţi.
Type
= (id1, id2,… , idn)
Exemple:
Type
Semafor = (rosu,galben,verde)
Saptamina=(luni, marti, miercuri, joi, vineri, sambata, duminica)
Dacă avem declaraţiile de variabile:
Var
S: semafor
Zi: saptamana
Variabila S poate avea una dintre valorile celor trei identificatori, ce numesc cele trei culori ale semaforului, iar variabila zi poate fi una dintre zilele săptămânii.
Un tip enumerare este un tip special, diferit de orice alt tip; de aceea, identificatorii din declaraţia unui tip enumerare nu pot fi utilizaţi în definirea altui tip enumerare. Tipul enumerare fiind ordinal, datelor acestui tip li se pot aplica operatorii relaţionali şi funcţiile ordinale standard ord, succ, pred. Semnificaţia valorilor de tip enumerare nefiind numerică, acestor date nu li se vor putea aplica operatorii aritmetici şi ele nu vor putea apărea în expresii aritmetice.
Datele de tip enumerare nu se pot nici citi şi nici scrie. Ele pot primi valori numai prin atribuire.
Datele de tip enumerare pot fi folosite în programe pentru a face mai suggestive anumite lucruri. De pildă, dacă facem un joc de poker, iar jucătorul va fi, pe rând omul şi calculatorul, atunci alternarea lor se descrie astfel:
Type
Jucator=(om, calculator)
Var
Juc: jucator
…
if juc = om then
…
else
if juc= calculator then
…

5.4. Tipul de date interval
Să presupunem că într-un program prelucrăm valori de unghiuri exprimate în grade. Evident valorile variabilelor care reprezintă unghiuri exprimate în grade trebuie să fie cuprinse în intervalul [0..360]. În acest caz trebuie să declarăm un tip nou de date numit unghi, şi orice variabilă care poate reprezenta un unghi va fi declarată de tipul unghi. Declaraţia de tip va fi de forma:
Type
Unghi= 0 .. 360
Iar declaraţia unei variabile X de tipul unghi se va face sub forma:
Var
X: unghi
Un tip de date obţinut prin restrângerea unui alt tip de date se numeşte tip interval. Se pot defini tipuri de date interval ale tipurilor ordinale. Definirea unui tip interval se face sub forma:
Type
= constanta1 .. constanta2
unde nume_tip este numele noului tip de date, constanta1 şi constanta2 sunt două constante de acelaşi tip ordinal care satisfac condiţia constanta1 <=. constanta2.
Tipul interval se generează dintr-un tip ordinal definit anterior sau standard, numit tip de bază al intervalului. Mulţimea valorilor acestui tip cuprinde un interval de valori ale tipului de bază, ale cărui limite se specifică prin cele două constante din definiţia tipului.
De exemplu se pot declara tipurile de date:
Type
Cifra = ‘0’ .. ‘9’
Adevarat= true .. true
Byte = 0 ..255
Zile=(luni, marti, miercuri, joi, vineri, sambata, duminica)
Zile_lucr= lini ..vineri
Operaţiile posibile cu datele de tip interval sunt cele premise de tipul de bază al acestuia.
Tipul Unghi este declarat ca interval al tipului cardinal. Dacă pentru variabila X încercăm să executăm o instrucţiune:
X:= 361
Compilatorul va semnala o eroare de depăşire a intervalului de valori,

subprograme

Abstracţia în programare
Abstracţia în programare se realizează cu ajutorul subprogramelor. De multe ori este necesar ca o anumită secvenţă de instrucţiuni să se execute de mai multe ori în cadrul unui program, eventual pentru alte date. De aceea este bine ca aceste instrucţiuni să fie grupate într-un modul purtând un nume. El va fi numit subprogram. Subprogramul se poate activa (lansa în execuţie) la cerere, prin intermediul acestor nume. Să exemplificăm, fie e necesar să se calculeze aria totală a două loturi dreptunghiulare. Algoritmul este următorul:
Algoritm Aria_totala_1
Var
S: real
A: real
B: real
S_total: real
Begin
; calcularea ariei primului lot
ReadReal(a)
ReadReal(b)
S:=a*b
S_total:=s
; calcularea ariei lotului 2
ReadReal(a)
ReadReal(b)
S:=a*b
S_total:=s_total+s
End
Fragmentul comun ReadReal(a)
ReadReal(b)
S:=a*b
Poate fi oformat ca subalgoritm astfel
Algoritm Aria_1_lot
Begin
ReadReal(a)
ReadReal(b)
S:=a*b
End
Atunci algoritmul principal va primi forma:
Algoritm Aria_totala_1
Var
S: real
A: real
B: real
S_total: real
Begin
; calcularea ariei primului lot
Aria_1_lot
S_total:=s
; calcularea ariei lotului 2
Aria_1_lot
S_total:=s_total+s
End
Avantajele folosirii subprogramelor
În general, subprogramele includ mai multe instrucţiuni, folosirea lor având ca efect reducerea dimensiunilor textului sursă al programelor, prin “factorizarea” unor secţiuni comune ale programelor. Subprogramele mai permit:
- sistematizarea elaborării programelor, prin împărţirea unei probleme mai complicate în probleme mai simple, tratate prin subprograme separate;
- scurtarea timpului de elaborare a programelor, prin utilizarea aceluiaşi subprogram în programe diferite;
- economiseşte spaţiul de memorie, la execuţia programului.
Proceduri şi funcţii
În limbajele de programare subprogramele se realizează cu ajutorul procedurilor îi funcţiilor. Utilizarea procedurilor presupune două elemente esenţiale:
- se referă la precizarea grupului de instrucţiuni commune;
- specifică locul sau locurile din program în care grupul de instrucţiuni trebuie executat.
Corespunzător celor două elemente menţionate, regăsim în program două construcţii distincte:
- o secţiune de program distinctă, numită d e f i n i ţ i a p r o c e d u r i i, care este inclusă în partea declarativă a programului, o singură dată;
- o instrucţiune specială, care se numeşte a p e l de p r o c e d u r ă şi care este inclusă în locurile în care ar trebui să fie executate acţiunile din grupul comun.
4.4.1. Definiţia şi apelul unei proceduri simple
Definiţia unei proceduri conţine:
- un antet
- un bloc, numit şi corpul procedurii.
Antetul precizează numele procedurii, care este utilizat şn program, în fiecare din apelurile acesteia.
Corpul procedurii are o parte declarativă şi una executabilă.
O procedură se defineşte în felul următor:
Procedure
Var
< variabile locale>
begin
< corpul procedurii>
end
Apelul procedurii este foarte simplu şi constă doar din numele procedurii. El trebuie inclus în partea executabilă a programului, ca o instrucţiune de sine stătătoare.
Execuţia procedurii
Execuţia apelului de procedură se face printr-un mecanizm mai complicat. Apelul provoacă suspendarea execuţiei procedurii curente, apelante (cea care conţine apelul de procedură) şi activarea procedurii apelate, adică execuţia instrucţiunilor din corpul acesteia. La sfârşitul execuţiei procedurii apelate, se reia execuţia procedurii apelante, din punctual imediat următor apelului.
Variabile locale şi variabile globale
Identificatorii declaraţi în procedură se numesc variabile locale. Ele pot fi folosite numai în această procedură şi nu pot fi accesate în exteriorul ei. Variabilele declarate în algoritmul principal se numesc variabile globale. Domeniul de valabilitate a variabilelor globale este întregul algoritm, inclusiv procedurile algoritmului.
Observaţii:
- o variabilă locală există numai în timpul execuţiei acelei proceduri, fiind cretă la activarea procedurii, prin alocarea spaţiului de memorie necesar şi fiind distrusă la îeşirea din procedură, prin eliberarea spaţiului de memorie. Acest mecanizm constituie un mijloc de economisire a spaţiului de memorie, o aceeaşi zonă de memorie putând fi folosită pentru a păstra, la momente diferite de timp, valorile variabilelor locale ale diversilor proceduri ale programului;
- variabilele locale sunt nedefinite la începutul execuţiei procedurii, nu sunt iniţializate la apelul procedurii şi nici ni-şi păstrează valoarea de la un apel la altul.
4.4.2. Proceduri cu parametri
Procedurile simple, fără parametri au posibilităţi limitate deaceea foarte des se folosesc procedurile cu parametri. Forma cea mai generală a procedurilor este cea parametrizată. De obicei, procedura execută un calcul cu valorile parametrilor săi de intrare şi furnizează rezultatele prin parametrii de ieşire.Se declară o procedură cu parametric astfel:
Procedure (lista parametrilor formali)
Var

begin

end
Se apelează procedura cu parametric astfel:
(lista parametrilor actuali)
Dacă procedura se apelează de mai multe ori, atunci la fiecare apel parametrul formal va conţine valori diferite, în dependenţă de parametrii actuali.
Ca şi variabilele locale, parametrii formali sunt cunoscuţi în procedură, dar sunt necunoscuţi în afara acesteia. Ei se comportă la fel ca variabilele locale, cu o singură excepţie: la apelul procedurii, se realizează iniţializarea parametrilor, printr-un anumit mecanizm. Astfel parametrii formali sunt definiţi ( au valori bine precizate) la începerea execuţiei procedurii. Parametrii nu pot fi utilizaţi în afara procedurii în care sunt declaraţi.
Între lista parametrilor actuali şi lista parametrilor formali se stabileşte o corespondenţă poziţională unu-la-unu. Parametrii pot fi transmişi prin două metode:
- prin valoare;
- prin referinţă.
Transmitera parametrilor prin valoare
Un parametru transmis prin valoare se descrie în lista parametrilor formali în felul următor:
:
Dacă parametrii sunt transmişi prin valoare atunci execuţia procedurii se desfăşoară astfel:
- se calculează valoarea fiecărui parametru actual;
- se alocă memorie pentru parametrii formali, transmişi prin valoare şi pentru variabilele locale ale procedurii;
- valorile parametrilor actuali calculate sunt atribuite parametrilor formali, iniţializându-le;
- se execută corpul procedurii;
- se eliberează memoria, ocupată de parametrii formali, transmişi prin valoare şi de variabilele locale;
- se reia execuţia procedurii apelante, de la instrucţiunea imediat următoare apelului.
În cazul transmiterii prin valoare, parametrii actuali pot fi orice expresii, al căror tip este compatibil cu tipul parametrului formal corespunzător. Parametrii pot fi transmişi prin valoare, dacă reprezintă datele de întrare pentru procedură.
Exemplu: să se calculeze aria totală a două loturi dreptunghiulare.
Rezolvare
Vom elabora procedura Aria_unui_lot, care va avea la întrare cele două dimensiuni ale dreptunghiului. Deci procedura va avea doi parametrii, transmişi prin valoare. Pentru calcularea ariei totale vom apela de două ori procedura Aria_unui_lot cu diferiţi parametric actuali
Algoritm Aria_totala
Var
A1,b1 : real;
A2,b2 : real
S_total: real
Pricedure Aria_unui_lot(latura1:real, latura2: real)
Var
S: real
Begin
S:=latura1 * latura2
S_total:= Stotal+ S
End
Begin
ReadReal(a1)
ReadReal(b1
S_total:=0
Aria_unui_lot(a1,b1)
ReadReal(a2)
ReadReal(b2)
Aria_unui_lot(a2,b2)
WriteReal(s_total)
End
La primul apel al procedurii Aria_unui_lot parametrul actual a1 se copie în parametrul formal latura1, iar parametrul actual b1 se copie în parametrul formal latura2. Începe a lucra procedura care calculează aria primului lot în variabila locală S şi apoi o adaugă la variabila globală S_total, care pănâ la întrare în procedură avea valoarea 0.
La cel de-al doilea apel al procedurii, parametrul actual a2 se copie în parametrul formal latura1, iar parametrul actual b2 se copie în parametrul formal latura2. Începe a lucra procedura care calculează aria celui de-al doilea lot în variabila S şi apoi o adaugă la variabila globală S_total., care până la întrare în procedură conţinea valoarea ariei primului lot.
Exemplu: să se afişeze diuvizorii a două numere naturale citite de la tastatură.
Rezolvare:
Vom elabora procedura Divizori, care va afişa divizorii oricărui număr natural. Procedura va avea o întrare, deci un parametru, transmis prin valoare. Corpul procedurii va conţine un ciclu cu contor, unde variabila ciclului va lua valori din intervalul 1.. N ( N – valoara numărului natural dat). Corpul ciclului va compara resturile de la împărţirea numărului natural N la valorile variabilei ciclui. Dacă restul este egal cu zero, înseamnă că valoarea variabilei ciclului este divisor pentru numărul N.
Algoritm Afisare_divizori
Var
Numar1: natural
Numar2: natural
Procedure Divizor(N: natural )
Var
I: natural
Begin
For I:=1 to N step 1
If N mod I =0 then
WriteNat(i)
End
End
End
Begin
ReadNat(numar1)
Divisor(numar1)
ReadNat(numar2)
Divisor(numar2)
End
Transmiterea parametrilor prin referinţă
Parametrii a căror declaraţie este prefixată de cuvăntul rezervat var sun consideraţi parametri-variabile. Pentru ei există un alt mecanism de transmitere a valorilor, numit transmitere prin referinţă a parametrilor. El constă în punerea în corespondenţă, la apelul procedurii, a parametrilor actuali cu parametrii formali, astfel încât, pe durata execuţiei procedurii, identificatorul unui parametru formal devine sinonim cu identificatorul paramtrului actual corespunzător. Datorită acestui mecanism, operaţiile procedurii au efect direct asupra parametrilor actuali.
Modificările parametrilor-variabile ai unei proceduri persistă (se transmit programului apelant) şi după terminarea execuţiei procedurii. O schimbare a parametrului formal se reflectă în celălalt parametru. Parametru actual corespunzător unui parametru formal variabilă nu poate fi o expresie, ci numai o variabilă. de acelaşi tip cu parametrul formal corespunzător.
Dacă procedura furnizează rezultatele sale programului apelant, atunci acest parametru trebuie să fie transmis numaidecât prin referinţă, iar dacă parametrii reprezintă date de întrare, atunci ei pot fi transmişi atât prin valoare cât şi prin referinţă.
Exemplu: să se calculeze aria totală a două loturi dreptunghiulare.
Rezolvare
Vom elabora procedura Aria_unui_lot, care va avea la întrare cele două dimensiuni ale dreptunghiului. Deci procedura va avea doi parametrii, transmişi prin valoare şi va returna aria calculată programului apelant, deci acest parametru se va transmite prin referinţă. . Pentru calcularea ariei totale vom apela de două ori procedura Aria_unui_lot cu diferiţi parametric actuali
Algoritm Aria_totala
Var
A1,b1 : real;
A2,b2 : real
S1,S2: real
S_total: real
Pricedure Aria_unui_lot(latura1:real, latura2: real, var S:real))
Begin
S:=latura1 * latura2
End
Begin
ReadReal(a1)
ReadReal(b1
Aria_unui_lot(a1,b1,s1)
S_total:=S1
ReadReal(a2)
ReadReal(b2)
Aria_unui_lot(a2,b2,S2))
S_total:=S_total+S2
WriteReal(s_total)
End
La primul apel al procedurii Aria_unui_lot parametrul actual a1 se copie în parametrul formal latura1, iar parametrul actual b1 se copie în parametrul formal latura2 şi se instalează corespondenţa între parametrul actual S1 şi parametrul formal S. Începe a lucra procedura care calculează aria primului lot în variabila S care corespunde zonei de memorie ocupate de variabila globală S1. După terminarea procedurii variabila S1 va conţine aria primului lot.
La cel de-al doilea apel al procedurii, parametrul actual a2 se copie în parametrul formal latura1, iar parametrul actual b2 se copie în parametrul formal latura2 şi se instalează corespondenţa între parametrul actual S2 şi parametrul formal S. Începe a lucra procedura care calculează aria lotului doi în variabila S, care corespunde zonei de memorie ocupate de variabila globală S2. După terminarea procedurii variabila S2 va conţine aria celui de-al doilea lot.
4.4.3. Funcţii
În limbajele de programare subprogramele pot fi realizate şi ca funcţii. Deosebirea între proceduri şi funcţii constă în numărul valorilor calculate şi returnate în punctele din care s-a făcut apelul:
- procedura calculează oricâte valori;
- funcţia calculează întotdeauna o singură valoare.
O funcţie este un subprogram care calculează şi întoarce ca rezultat o singură valoare. Forma generală a definiţiei unei funcţii este următoarea:
Function (lista_parametri_formali): tip_rezultat
Var
< variabile locale>
begin

end
Rezultatul calculat de o funcţie este obligatoriu de tip elementar sau string specificat în antet. Rezultatul calculat de funcţie se întoarce programului apelant cu ajutorul operatorului Return
Lista parametrilor formali are sintaxa identică celei de la procedură.
Apelul funcţiei se face chiar în expresia care utilizează valoarea calculată, într-o formă foarte apropiată de scrierea uzuală a formulelor în matematică. Apelul funcţiei poate să apară în orice expresie, ca operand care are tipul rezultatului funcţiei. Sintaxa apelului unei funcţii este următoarea:
< nume_funcţie >(lista_parametri_actuali)
Efectul funcţiei se manifestă atunci când la evaluarea expresiei este necesară valoarea operandului reprezentat de apelul de funcţie. În acest moment, evaluarea expresiei este suspendată temporar şi se realizează următoarele acţiuni:
- se face transferul parametrilor actual ai funcţiei;
- se execută corpul funcţiei; ca urmare este calculată valoarea funcţiei;
- acestă valoare este chiar valoarea operandului, folosită în continuare la reluarea evaluării expresiei ce conţine apelul funcţiei.
Exemplu: să se calculeze S=max(a,b,c)+max(d,e,f)
Rezolvare:
Vom elabora funcţia Max care are la întrare 3 numere întregi, fie n1,n1,n3. corpul funcţiei determină valoara maximă dintre numerele n1,n2,n3. Deci, funcţia va avea 3 întrări – 3 parametri formali, transmişi prin valoare.
Algoritm Suma_max
Var
A,b,c,d,e,f: integer
S: integer
Function max(n1: integer, n2: integer, n3: integer): integer
Var
N_max: integer
Begin
If n1>n2 then
N_max:=n1
Else
N_max:=n2
End
If n3> n_max then
N_max:=n3
End
Return n_max
End
Begin
ReadInt(a)
ReadInt(b)
ReadInt(c)
ReadInt(d)
ReadInt(e)
ReadInt(d)
S:=max(ab,c)+max(d,e,f)
End
Variabilei globale S i se atribuie valoare unei expresii cu doi operanzi. Operanzii reprezintă apeluri de funcţii. Înainte de a face operaţia adunării se calculează primul operand, care suspendă calculul expresiei şi face apelul funcţiei Max cu parametrii actuali (a,b,c). Funcţia returnează în punctul apelului funcţiei valoarea calculată de funcţie. Apoi se calculează cel de-al doilea operand prin apelul funcţiei Max cu parametrii actuali (d,e,f) ,care returnează în punctual apelului valoarea calculată de funcţie. După ce se adună valorile celor doi operanzi calculaţi.

structuri de control in programare

4. STRUCTURI DE CONTROL

În vederea elaborării unor programe clare şi uşor de întreţinut, programarea structurată impune restrângerea structurilor de control utilizabile în programe la patru structuri fundamentale:

- secvenţială;

- alternativă;

- repetitivă;

- abstracţia.

4.1. Structura secvenţială

Citirea, scrierea şi atribuirea reprezintă operaţiile de bază ale programelor. Obţinerea unor efecte mai complicate se face prin combinarea acestora în conformitate cu anumite reguli.

Secvenţa este cea mai simplă regulă de ordonare a unui grup de instrucţiuni. Conform acestei reguli, instrucţiunile unui algoritm sunt executate una după alta, în ordinea scrierii lor.

Pentru exemplificarea secvenţei, să considerăm problema găsirii ariei şi perimetrului unui dereptunghi. Datele problemei sun lungimile laturilor dreptunghiului, iar rezultatele sunt valorile ariei şi perimetrului. Convenim să utilizăm variabilele lung şi lat pentru valorile lungimii şi lăţimii dreptunghiului, respective aria şi perimetrul pentru rezultate.

Rezolvarea problemei presupune efectuarea următoarei secvenţe de operaţii:

- citirea valorilor lungimii şi lăţimii în variabilele lung şi lat;

- calculul valorii variabilei aria;

- calculul valorii variabilei perimetrul;

- afişarea rezultatelor obţinute.

Acestor operaţii le corespunde următorul algoritm:

Algoritm Calcul

Var

Lat: natural

Lung: natural

Aria: natural

Perimetrul: natural

Begin

WriteString(‘Întroduceţi lungimile laturilor dreptunghiului’)

ReadNat(lat)

Writeln

ReadNat(lung)

Writeln

Aria:= lung * lat

Perimetrul:= 2*(lung + lat)

WriteString(‘Aria= ‘)

WriteNat(aria)

Writeln

WriteString(‘Perimetrul= ‘)

WriteNat(perimetrul)

End.

Exemplu:

Să se scrie un algoritm de conversie a unui unghi exprimat din radiani în grade, minute, secunde,zecimi şi sutimi de secundă.

Rezolvare: Se citeşte unghiul dat, x în radiani şi se calculează cu relaţia:

Grade_fract = (180 *x) / π

Unghiul echivalent în grade exprimat printr-un număr real. Se extrage partea întregă grade din grade_fract . Partea fracţionară din grade_fract se înmilţeşte cu 60 obţinându-se numărul de minute exprimat printr-un număr real min_fract Partea întreagă din min_fract reprezintă numărul de minute, iar parea fracţionară , la fel ca pentru minute, se obţine numărul de secunde, apoi numărul de zecimi şi de sutimi.

O primă formă a algoritmului în pseudocod este următoarea:

- întroducerea unghiului în radiani;

- conversie;

- afişarea rezultatelor.

În algoritm vor fi folosite următoarele date:

X – unghiul exprimat în radian;

Grade_fract – unghiul exprimat în grade sub forma unui număr real;

Grade – numărul de grade sub forma unui întreg;

Min_fract – numărul de minute exprimat sub forma unui număr real rezultat din grade_fract după exstragerea părţii întregi (grade);

Minute – numărul de minute, valoare întreagă;

Sec_fract – numărul de secunde exprimat sub forma unui număr real;

Secunde – numărul de secunde, valoare întreagă;

Zec_fract – numărul de secunde exprimat sub forma unui număr real;

Zecimi – numărul de zecimi de secundă, valoare întreagă;

Sutimi - sutimile de secundă, valoare intregă.

Adăugând variabilele necesare, algoritmul devine:

- întroducerea unghiului în radiani (x);

- conversie (x,grade,minute,secunde,zecimi,sutimi);

- afişarea rezultatelor (x,grade, minute, secunde, zecimi, sutimi)

Subproblema 1 se rafinează astfel:

WriteString(‘Întrodu unghiul în radian’i)

ReadReal(x)

Writeln

Subproblema 2 se rafinează astfel:

Grade_fract:=x*180/ π

Grade:=RealToCard(grade_fract)

Min_fract:=(grad_fract- CardToReal(grade))*60

Minute:=RealToCard(min_fract)

Sec_fract::= (min_fract – CardToReal(minute))*60

Secunde:= RealToCard(sec_fract)

Zec_fract:= (sec_fract – sec)*10

Zecimi:= RealToCard(zec_fract)

Sutimi:=RealToCard((zec_fract –zecimi)*10)

Subproblema 3 se rafinează astfel:

WritString(‘Unghiul în radiani ‘)

WriteReal(x)

Writeln

WritString(‘Grade ‘)

WriteNatl(grade)

Writeln

WritString(‘minute ‘)

WriteNat(minute)

Writeln

WritString(‘secunde ‘)

WriteNat(secunde)

Writeln

WritString(‘zecimi ‘)

WriteNat(zecimi)

Writeln

WritString(‘sutimi ‘)

WriteNat(sutimi)

Writeln

Algoritmul este următorul:

Algoritm Conversie

Var

X: real

Grade_fract: real

Grade: natural

Min_fract: real

Minute: natural

Sec_fact: real

Secunde: natural

Zec_fract: real

Zecimi: natural

Sutimi: natural

Begin

WriteString(‘Întrodu unghiul în radiani)

ReadReal(x)

Writeln

Grade_fract:=x*180/ π

Grade:=RealToCard(grade_fract)

Min_fract:=(grad_fract- CardToReal(grade))*60

Minute:=RealToCard(min_fract)

Sec_fract::= (min_fract – CardToReal(minute))*60

Secunde:= RealToCard(sec_fract)

Zec_fract:= (sec_fract – sec)*10

Zecimi:= RealToCard(zec_fract)

Sutimi:=RealToCard((zec_fract –zecimi)*10)

WritString(‘Unghiul în radiani ‘)

WriteReal(x)

Writeln

WritString(‘Grade ‘)

WriteNat(grade)

Writeln

WritString(‘minute ‘)

WriteNat(minute)

Writeln

WritString(‘secunde ‘)

WriteNat(secunde)

Writeln

WritString(‘zecimi ‘)

WriteNat(zecimi)

Writeln

WritString(‘sutimi ‘)

WriteNat(sutimi)

Writeln

End.

Exemplu:

Se citeşte un număr natural format din 3cifre. Să se calculeze suma cifrelor acestui număr.

Rezolvare:

Prima formă a algoritmului în pseudocod este următoarea:

- citirea numărului din 3 cifre ;

- calcularea sumei cifrelor numărului întrodus;

- afişarea sumei cifrelor.

Vom folosi următoarele date:

Numar – numărul întreg din intervalul 100 ..999;

Cifra_1 – prima cifră a numărului;

Cifra_2 – prima din mijloc a numărului;

Cifra_3 – ultima cifră a numărului;

Suma – suma celor trei cifre.

Adăugând şi variabilele necesare, algoritmul devine:

- citirea numărului din 3 cifre (numar);

- calcularea sumei cifrelor numărului întrodus (suma);

- afişarea sumei cifrelor.

Prima subproblemă se rafinează astfel:

WriteString(‘Întroduceţi un număr din intervalul 100 ..999’)

ReadNat(numar)

Writeln

Subproblema 2 se împarte în următoarele subprobleme:

- determinarea ulimei cifre;

- determinarea cifrei din mijloc;

- determinarea primei cifre;

- calcularea sumei cifrelor.

Pentru a determina ultima cifră a unui număr natural se calculează restul de la împărţirea numărului la 10. De exemplu:

123 mod 10 =3

139 mod 10 =9

185 mod 10 =5

Deci,

Cifra_3 := numar mod 10

Pentru a detrmina cifra din mijloc, e necesar să ignorăm ultima cifră. În număr vor rămâne numai 2 cifre. Ultima cifră a acestui număr va fi cifra din mijloc a numărului iniţial, iar prima cifră – prima cifră a numărului iniţial. Pentru a ignora ultima cifră a numărului î-l vom împărţi la 10 (partea întreagă a câtului obţinut). De exemplu:

123 div 10 = 12

345 div 10 = 34

Subproblema 2 se rafinează asfel:

Cifra_3:=numar mod 10

Numar:=numar div 10

Cifra_2:= numar mod 10

Cifra_1:=numar div 10

Suma:=cifra1+cifra2+cifra3

Subproblema 3 se rafinează în felul următor:

WriteString(‘Suma cifrelor = ‘)

WriteNat(Suma)

Algoritmul rezolvării problemei este următorul:

Algoritm suma_cifrelor

Var

Numar: natural

Cifra_1: natural

Cifra_2: natural

Cifra_3: natural

Suma: natural

Begin

WriteString(‘Întroduceţi un număr din intervalul 100 ..999’)

ReadNat(numar)

Writeln

Cifra_3:=numar mod 10

Numar:=numar div 10

Cifra_2:= numar mod 10

Cifra_1:=numar div 10

Suma:=cifra1+cifra2+cifra3

WriteString(‘Suma cifrelor = ‘)

WriteNat(Suma)

WriteString(‘Suma cifrelor = ‘)

WriteNat(Suma)

End

4.2. Structura alternativă

În unele probleme se simte nevoia unei operaţii de decizie,de pildă într-un exemplu ca acela al determinării perimetrului unui triunghi cu lungimile laturilor a,b şi c. Calculul perimetrului este simplu, dar se pune problema: întotdeauna trei numere reale pot fi laturilor unui triunghi? Evident că nu; în primul rând ele trebuie să fie strict positive, în al doilea rând trebuie ca fiecare din ele să fie strict mai mică decât suma celorlalte două. Acest lucru nu poate fi evidenţiat cu simpla instrucţiune de atribuire. Ea poate fi realizată cu ajutorul structurii decizionale. În majoritatea limbajelor de programare există două tipuri de construcţii alternative:

- construcţia IF;

- costrucţia Case.

4.2.1. Construcţia IF

Are 2 forme.

În prima, instrucţiunea are două ramuri:

If condiţie then

Secvenţa_1

Else

Secvenţa_2

End

Cea de a doua formă are numai ramura Then:

If condiţie then

Secvenţa_1

End

Condiţia condiţie poate fi:

- fie o constantă booleană (True sau False), deşi nu are sens o asemenea utilizare;

- fie o variabilă booleană, care poate avea una din valorile True sau False;

- fie o expresie booleană, de exemplu (x or y);

- fie o expresie relaţională, de genul x unde x şi y sunt variabile de acelaşi tip;

- fie o expresie mixtă, de exemplu (x7);

- fie apelul unei funcţii logice.

Execuţia instrucţiunii If-Then-Else constă în:

- se evaluează condiţia;

- dacă valoarea condiţiei este True se execută Secvenţa_1 (ramura Then);

- dacă valoarea expresiei este False se execută Secvenţa_2 (ramura Else).

În concluzie, în funcţie de valoarea condiţiei, se execută numai una din cele două ramuri (sau Then sau Else). Programul continuă cu execuţia instrucţiunii care urmează după End.

Cea de a doua formă a structurii alternative reprezintă o ocolire. Secvenţa_1 se execută numai dacă condiţia are valoarea True.

Exemple:

- faptul că a,b şi c pot fi lungimile laturilor unui triunghi se poate exprima:

(a>0) and (b>0) and (c>0) and (b+c>a) and a+c>b) and (a+b>c) ;

- faptul că a este număr pozitiv se poate exprima a>0 ;

- faptul că a este număr par se poate exprima a mod 2 =0;

- faptul că a este număr impar se poate exprima a mod 2 #0;

- faptul că a este divizibil prin 7 se poate exprima a mod 7 =0;

- faptul că a reprazintă un număr format din 3 cifre se poate exprima a>=100 and a<=999;

- faptul că a reprezintă numărul unei luni de vară se poate exprima (a>=6 and a<=8) sau (a=6 or a=7 or a=8);

- faptul că a,b şi c reprezintă lungimile laturilor unui triunghi isoscel se poate preciza prin (a=b or b=c or c=a).

4.2.1.1.Simplificarea expresiilor logice

Multe expresii logice pot fi scrise corect prin diferite metode. Aplicând anumite reguli, expresiile logice pot fi simplificate în alte expresii mai simple. Cu acst scop se folosesc axiomele distributive şi legile lui de Morgan.

Axioma distributivă 1

O expresie de forma (P or Q) and (P or R) poate fi transformată în expresia echivalentă

P or (Q and R)

Pentru a demonstra identitatea celor două expresii vom construi tabelele de adevăr pentru ambele expresii.

Tabelul de adevăr pentru expresia (P or Q) and (P or R)

P	Q	R	P or Q	P or R	(P or Q) and (p or R)
False	False	False	False	False	False
False	False	True	False	True	False
False	True	False	True	False	False
False	True	True	True	True	True
True	False	False	True	True	True
True	False	True	True	True	True
True	True	False	True	True	True
True	True	True	True	True	True

Tabelul de adevăr pentru expresia P or (Q and R)

P	Q	R	Q and R	P or (Q and r)
False	False	False	False	False
False	False	True	False	False
False	True	False	False	False
False	True	True	True	True
True	False	False	False	True
True	False	True	False	True
True	True	False	False	True
True	True	True	True	True

Tabele de adevăr sunt identice. Deci, sunt identice şi expresiile logice.

Axioma distributivă 2

(P and Q) or (P and R) = P and (Q or R)

Legile de Morgan

1. (Not P) and (Not Q) = Not (P or Q)

2. (Not P) or (Not Q) = Not (P and Q)

Exemplu:

Să se elaboreze algoritmul care citeşte valorile a trei temperaturi. Determină temperatura minimă şi afişează mesajul ‘E frig’ dacă temperatura minimă este mai mică de - 4⁰C.

Rezolvare:

Algoritm Temp_min

Var

Temp1: integer

Temp2: integer

Temp3: integer

Min_temp: integer

Begin

WriteString(‘Întroduceţi 3 temperaturi’)

ReadInt(Temp1)

Writeln

ReadInt(Temp2)

Writeln

ReadInt(Temp3)

Writeln

If Temp1 < Temp2 then

Min_temp:= Temp1

Else

Min_temp:= Temp2

End

If Temp3 < Min_temp then

Min_temp:= Temp3

End

If Min_temp < -4 then

WriteString(‘E frig’)

End

End

Se permite folosirea instrucţiunilor If imbricate una în alta, ca în exemplul următor:

If a < b then

If a < c then

Writestring(‘1’)

Else

WriteString(‘2’)

End

End

Fie n condiţii c1, c2,… , cn care provoacă fiecare execuţia câte unei secvenţe s1,s2, … ,sn, la un moment dat putând să fie îndeplinită numai una din cele n condiţii. Următoarea secvenţă de algoritm

If c1 then

S1

End

If c2 then

S2

End

…

…

If cn then

Sn

End

este foarte dezavantajos concepută, deoarece se vor executa toate instrucţiunile If, chiar dacă s-a ajuns în situţia că una dintre condiţii este îndeplinită, deci celelalte sigur nu vor fi satisfăcute. Pentru a evita evaluarea tuturor condiţiilor, se vor folosi instrucţiuni If-Then-Else-End, incluse unele în altele, în care condiţiile mai probabile se pun la început. Se recomandă folosirea modelului din secvenţa următoare, cu scriere identată, pentru ca secvenţa de algoritm să fie uşor lizibilă:

If c₁ then

s₁

Else

If c₂ then

s₂

Else

…

else

if c_n-1 then

s _n-1

else

if c_n then

s _n

end

end

end

end

end

end

O secvenţă de forma:

If x=y then

Gasit:=true

Else

Gasit:=false

End

Se poate scrie mai efficient astfel:

Gasit:=x=y

4.2.2. Instrucţiunea Case (selecţia multiplă)

Dacă în algoritm e necesar de făcut o alegere nu din două alternative, dar din mai multe, atunci pe lângă construcţia if poate fi folosită construcţia Case, care are următorul format:

Case selector Of

Alternativa_1: secvenţa_1

Alternativa_2: secvenţa_2

:

Alternativa_n: secvenţa_n

Else

Secvenţa_x

End

Selector reprezintă o expresie ordinală.

Alternativa_i reprezintă o constantă de tipul selectorului.

Execuţia instrucţiunii Case constă în:

- se evaluează selectorul;

- se caută alternativa care cuprinde valoarea selectorului;

- dacă se găseşte o asemenea alternativă, se execută secvenţa care o urmează;

- în caz contrar, se execută secvenţa care urmează cuvântul cheie Case, în lipsa acestuia nu se execută nimic.

În concluzie, prin execuţia instrucţiunii Case se va executa numai o singură secvenţă (eventual nici una) dintre cele care urmează după alternativele Case sau după Else, execuţia programului continuând, apoi, cu instrucţiunea care urmează după End.

Exemplu: Se citeşte numărul zilei săptămânii. Să se afişeze denumirea zilei.

Rezolvare: problema poate fi rezolvată folosind construcţia If astfel:

Algoritm Denum_zilei_1

Var

N_zi: natural

Begin

WriteString(‘N zilei săptămânii: ‘)

ReadNat(n_zi)

Writeln

If n_zi=1 then

Writestring(‘Luni’)

Else

If n_zi=2 then

WriteString(‘MarţI’)

Else

If n_zi=3 then

WriteString(‘Miercuri’)

Else

If n_zi=4 then

WriteString(‘Joi’)

Else

If n_zi=5 then

WriteString(‘Vineri’)

Else

If n_zi=6 then

WriteString(‘Sâmbătă’)

Else

If n_zi=7 then

WriteString(‘Duminică’)

Else

WriteString(‘Eroare’)

End

End

End

End

End

End

End

End

O variantă mai lizibilă a algoritmului se obţine folosind construcţia Case:

Algoritm Denum_zilei_2

Var

N_zi: natural

Begin

WriteString(‘N zilei săptămânii: ‘)

ReadNat(n_zi)

Writeln

Case n_zi of

1: WriteString(‘Luni’)

2: WriteString(‘Marţi’)

3: WriteString(‘Miercuri’)

4: WriteString(‘Joi’)

5: WriteString(‘Vineri’)

6: WriteString(‘Sâmbătă’)

7: WriteString(‘Duminicâ’)

else

writeString(‘Eroare’)

end

end

4.3. Structura repetitivă

Repetarea unor calcule într-un algoritm se poate face fie multiplicand explicit instrucţiunile respective, fie utilizând construcţii speciale care să reprezinte această repetare.

Să considerăm un exemplu, care realizează citirea şi adunarea a 4 numere.

În algoritm se vor utiliza două variabile: S în care se va face adunarea numerelor şi N, care va primi pe rând valorile numerelor ce se citesc. Se citeşte iniţial primul număr, care va reprezenta şi valoarea iniţială a sumei. Fiecare nou număr citit se adaugă la vechea valoare a sumei S.

Algoritm Suma_1

Var

N: natural

S: natural

Begin

WriteString(‘Numărul 1 ?’)

ReadNat(N)

writeln

S:=N

WriteString(‘Numărul 2 ?’)

ReadNat(N)

S:=S+N

WriteString(‘Numărul 3 ?’)

ReadNat(N)

S:=S+N

WriteString(‘Numărul 4 ?’)

ReadNat(N)

S:=S+N

WriteString(‘Suma= ‘)

WriteNat(s)

End

Se poate observa că de fapt se execută de trei ori aceeaşi secvenţă de instrucţiuni: WriteString, ReadNat, S:= …. Primul număr citit este tratat puţin diferit deoarece la valoarea lui se va iniţializa suma. Algoritmul se poate modifica astfel încât toate numerele să fie tratate la fel. Va rezulta următorul algoritm:

Algoritm Suma_2

Var

N: natural

S: natural

Begin

S:=0

WriteString(‘Numărul 1 ?’)

ReadNat(N)

writeln

S:=S + N

WriteString(‘Numărul 2 ?’)

ReadNat(N)

S:=S+N

WriteString(‘Numărul 3 ?’)

ReadNat(N)

S:=S+N

WriteString(‘Numărul 4 ?’)

ReadNat(N)

S:=S+N

WriteString(‘Suma= ‘)

WriteNat(s)

End

Dacă acum trebuie să modificăm acest algoritm pentru a realiza suma a 5 numere soluţia este simplă: mai adăugăm o secvenţă de instrucţiuni WriteString, ReadNat, S:=. Cum putem însă să procedăm dacă este vorba de 100 de numere sau de 1000 de numere. Evident, avem nevoie de o altă soluţie. Este necesar un mecanism prin care să indicăm că secvenţa considerată anterior trebuie să fie repetată de 100 sau de 1000 de ori. Instrucţiunile care descriu execuţia repetată a unor prelucrări se numesc structuri repetitive sau cicluri.

O structură repetitivă este formată dintr-un preambul în care se stabilesc condiţiile repetării şi din instrucţiunile care urmează să se execute în mod repetat ( care formează corpul ciclului). Deci elementele ciclului sunt:

- corpul ciclului - indică consecutivitatea de operaţii care se execută la o repetare;

- condiţia ciclului - indică de câte ori, cât timp se execută corpul ciclului

Executarea corpului ciclului o singură dată se numeşte i t e r a ţ i e .

În limbajele de programare se folosesc 4 tipuri de structuri repetitive:

- For;

- While;

- Repeat;

- Loop.

4.3.1. Construcţia While

Construcţia While, numită şi construcţia de ciclare cu test iniţial sau construcţia de ciclare condiţionată anterior.Construcţia are următoarea sintaxă:

While condiţie do

Corpul ciclului

End

Condiţia reprezintă o expresie booleană.

Execuţia construcţiei While constă în:

1. se evaluează condiţia;

2. dacă expresia are valoarea True, se execută corpul ciclului şi se revine la pasul 1;

3. dacă expresia are valoarea False, execuţia programului continuă cu instrucţiunea care urmează după Enddo.

În concluzie, corpul ciclului se va executa atâta timp cât valoarea condiţiei de ciclare este True, ieşirea din ciclu având loc când expresia devine False. Dacă, la întrare în ciclu, condiţia de ciclare nu este îndeplinită (expresia are valoarea False), corpul ciclului nu se va executa niciodată.

4.3.1.1. Ciclul cu contor

Dacă se ştie de câte ori se repetă corpul ciclului, atunci aşa tip de ciclu se numeşte ciclu cu contor. El se termină atunci când toate iteraţiile au fost executate. Pentru numărarea iteraţiilor în ciclul cu contor se filoseşte o variabilă, numită variabila ciclului. Valoarea acestei variabile se incrementează la fiecare iteraţie, iar în condiţia ciclului se compară cu numărul dat de repetări,

Exemplu: Ciclu cu contor care se execută de 50 de ori:

i:=0

While n<50 do

Corpul ciclului

I:=i+1

Enddo

Pentru ca ciclul cu contor să se execute corect e necesar:

- până la intrare în ciclu să i se atribuie variabilei ciclui valoare iniţială (i:=0);

- să se modifice variabila ciclului în corpul ciclului (i:=i+1). Dacă variabila ciclului nu se va modifica, atunci ciclul va deveni infinit.

Exemplu: să se calculeze suma primelor 10 numere naturale.

Rezolvare:

În variabila S vom acumula suma celor 10 numere naturale. Iniţial variabila S se iniţializează la valoare 0. La fiecare iteraţie la variabila S se va aduna următorul număr natural x (s:=s+x) . Se începe cu primul număr natural. Deci până la intrare în ciclu variabila x se iniţializează cu valoarea 1, iar în corpul ciclului se va calcula valoarea următorului număr natural (x:=x+1). Condiţia ciclului va fi (x<=10).

Var

S: natural

x: natural

Begin

S:=0

x:=0

While x< 10 do

S:=s+x

x:=x+1

End

Exemplu: de la tastatură se citesc 5 numere interegi. Să se calculeze media aritmetică a numerelor întroduse.

Rezolvare:

Se va organiza un ciclu, care se va repeat de 5 ori. Dacă n este variabila ciclului, atunci condiţia ciclului va fi (n<5). Pentru ca ciclu să funcţioneze corect, până la intrare în ciclu variabilei n i se va atribui valoare iniţială (n:=0. În corpul ciclului se va citi de la tastatură numărul întreg în variabila Num şi se va aduna la variabila S. Iniţial variabilei S i se va atribui valoare iniţială (S:=0).

Var

Num: integer

S : integer

N : integer

Medie:integer

Begin

S:=o

N:=

While n<5 do

ReadInt(num)

S:=S+Num

N:=n+1

End

Medie:=S div 5

4.3.1.2. Ciclu cu condiţie de terminare

Destul de frecvent în programare un set de instrucţiuni se repetă nu de un număr dat de ori, ci pănă când se îndeplineşte o anumită condiţie. De exemplu: de la tastatură se citesc numere întregi până la apariţia primului număr negativ. Dacă numărul se va citi în variabila Num, atunci ciclul se va repeta atâta timp cât Num>=0. Pentru ca prima iteraţie să se execite corect e necesar ca prima citire să se facă până la intrare în ciclu.Corpul ciclului va începe cu prelucrarea numărului citit. Celelalte citiri se vor face după prelucrare în corpul ciclui .

Algoritmul va fi următorul:

ReadInt(Num)

While Num >=0 Do

{Prelucrare}

ReadInt(Num)

End

Practica progamării:

Dacă în algoritm se foloseşte ciclul While e necesar de determinat :

- ce se face la fiecare iteraţie. Setul de instrucţiuni care realizează iteraţia va forma corpul ciclului;

- în ce condiţii iteraţiile se vor executa; condiţiile vor forma condiţia ciclului;

- ce trebuie de făcut ca prima iteraţie să se execute corect. Va fi necesar ca aceste instrucţiuni să fie programate până la intrare în ciclu.

Exemplu: Să se calculeze cel mai mare divisor comun a două numere naturale m şi n.

Rezolvare:

Cel mai mare divisor comun se calculează folosind algoritmul lui Euclid:

- fie numerele naturale naturale a şi b;

- cât timp numerele nu sunt egale din cel mai mare se scade cel mai mic.

Var

A: natural

B: natural

Cmmdc: natural

Begin

ReadNat(a)

ReadNat(b)

While a<>b do

If a>b then

A:=a-b

Else

B:=b-a

end

End

Cmmdc:=a

4.3.2. Construcţia Repeat

Deseori e necesar ca condiţia ciclului să fie analizartă nu la începutul ciclului ca în cazul construcţiei While, dar la sfârşitul iteraţiei. Cu acrst scop se foloseşte construcţia Repeat, numită şi instrucţiune de ciclare cu test final sau instrucţiune de ciclare condiţionată posterior.

Construcţia are următoarea sintaxă:

Repeat

< corpul ciclului >

Until < condiţie>

Condiţia este o expresie logică, care reprezintă condiţia de ieşire din ciclu.

Execuţia instrucţiunii Repeat constă în:

1.Se execută corpul ciclului – instrucţiunile cuprinse între Repeat şi Until;

2. Se evaluează condiţia:

- dacă valoarea expresiei este False, se revine la punctual 1 şi se execută din nou corpul ciclului;

- dacă valoarea expresiei este True, programul continuă cu instrucţiunea după Until, deci se face ieşire din ciclu.

În concluzie, corpul ciclului se va executa atâta timp cât valoarea condiţiei de ciclare este False, ieşirea din ciclu având loc când expresia devine True.

Spre deosebire de construcţia While, corpul instrucţiunii Repeat se execută cel puţin o dată. Şi în cazul construcţiei Repeat, evaluarea expresiei are loc la fiecare pas al ciclului, deci va trebui să fie cât mai simplă. Utilizarea acestei construcţii este avantajoasă când există certitudinea necesităţii parcurgerii lui cel puţin o dată.

Ciclul cu contor realizat cu Repeat

Se foloseşte o variabilă care va număra iteraţiile, fie n. până la intrare în ciclu acestei variabile i se atribuie valoare iniţială (n:=1). În corpul ciclului variabila n va număra iteraţiile (n:=n+1). Ieşirea din ciclu se va face atunci când toate iteraţiile au fost executate ( n >numărul de repetări). Structura ciclului cu contor:

N:=1

Repeat

< corpul ciclului >

n:=n+1

Until n>numărul repetărilor

Exemplu: să se calculeze suma a 5 numere întergi citite de la tastatură.

Rezolvare:

Numărul citit de la tastatură se va păstra în variabila Num. Variabila n va număra iteraţiile. În variabila S se va acumula suma. Corpul ciclului se va repeat de 5 ori, deci condiţia de ieşire din ciclu va fi n>5

Algoritm summa

Var

S: integer

Num: integer

N: integer

Begin

S:=0

N:=1

Repeat

ReadInt(num)

S:=S+num

Until n>5

End

4.3.3.Echivalenţa ciclurilor Repeat şi While

Ambele cicluri descriu o repetare pe baza unei condiţii de terminare. Diferenţa între cele două instrucţiuni constă în momentul în care se face evaluarea condiţiei. Astfel, pentru Repeat (traducerea numelui instrucţiunii este repetă până când) evaluarea condiţiei se face după fiecare iteraţie. Iteraţiile se execută în mod repetat, până la îndeplinirea condiţiei, cu alte cuvinte atâta timp cât respectiva condiţie nu este îndeplinită. Pentru instrucţiunea While ( traducerea numelui este cât timp) evaluarea condiţiei se face înaintea de execuţia corpului ciclului. Prelucrarea care formează corpul ciclului se execută în mod repetat atâta timp cât condiţia este justă. Condiţia care apare în cele două construcţii este o expresie logică. Pentru Repeat valoarea True a condiţiei înseamnă închierea ciclului. Pentru While valoare True a condiţiei înseamnă continuarea repetărilor. Cu alte cuvinte pentru Repeat condiţia care apare în instrucţiune este condiţia de părăsire a ciclului, în timp ce pentru While este condiţia de rămânere în ciclu.

Prelucrările executate în cazul ciclului Repeat sunt:

Prelucrare,evaluare_condiţie,prelucrare, … eevaluare_condiţie

Deci prelucrarea se execută cel puţin o dată.

În cazul ciclului While, ordinea de execuţie a prelucrărilor este:

Evaluare_condiţie, prelucrare, evaluare_condiţie,… ,evaluare_condiţie

Deci este posibil ca prelucrarea să nu se execute nici o dată ( dacă condiţia de rămânere în ciclu nu este îndeplinită de la început).

Între cele două instrucţiuni se poate stabili o echvalenţă şi anume:

- un ciclul While se poate reprezenta cu ajutorul anui ciclu Repeat, dacă acest ciclu se întroduce într-o structură de decizie care utilizează condiţia de reluare a ciclului;

- un ciclu Repeat se poate înlocui printr-un ciclu While, precedându-l pe acesta cu o prelucrare.

Instrucţiunea

While do

end

poate fi reprezentată echvalent în felul următor:

if then

repeat

< prelucrare >

until not

endif

Instrucţiunea

Repeat

< prelucrare >

until

poate fi reprezentată echivalent în felul următor:

while not

< prelucrare >

end

Având în vedere că este posibil să obţinem structuri echivalente utilizând ambele instrucţiuni, se pune problema cum se face alegerea. Criteriul utilizat de obicei se referă la două aspecte. În primul rând trebuie să scriem programe corecte şi – dacă se poate – scurte. Deci, dacă este posibil ca de la început condiţia de execuţie repetată să nu fie îndeplinită, atunci se va utiliza un ciclu cu test la început (While), evitându-se astfel utilizarea unei combinaţii: if şi repeat. Pe de altă parte, dacă condiţia de repetare depinde de un calcul făcut în ciclu, adică instrucţiunile din corpul ciclului trebuie să se execute o singură dată, se va prefera o soluţie care să utilizeze o instrucţiune Repeat în loc să se utilizeze o soluţie în care apar instrucţiunile din corpul ciclului urmate de un ciclu While.

4.3.3.Construcţia For

Frecvenţa mare a ciclurilor cu contor în programe justifică adoptarea unei notaţii speciale pentru aceste cicluri. Construcţia For este o simplificare de notaţie pentru aceste cicluri. Are următoarea sintaxă:

For < v>:= to step

End

v - este un nume de variabilă de tip scalar, iar expr_init> şi sunt expresii de acelaşi tip cu v, numite respective expresie iniţială şi expresie finală. <pas> poate fi o valoare pozitivă sau negativă.

Semantica construcţiei For este următoarea:

1.se evaluează valoarea expr_init şi se atribuie valoarea calculată variabilei v;

2.se evaluează valoarea expresiei expr_final ;

3.se compară valoarea variabilei v cu valoarea expresiei expr_final:

- dacă pasul este pozitiv, se evaluează valoarea de adevăr a ecxpresiei v<= expr_final;

- dacă pasul este negativ, se evaluează valoarea de adevăr a expresiei v>=expr_final.

4.dacă valoare de adevăr a expresiei evaluate în punctual 3 este true se trece la punctul 5, iar dacă valoarea de adevăr este False se părăseşte ciclul For;

5.se execută corpul ciclului;

6.se face actualizarea valorii variabilei v:

- pentru pasul pozitiv v:=v+

- pentru pasul negativ v:=v-

7. se continuă cu pasul 3.

Exemplu: de la tastatură se citesc 5 numere întregi. Să se calculeze suma numerelor citite.

Rezolvare:

Corpul ciclului:

ReadInt(num)

S:=s+num

Se repetă de 5 ori.

Fie variabila ciclului I. Pentru a organiza un ciclu care se va repeat de 5 ori, variabilei I se va atribui iniţial valoarea 1. valoarea expresiei expr_final va fi egală cu 5, iar pasul egal cu 1.

Algoritm Suma Cu For

Var

S: integer

Num:integer

I: natural;

Begin

S:=0

For I:=1 to 5 step 1

ReadInt(num)

S:=S+num

End

End

4.3.1.Cicluri imbricate

Să considerăm problema găsirii numărului divizorilor proprii ai numerelor naturale mai mici decât o valoare dată. Algoritmul va fi următorul:

Algoritm divizori

Var

I,j,n,d: natural

Begin

ReadNat (n)

For I:=1 to n step 1

D:=0

For j:=2 to I div 2 step 1

If I mod j = 0 then

D:=d+1

End

End

WriteNat(d)

End

End

În aceast algoritm se calculează numărul divizorilor tuturor numerelor de la 1 la valoarea maximă n specificată de utilizator. Deoarece calculul numărului de divizori se face la fel pentru toate valorile, folosim un ciclu cu contor în corpul căruia se calculează numărul divizorilor unei valori oarecare i. Se verifică resturile împărţirii lui I la numerele j cuprinse între 2 şi (I div 2). De aici rezultă necesitatea folosirii unui al doilea ciclu, după j. La fiecare iteraţie, dacă împărţirea se face fără rest, se adaugă o unitate numărului de divizori.

Structura obţinută este compusă din două cicluri imbricate: un ciclu exterior, controlat de variabila I şi un ciclu interior, controlat de variabila j. Pentru fiecare valoare a lui I instrucţiunea if din ciclul controlat de j se execută de (I div 2 – 1) ori (cu I>=2).

Exemplu: să se realizeze următoarea piramidă:

1

1 2

1 2 3

. . . .

1 2 3 … n

în care numărul n este întrodus de la tastatură.

Rezolvare:

Se vor afişa n linii. Linia I cu I de la 1 la n. Pe fiecare linie I avem de afişat numerele 1,2,…i., deci numărul j, cu j de la 1 la I. La sfârşitul afişării unei linii, trebuie să trecem pe următoarea linie.

Algoritm Piramida

Var

I: natural

J: natural

N: natural

Begin

ReadNat(n)

For I:=1 to n step 1

For j:=1 to I step 1

WriteNat(j)

End

End

În limbajele de programare, variabila contor a unui ciclu For poate fi folosită în calculele din ciclu, cu condiţia ca instrucţiunea din componenţa ciclului să nu-i modifice valoarea. Singurul mecanizm de modificare a valorii contorului trebuie să fie cel al instrucţiunii For. Astfel, o construcţie de forma:

For I:=1 to imax step 1

. . .

I:=I+2

End

este eronată. Variabila I , care joacă aici rolul de contor al ciclului, este modificată explicit prin instrucţiunea I:=I+2; lucru nepermis de regulile limbajelor de programare.

4.3.4.Construcţia Loop

Permite ca condiţia să fie analizată în orice fragment al corpului ciclului. Construcţia Loop are următorul format:

Loop

end

Execuţia construcţiei Loop constă în:

1.se execută corpul ciclului;

2.gestiunea se transmite necondiţionat la prima instrucţiune a corpului ciclui.

Pentru a termina ciclul Loop în momentul necesar se foloseşte operatorul Exit. În corpul ciclului, de obicei se foloseşte următoarea construcţie:

If then

Exit

End

Una sau câteva construcţii de acest fel pot apărea în orice loc în corpul ciclului.

Exemplu: să se calculeze suma primelor 10 numere naturale

Rezolvare:

Suma va fi acumulată în variabila S. Numerele naturale vor fi generate în variabila i. Vom începe cu primul număr natural, deci pănă la întrare în ciclu I:=1. În corpul ciclului la variabila S se adună valoarea numărului I şi se generează următorul număr natural I:=I+1. Corpul ciclului trebuie să se repete de 10 ori. Deci, ieşirea din ciclu se va face când au fost însumate toate 10 numere naturale (I>10). Algoritmul va fi următorul:

Algoritm SumaCuLoop

Var

S: natural

I: natural

Begin

S:=0

I:=1

Loop

S:=s+I

I:=I+1

If I>10 then

Exit

End

End

End

4.3.4.1. Echivalenţa ciclului While şi Loop

Ciclul

While do

end

poate fi realizat cu construcţia Loop în felul următor:

loop

if not then

exit

end

end

4.3.4.2.Echivalenţa ciclului Repat şi Loop

Ciclul

repeat

until

poate fi realizat cu construcţia Loop în felul următor:

loop

if then

exit

end

end