elemente de bază ale unui algoritmarthur/cons/2016.consultatie...parametri •parametri formali...
TRANSCRIPT
Subprograme Dr. Arthur Molnar
Consultații admitere, 30.01.2016
1
Ce vom face astăzi
Subprograme
2.1. Introducere
2.2. Parametri
2.3. Mecanisme de transfer prin intermediul parametrilor
2.4. Subprograme predefinite
Probleme
2.5. Problema 1 (subiect admitere informatică, 2011)
2.6. Problema 2 (subiect concursul mate-info, 2015)
2
Ce vom face astăzi
Subprograme
2.1. Introducere
2.2. Parametri
2.3. Mecanisme de transfer prin intermediul parametrilor
2.4. Subprograme predefinite
Probleme
2.5. Problema 1 (subiect admitere informatică, 2011)
2.6. Problema 2 (subiect concursul mate-info, 2015)
3
Subprograme
• De ce să folosim subprograme? • Descompunem o problemă complexă în mai multe
probleme (mai) simple
• Reducem cantitatea de cod necesară
• Reutilizăm codul existent în alte programe
• Împărțim scrierea unui program mai multor programatori
• Abstractizăm implementarea
• Programele devin mai ușor de urmărit
4
Subprograme
• Specificația • Descrie pe scurt ce face subprogramul
• Datele de intrare tipul și semnificația parametrilor
• Datele de ieșire ce returnează subprogramul (tipul și semnificația)
• Dacă vreau să returnez o structură de date mai complexă?
• Dacă ea nu este predefinită?
• Raportarea erorilor
• Prin valoarea parametrului returnat
• Folosind o variabilă de sistem
• Excepții?
5
Subprograme
• Tipuri de subprograme
• Subprograme predefinite
• sqrt(x)
• read(a)
• Subprograme create de utilizator
• function prim(n:integer) : boolean;
Var i:integer; ePrim:boolean;
Begin
…
End;
6
Ce vom face astăzi
Subprograme
2.1. Introducere
2.2. Parametri
2.3. Mecanisme de transfer prin intermediul parametrilor
2.4. Subprograme predefinite
Probleme
2.5. Problema 1 (subiect admitere informatică, 2011)
2.6. Problema 2 (subiect concursul mate-info, 2015)
7
Parametri
• Ce este un parametru?
• O variabilă în cadrul unui subprogram ce reprezintă date prezente în subprogramul apelant
• Ce este transmiterea parametrilor?
• Mecanismul prin care un subprogram poate trimite informații unui alt subprogram pe care acesta îl apelează
• Valoarea vs. Referință – O tensiune constantă între dorința pentru eficiență (transmiterea prin referință) și corectitudinea semantică (prin valoare)
8
Parametri
• Parametri formali
• sqrt(x)
• function prim(n:integer) : boolean;
Var i:integer; ePrim:boolean;
Begin
…
End;
• Parametri actuali
• sqrt(5)
• prim(16)
9
Parametri
• Parametri formali
• Utilizați la scrierea programului
• Au sens doar în reprezentarea statică a programului (codul sursă, codul compilat)
• Reprezentați prin variabile
• Ce este o variabilă? • O locație în memorie asociată cu un nume simbolic
(identificator) ce conține o valoare.
• Variabila este utilizată prin referirea la numele său
• Separarea între numele și valoarea variabilei permite folosirea sa în mod independent de informația stocată
10
Parametri
• Parametri actuali
• Iau locul parametrilor formali
• Au sens doar în momentul în care programul este rulat (în memorie)
• Compilatorul face verificări pentru ca valoarea actuală stocată în adresa de memorie să fie conformă cu tipul declarat.
11
Ce vom face astăzi
Subprograme
2.1. Introducere
2.2. Parametri
2.3. Mecanisme de transfer prin intermediul parametrilor
2.4. Subprograme predefinite
Probleme
2.5. Problema 1 (subiect admitere informatică, 2011)
2.6. Problema 2 (subiect concursul mate-info, 2015)
12
• parametri formali efectivi (actuali)
• poziția
• tipul
• parametri de tip
• valoare: sqrt(x) / sqrt(4)
• referință read(a) / scanf(“%d”,&a)
• read(4) / scanf(“%d”,&4))
13
Mecanisme de transfer al parametrilor
Mecanisme de transfer al parametrilor • Cum se realizează transferul parametrilor?
• Sursa: http://swinbrain.ict.swin.edu.au/wiki/Pass_by_Value_vs._Pass_by_Reference
• Prin valoare (copiere) • Parametrul formal are rolul unei variabile locale
• Toate modificările asupra acestuia • Sunt vizibile doar în cadrul subprogramului
• Invizibile în afară
• Parametrul actual poate include o expresie • P(z+2)
• Acest mecanism permite transmiterea într-o singură direcție • Apelator Apelat
14
Mecanisme de transfer al parametrilor • Cum se realizează transferul parametrilor?
• Sursa: http://swinbrain.ict.swin.edu.au/wiki/Pass_by_Value_vs._Pass_by_Reference
• Prin referință • La apelarea subprogramului se utilizează adresa actuală, din
memoria calculatorului
• Accesarea în subprogramul apelat al parametrului => accesarea locației de memorie din cadrul subprogramului apelant => posibila modificare în cadrul programului appellant
• Transmiterea unei expresii ca argument va genera eroare de compilare
• P(z+2)
15
Mecanisme de transfer al parametrilor • Cum se realizează transferul parametrilor?
• Sursa: http://swinbrain.ict.swin.edu.au/wiki/Pass_by_Value_vs._Pass_by_Reference
• Prin referință • La apelarea subprogramului se utilizează adresa actuală, din
memoria calculatorului
• Accesarea în subprogramul apelat al parametrului => accesarea locației de memorie din cadrul subprogramului apelant => posibila modificare în cadrul programului appellant
• Transmiterea unei expresii ca argument va genera eroare de compilare
• P(z+2) Eroare!
16
Mecanisme de transfer al parametrilor • Prin valoare
17
Pascal
C
Mecanisme de transfer al parametrilor • Prin referință
18
Pascal
C
Mecanisme de transfer al parametrilor
19
Ce vom face astăzi
Subprograme
2.1. Introducere
2.2. Parametri
2.3. Mecanisme de transfer prin intermediul parametrilor
2.4. Subprograme predefinite
Probleme
2.5. Problema 1 (subiect admitere informatică, 2011)
2.6. Problema 2 (subiect concursul mate-info, 2015)
20
Subprograme
• Exemple de subprograme predefinite
21
Pascal C
read(a);
write(a);
val(s,v,cod); str(n)
scanf(“%d”,&a);
printf(“%d”,a);
v=atoi(s);//atof(s)
Subprograme
• Exemple de subprograme matematice
22
Funcția Pascal C
|x| abs(x) abs(x)
r2 sqr(r) -
√𝑥 sqrt(x) sqrt(x)
𝑒𝑟 exp(r) exp(r)
[r] int(r); trunc(r); round(r) (int) r
{r} frac(r) f-(int)f
Subprograme
• Subprograme predefinite pentru fișiere text
23
Functia Pascal C
definire f : Text FILE* f;
asociere assign(f,nume) -
deschidere reset(f)/rewrite(f)/appe
nd(f)
fopen(f,”r/w/a”)
citire read(f,s) fscanf(f,”%s”,s);
scriere write(f,s); fprint(f,”%s”,s);
inchidere close(f); fclose(f)
Ce vom face astăzi
Subprograme
2.1. Introducere
2.2. Parametri
2.3. Mecanisme de transfer prin intermediul parametrilor
2.4. Subprograme predefinite
Probleme
2.5. Problema 1 (subiect admitere informatică, 2011)
2.6. Problema 2 (subiect concursul mate-info, 2015)
24
Se dă următoarea problemă…
25
Se citește un șir X de numere naturale pozitive, citirea
terminându-se la introducerea lui 0 (nu se include în șir).
Scrieți un program care construiește și afișează șirul Y ce
conține, în ordine descrescătoare, numerele palindroame
distincte din X. Șirul Y se construiește direct ordonat.
Exemple:
• X = (2,2442,2,13,131,1,313,44,677)
• Y = (2442,313,131,44,2,1)
• X = (21,24,623)
• Y = se tipărește ‘Șirul Y este vid‘
Sursa: Subiect admitere informatică, 2011
Pași pentru rezolvarea problemei
26
1. Citim cu atenție enunțul
2. Ce subprograme sunt necesare?
• Ce subprograme sunt deja implementate în
bibliotecile limbajului?
• De ce parametri au nevoie subprogramele?
• Cum vom transmite parametri?
• Ce returnează fiecare subprogram?
• Nu creați subprograme ce nu acceptă parametri sau
nu returnează un rezultat
3. Implementăm subprogramele
• Suntem atenți la cum pot fi ele combinate pentru a
rezolva cerința
De ce subprograme avem nevoie?
27
• Citirea unui șir de numere naturale
• Verificarea că s-a citit un număr natural
• Afișarea unui șir de numere naturale
• Verificarea faptului că un număr este
palindrom
• Verificarea faptului că un șir conține un
anumit număr
• Inserarea unui număr într-un șir ordonat
• Construirea șirului Y
De ce subprograme avem nevoie?
28
Citirea unui șir de numere naturale
• Subprogramul citește un șir de numere
naturale
• Parametri intrare: -
• Parametri ieșire: șirul de numere, număr de
elemente
Verificarea că s-a citit un număr natural
• Subprogramul verifică dacă un număr dat
este natural
• Parametri intrare: numărul n citit
• Parametri ieșire: n daca n∈ 𝑵, altfel − 𝟏
De ce subprograme avem nevoie?
29
Afișarea unui șir de numere naturale
• Subprogramul afișează pe ecran șirul de
numere naturale dat
• Parametri intrare: șirul de numere, număr de
elemente
• Parametri ieșire: -
Verificarea faptului că un număr este palindrom
• Subprogramul verifică dacă un număr dat
este palindrom
• Parametri intrare: numărul n
• Parametri ieșire: True (!0) dacă e palindrom,
False (0) altfel
De ce subprograme avem nevoie?
30
Verificarea faptului că un șir conține un anumit
număr
• Subprogramul verifică dacă un șir dat ca
parametru conține un număr dat
• Parametri intrare: șirul de numere, lungimea sa,
numărul căutat
• Parametri ieșire: True (!0) dacă șirul conține
numărul, False (0) altfel
Inserarea unui număr într-un șir ordonat
• Subprogramul inserează numărul dat în șirul
ordonat dat
• Parametri intrare: șirul de numere, lungimea sa,
numărul de inserat
• Parametri ieșire: -
De ce subprograme avem nevoie?
31
Construirea șirului Y
• Subprogramul construiește după cerințe șirul
Y și îl returnează
• Parametri intrare: șirul X, lungimea sa
• Parametri ieșire: șirul Y, lungimea sa
Codul sursă…
32
Variantă a problemei de mai sus
33
Se citește un șir X de numere naturale pozitive, citirea
terminându-se la introducerea lui 0 (nu se include în șir).
Scrieți un program care construiește și afișează șirul Y ce
conține, în ordine descrescătoare, numerele palindroame
distincte din X. Șirul Y se construiește direct ordonat.
Modificați implementarea astfel:
• Șirul X se citește dintr-un fișier text în care numerele
apar separate prin spațiu.
• Șirul Y se scrie într-un fișier text în care numerele vor
apare separate prin spațiu
Sursa: Subiect admitere informatică, 2011
De ce subprograme avem nevoie?
34
• Citirea unui șir din fișier
• Scriere unui sir in fișier
De ce subprograme avem nevoie?
35
• Citirea unui șir din fișier
• Parametri intrare: numele fișierului
• Parametri ieșire: șirul X, lungimea șirului
• Scriere unui sir in fișier
• Parametri intrare: șirul X, lungimea șirului,
numele fișierului
• Parametri ieșire: -
Codul sursă…
36
Ce vom face astăzi
Subprograme
2.1. Introducere
2.2. Parametri
2.3. Mecanisme de transfer prin intermediul parametrilor
2.4. Subprograme predefinite
Probleme
2.5. Problema 1 (subiect admitere informatică, 2011)
2.6. Problema 2 (subiect concursul mate-info, 2015)
37
Concursul mate-info, 2015
38
O matrice A(n,m) cu elemente întregi se numește
rară dacă majoritatea elementelor sale sunt egale
cu 0. O matrice rară A(n,m) având k elemente
nenule poate fi memorată folosind un șir X
conținând k triplete de forma (linie, coloană,
valoare) corespunzătoare valorilor nenule ale
matricei – fără a folosi un tablou bidimensional.
Elementele șirului X se memorează în ordine
lexicografică (crescătoare) după (linie, coloană).
Concursul mate-info, 2015
39
De exemplu, pentru n=m=3, matricea A
0 5 2
0 2 0
2 0 3
se va memora sub forma șirului
X=((1,2,5),(1,3,2),(2,2,2),(3,1,2),(3,3,3))
Concursul mate-info, 2015
40
Să se scrie un program care citește de la tastatură
valorile n,m și două matrice rare A(n,m) și B(n,m),
calculează sub forma unei matrice rare suma
C(n,m) a celor două matrice A și B și afișează sub
forma unui tablou bidimensional matricea C(n,m).
Citirea unei matrice se va face prin citirea
numărului n de linii, numărului m de coloane și
citirea repetată a unor triplete (linie, coloană,
valoare) – corespunzătoare valorilor nenule din
matrice, până la citirea tripletului (-1,-1,-1). În cazul
citirii mai multor triplete cu aceeași linie și coloană,
se ia în considerare doar primul triplet citit.
Concursul mate-info, 2015
41
Se vor scrie subprograme pentru:
a) Verificarea dacă perechea (i1,j1) este “mai
mică lexicografic” decât perechea (i2,j2).
b) Inserarea unui triplet în șirul X asociat unei
matrice rare A(n,m).
c) Determinarea elementului de pe linia i și
coloana j a unei matrice rare A(n,m)
reprezentate sub forma unui șir X.
d) Citirea unei matrice rare A(n,m) – cf. mai sus
e) Determinarea matricei sumă C(n,m)
f) Tipărirea unei matrice rare A(n,m) sub forma
unui tablou bidimensional.
De ce subprograme avem nevoie?
42
Verificarea ordinii lexicografice a două perechi
• Subprogramul determină ordinea
lexicografică a perechilor transmise
• Parametri intrare: perechile (i1,j1) și (i2,j2)
• Parametri ieșire:
1 dacă (i1,j1) <= (i2,j2)
0 dacă (i1,j1) > (i2,j2)
De ce subprograme avem nevoie?
43
Inserarea unui triplet în șirul care reprezintă
matricea
• Subprogramul inserează tripletul (linie,
coloană, valoare) pe poziția sa în șirul X
• Parametri intrare: șirul X, tripleta (linie, coloană,
valoare)
• Parametri ieșire: -
De ce subprograme avem nevoie?
44
Determinarea elementului de pe linia i și coloana j a
unei matrice rare A(n,m) reprezentate sub forma
unui șir X.
• Subprogramul determină elementul curent de
pe linia și coloana dată a matricii reprezentate
de șirul X
• Parametri intrare: șirul X, linia, coloana
• Parametri ieșire: valoarea elementului
De ce subprograme avem nevoie?
45
Citirea unei matrice rare A(n,m) sub forma unui șir
de triplete
• Subprogramul citește matricea
• Parametri intrare: șirul X care va stoca matricea
• Parametri ieșire: șirul X modificat
De ce subprograme avem nevoie?
46
Determinarea matricei sumă C(n,m)
• Subprogramul determină suma a două matrici
rare A și B date sub formă de șiruri de triplete
• Parametri intrare: șirurile A,B și C care reprezintă
matricile
• Parametri ieșire: matricea C care conține
matricea sumă
De ce subprograme avem nevoie?
47
Tipărirea unei matrice rare A(n,m) sub forma unui
tablou bidimensional.
• Subprogramul tipărește matricea A dată
• Parametri intrare: matricea A
• Parametri ieșire: -
Să vedem și codul sursă… Atenție! Codul din slide-urile următoare este indentat
pentru a fi vizibil în cadrul prezentării Când scrieți cod atât pe foaie, cât și pe calculator, folosiți un stil corect și consecvent
48
Reprezentarea datelor…
49
De ce subprograme avem nevoie?
50
Verificarea ordinii lexicografice a două perechi
• Subprogramul determină ordinea
lexicografică a perechilor transmise
• Parametri intrare: perechile (i1,j1) și (i2,j2)
• Parametri ieșire:
1 dacă (i1,j1) <= (i2,j2)
0 dacă (i1,j1) > (i2,j2)
51
De ce subprograme avem nevoie?
52
Inserarea unui triplet în șirul care reprezintă
matricea
• Subprogramul inserează tripletul (linie,
coloană, valoare) pe poziția sa în șirul X
• Parametri intrare: șirul X, tripleta (linie, coloană,
valoare)
• Parametri ieșire: -
53
De ce subprograme avem nevoie?
54
Determinarea elementului de pe linia i și coloana j a
unei matrice rare A(n,m) reprezentate sub forma
unui șir X.
• Subprogramul determină elementul curent de
pe linia și coloana dată a matricii reprezentate
de șirul X
• Parametri intrare: șirul X, linia, coloana
• Parametri ieșire: valoarea elementului
55
De ce subprograme avem nevoie?
56
Citirea unei matrice rare A(n,m) sub forma unui șir
de triplete
• Subprogramul citește matricea
• Parametri intrare: șirul X care va stoca matricea
• Parametri ieșire: șirul X modificat
57
De ce subprograme avem nevoie?
58
Determinarea matricei sumă C(n,m)
• Subprogramul determină suma a două matrici
rare A și B date sub formă de șiruri de triplete
• Parametri intrare: șirurile A,B și C care reprezintă
matricile
• Parametri ieșire: matricea C care conține
matricea sumă
59
De ce subprograme avem nevoie?
60
Tipărirea unei matrice rare A(n,m) sub forma unui
tablou bidimensional.
• Subprogramul tipărește matricea A dată
• Parametri intrare: matricea A
• Parametri ieșire: -
61
Problemă adițională
62
Se citeşte de la tastatură numărul natural n. Se cere să se
scrie un program care construieşte şi tipăreşte o matrice
pătratică de ordinul n cu următoarele proprietăţi:
a) Elementele de pe diagonala principală sunt nule.
b) Elementele de pe linia i aflate sub diagonala
principală au valoarea i, iar cele de deasupra diagonalei
principale au valoarea k, unde k este al i-lea număr prim.
De ce subprograme avem nevoie?
63
• Construirea unei matrici nxn
• Parametri intrare: n
• Parametri ieșire: matricea nxn inițializată
• Calcularea celui de-al k număr prim
• Parametri intrare: numărul k
• Parametri ieșire: al k-lea număr prim
• Completarea elementelor sub diagonala
principală
• Completarea elementelor deasupra
diagonalei principale
Concluzii
• Evitați folosirea variabilelor globale!
• Utilizați parametrii de intrare și ieșire în cadrul subprogramelor!
• Folosiți-vă de faptul că un subprogram poate returna un rezultat!
• Fiecare subprogram să facă un singul lucru, dar bine!
• Fiecare subprogram să contribuie la rezolvarea problemei!
• Problemele de la admitere sunt gândite în așa fel încât se pot descompune ușor în subprobleme subprograme!
64
Mulțumesc
65
Prezentarea o găsiți la: http://www.cs.ubbcluj.ro/~arthur/cons Mai multe informații privind concursul mate-info și admiterea http://www.cs.ubbcluj.ro/concursul-mate-info-ubb/
Succes!