Post on 30-May-2018
transcript
8/14/2019 programarea calculatoarelorCap 1
1/15
Algoritmi.
CAPITOL 1
ALGORITMI
Exist dou moduri de reprezentare a algoritmilor: prin scheme logice; prin limbaje de tip pseudocod.
Schema logic este o transcriere grafic a pailor unui algoritm.Limbajul pseudocod este un limbaj cu reguli sintactice care permite exprimarea
ordinii de execuie a pailor algoritmilor.Un algoritm reprezint o succesiune finit de pai prin care din mulimea datelor de
intrare ale unei probleme se produc date de ieire corecte.Blocurile folosite ntr-o schem logic sunt urmtoarele:
bloc delimitaror
bloc de citire/scriere
bloc de atribuire
bloc de decizie
bloc de procedur
sgeat
conector de blocuri
Conform programrii structurate un algoritm cu un singur punct de nceput i unsingur punct de sfrit poate fi descris cu ajutorul celor 3 structuri de control prezentate maijos.
a)structura secvenial
Operaie 1
Operaie 2
CondiieDaNu
Nume
procedur
8/14/2019 programarea calculatoarelorCap 1
2/15
Algoritmi.4
b)structura alternativ
c)structura repetitiv
Programarea structural admite i utilizarea altor structuri de control cum sunt:selecia, ciclul cu test final i ciclul cu contor.
Structura ciclic cu test final are urmtoarea form:
Limbajul pseudocodLimbajele de tip pseudocod folosesc o sintax mult mai liber dect cele folosite de
limbajele de programare. Un algoritm scris n acest limbaj are avantajul c poate fi neles detoi programatorii, pe cnd un algoritm scris ntr-un limbaj de programare va fi neles doar decei care cunosc acel limbaj.
Limbajele de tip pseudocod folosesc diferite cuvinte cheie preluate dintr-un limbajnatural. Exemple: dac, atunci, altfel...Expresiile aritmetice se vor scrie:
baba
xaxa/
^
!!
a mod b = restul mpririi lui a la b;a div b = ctul mpririi lui a la b.
Operaii
Da
NuCondiie
NuDa
Operaii
Condiie
OperaiiOperaii
Condiie DaNu
8/14/2019 programarea calculatoarelorCap 1
3/15
Algoritmi.
Un limbaj pseudocod conine, n general, urmtoarele comenzi:1.de ncepere a algoritmului:nceput algoritm2.de citire:citete lista de variabile3.de atribuire:
variabil expresie4.de ramificare:
dac condiie atunci operaialtfel operai
sfrit dac5.de ciclare:
a) ct timp condiie executoperai
sfrit ct timp b) repet operaii
pn cnd condiie
6.de oprire:sfrit algoritm.
Aplicaii
Aplicaia 1:Pentru funcia:
f(x) =
"
e
0,5
0,122
3
xxx
xxx
s se realizeze schema logic i pseudocodul care calculeaz valoarea acestei funcii ntr-un
punct x dat.
Schema logic: tart
Citete x
0ex
123 n xxf 52 n xxf
DaNu
Scrie f
Stop
8/14/2019 programarea calculatoarelorCap 1
4/15
Algoritmi.6
Pseudocod:nceputalgoritmcitetexdacx e0atunci f 123 xx
altfel f 52 xx sfrit dacscriefSfritalgoritm
Aplicaia 2:S se realizeze schema logic i s se scrie pseudocodul care calculeaz media final a
unui student cunoscnd notele obinute la analiz matematic (n1), fizic (n2), utilizareacalculatoarelor (n3), precum i creditele aferente acestor materii.
Formula cu care se calculeaz media este urmtoarea :
Media =321
332211 ***
ccc
cncncn
Apoi, n funcie de media acestuia s se determine dac studentul beneficiaz de bursde merit, burs de student sau nu primete burs. Condiia pentru burs de merit este ca media 9.5, condiia pentru burs de student este 9.5>medie8, dac nu studentul este nebursier.
Schema logic:
321
3*32*21*1
ccc
cccMedia
n
321
3*32*21*1
ccc
cccMedia
n
Start
5.9uMedia
DaNu
Scrieburs de
0.8uMedia
DaNu
Citete n1, n2,n3, c1, c2, c3
Scrieburs de
Scrienebursier
Stop
8/14/2019 programarea calculatoarelorCap 1
5/15
Algoritmi.
Pseudocod:nceputalgoritmciteten1,n2,n3,c1,c2,c3
media
321
332211 ***
ccc
cncncn
dac media 9.5 atunci scrie burs de meritaltfel dac media 8.0 atunci scrie burs de student
altfel scrie nebursiersfrit dac
sfrit dacscrie mediaSfritalgoritm
Aplicaia3:S se realizeze schema logic i pseudocodul pentru rezolvarea ecuaiei de gradul 2.
Ecuaia de gradul 2 are urmtoarea form:ax2 + bx + c = 0
Schema logic:
DA
DA
NU DA
NU
Start
Citete a, b, c
Ecuaia are oinfinitate desoluii
b=0NU DA
NU DAc=0
Ecuaia nuare soluii
b
cx n
acb 42 n(
a=0
0"(
a
bx
21(
n
a
bx
22(
n
NU0!(
12
12
xx
a
bx
n
n
a
b
2Re n
a2
Im(
n
Stop
Scrie x
Scrie x1, x2
Scrie x1, x2
Scrie Re, Im
8/14/2019 programarea calculatoarelorCap 1
6/15
Algoritmi.8
Pseudocod:nceputalgoritmcitetea,b,cdaca=0atunci
dacb=0atuncidacc=0atunci scrie Ecuaiaare o infinitate de soluii
altfel scrie Ecuaianuare soluiisfrit dac
altfel xb
c
scriexsfrit dac
altfel acb 42
dac > 0atunci x1 ab
2(
x2a
b
2
(
scriex1,x2
altfel dac =0 atunci x1 -a
b
2
x2x1scriex1,x2
altfel Re -a
b
2
Im a2
(
scrie Re, Imsfrit dac
sfrit dacsfrit dacSfritalgoritm
Aplicaia 4:
Find date 3 numere reale s se determine dac acestea pot fi lungimile laturilor unuitriunghi i n caz afirmativ s se stabileasc natura acestuia.Avem urmtoarele condiii:
- triunghi echilateral: a = b = c- triunghi dreptunghic: 222 cba sau 222 acb sau 222 bac - triunghi isoscel: a =b sau b = c sau a =c
8/14/2019 programarea calculatoarelorCap 1
7/15
Algoritmi.
Schema logic:
Pseudocod:nceputalgoritmcitetea,b,cdac a>0i b>0i c > 0i a < b+ci b< c+ai c< b+a atunci
daca=b=c atunci scrie echilateral
altfel dac 222 cba
sau 222 acb
sau222 bac
atunci scrie dreptunghicsfrit dacdaca=b saub=c saua=c
atunci scrie isoscelsfrit dac
sfrit dacsfrit dacSfritalgoritm
NUDA
DA NU
tart
Citete a, b, c
a,b,c>0 ia
8/14/2019 programarea calculatoarelorCap 1
8/15
Algoritmi.10
Aplicaia5:S se realizeze schema logic i pseudocodul care determin suma S i produsul P pentru
un numr n citit.S = 1 + 2 + 3 + ..+ nP = 1 * 2 * 3 * * n
Schema logic:
Pseudocod:
nceputalgoritmCitetenSn0
Pn1in1ct timp ie nexecut SnS+i
PnP*i
in i+1sfritct timpscrie S, PSfritalgoritm
Nu
Start
Citete n
Sn 0Pn 1i n 1
Da
i e n
S nS + iPn P * ii n i + 1
Scrie S, P
Stop
8/14/2019 programarea calculatoarelorCap 1
9/15
Algoritmi. 11
Aplicaia 6:S se realizeze schema logic i pseudocodul care s determine media general a unui
student cunoscnd cele n note ale sale n cursul unui an de studiu.
Schema logic:
Pseudocod:
nceputalgoritmcitetenS0
i 1ct timp i nexecut citetenota
S S+notai i +1
sfritct timpM=S/nScrie MSfritalgoritm
Nu
tart
Citete n
Sn 0i n 1
Da
i e n
S nS + notai n i + 1
Scrie M
Stop
Citete notaM=S/n
8/14/2019 programarea calculatoarelorCap 1
10/15
Algoritmi.12
Aplicaia 7:S se realizeze schema logic i pseudocodul care calculeaz suma urmatoare pentru un
numr n citit.S = 1 + 3 + 5 + ..+ 2n-1
Schema logic:
Pseudocod:nceputalgoritmcitetenS0
i 1ct timp i 2n-1execut S S+ i
i i +2sfritct timpscrie SSfritalgoritm.
Aplicaia8:S se realizeze schema logic i pseudocodul care determin :
-numrul elementelor impare-numrul elementelor divizibile cu 5
-suma elementelor parepentru n numere citite.
Nu
Start
Citete n
Sn 0i n 1
Da
i e 2n-1
S nS + ii n i + 2
Scrie S
Stop
8/14/2019 programarea calculatoarelorCap 1
11/15
Algoritmi. 13
Schema logic:
Pseudocod
nceputalgoritmcitetenin1nrin0nrdn0Sn0
ct timp ie nexecutciteteadaca mod2=0atunci SnS+a
altfelnrinnri+1sfrit dacdaca mod 5 =0atunci nrd=nrd+1
Nu
Start
Citete n
Sn 0nrin 0nrdn 0
in 1
Da
i e n
Scrie S, nrd,nri
Stop
Citete a
Sn S+anrin nri+1
DaNu a mod 2 =0
nrdn nrd+1
DaNu a mod 5 =0
in i+1
8/14/2019 programarea calculatoarelorCap 1
12/15
Algoritmi.14
sfrit dacin i+1
sfritct timpscrie S,nri,nrdSfritalgoritm
Aplicaia9:S se realizeze schema logic i pseudocodul care determin numrul elementelor
negative i suma elementelor pozitive dintr-un ir de n numere citite.
Schema logic:
Pseudocod:nceputalgoritmcitetennrn 0Sn 0
in 1ct timp i enexecut citetea
daca
8/14/2019 programarea calculatoarelorCap 1
13/15
Algoritmi. 15
in i+1sfritct timpSfritalgoritm
Aplicaia 10:S se realizeze schema logic i pseudocodul care determin suma cifrelor unui numr
ntreg n citit.
Schema logic:
Pseudocod:nceputalgoritm
citetenSn 0
ct timpn { 0execut rn n mod10Sn S+r
nn [n/10]sfritct timpscrie SSfritalgoritm
Aplicaia 11:
S se realizeze schema logic i pseudocodul pentru determinarea valoarii maxime i avaloarii minime dintr-un ir de n numere citite.
Nu
Start
Citete n
Sn 0
Da
n { 0
rnn mod 10S n S + rn n [n/10]
Scrie S
Stop
8/14/2019 programarea calculatoarelorCap 1
14/15
Algoritmi.16
Schem logic:
Pseudocod:nceput algoritmCitete n, amaxn aminn ain 2
ct timp i en execut citete adac a>max atunci maxn a
altfel dac a max
min n a
in i+1
a
8/14/2019 programarea calculatoarelorCap 1
15/15
Algoritmi. 17
Aplicaia 12:S se realizeze schema logic care s calculeze i s se afieze valoarea expresiei (a-
m)^n/(n-a)^m pentru a, m, n citite de la tastatur m, n u 0 ntregi i a { n.
Schema logic: Start
Da
Pn1in 1
Scrie E
Stop
Nu
Citete m
m u 0 im=[m
Nu
Citete n
n u 0 in=[n
Da
Nu
Citete a
a { n
Da
Nu
i en
PnP*(a-m)in i+1
Da EnPP n 1in 1
i en
PnP*(n-a)in i+1
DaEnE / P