Fundamentele programFundamentele programăăriirii

C4C4 / 21.10.2008 / 21.10.2008

 CursCurs Data Data

1 30 Septembrie 2008 2  7 Octombrie 2008 3 14 Octombrie 2008 44 2121 Octombrie 2008Octombrie 2008

…  …

Continut:

4. Tipuri de date structurate în Pascal:

tablou Array

mulţime mulţime SetSet

şirCaractere şirCaractere StringString

înregistrare înregistrare Record Record

Tipul mulţime (Set )Tipul mulţime (Set ) : :

• Util: aplicaţii care folosesc noţiunea de mulţime din matematică.

• <tipSet> ::= Set Of <tipul_elementelor>

• Elem.: numere naturale < 256, caractere, sau elem. de tip enumerare,

iar cardinalul mulţimilor poate fi maxim 256 .

• Ex.:

Type MultimeNr = Set Of 0..255; { sau MultimeNr = Byte }MultimeCar = Set Of Char;MultimeLitM = Set Of ‘A’..’Z’;Zile = (Luni,Marti,Miercuri,Joi,Vineri,Sambata,Duminica);

Var MultimeCif : Set Of ‘0’..’9’;MZile : Set Of Zile;MZileLucratoare : Set Of Luni..Vineri;Vocale, Consoane : MultimeLitM;Numere : MultimeNr;

Operatorii pentru date tip multime :

a) pentru operaţii cu mulţimi : • reuniunea ( ) se notează cu + (A B vom scrie A + B ) ,• intersectia ( ∩ ) se notează cu (A ∩ B vom scrie A B ) ,• diferenta ( \ ) se notează cu ( A \ B vom scrie A B ) ;

b) relaţionali :• = pentru egalitatea a doua multimi ( = ), If A=B Then ...• <> pentru neegalitate ( ), While A<>B Do ...• >= pentru incluziunea nestricta “include” ( ) , Repeat ... Until A>=B ;• <= pentru incluziunea nestricta “inclus in” ( ) , Inclus := A<=B ;• In pentru apartenenţă (). Case e In A Of ... End;

Observaţie : e A se va scrie : Not (e In A).

ConstructoriiConstructorii de mulţimi se definesc astfel:

<constructor>::=[<listaElemente>] ,

unde listaElemente poate fi:

- o succesiune de elemente, sau

- subdomenii de forma elem1 .. .. elem2.

Ex.: mulţimea {1,10,100,101,...,199,200} se scrie [1,10,100..200], iar mulţimea vidă se scrie [ ] .

Ex.: Vocale := [‘A’,’E’,’I’,’O’,’U’];Consoane := [‘A’..’Z’] Vocale;Readln (N); Numere := [1..N]; { N este o variabilă de tip Integer

}.

Obs. O var. de tip mulţime nu se poate citi, iar o expr.de tip mulţime nu se poate

tipări (doar element cu element). De ex., Write(Consoane) nu este permisă.

• Citirea: M:=[ ]; Repeat Read(e); M:=M+[e] Until TerminCitire.;

• Tipărirea : For e:=Min To Max Do If e In M Then Write(e);

Exemplul următor îşi propune rezolvarea următoarei probleme :“ Să se determine numerele prime mai mici sau egale decât un număr n dat ”.

Pentru că vom utiliza tipul mulţime (Set), n va fi cel mult 255. !!

Vom rezolva această problemă în felul următor :

Date n;

Ciur={2,...,n};

Prime=;

Repetă

elementul minim din Ciur va fi mutat în mulţimea Prime, iar

din Ciur se elimină toţi multiplii acestuia

Până_când Ciur-ul devine vid;{ Ciur= }

Rezultate Prime.

Program Ciurul_lui_Eratostene; (* Numerele prime < n *)Var Ciur, Prime, Mp : Set Of 2..255; p, n : Byte; m : Integer;Begin Write (' Dati n : '); Readln (n); Ciur:=[2..n]; Prime:=[ ]; p:=2; Repeat If p în Ciur Then Begin Prime:=Prime+[p]; (* Prime:=Prime U {p} *) Mp:=[]; m:=p; Repeat Mp:=Mp+[m]; m:=m+p Until m>n; Ciur :=Ciur Mp (* Ciur := Ciur \ Mp *) End; {If} p:=p+1 Until Ciur = [ ]; Write(' Prime = {'); (* Tipar. mult. Prime *) For p:=1 To 255 Do If p In Prime Then Write (p,','); Write (Chr(8)+'}'); ReadlnEnd.

Un exerciţiu cu mulţimi pe care îl propunem ca temă este următorul :

“Sa se calculeze C.m.m.d.c. (a,b) “ astfel :

- se determină mulţimile Da şi Db a divizorilor lui a respectiv b,

- se calculeaza mulţimea Dc a divizorilor comuni ( Dc:=Da Db )

- Cmmdc (a,b) = Maxim ( Dc ).

Pot fi a şi b mai mari dacât 255 ? Cum poate fi modificat acest program pentru a

rezolva această problemă ? În mulţimi vom reţine doar indici din şirul tuturor

divizorilor. În felul acesta mulţimile pot conţine elemente de orice tip, dar

cardinalul maxim al mulţimilor va fi doar 255.

Rezolvati o problema in care elementele sunt reale, dar numarul lor nu depaseste

255 (utilizand operatorii existenti).

Teme:Teme:

Tipul şirCaractere Tipul şirCaractere (String )(String ) : :

• Util: ~~ Array Of Char

• <tipString>::= String [[ [m] ]] Lung. Max. = m <= 255255.

• Ex.: Type Linie = String [80]; { Siruri de maxim 80 de caractere }

SirCar = String; { Siruri de maxim 255 de caractere }Var Mesaj : String; Rand : Line;

S : String [20];X : Array [0..20] Of Char;

Există o compat. între variabilele de tip StringString şi cele de tip Array Of CharArray Of Char (S şi X, în exemplul de mai sus). Memoria ocupată în ambele cazuri fiind de 21 de octeti ( S[0] conţine numărul de caractere ale şirului S, care poate fi cel mult m) iar S[i] reprezintă caracterul i din sirul S ( ca şi X[i] , 1 i m ).

ObsObs. : 0 Ord(S[0]) m, pentru că S[0] este de tip Char.

Constante de tip String :

Descrierea constantelor de tip String se realizează utilizând caracterul apostrof () astfel: sir_caractere . Dacă dorim ca şirul de caractere descris să conţină acest caracter, atunci caracterul apostrof va fi dublat.

Ex. : Str. Lalelelor, Nr.2 , Domnu Trandafir ( reprezintă şirul Domnu Trandafir ).

a) Operaţia de concatenare a două şiruri este notată cu ++ . De exemplu Algoritmica, ++ Programare are valoarea Algoritmica, Programare.

b) Operatorii relaţionali permit compararea a două şiruri utilizând ordinea lexicografică (utilizată în dicţionare, cărţi de telefon, etc.) :

== şi <><> pentru egalitatea respectiv neegalitatea a două şiruri , <, >, <=, >=<, >, <=, >= pentru compararea lexicografică.

Ex. : ‘Alb’ < ‘Albastru’; ‘Ionescu’ < ‘Popescu’ ; ‘0...’ < ‘9...’ < ‘A...’ < ‘Z...’ < ‘a...’ < ‘z...’.

Operatori pentru String :

Facilităţi ale tipului StringString ( în plus faţă de Array Of Char ) :

Valorile variabilelor şi expresiilor de tip String pot fi citite respectiv tipărite, ex.: Mesaj:=‘Numele autorului’; Write (‘Dati ‘+Mesaj+’ : ‘); Readln (s);

- LengthLength (S) (=Ord(S[0]) ) returnează lungimea şirului S (Length(‘mare’)=4), - CopyCopy (S,p,l) returnează subşirul (lui S) de lungime l începând din pozitia p

( Copy(‘Marinescu’,2,4)=‘arin’ ), - ConcatConcat (S1,S2,...,Sn) (=S1+S2+...+Sn) ( Concat(‘Con’,’Cat’)=‘ConCat’), - PosPos (x,S) det. poz. subşirului x în şirul S sau 0 dacă şirul S nu conţine ca subşir

pe x ( Pos(‘in’,‘Marinescu’)=4 iar Pos(‘pop’,’Popescu’)=0 ),- DeleteDelete (s,p,l) şterge din s începând din poz. p , l caractere, ex.secventa :

s:=‘Ionescu’; Delete (s,4,4); Write (s); va tipari ‘Ion’;- InsertInsert (x,S,p) inserează şirul x în şirul S la poziţia p. De ex.:

s:=‘Alg.Progr.’; Insert(‘ şi ‘,s,5); Write (s); va tipari ‘Alg. şi Progr.’;- StrStr (e,S) depune în S, şirul cifrelor val. Expr.e , care poate avea ataşat un format

(:n:m ca şi Write). Ex. : v:=5/2; Str (v:5:2,S); va depune în S şirul ‘ 2.50’.

- ValVal (S,v,Cr) examinează şirul S. Dacă este corect atunci va depune în v valoarea iar în Cr val. 0. Dacă şirul S conţine caractere nepermise, atunci în v se depune valoarea 0 iar în variabila Cr (de tip întreg) poziţia primului caracter nepermis.Val (‘1234’,v,Cr); are ca efect : v=1234 şi Cr=0 , iarVal (‘19d7’,v,Cr); are ca efect : v=0 şi Cr=3 ( pe poziţia 3 se află ‘d’).

Problema pe care o vom rezolva utilizând tipul string este următoarea :“Să se calculeze valoarea unei expresii aritmetice de forma : n1n2[=] unde :n1,2 sunt două numere reale, este un operator aritmetic (+, , *, , / sau : ) iar

semnul egal la sfârşitul expresiei poate lipsi. Expresia (simplă, cu un singur operator şi fără paranteze) este dată sub forma unui şir de caractere, iar rezultatul se va afişa cu două zecimale. “

De exemplu pentru ‘123+45’ rezultatul este 168,00 , iar pentru ‘123.3:3=’ rezultatul este 41,10 .Problema o vom rezolva astfel :

e - reprezintă expresia sub forma unui şir de caractere, iar r este rezultatul (valoarea expresiei) dată tot sub forma unui şir de caractere în care se va înlocui marca zecimală ‘.’ cu ‘,’ . Dacă expresia nu se termina cu caracterul ‘=‘, acesta va fi adaugat şirului introdus.Se determină poziţia operatorului (p). Inseamnă că o=e[p] va fi caracterul ce va desemna operaţia ce urmează a fi facută. n1 este scris cu caracterele e1...ep-1 , deci poate fi obtinut cu procedura Val, iar apoi se sterg primele p caractere, ceea ce înseamnă că în expresia e mai ramane ‘n2=’. În continuare, se procedează analog, extragând pe n2, din şirul rămas , mai puţin ultimul caracter. După tipărirea rezultatului (a şirului r ) se va citi alt şir (altă expresie) până când se va introduce expresia vidă (şirul vid) adică se tastează doar Enter în momentul citirii expresiei.

Programul Pascal este următorul :

Program ValoareaExpresiei; (* '123+22=' *) (* n1 o n2 = ? *) (* o {+,-,x,:,*,/} *)

Var e,r : String; o : Char;

n1, n2 : Real; p , er : Integer;

Begin

Repeat Write (' Dati expresia (n1 o n2 =) : '); Readln (e);

If e>'' Then

Begin If Pos ('=',e)=0 Then e:=e+'=';

Val (e,n1,p); Val (Copy(e,1,p-1),n1,er); { p:=Poz(o) } {n1:=...}

o:=e[p]; Delete (e,1,p); Val (Copy(e,1,Length(e)-1),n2,er);

Case o Of

'+' : Str (n1+n2:8:2,r); '-' : Str (n1-n2:8:2,r);

'x','*' : Str (n1*n2:8:2,r); ':','/' : Str (n1/n2:8:2,r)

Else r:=' Operator necunoscut.'+o

End;

p:=Pos('.',r); If p>0 Then r[p]:=','; Writeln (r)

End

Until e=''

End.

Un alt exerciţiu pe care îl propunem ca temă este următorul:

“Să se calculeze valoarea unui polinom P (dat ca stringstring), într-un punct x dat.”

Polinomul P(X) = a0Xn + a1Xn-1 + ... + an-1X + an se dă sub forma:

“a0X^n+a1X^n-1+...+an-1X+an”.

De exemplu, polinomul P(X) = 3X5-7X2+12X-9 se poate scrie astfel :

3X^5-7X^2+12X-9 , utilizând caracterul ‘^’ pentru a marca puterea.

Pentru a rezolva această problemă, se poate extrage din şirul dat, pe

rând fiecare monom (acestea fiind separate de caracterul + sau -), iar din

fiecare monom se va extrage coeficientul şi puterea. În acest fel putem

memora polinomul ca un şir de perechi de forma (coeficient, gradcoeficient, grad), urmând să

calculăm valoarea polinomului obţinut.

Tema:Tema:

Tipul înregistrareTipul înregistrare (Record )(Record ) : :

• Permite gruparea datelor de tipuri diferitegruparea datelor de tipuri diferite înregistrare putem spune că este alcatuită din mai multe câmpuri, nu neapărat de acelaşi tip. Un câmp poate la rândul său să fie alcătuit din mai multe subcâmpuri şi aşa mai departe.

• Ex.: pentru studenţii unei facultăţi avem o structură în care elementele (Nr. matricol, Nume, Rezultate şi Medie) au tipuri diferite ( întreg, sir de caractere, 1..10 sau (FB,B,S,NS) sau (Admis,Respins), real).

• Situaţii în care nu toate înregistrările conţin aceleaşi informaţiinu toate înregistrările conţin aceleaşi informaţii, o structură variabilăvariabilă (diferite câmpuri) în funcţie de anumite valori ale unor câmpuri fixe. O înregistrare are o parte fixăo parte fixă formată din mai multe câmpuri de diverse tipuri, urmată eventual de o parte variabilăo parte variabilă.

Nr.matricol

Numele şiprenumele

Rezultate (Note şi calificative) Mediagenerală

Algebră Analiză Geometrie

Informatică Sport

12292 Avram Valentin 10 8 9 F.B. Admis 9.00

12295 Barbulescu Ioan 9 7 9 B. Admis 8.33

. . . . . . . . . . . . . . . . . . . . . . . .

Declararea tipului inregistareinregistare constă într-o o parte fixă (în care se declară câmpurile împreună cu tipurile lor) şi eventual o parte variabilă (CaseCase ... , în care câmpurile diferă în funcţie valoarea unor câmpuri din partea fixă) astfel :

Record<listăCâmpuri> : <tipCâmp> { ; // P. Fixa<listăCâmpuri> : <tipCâmp> }

[ CaseCase [ <id> : ] <tipSel> Of // P. Var.

<const> : (<listăCâmpuri> : <tipCâmp> { ; <listăCâmpuri> : <tipCâmp> } ) { ;

<const> : (<listăCâmpuri> : <tipCâmp> { ;

<listă_câmpuri> : <tipCâmp> } ) } ] End;

Prin <listăCâmpuri> înţelegem o listă de identificatori de câmpuri, iar <tipCâmp> este tipul câmpurilor care pot fi chiar Record.

Referirea unui câmp al unei variabile de tip inregistrare se face astfel :

<varRecord> <varRecord> .. <idCâmp> <idCâmp>Ex. UnStudent.MediaGen, UnStudent.Rezultate.Informatică. Dacă la Informatică este NS sau S, în partea variabilă scris şi practic, iar

dacă valoarea este B sau FB atunci în partea variabilă nota finală obtinută.

Instructiunea Instructiunea WithWith : :

În cazul în care referim mai multe câmpuri din cadrul unei înregistrări se poate evita precizarea multiplă a aceleaşi înregistrări prin instrucţiunea With. Aceasta are următoarea sintaxă :

<insWith>::=With <varRecord> { , <idCâmp> } DoDo <instrucţiune> ,ceea ce permite omiterea scrierii în <instrucţiune> a selectorilor precizaţi o singură

dată (<varRecord> ,<idCâmp> ).

De exemplu, în loc de Writeln (UnStudent.Nume, UnStudent.MediaGen);

se poate scrie mai simplu : With UnStudent Do Writeln (Nume, MediaGen);

În cazul în care un câmp este de tip record, se poate omite şi acest selector din instrucţiune, dacă acesta a fost precizat ca <idCâmp> în instrucţiunea With. De exemplu, în loc de

Readln (UnStudent.Rezultate.Algebra, UnStudent.Rezultate.Analiza, ...)se poate scrie mai simplu :

With UnStudent, Rezultate Do Readln (Algebra, Analiza, ...) .

Ex.: Se citesc informaţiile fiecărui student, apoi se ordonează descrescător după medii, iar în final se listează studenţii în ordinea mediilor.

Program Inregistrari;Type Calificativ = (NS,S,B,FB);

Student = RecordRecordNrMatricol : Word;NumePrenume : String[20];Rezultate : RecordRecord

Algebra, Analiza, Geometrie : 1..10;Informatica : Calificativ;Sport : (Respins, Admis);CaseCase Inf : CalificativCalificativ Of

Ns : (Scris,Practic : Integer);S,B,FB : (Nota : Integer)

EndEnd;MediaGen : Real;

EndEnd;

Var Studenti : Array [1..25] Of Student; UnStudent : Student;i, n, k : Byte; Ordonati : (Da, Nu); Rasp : String[10];

Begin n:=0; {Citeste datele fiecarui student} With UnStudent, Rezultate Do Begin Repeat Write (' Nume student : '); Readln (NumePrenume); If Nume_Prenume<>'' Then Begin Write (' Numar matricol : '); Readln (NrMatricol); Write (' Algebra (1..10) : '); Readln (Algebra); Write (' Analiza (1..10) : '); Readln (Analiza); Write (' Geometrie (1..10) : '); Readln (Geometrie); Write (' Informatica (NS..FB) : '); Readln(Rasp); Case Rasp[1] Of 'N' : Informatica:=NS; 'S' : Informatica:=S; 'B' : Informatica:=B;'F' : Informatica:=FB End; If Informatica = Ns Then Begin Write (' Scris, Practic : ');

Readln ( Scris, Practic) End Else Begin Write (' Nota : '); Readln ( Nota) End;

Write (' Sport(Adm,Resp) : '); Readln(Rasp); Case Rasp[1] Of 'A' : Sport:=Admis; 'R' : Sport:=Respins End;

If (Informatica in [FB,B,S]) And (Sport = Admis) And (Algebra>4) And (Analiza>4) And (Geometrie>4) Then MediaGen:=(Algebra+Analiza+Geometrie+Nota)/4 Else MediaGen:=0; n:=n+1; Studenti[n]:=Un_Student End {If} Until Nume_Prenume='' End; {With} k:=0; { Ordoneaza descrescator dupa medii } Repeat Ordonati:=Da; k:=k+1; For i:=1 To n-k Do If Studenti[i].MediaGen < Studenti[i+1].MediaGen Then Begin

UnStudent:=Studenti[i]; Studenti[i]:=Studenti[i+1];Studenti[i+1]:=UnStudent; Ordonati:=Nu End

Until Ordonati=Da; { Tipareste studentii în ordinea rezultata } For i:=1 To n Do With Studenti[i] , Rezultate Do Begin Write (Nr_Matricol:7,Nume_Prenume:20, Algebra:3,Analiza:3,Geometrie:3); Case Informatica Of

NS : Write (' Nesatisfacator ',Scris:3,Practic:3); S : Write (' Satisfacator ',Nota:6); B : Write (' Bine ',Nota:6);

FB : Write (' Foarte Bine ',Nota:6) End; Case Sport Of Admis: Write (' Admis '); Respins: Write (' Respins ') End; Writeln (MediaGen:6:2) End;{With} ReadlnEnd.

Tema:Tema:

Propunem modificarea acestui program astfel încât să se poată

obţine lista studenţilor în ordinea descrescatoare a notelor la fiecare

disciplină fară a interschimba lista studenţilor introdusă de la

tastatură. Pentru aceasta se va construi de fiecare dată un vector de

ordine O (oi, i=1,...,n ) unde oi reprezintă numărul de ordine al

studentului (din lista iniţială) care se afla pe locul i în lista ordonată.

Aceasta înseamnă că iniţial şirul O va conţine valorile (1,...,n), apoi se

va schimba această ordine, dacă este cazul, (se interschimbă doar

elementele şirului O, deci oi oi+1) iar în final se vor tipări studenţii

în ordinea dorită, adică se va tipări St[oi], i=1,...,n.

Într-un bloc de dimensiuni Într-un bloc de dimensiuni mxnmxn locuiesc locuiesc mmxxnn familiifamilii. Se cunoaşte pentru fiecare familie . Se cunoaşte pentru fiecare familie ffijij data la data la

care s-a mutat în acest bloc, iar pentru fiecare care s-a mutat în acest bloc, iar pentru fiecare membru de familie numele şi data naşterii.membru de familie numele şi data naşterii. Se cere:Se cere:

a)a) Lista (tabelul) cu toţi locatarii în ordine Lista (tabelul) cu toţi locatarii în ordine descrescătoare a vechimii în bloc;descrescătoare a vechimii în bloc;b)b) Lista cu locatarii în ordinea zilei de naştere Lista cu locatarii în ordinea zilei de naştere (luna, zi). ((luna, zi). (Cine-i născut în ianuarie, cine-i Cine-i născut în ianuarie, cine-i născut în februarienăscut în februarie, …), …)c)c) O histogramă cu numărul de persoane pe O histogramă cu numărul de persoane pe fiecare etaj (ca în figura alăturată).fiecare etaj (ca în figura alăturată).

Obs.: Obs.: DataData ( (calendaristicăcalendaristică) este de forma ) este de forma ((zi,luna,anzi,luna,an) () ( Ex.:1.02.2006). Ex.:1.02.2006).

Tema:Tema:

Să se scrie un program Pascal care să rezolve problemele de tipul: Mutând un singur băţ de chibrit, faceţi ca egalitatea să fie adevărată!

Exemplu : Pentru 3+6=14obţinem 9+5=14

. . . C4 / 21.10.2008 . . . C4 / 21.10.2008

Tema:Tema: