programare s˘i structuri de date - cs.ubbcluj.romarianzsu/postuniv/curs/curs01.pdf · pot exista...

PROGRAMARE SI STRUCTURI DE DATECURS 1

Lect. dr. Onet - Marian Zsuzsanna

Facultatea de Matematica si Informatica UBBın colaborare cu NTT Data

Lect. dr. Onet - Marian Zsuzsanna PROGRAMARE SI STRUCTURI DE DATE

Cuprins

Organizarea cursului

Introducere ın pseudocod

Tablouri (Array)

Vizibilitatea variabilelor

Subprograme


Date de contact

Adresa de e-mail: [email protected]

Daca aveti orice ıntrebari sau probleme legate de aceastadisciplina, nu ezitati sa ma contactati!

Pagina personala:www.ubbcluj.ro/˜marianzsu/PStructDate.html

Cursuri, seminarii, teme de laboratorAlte materiale

Consultatii:

De stabilit ...


Evaluare

Nota finala este alcatuita din 3 componente:

Examen scris (60%)Nota proiect (30%)Nota laborator (10%)

Pentru a promova, trebuie sa aveti minim nota 5 (fararotunjire) la:

Examen scrisProiectNota finala

Pentru activitatea de seminar veti primi puncte bonus, carevor fi adunate la nota finala (maximum 1 punct in total)


Obiectivele cursului

Introducere ın modul de calcul al complexitatii algoritmilor

Cunoasterea Tipurilor Abstracte de Date (TAD) Containere sia operatiilor specifice

Cunoasterea structurilor de date cu care putem implementaaceste containere, ımpreuna cu avantaje si dezavantaje


Introducere ın programare I

Pentru a rezolva o problema cu ajutorul calculatorului avemnevoie de un algoritm.

Un algoritm este o secventa de instructiuni folosita pentru arezolva o problema.

Pot exista mai multi algoritmi corecti pentru a rezolva oproblema.

Un program este implementarea unui algoritm ıntr-un limbajde programare.


Introducere ın programare II

Un algoritm este o secventa de instructiuni folosita pentru arezolva o problema.

Exista instructiuni specifice pentru calculatoare si trebuie saconstruim algoritmi folosind aceste instructiuni


Pseudocod

Pseudocodul este un limbaj de descriere al algoritmilor,destinat cititorului uman, nu calculatorului

Avantajele pseudocodului:

Este mai informal decat un limbaj de programareEste mai usor de ınteles, pentru ca nu contine elementespecifice unei limbaj de programareUn algoritm descris ın pseudocod poate fi transcris usor ıntr-unlimbaj de programare

Dezavantajul presudocodului:

Pseudocodul nu poate fi executat


Un algoritm

Un algoritm este o secventa de instructiuni folosita pentru arezolva o problema

In general un algoritm are date de intrare - date/informatiicare sunt cunoscute cand executia algoritmului ıncepe

In general un algorithm are date de iesire - date carereprezinta rezultatul algoritmului

Transformarea datelor de intrare ın date de iesire se faceprintr-o secventa de instructiuni specifice calculatoarelor.


Variabile I

Ce este o variabila?

Variabilele sunt folosite pentru a stoca datele de intrare,datele de iesire si valori intermediare necesare pentru a rezolvaproblema.

O variabila are un numeAcest nume este folosit pentru a se referi la variabilarespectiva.Nu putem avea 2 variabile cu aceeasi nume ıntr-un algoritm.Numele trebuie sa fie ales ın asa fel ıncat sa sugereze pentru cevom folosi variabila.


Variabile II

O variabila are o semnificatieFiecare variabila reprezinta date sau informatii din algoritmulnostru.Este important ca sa nu folosim aceeasi variabila sa reprezintedate cu semnificatii diferite.

O variabila are un tip (un domeniu)

Tipul variabilei arata ce valori pot fi stocate ın aceastavariabila si ce operatii pot fi efectuate folosind variabila.Exista tipuri predefinite ın fiecare limbaj de programare, dar ıngeneral pot fi definite si tipuri noi.


Variabile III

O variabila are o valoareAceasta valoare trebuie sa corespunda tipului/domeniuluivariabilei.Daca o variabila nu are valoare, se spune ca este neinitializata.Valoarea unei variabile poate fi modificata pe parcursulexecutiei algoritmului.

O variabila are o adresa de memorieEste zona de memorie unde calculatorul stocheaza valoareavariabilei.In anumite limbaje de programare avem acces la adresa uneivariabile, ın altele nu.


Constante

Constantele sunt similare cu variabile, cu diferenta ca nuputem modifica valoarea unei constante.

Sunt folosite pentru a stoca valori care nu se modifica (sau semodifica foarte rar), de ex. valoarea lui PI, cate zile suntıntr-o saptamana, rata TVA-ului, etc.

Avantajele folosirii constantelor:

Codul e mai lizibil, mai usor de ıntelesDaca totusi trebuie schimbata valoarea, schimbarea se faceıntr-un singur loc


Tipuri de date si operatii I

Majoritatea limbajelor de programare au anumite tipuri dedate predefinite ımpreuna cu operatii care pot fi efectuate pevalorile tipului.

Ce tipuri de date cunoasteti?

In pseudocod presupunem ca avem urmatoarele tipuri de date:

IntregRealBooleanCaracterString (sir de caractere)

In multe limbaje de programare, programatorul poate sadefineasca alte tipuri de date prin combinarea tipurilorexistente (de ex. tip numar rational, definit prin 2 numereıntregi)


Tipuri de date si operatii II

Tipul Intreg

Reprezinta valori ıntregi (pozitive si negative), de ex. 0, 1,10,512, -6124, ...

Operatii posibile:

adunare (+), scadere (-), ınmultire (*)ımpartire ıntreaga (/) (de ex. 13 / 5 = 2)comparatii: =, !=, <, >, <=, >=mod (sau %): restul ımpartirii (de ex. 13 mod 5 = 3)


Tipuri de date si operatii III

Tipul Real

Reprezinta valori reale (pozitive si negative), de ex. 0.4, -0.21,5.0, 0.00154, -65.02, ...

Operatii posibile:

adunare (+), scadere (-), ınmultire (*)ımpartire (/) (de ex. 13.0 / 5.0 = 2.6)comparatii: =, !=, <, >, <=, >=


Tipuri de date si operatii IV

Tipul Boolean

Variabile de tip Boolean pot avea doar 2 valori posibile:Adevarat sau Fals

In anumite limbaje de programare valoarea 0 se considera Falssi orice valoare diferita de 0 se considera Adevarat

Operatii posibile:

- negatie - NOT:

a not aAdevarat Fals

Fals Adevarat

De exemplu: Pentru a intra ın examen trebuia sa nuaveti mai mult de 2 absente.


Tipuri de date si operatii V

conjunctie - SI:

a b a si bAdevarat Adevarat Adevarat

Adevarat Fals Fals

Fals Adevarat Fals

Fals Fals Fals

De exemplu: Pentru a promova aceasta disciplina trebuie saaveti minim nota 5 la proiect si saaveti minim nota 5 la examenul scris.


Tipuri de date si operatii VI

disjunctie - SAU:

a b a sau bAdevarat Adevarat Adevarat

Adevarat Fals Adevarat

Fals Adevarat Adevarat

Fals Fals Fals

De exemplu: O persoana se poate pensiona dacaare 60 de ani sau a lucrat 40 de ani.


Tipuri de date si operatii VII

disjunctie exclusiva - XOR:

a b a xor bAdevarat Adevarat Fals

Adevarat Fals Adevarat

Fals Adevarat Adevarat

Fals Fals Fals

In limba romana nu exista cuvant separat pentru disjunctieexclusiva, tot sau este folosit.


Tipuri de date si operatii VIII

Tipul Caractere

Reprezinta un singur caracter, care poate fi o cifra, o litera(mica sau mare), un semn special (%, *, etc.) .

In general fiecare caracter are un numar ıntreg asociat si esteretinut ın memorie sub forma acestui numar


Tipuri de date si operatii IX


Tipuri de date si operatii X

Operatii posibile:

Comparatie a 2 caractereAdunarea unui numar la un caracter: ‘A’ + 7 = ‘H’ (65 + 7 =72) sau ‘A’ + 35 = ‘d’ (65 + 35 = 100)Scaderea unui numar dintr-un caracter: ‘a’ - 32 = ‘A’(97 - 32= 65) sau ‘7’ - 4 = ‘3’ (55 - 4 = 51)Verificarea daca un caracter c este o cifra: ‘0’ ≤ c ≤ ‘9’Verificarea daca un caracter c este litera mica: ‘a’ ≤ c ≤ ‘z’Transformarea unui caracter c care reprezinta o cifra ın cifrarespectiva: c - ‘0’Transformarea unui caracter c care reprezinta o litera mica ınnumarul de ordine a literei: c - ‘a’ (va returna 0 pentru ‘a’, 1pentru ‘b’, 2 pentru ‘c’, etc.)


Tipuri de date si operatii XI

Tipul String (sir de caractere)

Reprezinta o secventa de caractere folosita pentru a retinedate de tip text. De exemplu: “Rezultatul”, “abc”,“Ianuarie”, etc.

Operatii posibile:

Determinarea numarului de caractere (lungimea sirului)Accesarea caracterului de pe o pozitie, accesarea substringuluidintre 2 pozitiiConcatenarea a 2 stringuriComparatie de stringuri (folosind ordinea alfabetica)etc.


Tipuri de date si operatii XII

In pseudocod pentru a defini o variabila de un anumit tip vomfolosi notatia: nume variabila: tip

De exemplu:

nume: string

varsta: ıntreg

greutate: real

initiala parinte: caracter

permis: boolean //presupunem ca verificam daca are permisde conducere sau nu

Cand vrem sa definim mai multe variabile de un anumit tip,vom scrie:

nume, prenume, oras: string


Afisare si citire

Sunt metode prin care utilizatorul poate sa comunice cuprogramul

Prin citire introducem datele cu care vrem sa lucrezeprogramul. Operatia de citire necesita furnizarea variabilei ıncare vrem sa fie stocata valoarea citita.

Prin afisare putem vedea rezultatele programului pe ecran.Operatia de afisare necesita furnizarea valorii de afisat, subforma de variabila sau sub forma de valoare.

In pseudocod pentru citire folosim instructiunea citestenume variabila iar pentru afisare folosim scrienume variabila sau scrie valoare.


Hello World

algoritm HelloWorld estescrie “Hello World”

sf algoritm


Sa rescriem algoritmul, astfel ıncat sa salutam utilizatorul.

algoritm HelloUtilizator estenume: stringscrie “Cum te numesti?”citeste numescrie “Hello ” + nume

// semnul + reprezinta concatenare de stringurisf algoritm

// marcheaza ınceputul unui comentariu

Comentariile sunt texte care sunt ignorate de calculator candcodul este compilat sau rulat, dar sunt importante pentruprogramatori: ajuta la ıntelegerea codului.

Folosirea comentariilor este importanta!

E bine ca ınainte de o instructiune de citire sa afisam unmesaj care sa sugereze ce vrem sa citim.


algoritm HelloUtilizator estenume: stringscrie “Cum te numesti?”citeste numescrie “Hello ” + nume

// semnul + reprezinta concatenare de stringurisf algoritm

// marcheaza ınceputul unui comentariu

Comentariile sunt texte care sunt ignorate de calculator candcodul este compilat sau rulat, dar sunt importante pentruprogramatori: ajuta la ıntelegerea codului.

Folosirea comentariilor este importanta!

E bine ca ınainte de o instructiune de citire sa afisam unmesaj care sa sugereze ce vrem sa citim.


Atribuire I

Se foloseste pentru a seta valoarea unei variabile la o anumitavaloare.

In momentul ın care se declara o variabila este bine ca aceastasa fie initializata (adica sa primeasca o valoare).

In pseudocod folosim notatia variabila = valoare. Deexemplu:

nume = “Maria”

lungime = 10

PI = 3.1415

suma = 10+3


Atribuire II

Valoarea atribuita poate sa fie rezultatul unei expresii si poatesa depinda de valoarea altor variabile. De ex (presupunem can, a si b sunt variabile existente):

nume = “Maria” + “ Alina”

lungime = 2 * n

suma = a + b

Prima data se evalueaza partea dreapta a expresiei, iarrezultatul evaluarii este atribuit variabilei din partea stanga.De aceea, putem scrie expresii de genul: v = v + 1

Prima data se evalueaza v + 1, dupa care rezultatul i seatribuie lui v.


Atribuire III

Pentru a verifica daca valoarea unei variabile este egala cu oanumita valoare, se foloseste notatia variabila == valoare.De exemplu:

nume == “Maria”lungime == 10suma == 13a == suma (presupunem ca exista variabila suma)

Pentru a verifica daca valoarea unei varibile este diferita de oanumita valoare, se foloseste notatia variabila != valoare.De exemplu:

nume != “Maria”suma != 13suma != a (presupunem ca exista variabila a)


Arie si perimetru dreptunghi

Sa se calculeze aria si perimetrul unui dreptunghi cu laturi a sib.

Formula pentru a calcula aria unui dreptunghi cu laturi a si beste: a ∗ bFormula pentru a calcula perimetrul unui dreptunghi cu laturia si b este: 2 ∗ (a + b)


algoritm AriePerimetruDreptunghi estea, b, arie, perimetru: realscrie “Cat este lungimea dreptunghiului?”citeste ascrie “Cat este latimea dreptunghiului?”citeste barie = a * bperimetru = 2 * (a + b)scrie “Aria este: ” + arie + ” perimetrul este: ” + perimetru

sf algoritm


Instructiuni conditionale

Sa se considere urmatoarea problema: Sa se citeasca de latastatura un numar pozitiv si sa se afiseze un mesaj din caresa reiasa daca numarul este par sau impar.

Cum verificam daca un numar este par sau nu?

Pentru a verifica daca un numar este par sau impar se verificarestul ımpartirii la 2 (operatia mod). Daca restul este 0,numarul este par, daca restul este 1, numarul este impar.


Instructiuni conditionale II

De foarte multe ori avem de efectuat operatii diferite ınfunctie de anumite conditii. In aceste situatii folosiminstructiunea conditionala:

daca conditie atunciinstructiune

altfelinstructiune

sf daca

La partea instructiune se poate scrie o singura instructiune,sau mai multe instructiuni.


Instructiuni conditionale III

Partea altfel poate sa lipseasca, daca nu avem nimic deexecutat pe ramura respectiva:

daca conditie atunciinstructiune

sf daca

Pe partea altfel putem adauga ınca o conditie:

daca conditie1 atunciinstructiune

altfel daca conditie2 atunciinstructiune

altfelinstructiune

sf daca


Numar par sau impar

algoritm ParImpar estenumar, rest: ıntregscrie “Introduceti numarul:”citeste numarrest = numar mod 2daca rest == 0 atunci

scrie “Numarul este par”altfel

scrie “Numarul este impar”sf daca

sf algoritm


An bisect

Sa consideram urmatoarea problema: Sa se citeasca de latastatura un an si sa se afiseze cate zile a avut anul respectiv.

Numarul de zile ıntr-un an este 366 daca anul e bisect si 365daca anul nu e bisect.

Cand este un an bisect?

Un an este bisect daca este divizibil cu 4 si nu este divizibil cu100, sau daca este divizibil cu 400. De exemplu: 2000, 2004,2016, 2104, etc. sunt ani bisecti, dar 2001, 2002, 1900, 2100,2200, etc. nu sunt.


An bisect II

algoritm AnBisect estean, rez: ıntregscrie “Introduceti anul:”citeste anrez = 365 //presupunem ca nu e an bisectdaca an mod 400 == 0 SAU (an mod 4 == 0 SI an mod 100 !=0) atunci

rez = 366sf dacascrie “Numarul de zile este “ + rez

sf algoritm


Instructiuni repetitive

Sa consideram urmatoarea problema: Sa se citeasca de latastatura 10 numere si sa se calculeze suma si media lor. Deexemplu, daca numerele citite sunt 7, 13, 62, 61, -32, 9, 85,1, 56, 42, suma lor este 304, iar media lor este 30.4.

Desi stim sigur ca este nevoie de 10 numere, a lua 10 variabilesi a scrie instructiunea de citire de 10 ori nu pare o solutiefoarte buna.

Cand avem de repetat aceleasi instructiuni de mai multe ori,vom folosi instructiuni repetitive: ciclu pentru sau ciclucattimp


Instructiunea pentru I

Se foloseste cand stim de cate ori trebuie sa repetam anumiteinstructiuni

ın pseudocod instructiunea pentru arata ın modul urmator:

pentru variabila = val inceput, conditie, pas executainstructiune

sf pentru

variabila se numeste variabila de ciclu. In momentul ın careıncepe executia ciclului, variabila primeste valoareaval inceput.


Instructiunea pentru II

La fiecare iteratie, se verifica daca conditia este adevarata.Daca da, se opreste ciclul. Daca nu, se executa intructiuniledin interiorul ciclului, iar valoarea lui variabila se modifica cuvaloarea pasului (practic variabila = variabila + pas).

De multe ori conditia contine o comparatie a variabilei cu ovaloare limita (de exemplu, variabila < 10).

Daca conditia este falsa de la ınceput, ciclul nu se executadeloc.


Suma si medie

algoritm SumaSiMedie estesuma, contor, numar: ıntregmedie: realsuma = 0 // initializam sumamedie = 0.0 // si mediapentru contor = 1, contor ≤ 10, 1 executa

scrie “Dati un numar: “citeste numarsuma = suma + numar

sf pentrumedie = suma / 10.0scrie “Suma este: “ + sumascrie “Media este: “ + medie

sf algoritm


Suma si medie II

Ce se ıntampla daca nu 10 numere trebuie citite ci n? (Unden este o valoare care trebuie citita la ınceputul algoritmului)


algoritm SumaSiMedie2 estesuma, contor, numar, cate: ıntregmedie: realsuma = 0 // initializam sumamedie = 0.0 // si mediascrie “Numarul de numere care vor fi citite: “citeste catepentru contor = 1, contor ≤ cate, 1 executa


sf pentrumedie = suma / (cate * 1.0) //fortez ımpartirea cu numar realscrie “Suma este: “ + sumascrie “Media este: “ + medie

sf algoritm


Suma si medie II

Este corect codul nostru? Vom avea solutia corecta de fiecaredata? Pentru fiecare valoare a lui n?

Avem probleme daca utilizatorul introduce valoarea 0 pentrun. Impartirea la 0 este o operatie care cauzeaza eroare. Deaceea, ınainte de a face o ımpartire, trebuie sa verificam sa nuımpartim la 0.

Daca n este 0, atunci nu facem ımpartirea, si medie ramane 0.


Suma si medie II

algoritm SumaSiMedie2 estesuma, contor, numar, cate: ıntregmedie: realsuma = 0 // initializam sumamedie = 0.0 // si mediascrie “Numarul de numere care vor fi citite: “citeste catepentru contor = 1, contor ≤ cate, 1 executa


sf pentrudaca cate != 0 atunci

medie = suma / (cate * 1.0) //fortez ımpartirea cu numar realsf dacascrie “Suma este: “ + sumascrie “Media este: “ + medie

sf algoritm


Instructiunea cattimp I

Ce se ıntampla daca nu se stie de la ınceput numarul denumere de adunat, ci se stie ca trebuie sa citim numere panacand utilizatorul introduce numarul 0?

Daca nu stim de cate ori trebuie sa repetam instructiunile, nuputem folosi ciclu pentru.

In situatiile ın care anumite instructiuni trebuie repetate panacand o conditie devine adevarata (sau falsa), se foloseste ciclulcattimp.


Instructiunea cattimp II

cattimp conditie executainstructiune

sf cattimp

La intrare ın ciclul cattimp se verifica conditia. Daca esteadevarata, se executa instructiunile din ciclu. Dupa aceea, sereverifica conditia. Daca este adevarata, se executa din nouinstructiunile din ciclu. Dupa care iar se verifica conditia si asamai departe.

In momentul ın care conditia este falsa, nu se mai executainstructiunile din ciclu, executia continua cu instructiuniledupa sf cattimp.


Instructiunea cattimp III

Daca conditia este falsa de la ınceput, instructiunile din ciclulcattimp nu se executa deloc.

Instructiunea (sau instructiunile) din ciclul cattimp trebuie sacontina elemente care sa modifice conditia, altfel, dacaconditia nu devine falsa niciodata, vom avea un ciclu infinit!


Suma si medie III

algoritm SumaSiMedie3 estesuma, contor, numar, cate: ıntregmedie: realsuma = 0 // initializam sumamedie = 0.0 // si mediacate = 0 //trebuie sa numar cate numere sunt citite, pentru a calcula mediascrie “Dati un numar: “citeste numarcattimp numar != 0 executa

suma = suma + numarcate = cate + 1 //incrementez numarul de numere cititescrie “Dati un numar: “ //citesc o noua valoare pentru numarciteste numar

sf cattimp//continuare pe pagina urmatoare...


daca cate != 0 atuncimedie = suma / (cate * 1.0)

sf dacascrie “Suma este: “ + sumascrie “Media este: “ + medie

sf algoritm


Suma si medie III

Bucata de cod care afiseaza mesajul “’Dati un numar” si careciteste numarul apare de 2 ori ın codul nostru. Daca vrem sanu scriem de 2 ori aceste instructiuni, putem face citire doar ınciclul cattimp. In acest caz citirea se face la ınceputul ciclului(ınainte de adaugare). Trebuie sa fim atenti sa initializamvariabila numar ın asa fel ıncat executia sa intre ın cattimp.


Suma si medie III

Exemplu 10 - SumaSiMedie3

algoritm SumaSiMedie3 estesuma, contor, numar, cate: ıntregmedie: realsuma = 0 // initializam sumamedie = 0.0 // si medianumar = 1 //putem initializa variabila cu orice numar diferit de 0cate = 0 //trebuie sa numar cate numere sunt citite, pentru a calcula mediacattimp numar != 0 executa

scrie “Dati un numar: “ //citesc o noua valoare pentru numarciteste numarsuma = suma + numarcate = cate + 1 //incrementez numarul de numere citite

sf cattimpdaca cate != 0 atunci

medie = suma / (cate * 1.0)sf dacascrie “Suma este: “ + sumascrie “Media este: “ + medie

sf algoritm


Suma si medie III

Cat va fi rezultatul daca introducem pe rand numerele 10, 51,3, 0?

In loc sa avem rezultatul 64 si 21.333, rezultatul afisat va fi64 si 16. Motivul este faptul ca momentan si valoarea 0 estenumarata de variabila cate, si ımpartirea se face la 4, nu la 3.

Exista doua solutii:

sa initializam variabila cate cu -1 astfel, la final va avea exactvaloarea care ne trebuiesa facem ımpartirea la cate - 1, si sa verificam daca cate arevaloarea 1, nu 0.


Suma si medie III

Solutia 1

algoritm SumaSiMedie3 estesuma, contor, numar, cate: ıntregmedie: realsuma = 0 // initializam sumamedie = 0.0 // si medianumar = 1 //putem initializa variabila cu orice numar diferit de 0cate = -1 //trebuie sa numar cate numere sunt citite, pentru a calcula//media. Initializam cu -1, pentru a avea la final valoarea bunacattimp numar != 0 executa



medie = suma / (cate * 1.0)sf daca//continuare pe pagina urmatoare...


scrie “Suma este: “ + sumascrie “Media este: “ + medie

sf algoritm


Suma si medie III

Solutia 2

algoritm SumaSiMedie3 estesuma, contor, numar, cate: ıntregmedie: realsuma = 0 // initializam sumamedie = 0.0 // si medianumar = 1 //putem initializa variabila cu orice numar diferit de 0cate = 0 //trebuie sa numar cate numere sunt citite, pentru a calcula mediacattimp numar != 0 executa



medie = suma / (cate * 1.0 - 1)sf dacascrie “Suma este: “ + sumascrie “Media este: “ + medie

sf algoritm


Cicluri pentru si cattimp I

Orice ciclu pentru poate fi rescris ca un ciclu cattimp:

initializam o variabila cu valoarea val ınceput ınainte de ciclulcattimpconditia din ciclul cattimp va verifica daca valoarea variabilei emai mica (mai mare) decat val final

ın interiorul ciclului cattimp modificam valoarea variabilei cuvaloarea pasului

Deci, putem scrie solutia pentru SumaSiMedie2 - cand stiamca vom lucra cu n numere - folosind ciclul cattimp


Cicluri pentru si cattimp II

algoritm SumaSiMedie2 estesuma, contor, numar, cate: ıntregmedie: realsuma = 0 // initializam sumamedie = 0.0 // si mediascrie “Numarul de numere care vor fi citite: “citeste catecontor = 1cattimp contor ≤ cate executa

scrie “Dati un numar: “citeste numarsuma = suma + numarcontor = contor + 1


medie = suma / (cate * 1.0)sf dacascrie “Suma este: “ + sumascrie “Media este: “ + medie

sf algoritm


Array I

Sa consideram problema urmatoare: Se citesc n numerepozitive de la tastatura. Sa se determine cate dintre numerelecitite sunt strict mai mici decat media numerelor.

De exemplu daca citim urmatoarele 9 numere: 102, 58, 21,634, 299, 11, 648, 24, 77, suma lor este 1874, media lor este208.22, si sunt 6 numere care sunt mai mici decat media (102,58, 21, 11, 24, 77).


Array II

Stim deja cum se calculeaza media a n numere. Diferenta fatade problemele anterioare este ca aici prima data trebuie sacalculam media, si abia dupa ce stim media putem verificanumerele. Dar pentru acest lucru trebuie sa retinem toatenumerele undeva.

Cand trebuie sa retinem mai multe elemente de acelasi tip,trebuie sa folosim un array.


Array III

Un array este o colectie de elemente de acelasi tip, care ocupaun spatiu continuu de memorie.

Array-ul se mai numeste sir, vector, tablou.

Pentru a defini un array trebuie sa specificam ce tip vor aveaelementele din array si cate elemente vrem sa existe ın array.


Array IV

In pseudocod un array se defineste folosind notatia:

nume variabila: tip[]saunume variabila: tip[N]de exemplu:elemente: ıntreg[]luni: ıntreg[12]

In exemple si explicatii, vom reprezenta array-ul folosindparanteze drepte si enumerand elementele. De exemplu: [102,58, 21, 634, 299, 11, 648, 24, 77].


Array V

Accesarea elementelor dintr-un array se face pe baza pozitiilor.Primul element se gaseste pe pozitia 0, al doilea element pepozitia 1, etc.

Ultimul element ıntr-un array cu n elemente se gaseste pepozitia n-1.

Elementul de pe o pozitie se acceseaza folosind parantezedrepte


Array VI

scrie “primul element” + elemente[0]scrie “al doilea element” + elemente[1]scrie “al i-lea element” + elemente[i-1]elemente[3] = 99elemente[i] = elemente[i-1] + 1

Inainte de a accesa un element de pe o pozitie, trebuie sa neasiguram ca pozitia este valida!


Mai mic ca medie

algoritm NumereMaiMiciCaMedie estesuma, nr, contor: ıntregsuma = 0scrie “Numarul de numere:”citeste nrelemente: ıntreg[nr] //aici vom retine numerelepentru contor = 0, contor < nr, 1 executa

scrie “Dati un numar:”citeste elemente[contor]suma = suma + elemente[contor]

sf pentrumedie: realmedie = 0daca nr != 0 atunci

medie = suma / (nr * 1.0)sf daca//continuare pe pagina urmatoare


rezultat: ıntregrezultat = 0//parcurgem din nou array-ul pentru a vedea care numere sunt mai mici// decat mediapentru contor = 0, contor < nr, 1 executa

daca elemente[contor] < medie atuncirezultat = rezultat + 1

sf dacasf pentruscrie “Sunt “ + rezultat + “ numere mai mici ca media”

sf algoritm


String - un sir de caractere I

Orice string poate fi considerat un array cu elemente de tipcaracter (o singura litera).

De exemplu, stringul “Maria”, poate fi considerat un array cu5 elemente: [‘M’, ‘a’, ‘r’, ‘i’, ‘a’].

Pentru a accesa un caracter de pe o pozitie dintr-un string,folosim paranteze drepte (cum facem la array).

Pentru a accesa lungimea stringului (adica numarul decaractere din array), presupunem ca avem functia lungime.


String - un sir de caractere II

nume = “Maria” //o variabila de tip string, cu valoarea Marianume[0] este ‘M’nume[1] este ‘a’...lungime(nume) este 5nume[lungime(nume)-1] este ‘a’ //ultima litera din stringnume[lungime(nume)] nu este o expresie valida - nu existacaracter pe pozitia respectiva


String - un sir de caractere III

Sa consideram urmatoarea problema: CamelCase este otehnica de a scrie cuvinte compuse sau fraze fara a folosispatiu, scriind toate cuvintele ımpreuna, dar ıncepand fiecarecuvant nou cu litera mare. CamelCase este folosit des deprogramatori, pentru a da nume de variabile, nume de functii,etc. Un exemplu este chiar numele algoritmului scris maiınainte: NumereMaiMiciCaMedie. Citind de la tastatura uncuvant scris cu CamelCase, sa determinam din cate cuvinteeste alcatuit. Presupunem ca prima litera este mica, deciprimul cuvant ıncepe cu litera mica.


String - un sir de caractere IV

De exemplu:

numeVariabila contine 2 cuvinte

variabila contine 1 cuvant

numeLungSiComplicat contine 4 cuvinte

numeSiMaiLungSiMaiComplicat contine 7 cuvinte

Cum putem rezolva problema?


String - un sir de caractere V

Din moment ce stim ca fiecare cuvant ıncepe cu o litera mare,si ca ın fiecare cuvant doar prima litera e mare, trebuie sanumaram cate litere mari sunt ın cuvant. Dar sa nu uitam caprimul cuvant ıncepe cu litera mica, deci rezultatul este cu 1mai mult decat numarul de litere mari.

Pentru a verifica daca o litera este mare, pur si simplu ılcomparam cu prima si cu ultima litera mare din alfabet (‘A’ si‘Z’). Daca este ıntre aceste 2 litere, atunci e litera mare.


algoritm CamelCase estecuvant: stringnrCuvinte, poz: ıntregscrie “Dati stringul:”citeste cuvantnrCuvinte = 1 //sigur contine macar un cuvantpentru poz = 0, poz < lungime(cuvant), 1 executa

daca cuvant[poz] >= ‘A’ SI cuvant[poz] <= ‘Z’ atuncinrCuvinte = nrCuvinte + 1

sf dacasf pentruscrie “Numarul de cuvinte: “ + nrCuvinte

sf algoritm


Tema de gandire: Cum ar trebui modificat codul, daca nu stiudaca primul cuvant va ıncepe cu litera mica sau mare?Variabila cuvant poate fi de exemplu NumeVariabila saunumeVariabila, ın ambele cazuri rezultatul fiind 2.


Arrayuri multidimensionale I

Arrayurile de care am vorbit pana acum erau unidimensionale,dar exista si arrayuri bidimensionale, tridimensionale, etc.

Un array bidimensional, numit si matrice, contine 2dimensiuni: linii si coloane

jocul Sudokutabla de sahetc.

Pentru a defini un array bidimensional este necesar saspecificam numarul de elemente pentru ambele dimensiuni(numarul de linii si numarul de coloane).


Arrayuri multidimensionale II

De exemplu, ın pseudocod un array bidimensional se definesteın modul urmator:

matrice: ıntreg[N][N]harta:ıntreg[10][30]elemente: ıntreg[N][M]

Un array bidimensional cu N linii si M coloane are ın total N *M elemente.


Arrayuri multidimensionale III

Pentru accesarea unui element dintr-un array bidimensional vatrebui sa specificam 2 valori: linia si coloana unde se gasesteelementul. De exemplu:

Daca matrice are N linii si M coloane:matrice[0][0] este primul element din prima liniematrice[0][M-1] este ultimul element din prima liniematrice[5][9] este a 10-lea element din linia 6 (presupunem caexista elementul)matrice[N-1][0] este primul element din ultima liniematrice[N-1][M-1] este ultimul element din ultima linie


Arrayuri multidimensionale IV

Sa consideram problema urmatoare: Sa se citeasca de latastatura o matrice cu N linii si M coloane. Sa se calculezesuma numerelor de pe linii pare si suma numerelor de pecoloane impare.

Pentru a lucra cu arrayuri bidimensionale, ın general, vomavea nevoie de 2 cicluri pentru, unul pentru indexul liniilor siunul pentru indexul coloanelor.


Arrayuri multidimensionale V

De exemplu:

0 1 2 3 4 5 6 7

0 1 6 11 43 2 -5 17 21

1 -9 18 3 62 95 22 37 1

2 5 30 51 24 68 91 16 43

3 21 33 8 57 5 41 24 35

4 28 81 31 63 6 68 59 11

5 5 77 59 69 7 82 47 48

6 20 4 44 14 8 43 2 60


Arrayuri multidimensionale VI

Numere pe linii pare:

0 1 2 3 4 5 6 7

0 1 6 11 43 2 -5 17 21

1 -9 18 3 62 95 22 37 1

2 5 30 51 24 68 91 16 43

3 21 33 8 57 5 41 24 35

4 28 81 31 63 6 68 59 11

5 5 77 59 69 7 82 47 48

6 20 4 44 14 8 43 2 60


Arrayuri multidimensionale VII

Numere pe coloane impare:

0 1 2 3 4 5 6 7

0 1 6 11 43 2 -5 17 21

1 -9 18 3 62 95 22 37 1

2 5 30 51 24 68 91 16 43

3 21 33 8 57 5 41 24 35

4 28 81 31 63 6 68 59 11

5 5 77 59 69 7 82 47 48

6 20 4 44 14 8 43 2 60


SumaLiniiColoane

algoritm SumaLiniiColoane esten, m, i, j: ıntregscrie “Dimensiunile matricii:”citeste nciteste mmatrice: ıntreg[n][m]//citirea elemenelor

pentru i = 0, i < n, 1 executa //i reprezinta linia curentapentru j = 0, j < m, 1 executa //j reprezinta coloana

curentascrie “Elementul de pe pozitia “ + i + “ “ + jciteste matrice[i][j]

sf pentrusf pentru

//continuam pe pagina urmatoare


SumaLiniiColoane II

sumaL, sumaC: ıntregsumaL = 0sumaC = 0//parcurgem matricea pentru a calcula sumelepentru i = 0, i < n, 1 executa

pentru j = 0, j < m, 1 executadaca i mod 2 == 0 atunci

sumaL = sumaL + matrice[i][j]sf dacadaca j mod 2 == 1 atunci

sumaC = sumaC + matrice[i][j]sf daca

sf pentrusf pentruscrie “Suma liniilor pare: “ + sumaLscrie “Suma coloanelor impare: “ + sumaC

sf algoritm


SumaLiniiColoane III

Tema de gandire: Ce se ıntampla daca rescriu partea decomparatie ın modul urmator:

daca i mod 2 == 0 atuncisumaL = sumaL + matrice[i][j]

altfel daca j mod 2 == 1 atuncisumaC = sumaC + matrice[i][j]

sf daca


Arrayuri multidimensionale

Pentru a defini arrayuri multidimensionale folosim urmatoareainstructiune:

tablouMultiD: ıntreg[D1][D2][D3]...[Dn]

Iar pentru accesarea unui element, trebuie sa folosim cate unindice pentru fiecare dimensiune:

tablouMultiD[0][0][0]...[0] = 0


Vizibilatatea variabilelor

Vizibilitatea variabilelor descrie viata unei variabile, zona sa dedisponibilitate (ın care parte a codului poate fi folosita - estevizibila) dupa ce a fost definita

Consideram ca o variabila este definita ın momentul ın careapare pentru prima oara ın cod

Cateodata introducem o variabila fara sa-i atribuim o valoare(mai mult la arrayuri)


Vizibilitatea variabilelor II

O variabila definita ıntr-un algoritm (dar nu ıntr-o instructiunedaca, cattimp sau pentru) este vizibila ın tot algoritmul dupace a fost definita.

O variabila definita ıntr-un bloc (instructiune daca, cattimpsau pentru) este vizibila dupa ce a fost definita pana la finalulblocului respectiv.

O variabila definita ın afara unui algoritm, numita variabilaglobala, este vizibila ın toti algoritmii din fisierul respectiv.Este o practica gresita sa folosim variabile globale!


Vizibilitatea variabilelor III

Sa consideram problema urmatoare: cititi un numar de latastatura si afisati numarul de divizori ai numarului, urmat delista divizorilor.

Pentru a numara divizorii trebuie sa verificam pe rand fiecarenumar ıntre 1 si numarul respectiv, daca este divizor.Pentru a afisa divizorii, le vom retine ıntr-un array, si le vomafisa dupa ce am afisat numarul de divizori.


Vizibilitatea variabilelor IV

1.algoritm Divizori este2. scrie “Dati un numar:”3. numar: ıntreg4. citeste numar5. divizori: ıntreg[numar] //tablou ın care retinem divizorii6. nrDiv: ıntreg7. nrDiv = 0 // numarul de elemente din tabloul divizori8. divizorPosibil:ıntreg9. pentru divizorPosibil = 1, divizorPosibil < numar+1, 1 executa10. rest:ıntreg11. rest = numar mod divizorPosibil12. daca rest == 0 atunci13. divizori[nrDiv] = divizorPosibil14. nrDiv = nrDiv + 115. sf daca16. sf pentru17. scrie “Numarul de divizori: “ + nrDiv


Vizibilitatea variabilelor V

18. scrie “Divizorii sunt: ”19. div: ıntreg20. pentru div = 0, div < nrDiv, 1 executa21. scrie divizori[div]22. sf pentru23.sf algoritm


Vizibilitatea variabilelor V

Algoritmul divizori contine 6 variabile:

numar - definita pe randul 3, vizibila pana la finalulalgoritmuluidivizori - definita pe randul 5, vizibila pana la finalulalgoritmuluinrDiv - definita pe randul 6, vizibila pana la finalul algoritmuluidivizorPosibil - definita pe randul 8, vizibila pana la finalulalgoritmuluirest - definita pe randul 10, vizibila doar ın ciclul pentru (panarandul 16 inclusiv)div - definita pe randul 19, vizibila pana la finalul algoritmului


Vizibilitatea variabilelor VI

Nu pot exista 2 variabile cu acelasi nume vizibile ın aceeasizona a codului

Daca o variabila nu mai este vizibila, o alta variabila cu acelasinume poate fi definita

Incercarea de a folosi o variabila care nu mai este vizibila(precum si folosirea unei variabile care niciodata nu a fostdefinita), duce la o eroare


Exemple vizibilitatea variabilelor

Ce va fi afisat daca executam urmatoarele bucati de cod?


Exemplu 1

Exemplu 1

ınceput: ıntregınceput = 6sfarsit, i: ıntregsfarsit = 13pentru i = ınceput,i < sfarsit, 1, executa

contor: ıntregcontor = 0daca i mod 2 == 0 atunci

contor = contor + 1scrie “Numere pare gasite pana acum:” + contor

sf dacasf pentruscrie “Total numere pare: “ + contor


Examplu 1

Daca lucram ın limbajul Java (si rescriem bucata de cod ınJava), vom avea o eroare la compilare, pentru ca la finalıncercam sa afisam variabila contor care nu mai este vizibila.

Daca lucram ın Python, codul va afisa mesajul Numere paregasite pana acum: 1 de 4 ori, dupa care va da un mesaj deeroare la ultimul rand, pentru ca variabila contor nu estevizibila decat ın ciclul pentru


Exemplu 2

Exemplu 2

nr, nrPasi: ıntregnr = 129nrPasi = 0cattimp nr > 50 executa

scrie “Numarul: ” + nrrest: ıntregrest = nr mod 2nr = (nr + rest) / 2nrPasi = nrPasi + 1

sf cattimpscrie “A fost nevoie de ” + nrPasi + “ pasi”

Codul va afisa mesajele:

Numarul: 129Numarul: 65A fost nevoie de 2 pasi


Exemplu 3

Exemplu 3

nr, i: ıntregnr = 7pentru i = 1, i < nr, 1 executa

verif: ıntregverif = idaca verif mod 3 == 1 atunci

scrie verifsf daca

sf pentruscrie “Ultima valoare verificata: ” + verif

Eroare de compilare pentru ca variabila verif nu esteaccesibila ın afara ciclului pentru.

Codul va afisa numerele 1 si 4, dupa care va da un mesaj deeroare pentru ca variabila verif nu este vizibila ın afara cicluluipentru.


Exemplu 4

Exemplu 4

nr, index: ıntregnr = 7index = 10cattimp index > nr executa

nr = nr - 1suma: ıntregsuma = suma + nrscrie “Suma curenta:” + suma

sf cattimp

Problema este ca variabila suma nu este initializata, deci nuputem calcula cat este suma + nr

Anumite limbaje de programare dau o eroare ın acest caz (lacompilare sau la rulare), ın alte limbaje suma poate fiinitializata cu ceva valoare, dar nu stim ce.


Exemplu 5

Exemplu 5

nr,i: ıntregnr = 9pentru i = 1, i < nr, 3 executa

suma: ıntregsuma = 0 + iscrie “Suma curenta:” + suma

sf pentrusuma: ıntregsuma = nr * 2scrie “Suma intermediara: ” + sumapentru i = 1, i < 4, 1 executa

suma = suma + isf pentruscrie “Suma finala: ” + suma


Codul de mai sus va afisa urmatoarele mesaje:

Suma curenta: 1Suma curenta: 4Suma curenta: 7Suma intermediara: 18Suma finala: 24


programare s˘i structuri de date - cs.ubbcluj.romarianzsu/postuniv/curs/curs01.pdf · pot exista...

Documents