elemente de bază ale unui algoritmarthur/cons/2016.consultatie...parametri •parametri formali...

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!