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

65
Subprograme Dr. Arthur Molnar Consultații admitere, 30.01.2016 1

Upload: others

Post on 26-Dec-2019

16 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

Subprograme Dr. Arthur Molnar

Consultații admitere, 30.01.2016

1

Page 2: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 3: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 4: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 5: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 6: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 7: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 8: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 9: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

Parametri

• Parametri formali

• sqrt(x)

• function prim(n:integer) : boolean;

Var i:integer; ePrim:boolean;

Begin

End;

• Parametri actuali

• sqrt(5)

• prim(16)

9

Page 10: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 11: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 12: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 13: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

• 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

Page 14: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 15: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 16: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 17: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

Mecanisme de transfer al parametrilor • Prin valoare

17

Pascal

C

Page 18: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

Mecanisme de transfer al parametrilor • Prin referință

18

Pascal

C

Page 19: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

Mecanisme de transfer al parametrilor

19

Page 20: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 21: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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)

Page 22: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 23: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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)

Page 24: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 25: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 26: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 27: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică 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

Page 28: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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 − 𝟏

Page 29: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 30: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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: -

Page 31: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 32: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

Codul sursă…

32

Page 33: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 34: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

De ce subprograme avem nevoie?

34

• Citirea unui șir din fișier

• Scriere unui sir in fișier

Page 35: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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: -

Page 36: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

Codul sursă…

36

Page 37: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 38: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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ă).

Page 39: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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))

Page 40: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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.

Page 41: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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.

Page 42: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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)

Page 43: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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: -

Page 44: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 45: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 46: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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ă

Page 47: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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: -

Page 48: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 49: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

Reprezentarea datelor…

49

Page 50: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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)

Page 51: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

51

Page 52: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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: -

Page 53: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

53

Page 54: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 55: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

55

Page 56: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 57: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

57

Page 58: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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ă

Page 59: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

59

Page 60: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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: -

Page 61: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

61

Page 62: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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.

Page 63: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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

Page 64: Elemente de bază ale unui algoritmarthur/cons/2016.Consultatie...Parametri •Parametri formali •Utilizați la scrierea programului •Au sens doar în reprezentarea statică a

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