programiranje libro

8/3/2019 programiranje libro

1/82

Elektrotehniki fakultetUniverziteta u Beogradu

Programiranje 1Materijal za vebe na tabli i pripremu ispita

verzija: 2009-12-30

Pregled iz teorije izloen u ovim materijalimatreba koristiti PRVENSTVENO kao podsetnik, a ne kao jedini izvor znanja

Osim u belekama sa predavanja, detaljna objanjenja se mogupronai u sledeim knjigama:

Jozo Dujmovi, Programski jezici i metode programiranja Kathleen Jensen, Niklaus Wirth, Pascal prirunik

Vie zadataka se moe pronai u zbirci prof. Krausa: Laslo Kraus, Zbirka zadataka iz Programskih jezika

Navedene knjige se mogu pronai u skriptarnici ili u bibliotecifakulteta.

Za svaki zadatak koji se moe pronai u zbirci prof. Krausa, ovde jenaveden samo tekst zadatka, bez reenja. Svaki od zadataka jenumerisan brojem koji oznaava stranu na kojoj se dati zadataknalazi u zbirci. Priloena su i reenja (kompletna ili odgovarajui deo)

onih zadataka iji je tekst blago izmenjen u odnosu na zbirku.

Zadaci koji su tipa ispitnih pitanja su priloeni u celosti, ukljuujui iobrazloenje reenja tamo gde je to potrebno.

U materijal je ukljueno i nekoliko ispitnih zadataka, koji su reeni upotpunosti i detaljno komentarisani.

Materijal se stalno unapreuje, nove verzije e redovno biti dodavanena Internet stranicu predmeta:

http://rti.etf.rs/rti/ir1p1

Molimo da sugestije, primedbe ili uoene greke poaljete putemelektronske pote na adresu [email protected].


2/82

Elektrotehniki fakultet Univerziteta u Beogradu Programiranje 1

Materijal za vebe na tabli i pripremu ispita Strana 2 od 82

SadrajSpisak izmena: 4

Bulova algebra 5Izvod iz teorije 5Zadatak Z1BA 7Zadatak Z2BA 7

Zadatak Z3BA 7Zadaci za samostalnu vebu 8Predstavljanje brojeva 9

Sistemi za predstavljanje nenegativnih celih brojeva 9Klasifikacija brojnih sistema sa osnovom 9Konverzija iz sistema sa osnovom r u decimalni sistem 10Konverzija iz decimalnog u sistem sa osnovom r 10

Sistemi za predstavljanje negativnih celih brojeva 11Sistem znaka i magnitude 11Sistem komplementa 11

Promena znaka 14Sabiranje u sistemu komplementa dvojke (L=2n) 15Oduzimanje u sistemu komplementa dvojke (L=2n) 17Zadatak B1 18

Zadaci sa vebi na tabli 19Zadatak IZ1 19Zadatak IZ2 19Zadatak IZ (Oktobar 2007) 20Zadaci za samostalnu vebu (sa ranijih ispita) 22

picoComputer 23

Referentni prirunik za picoComputer 23Tabela 1.1: Osnovne mainske instrukcije koje izvrava pC 24

Tabela 1.2: Pregled strukture mainskih instrukcija za pC 25Tabela 1.3: Sintaksa simbolikog mainskog jezika pC 26Uputstvo za korienje programa PCAS 27Zadatak Z22 28Zadatak Z23s (skraena varijanta zadatka sa strane 23) 28Zadatak Z23 29Zadatak Z24 29Zadatak IZ6 29Zadatak Z25 30Zadatak Z26 30Zadatak IZ7 30Zadatak Z27 30Zadatak Z28 30Zadatak Z29 (dodat u verziji 2009-10-27) 31Zadatak IZ24 31Zadatak IZ 2006-11-30 (Kolokvijum 2006) 31Zadatak IZ 2006-11-30 (Kolokvijum 2006) 31Zadatak IZ 2006-11-30 (Kolokvijum 2006) 32

Sintaksne notacije 33

Elementi notacija 33BNF notacija 33EBNF notacija 33Notacija sa zagradama 33


3/82



Sintaksni dijagrami 34Zadatak IZ32A (integralni ispit, 14.03.2002. godine) * 34Zadatak IZ8 35Zadatak IZ9 35Zadatak IZ 2006-11-31 (Kolokvijum 2006) 36Zadatak IZ10 36Zadatak Z72 (modifikovan) 37

Zadatak IZ11 (Januar 2007) 41Zadatak IZ 2005-12-02 (Kolokvijum 2005) 41Zadatak IZ 2005-12-02 (Kolokvijum 2005) 41

Pascal 42Zadatak UVODNI_01 42Zadatak UVODNI_02 43Zadatak Z89 45Zadatak Z91 45Zadatak Z41.PAS 46

Skupovi, nabrojani tip, potprogrami, zapisi 47

Zadatak Z38.PAS 47Zadatak IZ53 48Zadatak IZ50 48Zadatak IZ 2006-09-20 (MODIFIKACIJA) 49Zadatak Z97 51Zadatak IZ 2007-09-18 (Oktobar 2007-1) 53Zadatak IZ Februar 2007-2 (Modifikovan) 55Zadatak IZ51 56Zadatak IZ Februar 2007 P4 57Zadatak Z105 58

Rekurzija 59Zadatak Z103 59Zadatak IZ52 59Zadatak IZ Januar 2007 P4 60Zadatak IZ 2006-02-01 (Januar 2006 P5) 60Zadatak IZ 2006-06-21 (Jun 2006 P6) 60

Datoteke 61Zadatak ZD1 62Zadatak Z115 62Zadatak Z114 (ispravka stilske greke u postavci) 63Zadatak IZ 2006-02-01 (Januar 2006) 64

Zadatak Z116 (precizirana postavka, izmenjen identifikator za datoteku) 64Zadatak Z117 65Zadatak IZ 2006-09-20 (Septembar 2006) Modifikacija 66Zadatak IZ 2006-06-21 (Jun 2006) 67Zadatak IZ 2006-06-21 (Jun 2006) 68

Dinamika alokacija memorije 69Zadatak Z123 69Zadatak IZ54 70Zadatak IZ Februar 2007 P5 70Zadatak IZ Januar 2007 P5 71

Zadatak IZ 2006-06-21 (Jun 2006 P5) 71Zadatak Z125 71Zadatak IZ 2005-06-22 (Jun 2005) (ispravka greaka u reenju, dopunjen komentar) 73Zadatak Z127 75


4/82



Sloenost algoritma 77Pravila za prebrojavanje instrukcija radi utvrivanja I(n) 77Zadatak NZ1 78Zadatak NZ2 79Zadatak Z64.PAS 80Zadatak Z65.PAS 81Zadatak Z68a.PAS 82

Spisak izmena:

Verzija 2009-12-30: ispravljene su uoene greke u reenju zadatka IZ 2005-06-22 (Jun 2005) idopunjen je komentar zadatka.

Verzija 2009-12-16: postavka zadatka Z116 je formulisana preciznije. Identifikator datoteke Tekstjepromenjen u datoteka, radi bolje itljivosti programa.

Verzija 2009-12-15: ispravka stilske greke u postavci zadatka Z114 na strani 63.

Verzija 2009-11-26: ispravljene formule za zbir i razliku komplemenata na stranama 15 i 17.

Verzija 2009-10-27: dodat Z29 (pC)


5/82



BULOVA ALGEBRABulova algebra je ovde predstavljena kratkim izvodom iz teorije, kao i nekim zadacima sa vebi.

Izvod iz teorijeNeka su nad skupom B={a, b, c, } definisane:

unarna operacija "" (komplementiranje),binarna operacija "+" (sabiranje), ibinarna operacija "" (mnoenje),

i to tako da: a B b B a b, BcBba , a b c, BcBba , cba .

Drugim reima, operacije su zatvorene nad skupom B.Struktura koju ini skup B sa istaknutim elementima 0 i 1 i operacijama "" (komplementiranje), "+"

(sabiranje) i "" (mnoenje), predstavlja Bulovu algebru ako operacije zadovoljavaju sledee aksiome:1. zakon asocijativnosti: cbacbacbacba , 2. zakon komutativnosti: abbaabba , 3. zakon o neutralnom elementu: aaaaaa 11,00 4. zakon o komplementu: 01 aaaaaaaa , 5. zakon distributivnosti: cabacbacabacba ,

Dualni Bulov izraz: ako je ,,, cbaQ Bulov izraz, dualni Bulov izraz ,,, cbaQd se dobija izizraza Q tako to se svaka operacija sabiranja zameni operacijom mnoenja, svaka operacijamnoenja zameni operacijom sabiranja, i svaka konstanta svojim komplementom.

Teoreme:1. zakon o jedinstvenom komplementu: axxaxa 01, 2. 01,10

3. zakon involucije operacije komplementiranja: aa 4. 00,11 aa 5. zakon idempotentnosti: aaaaaa , 6. zakon apsorpcije: abaaabaa ,

7. zakon saimanja: ababaababa ,

8. zakon nepotpunog saimanja: babaababababaababa ,

9. zakon generalisanog saimanja:

cbcabacbcacbcabacbca , 10.De Morganova teorema: babababa , 11.generalizovana De Morganova teorema: ,,,,,, cbaQcbaQ d 12.princip dualnosti: ,,,,,,,,,,,, zyxRcbaQzyxRcbaQ dd

Primeri Bulove algebre:

1. u skupovima: UAa c 1,0,,, 2. u matematikoj logici: , , , 0 , 1a a F T


6/82



3. prekidaka logika:Bulova algebra na skupu B={0, 1}


7/82



Zadatak Z1BAUprostiti algebarske izraze:A) cbcbaba B) cbcbaba C) cbacba

Reenje:A) cbcbaba - apsorpcija: ababcababcab 11 cbba - distibutivnost "" prema "+"

cab B) cbcbaba - distibutivnost "" prema "+"

cbcbba - distibutivnost "+" prema "" cbcbbba - bb je 1

cbcba cbcaba

C) cbacba - distibutivnost "" prema "+" bacccba - cc je 0 bacba - oba sabirka e imati u sebi proizvod koji je 0

0 bcbaacba - prvi proizvod je nula zbog aa , a drugi zbog bb

Zadatak Z2BADokazati jednakost: cabccaabdbc Napomena: pri dokazivanju jednakosti, mogu se koristiti sledea dva pristupa jedan pristup je dase primenom teorema od jedne strane jednakosti dobije druga, dok se drugi pristup sastoji u tomeda se obe strane jednaine uz pomo teorema transformiu dok ne postanu identine. Iako ne postojiformalno pravilo, prvi pristup je bolji ako je jedan od izraza jednostavan, a drugi ako su oba izrazakomplikovana.

Reenje: cabccadcababcdbccaccabdbccaabdbc

U poslednjem koraku upotrebljena je apsorpcija za prva dva, odnosno druga dva sabirka: bcadbcabcdbc 1 , odnosno cabdcacadcab 1 .

Zadatak Z3BAAko je cbaba , dokazati da je bcaca .

Reenje:bcaca - zameni se c

bbabaababaa - primenimo De Morganovu teoremu, dva putabbaabaababaa - za pretposlednji sabirak vai 00 bbaa

bbababaa 0 bbabbbabaaaa

bbabaaba 00

bbabaaaab bbaab 0 - ovde se mogao direktno primeniti zakon saimanjabbaa

bb


8/82



Zadaci za samostalnu vebuKoji je od ponuenih izraza Bulove algebre ekvivalentan izrazu caabdbc ?(A) cabc B) cabcdc C) abbc

Dovoljan uslov da vrednost sledeeg izraza beadcba )( Bulove algebre bude 1 je:(A) 0c i 0d B) 0d i 0a (C) 1e i 0c

Koji je od ponuenih izraza Bulove algebre ekvivalentan izrazu )()()( accbba ?(A) )()()( accbba B) cbacba C) cba

Dovoljan uslov da vrednost sledeeg izraza ceadbca )( Bulove algebre bude 1 je:(A) 0b i 0d B) 0d i 0a (C) 0b i 1e

Koji od ponuenih odgovora je ekvivalentan datom izrazu bacbba )()( Bulove algebre:(A) cba B) )()( abca C) ))(( bacbba


9/82



PREDSTAVLJANJE BROJEVA

Sistemi za predstavljanje nenegativnih celih brojevaU cifarskoj reprezentacijinenegativni ceo broj se predstavlja kao ureena n-torkaelemenata koji se

nazivaju cifre; n-torka se naziva vektor cifarai zapisuje se kao: 01210121

,,,,,, XXXXXXXXXXXinninn

Brojni sistem odreuju sledei elementi:

1. Skup (numerikih) vrednosti cifara. Sai

D obeleavamo skup vrednosti koje uzimai

X, a sa

iD broj elemenata skupa

iD . U decimalnom brojnom sistemu vai 9,8,7,6,5,4,3,2,1,0

iD ,

10:,10 niiDi

.2. Pravilo interpretacije. Re je o pravilu preslikavanja skupa vrednosti vektora cifara u skup

brojeva.

Skupbrojevapredstavljenih vektorom cifara sa nelemenata je konaan skupsa najvie:

1

0

n

i

iDK

elemenata, poto je ovo najvei broj razliitih vrednosti vektora cifara.(Primer: za n

iDKniiDD 10:, )

Neredundantan brojni sistem:ako svaki vektor cifara predstavlja razliit broj (preslikavanje 1:1).Redundantan brojni sistem:ako vie razliitih vektora cifara predstavlja isti broj.

Najee se koriste teinski sistemi (sistemi sa teinskim pozicionim kodom). Za njih vai pravilopreslikavanja:

1

0

n

i

iiWXX

gde jei

W"teina" i-tog razreda. Vektoru cifara Xodgovara vektor teina: .,,...,011WWWW

n U brojnim sistemima sa osnovom(eng. radix) vektor teina se nalazi u sledeem odnosu sa vektoromosnova :,,...,

011RRRR

n

110,1 iii RWWW , to se svodi na:

11:,,11

0

0

niiRWWi

j

ji

Klasifikacija brojnih sistema sa osnovom1. Prema vektoru osnovabrojni sistemi se dele na one sa fiksnom i one sa meovitom osnovom.1.1.Fiksna osnova: svi elementi vektora osnova imaju istu vrednost r. Vektor teina je tada

,1,,,...,, 1221 rrrrW nn a pravilo preslikavanja:

1

0

n

i

i

i rXX

1.2.Meovita osnova:elementi vektora osnova su razliiti. Primer za ovakav brojni sistem moe bitipredstavljanje vremena vektorom cifara (, , ). Vrednosti za vektorosnova i vektor teina su 1,60,3600;60,60,24 WR .


10/82



2. Prema skupu vrednost cifara brojni sistemi sa osnovom se dele u kanonike i nekanonikesisteme.

2.1.Kanoniki sistemi:skup vrednosti 1,...,1,0 iiRD .

2.2.Nekanoniki sistemi:skupvrednosti Dinije kanoniki (primer: rimski brojevi).

Kanoniki skupovi daju neredundantne sisteme.Sistem sa fiksnom pozitivnom osnovom r i kanonikim skupom vrednosti cifara naziva se

konvencionalnim brojnim sistemom sa osnovom r.Najee se koriste:

,10r 9,8,7,6,5,4,3,2,1D decimalni (eng. decimal, skraeno dec.),2r 1,0D binarni (eng. binary, skraeno bin.),8r 7,6,5,4,3,2,1,0D oktalni (eng. octal, skraeno oct.),16r FEDCBAD ,,,,,,9,8,7,6,5,4,3,2,1,0 heksadecimalni (eng. hexadecimal, skraeno hex.)

Za predstavljanje brojeva u raunaru koristi se binarni brojni sistem, a oktalni i heksadecimalni supogodni za "skraeno" zapisivanje binarno predstavljenih brojeva.

10)8(162 178262210110010 BX

Konverzija iz sistema sa osnovom r u decimalni sistem 1 2 1 0 10n n rC C C C X

1 2 0

1 2 0 1 2 1 010

n n i

n n i n nX C r C r C r C r C r C r C r C

Primeri: 12120202110011

)2(X

12120202 12124

1019129

)16(03DAX

316016101613 31601610208

)10(558113163488

Konverzija iz decimalnog u sistem sa osnovom r 1 2 1 010 n n r X C C C C

1 0 1 2 1 n-1 1/ C ; / C ; ; X / 0 n X r X X r X r C

Primer:

102/1

012/2

022/4

142/9

192/19X

)2(

10011X

D13016/13A101316/218

0021816/3488

33348816/55811X

)16(

03DAX


11/82



Sistemi za predstavljanje negativnih celih brojeva

Sistem znaka i magnitudeCeo broj se predstavlja pomou para

msxx , , gde je

sx znak, a

mx magnituda. Dve vrednosti znaka

(+,-) se predstavljaju pomou binarnih vrednosti (0,1), respektivno.Magnituda se moe predstaviti bilo kojim sistemom za predstavljanje nenegativnih celih brojeva. Akose koristi konvencionalni sistem sa osnovom r opseg celih brojeva je ,10

nrx gde je n

broj cifara za predstavljanje magnitude.Nulaima dve reprezentacije: 0,0

msxx (pozitivna nula), 0,1

msxx (negativna nula).

Sistem komplementaU sistemu komplementa ne pravi se razdvajanje izmeu predstavljanja znaka i predstavljanjamagnitude, ve se kompletan ceo broj sa predznakom predstavlja preko nenegativnog celog broja Acna sledei nain:

,mod LAAc

gde je L pozitivan ceo broj, nazvan komplementaciona konstanta. Komplementaciona konstanta

treba da zadovoljava uslov2maxL

A da bi se dobila jednoznana predstava, tj. da se podruja

pozitivnih i negativnih brojeva ne bi preklapala. Po definiciji "mod" (moduo, ostatak pri celobrojnomdeljenju) funkcije, imajui u vidu navedeni uslov, gornji izraz je ekvivalentan sa:

0,

0,

AAL

AAAc

obrnuto:

LAL

L,A

LA,A

A

cc

cc

2

20

(Matematika definicija "mod" funkcije ima uslov: 0A ; ovde je za negativno A dato 0A , zboguvoenja "negativne nule".)Preslikavanje se moe predstaviti tabelarno na sledei nain:

A 0 1 2 L/2-1 -(L/2-1) 2 1 0

Ac 0 1 2 L/2-1 (L/2+1) L2 L1 L

Napomena:Ac se posmatra kao pozitivan broj bez znaka (znak je implicitno zadat u Ac).Primer: Predstaviti sve cele brojeve koji zadovoljavaju uslov: 2/

maxLA , ako je

a) 10L

Reenje:452/

max AL

A 0 1 2 3 4 -4 -3 -2 -1 -0

Ac 0 1 2 3 4 6 7 8 9 10

b) 9L Reenje

45.42/max

AL

A 0 1 2 3 4 -4 -3 -2 -1 -0

Ac 0 1 2 3 4 5 6 7 8 9

Vrednost Ac se moe predstaviti u bilo kom sistemu za pozitivne cele brojeve. Ako se koristi


12/82



konvencionalni brojni sistem sa osnovom r i vektorom od n cifara, opseg moguih vrednosti je:10 n

crA .

Uobiajeni izbor za komplementacionu konstantu L je nrL ili 1 nrL .Komplement osnoveIzbor nrL definie sistem komplementa opsega(eng. Range Complement RC), takoe poznatkao sistem komplementa osnove, a za r=2, komplement dvojke(eng. two's complement). U ovom

sistemu vrednost Ac=L je izvan opsega i stoga postoji samo jedna reprezentacija A=0. Opseg celihbrojeva sa predznakom je:

1

2

10

nrA podrazumevajui da je osnova parna. Vrednost

n

crA

2

1 se ponekad koristi za predstavljanje ,

2

1 nrA to daje za rezultat nesimetrinu

reprezentaciju pozitivnih i negativnih vrednosti.

A 0 1 2 12

1nr nr

2

1 -2 -1

Ac 0 1 2 12

1

n

r

n

r2

1

rn

-2 rn

-1

Komplement najvee cifreIzbor 1 nrL definie sistem komplementa najvee cifre(eng. Digit complement DC), takoepoznat kao sistem umanjenog komplementa osnove, a za r=2, komplement jedinice (eng. one'scomplement). U ovom sistemu Ac=L se moe prikazati sa n cifara, tako da ovde postoje dvereprezentacije A=0: Ac=0 i Ac=rn-1. Opseg celih brojeva sa predznakom je:

12

10 nrA podrazumevajui da je osnova parna.

A 0 1 2 121

nr 1( 1)2nr -1 0

Ac 0 1 2 12

1nr nr

2

1 rn-2 rn-1

Primer 1: Predstaviti 34 A u sistemima komplementa dvojke i jedinice.Reenje:U simetrinom opsegu: 328,82/43

max nrLLLA nn

A3 2 1 0 -0 -1 -2 -3 -4

Ac 3 2 1 0 0 7 6 5 4Komplement dvojkeX 011 010 001 000 000 111 110 101 100

Ac 3 2 1 0 7 6 5 4 3Komplement jediniceX 011 010 001 000 111 110 101 100 -

Osobine sistema komplementa dvojke i jedinice (iz primera):

1. Reprezentacija 0:1.1.u sistemu komplementa dvojke jedinstvena1.2.u sistemu komplementa jedinice dve reprezentacije 0.2. Opseg brojeva:2.1.u sistemu komplementa dvojke nije simetrian: 12,2 11 nn . Sistem nije zatvoren u

odnosu na operaciju promene znaka.2.2.u sistemu komplementa jedinice je simetrian: 12,12 11 nn .


13/82



Primer 2: Predstaviti broj A=-236(8) u komplementu osnove.Reenje:Prvi nain:r=8, pretpostavimo da je n=3 dovoljno veliko.

103

5128 nrL

108 15868382236 A

2562

158 LA , to znai da je n=3 dovoljno veliko.

10354158512 ALAc

8542

508/5

458/44

2448/354

cA

Drugi nain:L=512(10)=1000(8)

8236A

888 5422361000 cA

Primer 3: Predstaviti broj 162A8A u komplementu cifre:

Reenje:Prvi nain:

r=16, pretpostavimo 103

409511613 nrLn

1016 22102161016828 AA

3,2

4095

22210 n

LA , poto nije dovoljno veliko, uzimamo

6553511644 Ln

63325221065535 ALAc

F15016/15

771516/247

5524716/3957

D13395716/63325X

16F75DcA

Drugi nain:

16104

65535116 FFFFL

L: FFFF(16)

:A -8A2(16)

Ac: F75D(16)


14/82



Promena znakaAko se sa F oznai broj (-A), tada vai da je

cccALAF , gde je L komplementaciona

konstanta.Dokaz:

cc

cc

cc

ALA

A,A

AA,LAL

A,ALL

AA,LAL

AA,L

A,AA

-A,AL

AA,A

0

0

0

0

0

0

0

0

U komplementu jedinice: ccc

n

cAAAA 111112 (bit po bit)

U komplementu dvojke: 11122 cc

n

c

n

cAAAA

Primer:a) n=4, komplement jedinice

412118111011 4 AAc

4440100 AAAc

b) n=4, komplement dvojke

555010100011

0100

516118111011

AAA

A

AA

c

c

cc

Drugi, jednostavniji, nain za odreivanje drugog komplementa podrazumeva da se binarnareprezentacija broja deli na dva dela. Desni deo ine, itajui sa desna na levo, sve nule i prva

jedinica na koju se naie (u slu

aju da je krajnje desna cifra jedinica, onda se desni deo sastoji samood te jedinice). Taj deo se samo prepisuje u rezultat. Levi deo ine preostale cifre, i taj deo se bit po

bit komplementira:

primer za n=4:

0101

1|010

1|101

1011cA

primer za n=8:

01011100

100|01011

100|10100

10100100cA


15/82



Sabiranje u sistemu komplementa dvojke (L=2n)Zbir brojeva A i B: F=A+B.Prilikom sabiranja dva broja moe doi do prekoraenja opsega (overflow: V), to daje pogreanrezultat. Prekoraenje se dogodilo kada suAi B negativni(An-1=1, Bn-1=1), a zbir je nenegativanbroj(Fn-1=0) ili kada suA i B nenegativni(An-1=0, Bn-1=0), a zbir F negativanbroj (Fn-1=1).

111111 nnnnnn FBAFBAV

Prenos u i-ti razred obeleavamo sa Ci.Ako suAc i Bckomplementi dvojke brojevaAi B, a Fckomplement F, moe se pokazati da vai

mod 2nc c c A B F

Drugim reima: sabirajui po modulu 2n brojeve predstavljene u komplementu 2, dobijamo njihovzbir predstavljen u komplementu 2. Razmotriemo posebno etiri mogua sluaja:

1. 0,00,11

nn BABBA

Poto postoji n binarnih razreda:

ako je ;0,02 11

VFBA nn

ako je 1,12

1

1

VFBAn

n (greka zbog prekoraenja).

c

nnn

ccFFBABABA 2mod2mod0,02mod

Primeri: za n=4 (L=24=16)A=3, B=2 A=5, B=6

Ac: 0011 = 3 Ac: 0101 = 5

Bc: 0010 = 2 Bc: 0110 = 6

Fc: 0101 = 5 Fc: 1011 = 582/11 FL

Ci+1: 0010 Ci+1: 0100,prekoraenje!!!

2. 1,00,11

nn BABBA 0,0:

1 VFBA n 0,1:

1 VFBA n

nnnnncc

BABABA 2mod22mod22mod

nn BA 2mod2 poto je nnn xx 2mod2mod2 , vai nBA 2mod

Primeri: za n=4 (L=24

=16)a)A= 6, B= -3 b)A=3, B=-6Ac: 0110 = 6 Ac: 0011 = 3Bc: 1101 = 13 Bc: 1010 = 10Fc: 0011 = 3 Fc: 1101 = 32/13 FL Ci+1: 1100 Ci+1: 0010

3. 0,10,11

nn BABBA 0,1:

1 VFBA n 0,0:

1

VFBAn

nnnnncc

ABABA 2mod22mod22mod

c

nnnFBAAB 2mod2mod2


16/82



Primeri: za n=4 (L=24=16)a)A= -7, B= 5 b)A=-2, B=3

Ac: 1001 = 9 Ac: 1110 = 14Bc: 0101 = 5 Bc: 0011 = 3Fc: 1110 = 22/14 FL Fc: 1110 = 1Ci+1: 0001 Ci+1: 1110

4. 1,10,11

nn BABBA


ako je ;0,121

1

VFBAn

n

ako je 1,021

1

VFBAn

n , (greka usled prekoraenja)

nnnncc

BABA 2mod222mod

nnnnnn

BABA 2mod222mod22 c

n

ccFBA 2mod

Primeri: za n=4 (L=24=16)A=-1, B=-3 A=-4, B=-7Ac: 1111 = 15 Ac: 1100 = 12Bc: 1101 = 13 Bc: 1001 = 9Fc: 1100 = 42/12 FL Fc: 0101 = 5Ci+1: 1111 Ci+1:1000, prekoraenje!!!

Ako se sa Cn-1 oznai prenos u poslednji (n-1) razred (razdred znaka), a sa Cn prenos iz poslednjegrazreda moe se zakljuiti da se prekoraenje moe raunati kao:

1 nn CCV (ekskluzivno ili).


17/82



Oduzimanje u sistemu komplementa dvojke (L=2n)Razlika brojeva A i B: F=A-B.Prilikom oduzimanja dva broja moe doi do prekoraenja opsega (overflow: V), to daje pogreanrezultat. Prekoraenje se dogodilo (V=1) kada je Anegativan (An-1=1), B nenegativan (Bn-1=0), arazlika F nenegativanbroj (Fn-1=0), ili kada jeA nenegativan(An-1=0), B negativanbroj (Bn-1=1), arazlika F negativanbroj (Fn-1=1).

111111 nnnnnn FBAFBAV Pozajmicu iz i-tog razreda obeleavamo sa Ci.

Ako suAc i Bc komplementi dvojke brojeva A i B, a Fc komplement F, moe se pokazati da vai mod 2 .nc c c A B F

Dokaz:Kako iz: ,22 n

ccc

n

ccBBBBLB dobija se:

nnc

n

ccBABA 2mod22mod poto je nnn xx 2mod2mod2 , vai

n

cc BA 2mod zbog nn

cc XAXA 2mod2mod , vai

c

nnn

cFFBABA 2mod2mod2mod

Diskusija:1. 0,00,

11 nn BABBA

1.1. 0,0:1

VFBA n 1.2. 0,1:

1 VFBA n

Primeri: za n=4 (L=24

=16)a)A= 3, B=2 b)A=5, B=6Ac: 0011 = 3 Ac: 0101 = 5Bc: 0010 = 2 Bc: 0110 = 6Fc: 0001 = 1 Fc: 1111 = 12/15 FL Ci+1: 0000 Ci+1: 1110

2. 1,00,11

nn BABBA


2.1.ako je ;0,02 11

VFBA nn

2.2.ako je 1,12

1

1

VFBAn


Primeri: za n=4 (L=24=16)A=3, B=-2 A=5, B=-6Ac: 0011 = 3 Ac: 0101 = 5Bc: 1110 = -2 Bc: 1010 = 6Fc: 0101 = 5 Fc: 1011 = 582/11 FL Ci+1: 1100 Ci+1: 1010 prekoraenje!!!


18/82



3. 0,10,11

nn BABBA


3.1.ako je ;0,121

1

VFBAn

n

3.2.ako je 1,021

1

VFBAn


Primeri: za n=4 (L=24=16)A=-4, B=3 A=-8, B=2Ac: 1100 = 12 Ac: 1000 = 8Bc: 0011 = 3 Bc: 0010 = 2Fc: 1001 = 782/9 FL Fc: 0010 = 6Ci+1: 0011 Ci+1: 0110 prekoraenje!!!

4. 1,10,11

nn BABBA 4.1. 0,1:

1 VFBA n

4.2. 0,0:1

VFBA n

Primeri: za n=4 (L=24=16)A=-7, B=-4 A=-1, B=-3Ac: 1001 = 9 Ac: 1111 = 15Bc: 1100 = 12 Bc: 1101 = 13Fc: 1101 = 32/13 FL Fc: 0010 = 2Ci+1: 1100 Ci+1: 0000

Ako se sa Cn-1 oznai pozajmica iz poslednjeg (n-1) razreda (razreda znaka), a sa Cn pozajmica iznepostojeeg (n-tog) razreda moe se zakljuiti da se prekoraenje moe raunati kao:

1nn CCV .

Zadatak B1Neka se u osmobitnim lokacijama ai bnalaze brojeviAi B. Odrediti broj Fkoji sadri lokacija fnakonizvrene operacije oduzimanja F=A-Bi vrednost indikatora u sledeim sluajevima:

a) A=+1011101, B=+0110011;b) A=+1011101, B=-0110011;c) A=-1011101, B=+0100010;d) A=-1011101, B=+1010001;e) A=-1011101, B=-0100010.

Brojevi se u raunaru predstavljaju u komplementu dvojke, na irini od 8 bita.

Reenje:n=8, L=2n=28=256, L/2=128

a)Ac: 01011101 = 93 A=93 b) Ac: 01011101 = 93 A=93Bc: 00110011 = 51 B=51 Bc:11001101 = 205 A=-51Fc: 00101010 = 42 Fc: 10010000 = 144Ci+1: 00101010 = 42 Ci+1: 10000000

;4212842 FFc

;112256144128144 FFc

000 V 101 V

Na isti nain se reavaju problemi pod c), d) i e).


19/82



Zadaci sa vebi na tabli

Zadatak IZ1Sadraj 10-bitne memorijske lokacije je 2A616. Ako je na posmatranoj memorijskoj lokaciji smetenceo broj (INTEGER) predstavljen u punom komplementu, kolika je decimalna vrednost posmatranogcelog broja?

A) 678

B) 346C) 346

Reenje:062 Ax (jer je bit najveeg znaaja = 1)

159x +1

101016

3463461016516115 xAx

Odgovor: C

Zadatak IZ2U raunaru, koji ima memorijsku re irine 14b, izvrena je operacija: Y:=MAXINT+X. Ako je preoperacije sadraj memorijske lokacije X: 2A6C16, kolika je decimalna vrednost rezultata Y nakonizvrene operacije?

A) 2667B) 19051C) 1428

Reenje:MAXINT = 1FFF

+ X = 2A6C

Y = 0A6B > 0 Y = (10*16+6)*16+11 = 266710(vodee cifre su namerno prikazane umanjene da bi se naglasilo da predstavljaju samo dva bita, a neetiri kao ostale cifre u posmatranim brojevima)

Odgovor: A


20/82



Zadatak IZ (Oktobar 2007)Posmatra se raunar koji radi sa 9-bitnim brojevima predstavljenim u komplementu dvojke. Koja sevrednost dobije kada se na ovom raunaru izrauna izraz (A-B)-(C-D)? Vrednosti operanada A i Bsu 21710 i -F116, predstave operanada C i D su 11516 i 0110001012.

A) -12210

(B) -8616C) 1011110102

Reenje:Zadatak ilustruje razliku izmeu vrednosti operanda i predstave operanda u memoriji raunara.

Vrednost operanda se dobija interpretacijom predstave operanda, primenom zadatih pravila. Uovom sluaju, pravila su odreena sistemom komplement dvojke.

Zadatak je mogue reiti na vie naina. Ovde e biti prikazana dva pristupa.

1. Raunanje na osnovu vrednosti operanadaZa operande A i B su date njihove vrednosti. Pri tome, operand A je dat u decimalnom brojnomsistemu, a operand B u heksadecimalnom. Radi jednostavnijeg rauna, najpre treba odrediti vrednostoperanda B u decimalnom brojnom sistemu: B = - (15 * 161 + 1 * 160 ) = -241.

Za operande C i D su date njihove predstave. Pri tome, predstava operanda C je data uheksadecimalnom brojnom sistemu, a predstava operanda D je data u binarnom brojnom sistemu.Slino prethodnom sluaju, da bi se jednostavnije odredile vrednosti ovih operanada, treba ihprikazati u binarnom brojnom sistemu: tako se direktno vidi vrednost svakog bita broja, ime sesmanjuje mogunost greke prilikom interpretacije. Reprezentacija C: 1000101012. Oigledno, broj ulokaciji C je negativan. Da bi se odredila njegova vrednost, najpre ga treba pretvoriti u pozitivan broj.

Reprezentacija C : 0111010112, odnosno C = -235. Odreivanje vrednosti operanda C je moglo i jednostavnije da se obavi: negativan broj se interpretira kao ceo broj bez znaka i od njega seoduzme 2n, gde je n u ovom sluaju 9, dakle oduzme se 512. Interpretacijom reprezentacijeoperanda C kao celog broja bez znaka dobija se vrednost 256+16+4+1 = 277. Prema tome,277-512 = -235, to je traena vrednost. Slino se dobija D = 128+64+4+1 = 197.

Sada treba razmatrati parcijalne sume A-B i C-D zato to raunar rezultat svake od njih mora dasmesti u memoriju pre nego to obavi sledeu operaciju. Prilikom svake od operacija moe doi doprekoraenja, pa je zato preporuljivo da se najpre odrede vrednosti minINT i maxINT za ovajraunar. Za 9-bitni raunar, minINT = -256, maxINT = 255. A-B = 217-(-241) = 458. Oigledno

dolazi do prekoraenja (rezultat je vei od maxINT). Prekoraenje oznaava da je rezultatoperacije netaan. Ipak, rezultat te operacije (iako netaan) e biti upisan u memoriju raunara.Vrednost rezultata je 458-512 = -54. Slino tome, C-D = -235-197 = -432. I u ovom sluaju dolazi doprekoraenja a rezultat je -432+512 = 80. Konano, vrednost celog izraza je -54-80 = -134.Oigledno, odgovor pod A) je netaan. Takoe, odgovor pod C) je netaan jer je u pitanju pozitivanbroj, a vrednost ovog izraza je negativan broj. Odgovor pod B) je taan: 8*161 + 6 * 160 = 128+6 =132.

NAPOMENA: u zadatku se traila VREDNOST rezultata. Da se traila predstava rezultata umemoriji, onda bi reenje pod C) bilo tano. Takoe treba primetiti da je prekoraenje kod

aritmetikih operacija sasvim normalna pojava i da rezultat, iako netaan, postoji.


21/82



2. Raunanje na osnovu binarne reprezentacije operanadaBinarna reprezentacija operanda A je 0110110012, a operanda B je 1000011112. S obzirom na to da

je operand B negativan i da se trai razlika A-B, jednostavnije je da se B pretvori u pozitivan broj i dase onda odredi zbir.

A 0 1 1 0 1 1 0 0 1-B 0 1 1 1 1 0 0 0 1+ 1 1 1 0 0 1 0 1 0

Na slian nain se odreuje predstava razlike C-D:C 1 0 0 0 1 0 1 0 1D 0 1 1 0 0 0 1 0 1- 0 0 1 0 1 0 0 0 0

Konano: A-B 1 1 1 0 0 1 0 1 0C-D 0 0 1 0 1 0 0 0 0- 1 0 1 1 1 1 0 1 0

Na kraju ostaje da se odredi VREDNOST rezultata ija je PREDSTAVA na datom raunaru1011110102. Oigledno, u pitanju je negativan broj, a njegova apsolutnavrednost je 100001102 =8616 = 13210. Prema tome, taan rezultat je B) poto je u pitanju negativan broj.

DiskusijaOvaj zadatak pokazuje da je veoma bitno praviti razliku izmeuVREDNOSTI i PREDSTAVE broja.Osim toga, naroito ako se zadatak reava na 2. nain (od naina ovde prikazanih), ne treba prebrzodonositi zakljuak da je C) taan odgovor samo zato to je ponuen isti niz bita.


22/82



Zadaci za samostalnu vebu (sa ranijih ispita)U nekom raunaru celi brojevi se predstavljaju u 10-bitnim lokacijama u drugom (potpunom)komplementu. U kojem od navedenih sluajeva e prilikom sabiranja celih brojeva I i J doi doprekoraenja? A) Sadraj lokacije u koju je smeteno I je 3FA(16), a lokacije u koju je smeteno J je 1FF(16)B) Vrednost broja I je -202, a vrednost broja J je -310 u dekadnom brojnom sistemu.

(C) Vrednost broja I je 110, a vrednost broja J je 423 u dekadnom brojnom sistemu.Na raunaru koji ima memorijsku re irine 14 bita izvri se operacija: Y:=minint-X. Ako je preoperacije sadraj memorijske lokacije X, koja sadri 14-bitni ceo broj, jednak 2A6C16, kolika jedecimalna vrednost celobrojnog rezultata Y nakon izvrene operacije?(A) -2668 B) 2668 C) 2667

Celi brojevi A, B i C prikazani su u drugom komplementu na irini od 8 bita. Neka je vrednost brojaA=10510, a binarna predstava broja B u memoriji se moe zapisati kao 7516. Ako je potrebnoizraunati izraz A:=A-B+C, koji je uslov neophodan i dovoljan da bi se obezbedilo da pri raunanju nedoe do prekoraenja? Napomena: Prvo se vri oduzimanje, pa sabiranje. A) C>0 (B) C-116(10) C) C104(10)

Ukoliko je sadraj lokacije u koju je smeten najvei ceo broj MAXINT prikazan u drugomkomplementu na nekom raunaru 7FFF(16), kako onda na tom raunaru izgleda prikaz broja koji sedobija kao zbir MININT i broja iji je prikaz 03F0(16)? A) 1000 0011 1111 0001(2) B) 101 740(8) C) 43F0(16)

Dva broja prikazana su u drugom komplementu na duini od 8 bita. Vrednost broja A iznosi -99, abinarni sadraj lokacije u kojoj se nalazi drugi broj B je 11001011. Kolika je vrednost razlike A-B? A) 104 B) -47 (C) -46


23/82



PICOCOMPUTERReferentni prirunik za picoComputer

O P E R A T I V N A M E M O R I J A C E N T R A L N I P R O C E S O R

0 0101 1010 0011 1100123456

FIKSNAZONA

PODATAKA

7 1110 1000 0000 11118..

.

PROGRAM(mainske instrukcije)

.

.SLOBODNA ZONA

.

.PODACI

.

.

.m-1 S T E K

15 0VELIINA MEMORIJE: m 65536 ( REI SU DUINE 16b )

SLIKA 1 SASTAVNI DELOVI I ORGANIZACIJA pC-a

Za komuniciranje sa spoljnim svetom (ulaz podataka i prikaz rezultata), pC koristi terminal,koji predstavlja dva ureaja tastaturu i ekran u istom kuitu. Unos podataka u memoriju pC-a jeposredstvom tastature, a prikaz podataka iz memorije je na ekranu. Sva tri sastavna dela pC-a(memorija, procesor i terminal), razmenjuju podatke preko odgovarajue bidirekcione magistrale.

Struktura mainskih instrukcija, koje izvrava pC, je:

kd operacije i1 a1 i2 a2 i3 a3

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

Kd operacije (bitovi 1215) je etvorobitan, to znai da je mogue direktno definisati najvie 16razliitih kodova operacije, a potrebno je obezbediti instrukcije bar za sledea etiri osnovna tipa:

1. instrukcije prenosa podataka2. aritmetike instrukcije3. kontrolne instrukcije4. ulaznoizlazne instrukcije

T E R M I N A L

MDIR

ADRESABILNIREGISTRI

INTERNIREGISTRI

SPPC

E K R A N

T A S T A T U R A

MAGI

STR

AL

A

A L U

T E R M I N A LSLOBODNA ZONA

vrh

dno


24/82



Tabela 1.1: Osnovne mainske instrukcije koje izvrava pC

NAZIV BINARNI I SIMBOLIKIINSTRUKCIJE KD OPERACIJE OPIS AKTIVNOSTI, KOJU REALIZUJE INSTRUKCIJA

POMERANjE 0000 MOV i3=0, a3=0 A1:=A2i3=1, a3=0 A1:=val(val(PC))i3=0, a3>0 A1[j]:=A2[j], j=0,1,,val(A3)1

i3=1, a3=7 A1[j]:=A2[j], j=0,1,,val(val(PC))1SABIRANjE 0001 ADD1001 ADD

ODUZIMANjE 0010 SUB1010 SUB

MNOENjE 0011 MUL1011 MUL

DELjENjE 0100 DIV1100 DIV

A1:=A2+A3 ( svi argumenti su promenljive )A1:=A2+val(val(PC)), ili A1:=val(val(PC))+A3

A1:=A2A3 ( svi argumenti su promenljive )A1:=A2val(val(PC)), ili A1:=val(val(PC))A3

A1:=A2A3 ( svi argumenti su promenljive )A1:=A2val(val(PC)), ili A1:=val(val(PC))A3

A1:=A2/A3 ( svi argumenti su promenljive )A1:=A2/val(val(PC)), ili A1:=val(val(PC))/A3

Za kodove > 8 mora biti adr(A2)>0 adr(A3)>0USLOVNI SKOK, AKO 0101 BEQJE PRVI ARGUMENTJEDNAK DRUGOM

USLOVNI SKOK, AKO 0110 BGTJE PRVI ARGUMENT

VEI OD DRUGOG

Uslovni skokovi realizuju operaciju: ako je Uslov_Ispunjen PC:=Adresa_Skoka. Mogue je koristiti tri vrste uslova:(1) A1=A2, ili A1>A2 ( kodirano: a1>0 a2>0 )(2) A1=0, ili A1>0 ( kodirano: a1>0 i2=a2=0 )(3) 0=A2, ili 0>A2 ( kodirano: i1=a1=0 a2>0 )Uslovi: adr(A1)>0 adr(A2)>0Dozvoljene su dve adrese skoka:(1) i3=0 0a37 Adresa_Skoka=val(a3)(2) i3=1 a3=0 Adresa_Skoka=val(val(PC))

ULAZ PODATAKA 0111 IN

IZLAZ PODATAKA 1000 OUT

Prenos n celobrojnih vrednosti, posredstvom tastature, na lokacije A1[j],J=0,,n-1. Ako je i2=0 bitovi 06 desne polurei sadre n, pa jen127. Ako je i2=1 a2=0 n=A3. Uvek mora biti n>0.

Prenos n celobrojnih veliina, sa lokacija A1[j], j=0,,n1 na ekranterminala. Interpretacija n je ista, kao u instrukciji IN.

SKOK U 1101 JSRPOTPROGRAM

POVRATNI SKOK 1110 RTSIZ POTPROGRAMA

stek:=PC+1; PC:=val(val(PC)). Poetna vrednost PCa nakon skoka jeadresa druge rei instrukcije.

PC:=stek (programski broja se puni vrednou povratne adrese uzete sasteka)

KRAJ RADA 1111 STOP Prestanak inkrementiranja PC-a. Ako je sadraj adresnih polja razliit od0000, onda e, na ekranu terminala, pre zavretka rada, biti prikazanekrajnje vrednosti odgovarajuih argumenata ( ovako nije mogue prikazati

krajnji sadraj lokacije 0 ).

OBJANjENjE: A1[j] je oznaka lokacije, ija je adresa adr[A1]+j, j0. A1[0] je isto to i A1.


25/82



Tabela 1.2: Pregled strukture mainskih instrukcija za pC

KDOPERACIJE MAINSKA INSTRUKCIJA OPIS AKTIVNOSTI, KOJU INSTRUKCIJA REALIZUJE

MOV 0000 0000 xxxx yyyy 0000

0000 xxxx ???? 1000cccc cccc cccc cccc

0000 xxxx yyyy 0nnn

0000 xxxx yyyy 1111cccc cccc cccc cccc

X:=Y

X:=C

X[j]:=Y[j], j=0,..........,N1

X[j]:=Y[j], j=0,..........,C1

ADD b001SUB b010MUL b011DIV b100

0kkk xxxx yyyy zzzz

1kkk xxxx yyyy 0000cccc cccc cccc cccc

1kkk xxxx 0000 zzzzcccc cccc cccc cccc

X : = Y Z, { +, , *, / }

X : = Y C ( yyyy>0 )

X : = C Z ( zzzz>0 )

BEQ 0101BGT 0110

kkkk xxxx yyyy 1000cccc cccc cccc cccc

kkkk xxxx 0000 0nnn

0101 xxxx xxxx 1000cccc cccc cccc cccc

if X Y then PC:=cccccccccccccccc( xxxx>0, yyyy>0 )

if X Y then PC:=val(nnn) ( xxxx>0 )

PC:=cccccccccccccccc ( xxxx>0 )( GOTO C )

IN 0111OUT 1000

kkkk xxxx 1000 nnnn

kkkk xxxx 0ccc cccc

ULAZ/IZLAZ za X[j], j=0,...........,N1

ULAZ/IZLAZ za X[j], j=0,...........,C1

JSR 1101

RTS 1110

1101 ???? ???? ????cccc cccc cccc cccc

1110 ???? ???? ????

Stek:=PC+1, PC:=cccccccccccccccc

PC:=stek

STOP 1111 1111 0000 0000 0000

1111 xxxx yyyy zzzz

Kraj rada

Prikaz X, Y i kraj rada ( xxxx>0, yyyy>0 )


26/82



Tabela 1.3: Sintaksa simbolikog mainskog jezika pCSintaksa SMJ za pC je ovde priloena u notaciji sa zagradama.

Specifikacija simbola: simbol = konstanta [ ; komentar ]

Specifikacija poetka programa: ORG konstanta [ ; komentar ]

Sintaksa izvrnih instrukcija:

];[)(

,)(

,)(

:][

];[]:[

];[]:[

];[

)(

#

konstanta

,)(

]:[

];[)(

,

)(,0

0,)(

)(,

)(

:][

];[

)(,

#

konstanta

)(

#

konstanta

,)(

,)(

:][

];[

#

konstanta

,)(

)(

#

konstanta

,)(

:

komentarsimbol

simbolsimbol

simbolsimbol

simbolSTOPsimbol

komentarRTSsimbol

komentarsimbolJSRsimbol

komentar

simbol

simbol

simbol

simbol

simbol

OUT

INsimbol

komentarsimbol

simbol

simbol

simbol

simbol

simbol

simbol

simbol

simbol

simbol

BGT

BEQsimbol

komentar

simbol

simbol

simbol

simbol

simbol

simbol

simbol

simbol

simbol

simbol

DIV

MUL

SUB

ADD

simbol

komentar

simbol

simbolsimbol

simbol

simbol

simbol

simbol

simbol

simbolMOVsimbol


27/82



Uputstvo za korienje programa PCAS

Poetak rada: treba pokrenuti PCAS:EXEPCAS je prevodilac za simboliki mainski jezik pC-a i simulator pC-a. Princip rada: unoenje zahteva

je omogueno izborom jedne od ponuenih mogunosti, ili unoenjem traenog podatka principMENU-a.

Raspoloive operacije ( glavni MENU ):

A Uitavanje programa za pC ( simboliki mainski jezik ). PCA je standardni tip za datoteke saizvornim tekstom ( ime_prog.PCA ). Datoteke kreirati EDITOR-om teksta.

M Uitavanje programa za pC ( mainski jezik ). HEX je standardni tip za datoteke sa mainskimProgramom ( ime_prog.HEX ). Ove datoteke nastaju posle prevoenja izvornog programa,ali mogu biti kreirane i EDITOR-om teksta. Format datoteke je:

aaaa Poetna adresa programa (hex)iiii

iiiiSukcesivne mainske rei programa (hex)

S Ispisivanje teksta izvornog programa, koji je u radnoj memoriji

D Prikazivanje mainskog programa, koji je u radnoj memoriji

C Prevoenje simbolikog mainskog programa, koji je u radnoj memoriji, formiranje datotekeime_prog.HEX i ubacivanje mainskog programa u radnu memoriju nakon zahteva

R Izvravanje mainskog programa, koji je u radnoj memoriji

T Naizmenino ukljuivanje/iskljuivanje trasiranja rada programa. Ako je ukljueno trasiranje preizvravanja svake mainske naredbe, bie prikazan trenutni sadraj brojaa naredbi, bieprikazani sadraji memorijskih lokacija, ije su adrese 07 i bie prikazan kd te naredbe.

L Naizmenino ukljuivanje/iskljuivanje zapisivanja podataka o radu sistema PCAS u datoteciime_prog.LOG ( dnevnik-datoteka; izvetaj-datoteka ). Ako u radnoj memoriji ne postoji programu trenutku ukljuivanja zapisivanja PCAS.LOG je naziv datoteke, pa je omogueno beleenje

rezultata rada korisnikovog programa zbog kasnijeg lakeg tampanja.

H Traenje pomoi o nainu korienja PCASA-a i o sintaksi simbolikog mainskog jezika za pC

Q Kraj radaUobiajeni redosled:

$ EDIT ime_prog.PCA PRIPREMA IZVORNOG PROGRAMA$ PCAS STARTOVANjE PCAS-A

A UBACIVANjE IZVORNOG PROGRAMAL POETAK FORMIRANjA ime_prog.LOGC PREVOENjE IZVORNOG PROGRAMA

R IZVRAVANjE PREVEDENOG PROGRAMAQ KRAJ RADA ( KRAJ KORIENjA PCAS-A )$ TYPE ime_prog.LOG BRZI PREGLED DOBIJENIH REZULTATA


28/82



Zadatak Z22Sastaviti program na simbolikom mainskom jeziku raunara pC za izraunavanje i ispisivanjevrednosti izraza 22 bbaac , gde su a i b celi brojevi koji se uitavaju sa tastature.

A=1B=2C=3T=4ORG 8

IN A,2MUL C,A,AMUL T,A,BADD C,C,TMUL T,B,BADD C,C,TSTOP C

Zadatak Z23s (skraena varijanta zadatka sa strane 23)Sastaviti program na mainskom jeziku pC koji uitava 2 cela broja sa tastature i ispisuje ih ponerastuem redosledu.

Reenje:Osnovni algoritam:

a) Uitaj a i bb)Ako je aB, skoimo na (7) 9 BGT 0 #A 0 #B 1 0 6128

10 adr(naredba 7) 00103. Ako je A=B, skoimo na (7) 11 BEQ 0 #A 0 #B 1 0 5128

12 adr(naredba 7) 00104. P A 13 MOV 0 #P 0 #A 0 0 00105. A B 14 MOV 0 #A 0 #B 0 0 01206. B P 15 MOV 0 #B 0 #P 0 0 02007. Ispii A i B i zavri 16 STOP 0 #A 0 #B 0 F120

Jednostavnije reenje:a) Uitaj a i bb)Ako je a>b ispii a i b i zaustavi programc) U suprotnom ispii b i a i zaustavi program

Napomena: reenje jeste jednostavnije ali je u praksi primenljivo samo u situaciji kada se obraujudva broja (porede po vrednosti). Takoe, dobra praksa je da se izbegava viestruka pojavainstrukcije za prekid programa (STOP) jer to program generalno ini manje preglednim i teim za

razumevanje.

A=1B=2ORG 8

IN A,2BGT A,B,ISPIS1STOP A,B

ISPIS1: STOP B,A


29/82



Zadatak Z23Sastaviti program na mainskom jeziku raunara pC koji uitava 3 cela broja sa tastature i ispisuje ihpo nerastuem redosledu.


a) Uitaj A, B, C

b)Ako je A < B zameni im mestac)Ako je A < C zameni im mestad)Ako je B < C zameni im mestae) Ispii A, B, C i zavri

Napomena: savetuje se studentima da za ovaj zadatak sami pokuaju da napiu program nasimbolikom mainskom jeziku korienjem reenja iz prethodnog zadatka.

Zadatak Z24

Sastaviti program na mainskom jeziku raunara pC koji uitava n celih brojeva sa tastature, a zatimizraunava i ispisuje celobrojni deo aritmetike sredine tih brojeva.


a) Uitaj nb) Uitaj n celih brojevac) Izraunaj sumu uitanih brojevad) Srednja vrednost je suma podeljena sa ne) Ispii rezultat i zavri

N=1SUMA=2

NIZ=3I=4

ADRNIZ=100ORG 8

IN NSUB SUMA,SUMA,SUMA

MOV NIZ,#ADRNIZIN (NIZ),N

MOV I,N

CIKLUS: ADD SUMA,SUMA,(NIZ)SUB I,I,1

ADD NIZ,NIZ,1BGT I,0,CIKLUSDIV SUMA,SUMA,NSTOP SUMA

Zadatak IZ6Koji od sledeih programa za pC ispisuje vrednost 1?

A) A=1ORG 8MOV (A), #ASTOP A

B) A=1ORG 8MOV A, #ASTOP A

C) A=1ORG 8OUT ASTOP

Obrazloenje:Program pod A) upisuje 1 na lokaciju, ija je adresa sluajna, jer sadraj lokacije A nije definisan rezultat ispisivanja sadraja lokacije A je sluajna vrednost.Program pod B) upisuje 1 na lokaciju A rezultat ispisivanja sadraja lokacije A je 1.Program pod C) ispisuje sluajnu vrednost ( sadraj lokacije A ), koja nije definisana.

Odgovor: B


30/82



Zadatak Z25Sastaviti program na simbolikom mainskom jeziku raunara pC za izraunavanje zbira prvih nprirodnih brojeva i zbira kvadrata prvih n prirodnih brojeva.Reenje:

S1 =

n

i

nni

1 2

1S2 =

n

i

nnni

1

2

6

121

Zadatak Z26Sastaviti program na simbolikom mainskom jeziku raunara pC kojim se na osnovu dva data nizabrojeva a[i] i b[i] formira novi niz c[i], tako da vai c[i] = a[i] + b[i] ( i = 0, 1, 2, ..., n 1 ).

Zadatak IZ7Koje vrednosti ispisuje priloeni program za pC?

X=1Y=2Z=3ORG 8

MOV X, #YADD Y, X, #XMOV (Y), #YSTOP X, Y, Z

A) 1 2 3B) 2 3 3C) 2 3 2

Obrazloenje:X=1 ; promenljiva X je na lokaciji, ija je adresa 1

Y=2 ; promenljiva Y je na lokaciji,ija je adresa 2Z=3 ; promenljiva Z je na lokaciji, ija je adresa 3ORG 8 ; program e biti smeten od adrese 8 u memoriji pCMOV X, #Y ; X := adr ( Y ) = 2

ADD Y, X, #X ; Y := 2 + adr ( X ) = 2 + 1 = 3MOV (Y), #Y ; Z := adr ( Y ) = 2STOP X, Y, Z ; bie ispisane vrednosti: 2 3 2

Odgovor: C

Zadatak Z27Sastaviti program na simbolikom mainskom jeziku raunara pC kojim se iz datog niza celih brojevaizostavljaju svi elementi ije su vrednosti parne.

Zadatak Z28Sastaviti potprogram na simbolikom mainskom jeziku raunara pC za izraunavanje n!.


31/82



Zadatak Z29 (dodat u verziji 2009-10-27)

ta ispisuje sledei program na SMJ za pC, ako se unesu vrednosti 10 i 12?AdrA=100A=1V=2T=3R=4

ORG 8IN VJSR BOUT VIN VJSR BSTOP V

B: MOV A, #AdrAC: DIV T, V, 2MUL T, T, 2BEQ V, T, D

MOV (A), 1

BEQ V, V, ED: MOV (A), 0E: ADD A, A, 1

DIV V, V, 2BGT V, 0, C

MOV R, #AdrAMOV V, (R)

F: ADD R, R, 1BEQ A, R, KRAJ

MUL V, V, 2

ADD V, V, (R)BEQ V, V, FKRAJ: RTS

A) 14 16 (B) 5 3 C) 13 7

Zadatak IZ24U memoriji picoComputera nalazi se lista celih brojeva predstavljena na sledei nain: ako se nalokaciji sa adresom A nalazi ceo broj, na lokaciji sa adresom A+1 se nalazi adresa sledeeg celog

broja u listi. Adresa 0 oznaava kraj liste. ta oznaava potprogram PP?U=1 PP: MOV S,0S=2 PETLJA: ADD S,S,(U)ORG=8 ADD U,U,1

BEQ (U),0,KRAJMOV U,(U)BEQ U,U,PETLJA

KRAJ: RTS

A) Broj elemenata u listi na koju ukazuje U.(B) Zbir elemenata u listi na koju ukazuje U.C) Zbir elemenata uveanih za jedan u listi na koju ukazuje U.

Zadatak IZ 2006-11-30 (Kolokvijum 2006)Sledei program na simbolikom mainskom jeziku za picoComputer, za zadate ulazne vrednosti 3 i 4respektivno, ispisuje:

M=0N=1Q=2X=3Y=4Z=5ORG 8

MOV M, #QIN Q, MSUB (X), X, #XSUB (Y), (Q), (X)DIV Z, (N), (X)OUT M, XSTOP

A) 3 4 1 4B) 3 4 -1 4(C) 2 3 3 4

Zadatak IZ 2006-11-30 (Kolokvijum 2006) Ako su ispravno deklarisani svi simboli, a u lokaciji A se nalazi adresa prvog elementa niza celihbrojeva ija se duina nalazi u lokaciji N, sledei potprogram PP:PP: MOV I,0

SUB S,S,SL0: BGT 0,(A),L1

ADD S,(A),SBEQ S,S,L2

L1: SUB S,S,(A)L2: ADD A,A,1

ADD I,I,1BGT N,I,L0

RTS

A) u lokaciju S smeta sumu apsolutnih vrednosti elemenata nizaB) u lokaciju S smeta sumu pozitivnih vrednosti elemenata niza(C) u lokaciju S smeta sumu pozitivnih umanjenu za sumu negativnihvrednosti elemenata niza


32/82



Zadatak IZ 2006-11-30 (Kolokvijum 2006)ime treba zameniti #### u sledeem programu za picoComputer da bi on za uitanu pozitivnuvrednost N ispisivao sve cele brojeve vee od 1 sa kojima je uneti broj deljiv?

N=1I=2L=3T=4

ORG 8IN NDIV L,N,2

MOV I,2

####OUT I

L1: ADD I,I,1BEQ I,I,L0

L2: STOP

A) BGT I,L,L2L0: DIV T,N,I

MUL T,T,IBGT N,T,L0

(B) L0: BGT I,L,L2DIV T,N,I

MUL T,T,IBGT N,T,L1

C) BGT I,L,L2L0: DIV T,N,I

MUL N,T,IBGT N,T,L1


33/82



SINTAKSNE NOTACIJE- sintaksa i semantika programskih jezika: sintaksa se bavi formalnom ispravnou nekog iskaza naobjektnom jeziku bez ulaenja u logiku ispravnost.primer: a+b*c - ispravno napisano

a+c* - neispravno napisano- metajezik je niz pravila za opis sintakse objektnog jezika, tzv. gramatika objektnog jezika.

Elementi notacijaSvaka notacija ima svoje elemente kojima se opisuje objektni jezik. Ovde su navedeni elementi etirinotacije, iako jednu od njih, i to notaciju sa zagradama, nije potrebno spremati za ispit.

BNF notacija1. neterminalni simboli 2. terminalni simboli slovo3. metajeziki operator dodele ::=

4. metajeziki operator nadovezivanja slovo5. metajeziki operator izbora ::= | isto sto i

z::x

y::x

6. ponavljanje prethodnog elementa

seapodrazumevj1seapodrazumevi{x}

Primer: ::= | ::= 0|1|2|3|4|5|6|7|8|9

primer za 12: 12- rekurzivna definicija ostvaruje opis beskonanog broja nizova cifara

- objektni jezik je skup nizova terminalnih znakova, odnosno nizova cifara {0,1,...,9,00,01,...,123}EBNF notacija1. neterminalni simboli x2. terminalni simboli "slovo"3. metajeziki operator dodele =4. metajeziki operator nadovezivanja x"slovo"

5. metajeziki operator izbora x = (y|z) isto sto izx

yx

(zagrade preciziraju operande operatora izbora)

6. ponavljanje prethodnog elementa

seapodrazumevj 0seapodrazumevi{x}7. opcija [x]8. na kraju pravila stoji taka .

Notacija sa zagradama1. neterminalni simboli x2. terminalni simboli slovo3. metajeziki operator dodele =4. metajeziki operator nadovezivanja x slovo

5. metajeziki operator izbora

yx

6. ponavljanje prethodnog elementa x...7. opcija [x]


34/82



x

x

x

Sintaksni dijagrami

1. neterminalni simboli

2. terminalni simboli

3. dodela

4. nadovezivanje

5. izbor

6. ponavljanje

7. opcija

Zadatak IZ32A (integralni ispit, 14.03.2002. godine) *U nekom jeziku celobrojne konstante se mogu pisati u heksadekadnom ili binarnom brojnom sistemu.

Ako se piu u heksadekadnom brojnom sistemu, moraju poinjati cifrom 0-9 i moraju se zavritisufiksom H. Ako se piu u binarnom brojnom sistemu, ne smeju poinjati nulom i moraju se zavritisufiksom B. Koju sintaksnu definiciju treba dodati datim definicijama da bi se dobila ispravnasintaksna definicija konstante u ovom jeziku?

::=B|H::=1|::=0|1::=|2|3|4|5|6|7|8|9::=A|B|C|D|E|F

A) ::=| B) ::=|| C) ::=||

Obrazloenje:Interesantna stvar u ovom zadatku je nain na koji je definisana dekadna cifra. Umesto prostognavoenja svih mogunosti, autor zadatka se odluio na korienje ve postojee definicije binarnecifre. Binarne konstante su ispravno definisane. Ostaje da se vidi koje od ponuenih reenjazadovoljava uslov da heksadekadne konstante moraju poinjati dekadnom cifrom.

Odgovor pod A) ne zadovoljava pomenuti uslov zadatka, zato to dozvoljava da konstanta poneheksadekadnom cifrom. Odgovor pod B) ne pokriva bilo koji sluaj kada u heksadekadnom brojupostoji dekadna cifra posle heksadekadne, primer: A116, B12C16... Odgovor pod C) je ispravan jerpokriva sve sluajeve i zadovoljava uslov zadatka vezan za heksadecimalne konstante.

slovo

Yx

b

a

slovox


35/82



Zadatak IZ8U nekom jeziku sintaksa izraza se definie u BNF notaciji na sledei nain:

::= | , ::= A|B|C|D|E::= +|-|*|/

Koji od sledeih izraza sintaksno odgovara datoj definiciji?

A) A, B+, C+, D, E-/B) A+B, C/, D/C) A, A, A*+, B, C-/

Reenje:A) A , B + , C + , D , E - /

, , , , , , , ,

, , ,

B) A + B , C / , D /, , , ,


36/82



[ ]

' 'm s

skup malih

slova

m sm s

,

' '' .. '

Zadatak IZ 2006-11-31 (Kolokvijum 2006)Data je sintaksna definicija u BNF notaciji: ::= 0 | 0101 | 1Koji od sledeih nizova odgovara datoj sintaksnoj definiciji?

A) 1001001 B) 0100001 (C) 0101001

Zadatak IZ10Koja od navedenih sintaksnih definicija ispravno definie skup malih slova (na primer: ['a','c','s'..'w'])pod pretpostavkom da ne treba da se definie malo slovo?

A) u BNF notaciji ::= [] ::= |, :: ''|''..''

B) u EBNF notacijiSkup_MS = "[" Niz "]".

Niz = [ Elem { "," Elem }].Elem = ( "'" MS "'" | "'" MS "'..'" MS "'").

C) U notaciji sa zagradama:

...'ms'..'ms'

'ms'skup_ms

Reenje:Odgovor pod A) je neispravan, jer ne omoguava definisanje praznog skupa, jer lista navedenaizmeu srednjih zagrada mora da sadri bar jedan element. Trebalo bi:

::= []|[] ::= |, :: ''|''..''

Odgovor pod B) je ispravan, jer po EBNF notaciji ono to je izmeu zagrada [ ] moe da se izostavi,ili pojavi jednom, pa je mogue definisati i prazan i neprazan skup. Neprazan skup ima samo jedanelement ili vie elemenata razdvojenih zarezom, to je omogueno korienjem zagrada { }, kojeznae da se ono to je izmeu njih navedeno moe pojaviti 0, 1 ili vie puta. Element moe biti slovoili opseg slova. Apostrof se pojavljuje kao terminalni simbol pa se navodi pod navodnicima, popravilima EBNF notacije.Odgovor pod C) je neispravan, jer se nigde srednje zagrade ne pojavljuju kao terminalni simboli.Takoe se nigde ne pojavljuje zarez kojim se razdvajaju elementi skupa. Trebalo bi:

]...'ms'..'ms'

'ms',

'ms'..'ms'

'ms'[skup_ms

Skup moemo definisati i korienjem sintaksnih dijagrama:

Odgovor:B


37/82



Zadatak Z72 (modifikovan)Napomena: ovo je stariji zadatak, preuzet iz materijala za EF2PJ, i odnosi se napseudojezik, a ne na programski jezik Pascal. U svakom sluaju, zadatak predstavljadobar primer za ilustraciju razlika izmeu pojedinih notacija.Sastaviti BNF notaciju, EBNF notaciju, sintaksni dijagram i notaciju sa zagradama za opis sintaksepodataka nizovnog tipa sa skalarnim elementima.

(Primer: Matrica: ARRAY [ 10..100, LOGICAL ] OF INTEGER)Reenje:

A) BNF notacija: ::= : ARRAY [ ] OF ::= | | |

_ ::= | , ::= LOGICAL | CARDINAL | INTEGER | CHARACTER | REAL |

() | | ::= A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q| R |

S | T | U | V | W | X | Y | Z ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ::= LOGICAL | CHARACTER | | ::= , ::= .. ::= | '' | ::= ::=


38/82



C) Sintaksni dijagram

: ARRAY [Identifikator Dimenzija Skalarni tip] OF

,

Definicija

niza

_

Cifra

SlovoIdentifikator

LOGICAL

CHARACTER

Identifikator

Opseg

Dimenzija

LOGICAL

CHARACTER

Identifikator

Opseg

CARDINAL

INTEGER

REAL

( )Niz identifikatora

Skalarnitip

A B C D E F G H I J K L M

N O P Q R S T U V W X Y Z

Slovo


39/82


40/82



D) Notacija sa zagradama

definicija_niza = identifikator : ARRAY [ niz_dimenzija ] OF skalarni tip

K

_

cifra

slovo

slovotoridentifika

niz dimenzija = dimenzija [ { , dimenzija } ... ]

toridentifika

opseg

)toraidentifika_niz(

REAL

CHARACTER

INTEGER

CARDINAL

LOGICAL

tip_skalarni

slovo = A | B | C | D | E | F | G | D | I | J | K | L | M | N | O | P | Q | R | S | T |U | V | W | X | Y | Z

cifra = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

toridentifika

opseg

CHARACTER

LOGICAL

enzijadim

niz identifikatora = identifikator [ { , identifikator } ...]

opseg = konstanta .. konstanta

toridentifika

'znak'

broj_ceo

tatankons

cifrabrojceo

_

znak_specijalan

cifra

slovo

znak

specijalan znak = + | - | * | / | = | . | , | : | ; | ( | ) | ' | " | ! | # | $ | % | & |

_ | ? | @ | ^ | \ | ~ | ` | [ | ] |


41/82



Zadatak IZ11 (Januar 2007)Koji od ponuenih izraza odgovaraju sledeoj sintaksnoj definiciji :

::= b::= a|::= a|bb::= aa

A) baabaabaabaaB) baaabbaabbaab(C) babbaaabbaa

ReenjePosmatranjem datih pravila, moe se uoiti da ne postoji smena koja omoguava da se neterminal bpojavi na kraju niza. Prema tome, odmah se moe zakljuiti da je odgovor pod B) netaan. Slinotome, pravila dozvoljavaju da se pojedinani neterminal b pojavi samo na poetku izraza. U ostatkuizraza, neterminal b mora da se pojavljuje u parovima. Prema tome, odgovor A) je netaan. Ostajeda se analizira odgovor C) za koji se posmatranjem ne moe odmah dati odgovor.

C)babbaaabbaababbaaabbbabbaaababba baa baa ba ba b b b ?

Ako je ovaj odgovor taan, par terminala bb sepojavljuje samo ako za njim sledi par neterminala aa.Zato se zakljuuje da se kraj izraza dobija izneterminala y. Slino se postupa sa drugim paromneterminala bb.Od tada, kao to je prikazano, mogua su dva puta usmenjivanju, od kojih jedan ne moe da se svede naneterminal start. U takvoj situaciji treba probati svemogunosti jer u suprotnom moe pogreno da sezakljui da ni ovaj izraz ne odgovara datoj sintaksnojdefiniciji.

Zadatak IZ 2005-12-02 (Kolokvijum 2005)Koji od prikazanih realnih brojeva odgovara ponuenoj sintaksnoj definiciji u EBNF notaciji?

RealanBroj = Znak Cifra "." NizCifara "E" Znak Eksp.Znak = [("+" | "-")].Cifra = ("1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9").

NizCifara = {(Nula | Cifra)}.Nula = "0".Eksp = (Cifra [Cifra] | Nula [Cifra] | [Cifra] Nula).

A) +3.14159265E00(B) -2.718281E-10C) 128.E+3

Zadatak IZ 2005-12-02 (Kolokvijum 2005)Za koja od ponuenih sintaksnih pravila S generie istu sekvencu kao dat sintaksni dijagram?

A) BNF: ::= 101|10 ::= 1

0

::= {10}

B) EBNF:S = "1" A {A} ("1" | "0").

A = "1" [A] "0".

C) EBNF:S = (B|"1"{A}"0").B = "1" S "0" S "1".

A = "1" {A} "0".


42/82



PASCALZadatak UVODNI_01Sastaviti program na programskom jeziku Pascal koji na standardnom izlazu ispisuje poruku "Zdravosvete!".

PROGRAM ZDRAVO_SVETE(output);BEGINWRITELN(output, 'Zdravo svete!')

END.

Tradicionalno, prvi program koji se pie na viem programskom jeziku (poput jezika Pascal) treba dabude "Zdravo svete!" ("Hello world!" na engleskom jeziku).

Prema standardu jezika Pascal, svaki program poinje rezervisanom rei PROGRAMnakon ega sledi

naziv programa koji progamer sam bira, u ovom sluaju ZDRAVO_SVETE. Generalni savet u veziimenovanja programa jeste da ime treba da jezgrovito opie namenu programa, ako je to mogue.Treba izbegavati generika imena poputMOJ_PROGRAM. Potom se izmeu zagrada navode logiki naziviulaznih i izlaznih ureaja koje e program koristiti, u ovom sluaju oznaka za standardni izlaz output koji je najee ekran raunara. Rezervisana re PROGRAM i ostatak reda predstavljajudeklarativni deo programa koji se ne pretvara u mainski kod, ve slui kao uputstvo prevodiocu.Neki prevodioci za Pascal, poput Turbo Pascal-a, ne insistiraju na tome da program mora da ponena opisan nain. Ipak studentima se savetuje da se dre propisanog standarda prilikom pisanjaprograma.

Program zapravo poinje sa rezervisanom re

i BEGIN a zavrava se rezervisanom re

i END iza koje, uprikazanom sluaju (kraj programa) sledi taka ("."). Ove dve rezervisane rei oznaavaju granice u

okviru kojih se nalazi program koji se izvrava. Sam program ima tano jednu instrukciju:WRITELN.Njen naziv potie od "write line", to u prevodu sa engleskog jezika znai "pii liniju". Ova instrukcijaispisuje navedeni znakovni niz na navedenom izlaznom ureaju, nakon ega se izlaznom ureajusignalizira da tekst koji bude sledio (ako ga bude) treba ispisati u narednoj liniji. Jednostavno reeno,nakon ispisa zadatog teksta prelazi se u sledei red. Treba primetiti da instrukcijaWRITELN u ovomprogramu ima dva argumenta, od kojih je prvi logiki naziv ureaja na kojem treba ispisati poruku, adrugi sama poruka. Generalno, instrukcijaWRITELN moe imati vie od dva argumenta, ali prvi morabiti logiki naziv izlaznog ureaja. Jo jednom, neki prevodioci za Pascal dozvoljavaju da se nenavede naziv izlaznog ureaja i tada se podrazumeva standardni izlaz. Kod takvih prevodilaca,instrukcija WRITELN('Zdravo svete!') bi imala isti efekat kao i gore navedena. Ponovo, studentimase preporuuje da eksplicitno navode logike nazive ulazno-izlaznih ureaja.

Primetiti da se u programskom jeziku Pascal znakovni nizovi navode pod apostrofima a ne podznacima navoda.


43/82



Zadatak UVODNI_02Registarski broj se predstavlja kao petocifren ceo broj u opsegu od 10000 do 30000, od ega prveetiri cifre ine registarski broj u uem smislu a peta cifra ini kontrolnu cifru. Uloga kontrolne cifre

jeste da sprei pogrean unos registarskog broja. Registarski broj je ispravan ako je suma svih cifaradeljiva sa 7. Napisati program na programskom jeziku Pascal koji sa standardnog ulaza itaregistarski broj firme i proverava da li je broj ispravan. U sluaju ispravnog broja na standardnom

izlazu ispie "Ispravan" a u suprotnom "Neispravan".PROGRAM REG_BR(input, output);

VARi, broj, suma : INTEGER;

BEGINREAD(input, broj);IF (broj < 10000) OR (broj > 30000) THEN

WRITELN(output, 'Neispravan')ELSEBEGIN

suma := 0;FOR i := 1 TO 5 DO

BEGIN suma := suma + broj MOD 10;broj := broj DIV 10

END;

IF suma MOD 7 = 0 THENWRITELN(output, 'Ispravan')

ELSEWRITELN(output, 'Neispravan');

ENDEND.

Program ilustruje korienje kontrolne strukture IF-THEN-ELSE kao i korienje FORciklusa.

Popularni prevodioci za Pascal poput Turbo Pascal-a ili Free Pascal-a predstavljaju cele brojeve naduini od 16 bita, to znai da je vrednost najveeg celog broja 32767. Da bi registarski broj mogaoda se uita sa standardnog ulaza kao ceo broj, uvedeno je vetako ogranienje da je registarski brojpetocifren, u opsegu od 10000 do 30000. Studentima se preporuuje da razmisle i da napiuprogram koji bi istu proveru vrio nad registarskim brojevima sa veim brojem cifara (na primerdvanaest).

Pre rezervisane rei BEGIN kojom poinje program, nalazi se deklarativna sekcija programa koja

poinje rezervisanom reiVARi u kojoj se prevodiocu navode nazivi i tipovi promenljivih koje e bitikoriene u programu. U ovom programu se koriste tri celobrojne promenljive. Praktian savet zaimenovanje promenljivih jeste da njihovo ime odraava njihovu namenu. Na primer, u promenljivoj

broje biti smeten registarski broj koji se unosi sa standardnog ulaza a u promenljivoj sumae bitismeten zbir vrednosti svih cifara registarskog broja. Promenljiva i u ovom programu ima sporednuulogu jer slui kao broja ciklusa, pa ne mora da ima smisleno ime (kao brojai ciklusa tradicionalnose koriste jednoslovni identifikatori poput i, j, k, ...). Treba izbegavati davanje jednoslovnih nazivabez posebnog znaenja veem broju promenljivih jer utiu na smanjenu preglednost i razumljivostprograma.

U programu se, najpre, instrukcijom READ sa standardnog ulaza (input), koji najee predstavljatastaturu raunara, ita ceo broj i smeta se u promenljivu broj. Nakon toga se ispituje vrednostuitanog broja. Ako je vrednost promenljivebroj manja od 10000 ili vea od 30000, onda onaprema postavci zadatka ne predstavlja registarski broj firme. Zbog toga se, ako je taj uslov ispunjen,


44/82



ispisuje poruka "Neispravan". U suprotnom, izvrenje programa preskae instrukciju WRITELN inastavlja se unutar ELSE grane.

ELSE grana poinje rezervisanom rei BEGIN i zavrava se sa END. U ovom sluaju BEGIN i END neoznaavaju poetak i kraj programa ve oznaavaju blok instrukcija koje logiki predstavljaju jednucelinu u programu. Naime, ako bi u ELSE grani postojala samo jedna instrukcija, onda par BEGIN i ENDne bi bio neophodan jer se tada nedvosmisleno zna koja instrukcija potpada pod ELSE granu. U

suprotnom sluaju, par BEGIN i END je neophodan jer drugaije prevodilac ne bi mogao da zna gde sezavrava niz instrukcija koje logiki spadaju pod ELSE granu. Ovaj princip (par BEGIN i END) se koristikod svih kontrolnih struktura koje obuhvataju vie instrukcija.

U ELSE grani se najpre vrednost promenljive suma postavlja na 0. Veoma je bitno navesti poetnuvrednost svih promenljivih (osim, naravno, onih ija se vrednost ita sa nekog ulaznog ureaja) prenjihovog korienja u nekom izrazu. U suprotnom ponaanje programa moe biti nepredvidivo, osimako prevodilac ne pravi takav kod da po startovanju programa automatski postavi vrednosti svihpromenljivih na podrazumevanu vrednost. Dobra programerska praksa jeste da se ne treba oslanjatina mogunosti prevodioca jer one ne moraju biti standardne, pa e se isti program preveden na

drugom prevodiocu drugaije ponaati.

Nakon toga se otpoinje ciklus sa 5 iteracija i u svakoj iteraciji e se najpre promenljivoj suma dodatiostatak deljenja promenljivebroj sa 10 a zatim e se izvriti celobrojno deljenje promenljive broj sa10. Na primer ako promenljivabroj ima vrednost 12203, nakon prve iteracije promenljiva sumaeimati vrednost 3 a promenljiva broj 1220, nakon druge 3 i 122, nakon tree 5 i 12, nakon etvrte 7 i1 i na kraju 8 i 0. FORciklus e se ponoviti tano 5 puta (tokom kojih e promenljiva i menjativrednost od 1 do 5, to je u ovom sluaju nebitno).

Na kraju se ispituje da li je vrednost promenljive suma deljiva sa 7, odnosno da li je ostatak prilikom

deljenja sa 7 jednak 0. U sluaju da jeste, ispisae se poruka "Ispravan" a u suprotnom sluaju"Neispravan".

Napomena u vezi formatiranja izvornog teksta programa: preglednost programa je dalekovea ako se instrukcije izmeu jednog para BEGIN i END pomere za nekoliko mesta udesno jer je tadavizuelno jasno koji skup instrukcija pripada datom bloku. Pravilno formatiranje ne predstavljapreduslov uspenog prevoenja programa, jer bi prevodilac uspeno preveo i program koji se upotpunosti nalazi u jednom redu teksta. Pravilno formatiranje pomae programeru u procesuprogramiranja i to je jo vanije kasnijeg prepravljanja i unapreivanja programa.


45/82



Zadatak Z89Sastaviti program na programskom jeziku Pascal za nalaenje zbira elemenata zadatog niza brojeva.Program treba da uita preko glavne ulazne jedinice broj elemenata niza a zatim i elemente niza, daispie na glavnoj izlaznoj jedinici uitani niz brojeva i rezultat. Prethodne operacije treba ponavljatisve dok se za duinu niza ne uita nula.

PROGRAM z89(input,output);

CONST MaxDuz = 100;VAR

niz:ARRAY[1..MaxDuz] OF integer;n,i,zbir:integer;

BEGINwrite(output,'Unesite broj elemenata niza: ');readln(input,n);

WHILE(n>0) AND (n


46/82



Zadatak Z41.PASSastaviti program na programskom jeziku Pascal kojim se u tekstu, koji se u proizvoljnom brojuredova uitava preko standardnog ulaza (input), odredi broj cifara, velikih slova, malih slova, iostalih znakova. Tekst koji treba obraditi se zavrava praznim redom. Rezultate ispisati nastandardnom izlazu (output).

PROGRAM znakovi(input, output);

VARn_cif, n_vel, n_mal, n_ost, i: integer;linija: STRING[255]; { max. duzina stringa za Turbo Pascal }znak: char;

BEGINn_cif := 0; n_vel:= 0; n_mal := 0; n_ost := 0;writeln(output, 'Unesite linije koje treba obraditi (prazan red za kraj unosa)');readln(input, linija);

WHILE (Length(linija) > 0) DOBEGINFOR i := 1 TO Length(linija) DO

BEGINznak := linija[i];IF (znak >= '0') AND (znak = 'A') AND (znak = 'a') AND (znak 0) }

writeln(output, 'Cifara ima ukupno: ', n_cif);writeln(output, 'Velikih slova ima ukupno: ', n_vel);writeln(output, 'Malih slova ima ukupno: ', n_mal);writeln(output, 'Ostalih znakova ima ukupno: ', n_ost);

writeln(output, 'Pritisnite [ENTER] za kraj programa');readln(input)

END.

Zadatak ilustruje korienje STRING tipa podataka, korienje IF-ELSE IF-ELSE kontrolnestrukture, kao i korienje petlje sa izlazom na dnu. Poslednja dva reda pokazuju kako se programiraekanje da korisnik proita ispisane poruke, pa tek onda kada sam odlui, zavrava izvravanje

programa.


47/82



Skupovi, nabrojani tip, potprogrami, zapisi

Zadatak Z38.PASSastaviti program na programskom jeziku Pascal za odreivanje broja razliitih elemenata u zadatomnizu celih brojeva koji spadaju u opseg od 0 do 255.

PROGRAM Skupovi(input, output);

CONSTMAX_DUZ = 300;

VARniz: ARRAY[1..MAX_DUZ] OF 0..255;

broj: integer;n, k, i: 0..MAX_DUZ;skup: SET OF 0..255;

BEGINREPEAT{ unos elemenata niza }n := 1;REPEATwriteln('Unesite ', n, '. element niza (0..255, van opsega za kraj unosa): ');readln(input, broj);IF (broj >= 0) AND (broj 255) OR (n>MAX_DUZ);

{ ukoliko niz nije prazan, odredjivanje broja razlicitih elemenata }IF (n > 1) THEN

BEGINskup := [];k := 0;FOR i:= 1 TO n-1 DOIF NOT (niz[i] IN skup) THENBEGIN{ povecavamo brojac za broj razlicitih elemenata }k := k + 1;{ ovde + NIJE operacija sabiranja, vec operacija unije skupova }{ element pretvaramo u skup koji sadrzi samo taj element }{ to se obavlja tako sto element stavimo u [] }skup := skup + [niz[i]]

END;

{ ispisivanje rezultata }writeln(output, 'Broj razlicitih elemenata je: ', k)

END

{ ponavljamo ceo proces sve dok se ne unese prazan niz }UNTIL n = 1

END.

Zadatak ilustruje korienje skupovskog tipa, petlje sa izlazom na dnu i brojake petlje. Pokazano je ikorienje komentara.


48/82



Zadatak IZ53Pod pretpostavkom da je sledei progamski segment na programskom jeziku Pascal semantikiispravan, ta ispisuje?

a := [3]; b := [2]; c := (a+b) * (a-b);FOR i := 0 TO 5 DO IF i IN c THEN write (i: 2);

A) 3 2 B) 5 C) 3Obrazloenje:Kontekst odreuje da su a,b i c skupovne promenljive, pa je prema tome c presek unije skupova a i

b { [3, 2] } i razlike skupova a ib { [3] }, tj. skup { [3] }.Dakle , ispisivanje e se izvriti samo za i = 3.

Zadatak IZ50Ako je deklarativni deo programa na programskom jeziku Pascal:

TYPEptice = ( slavuj, roda, vrabac );avioni = ( mig, boing, mirage );

VARp: ptice;a: avioni;aa: ARRAY [ptice] OF avioni ;

koja e onda sekvenca naredbi tog programa biti formalno ispravna?A)

a := mig;FOR p := slavuj TO vrabac DOaa[p] := succ( succ( a ) );

B)

p := pred( vrabac );a := succ( boing );IF p = a THEN writeln;

C)p := vrabac;a := mirage;IF ord( pred(p) ) = ord( a )THEN writeln(a);

Odgovor: A

Obrazloenje:

A) ispravno popunjava vektor aviona podatkomija je vrednostmirage;B) poredi promenljive razliitog tipap = a;C) sadri ispis (writeln) nabrojivog tipa, to nije defiisano ISO standardom za Pascal.


49/82



Zadatak IZ 2006-09-20 (MODIFIKACIJA)Napisati program na jeziku Pascal kojim se iz jednodimenzionog niza brojeva tipa REAL izdvajanajdui podniz koji je ureen strogo rastue. Pretpostaviti da niz sadri bar jedan element. Programtreba da uita niz, izdvoji najdui podniz u drugi niz i ispie drugi niz na standardnom izlazu. Programtreba da ponavlja ove korake sve dok se za duinu niza unosi prirodan broj.

Program Zakdatak1 (input, output);Const MAX=100;Type niz=array[1..MAX] of real;

VarnizA, nizB: niz;duzinaA, duzinaB, i: integer;trduz, maxduz: integer;trind, maxind: integer;

BeginRepeatwriteln(output);write(output,'Unesite duzinu niza(0 za kraj rada) ');readln(input, duzinaA);

If duzinaA > 0 Then

Unos duine niza iprovera validnosti

Beginwriteln(output, 'Unesite elemente niza ');for i:= 1 To duzinaA Do

read(input, nizA[i]);

Unos elemenata niza

maxduz:= 1; maxind:= 1; trduz:= 1; trind:= 1; Inicijalizacijapromenljivih

For i:=2 To duzinaA DoBeginIf nizA[i] > nizA[i-1] Thentrduz:= trduz +1

ElseBeginIf trduz > maxduz ThenBeginmaxduz:= trduz;maxind:= trindEnd;trind:= i;trduz:= 1

EndEnd;If trduz > maxduz ThenBegin

maxduz:= trduz;maxind:= trindEnd;

Glavna obrada:pronalaenje najduegpodniza kojizadovoljava zadati

kriterijum.

U ciklusu se prolazikroz sve elementeniza, poevi oddrugog, i utvruje seda li je izmeu dvauzastopna elementa

postoji traeniporedak.

For i:=maxind To (maxind+maxduz-1) DonizB[i-maxind+1]:= nizA[i];

duzinaB:= maxduz;

Prepisivanje uoenogpodniza niza A uniz B

writeln(output,'Najduzi strogo rastuci podniz je);For i:= 1 To duzinaB Dowrite(output, nizB[i]:2:2, ' ')

Ispis niza B

End

Until duzinaA


50/82



U postavci zadatka nije naznaeno, pa se kao razumna pretpostavka uzima da je najvea duinaniza koji se unosi 100 elemenata. Definisan je poseban tip podatka niz za potrebe deklarisanjapromenljivih tipa niza (nizA i nizB).

Ideja za reenje ovog programskog problema je sledea: treba analizirati sve uzastopne elementeniza i brojati koliko uzastopnih elemenata zadovoljava postavljeni kriterijum: trai se najdui strogorastue ureen podniz. Drugim reima, trai se podniz kod kojeg je svaki element vei od

prethodnog. Kad god se bude ustanovilo da dati kriterijum nije zadovoljen, treba prekinuti brojanje iutvrditi da li je novootkriveni (tj. upravo analizirani podniz) dui od prethodno poznatog najduegpodniza. Ako jeste, onda novootkriveni podniz treba proglasiti za najdui. U suprotnom treba gaodbaciti. U postavci zadatka nije precizirano ta treba raditi ako postoji vie podnizova iste(maksimalne) duine. Zbog toga e u reenju biti usvojena pretpostavka da prvi takav podniz na kojise naie prilikom obrade treba proglasiti za "pobednika" i njega izdvojiti.

Za potrebe uoavanja traenog podniza u nizu A koristie se dve promenljive: trduz i trind. Njhovanamena je sledea: trduz oznaava TRenutnu DUinu podniza koji se analizira, a trind (TRenutniINDeks) oznaava indeks u nizu A od kojeg poinje podniz koji se analizira. Te dve informacije (gde

poinje podniz i koja je njegova duina) su dovoljne da bi moglo da se izvri njegovo izdvajanje udrugi niz. S obzirom na to da traeni podniz moe poeti od prvog elementa niza A, poetna vrednostza trind treba da bude 1. Takoe, prilikom planiranja treba pretpostaviti da niz A moe biti ureennerastue (odnosno naredni element u nizu je jednak ili manji od prethodnog). U tom sluaju nepostoji podniz duine dva ili dui koji zadovoljava traeni uslov, pa je zbog toga poetna vrednost zatrduz postavljena na 1.

Nakon ovog objanjenja, smisao promenljivih maxduz i maxind je jasna: u njima e se pamtitiduina najdueg podniza i indeks u nizu A od kojeg poinje najdui podniz. Svaki put kada se uoi datraeni poredak nije zadovoljen izmeu dva susedna elementa u nizu A, program proverava da li jeduina novootkrivenog podniza vea od duine prethodno poznatog najdueg podniza. Ako jeste,program prepisuje vrednosti trduz i trind u maxduz i maxind, respektivno, i time novootkrivenipodniz "proglaava" za najdui podniz. U nastavku, u svakom sluaju (bilo da je novootkriveni podnizdui od prethodnog najdueg ili ne) se vrednost promenljive trduz postavlja na 1 a vrednostpromenljive trind na indeks elementa niza A koji je "prekinuo" traenu sekvencu. Time se praktinoinicira traenje novog podniza poevi od "prekidnog" elementa, a kao i ranije, pretpostavlja se da jenjegova nova duina 1.

Kada se zavri FOR ciklus, potrebno je jo jednom proveriti da li je novootkriveni podniz dui negoprethodno otkriven najdui podniz. To je potrebno uraditi u posebnom sluaju kada se najdui podniznalazi na kraju niza A, odnosno kada je poslednji element podniza ujedno i poslednji element niza A.

Ako je to sluaj, FOR ciklus e doi do poslednjeg elementa niza A, a kako je za njega ispotovantraeni poredak, program nee izvriti granu koja postavlja nove vrednosti za maxind i maxduz. Usluaju da se nakon FOR ciklusa jo jednom ne izvri potrebna provera, stvarni najdui podniz, koji senalazi na kraju niza A, bi ostao "neprimeen".

Nakon toga se vri prepisivanje uoenog podniza iz niza A u niz B. Uoeni podniz poinje od onogelementa niza A koji odgovara indeksu zapamenom u maxind, a duina tog niza je zapamena umaxduz. Zbog toga poslednji element podniza ima indeks maxind+maxduz-1 u nizu A. Slino tome,elementi koji se prepisuju u niz B se smetaju poevi od indeksa 1. Kako je ciklus formiran odbrojake promenljive i koja slui za indeksiranje niza A, odgovarajui indeks niza B se dobija

oduzimanjem maxind od tekue vrednosti promenljive i i dodavanja 1 (da bi prvi element bio podindeksom 1).


51/82



Zadatak Z97Sastaviti program na programskom jeziku Pascal za izraunavanje aritmetike i geometrijske sredinezadatog niza pozitivnih brojeva.

Prvo reenje (loe)

PROGRAM z97(input,output);

VAR n,i:integer;niz:ARRAY[1..100] OF real;a,g,tmp:real;

BEGINwrite(output,'Unesite duzinu niza: ');read(input,n);writeln(output,'Unesite clanove niza:');FOR i:=1 TO n DO niz[i]:=tmp;a:=0; g:=1;FOR i:=1 TO n DO BEGINa:=a+niz[i]/n;g:=g*exp(ln(niz[i])/n)

END;writeln(output,'Aritmeticka sredina je ',a:2:2,'.');writeln(output,'Geometrijska sredina je ',g:2:2,'.')

END.

Iako tano, prikazano reenje je loe iz vie razloga. Najpre, ne proverava se da li su unete vrednostikorektne. Na primer, da li su za duinu niza i za elemente niza unete pozitivne vrednosti. Zatimraunanje aritmetike i geometrijske sredine, iako korektno napisano, nije spremno za viestrukuupotrebu: naime, ako bi se traila modifikacija programa takva da se ove vrednosti odreuju za vienizova da bi se u zavisnosti od rezultata vrila obrada tih nizova, u ovakvom reenju bi biloneophodno da se napiu novi FORciklusi koji vre raunanje ovih vrednosti, ali za druge duine i za

druge podatke. To je izrazito nepraktino i podlono je grekama. Osim toga nije pregledno.Mnogo bolje reenje, sa programerske take gledita, jeste da se napiu posebni potprogrami koji bivrili odreenu aktivnost: uitavanje broja, uitavanje niza, raunanje neke vrednosti, itd. Takavprogram je pregledan, znaajno laki za analizu, jednostavniji za odravanje (modifikovanje) iunapreivanje.

Kako odrediti kada treba neki deo programa smestiti u potprogram? Potprogram treba da bude dobroizolovana celina koja obavlja neku aktivnost. Generalno govorei, kada god se uoi sekvenca odnekoliko instrukcija (dve ili vie) kojima se moe pripisati jasno znaenje, naroito ako je potrebno data sekvenca postoji na vie mesta u programu. U gornjem primeru, raunanje aritmetike sredine sesvodi na jedan ciklus u kojem se obavlja jedna jednostavna radnja, pa se na prvi pogled moda moerei da nije pravi kandidat za potprogram. Meutim, smisao te kratke sekvence je sasvim jasan injena upotreba je precizno ograniena inei je zapravo dobrim kandidatom za potprogram.

Bitno je da potprogrami ne koriste globalne promenljive (tj. promenljive glavnog programa).Jedna od bitnih osobina potprograma je njihova viestruka upotrebljivost. Ta osobina se ostvarujeparametrizacijom potprograma njihovim argumentima: potprogramima se dostavljaju podaci nadkojima oni obavljaju neku obradu. Kako konkretne vrednosti tih podataka (argumenata) nisu unapredpoznate, potprogrami se mogu pozivati iz razliitih konteksta ime je ostvarena viestrukaupotrebljivost.


52/82



Drugo reenje (dobro)

PROGRAM z97m(input,output);TYPE NizBrojeva = ARRAY[1..100] OF real;

VAR n,i:integer;niz:NizBrojeva;a,g,tmp:real;

PROCEDURE citaj_duzinu(var n : integer);BEGIN

REPEATread(input, n);IF n < 1 THEN writeln(output,'Unesite pozitivnu vrednost!')

UNTIL n > 0END;

PROCEDURE citaj_poz_vrednost(var r : real);BEGIN

REPEATread(input, r);IF r < 1 THEN writeln(output,'Unesite pozitivnu vrednost!')

UNTIL r > 0END;

PROCEDURE citaj_niz(var niz : NizBrojeva; var duz : integer );VAR i : integer;BEGIN

writeln(output,'Unesite duzinu niza');citaj_duzinu(duz);writeln(output,'Unesite elemente niza');FOR i := 1 TO duz DO citaj_poz_vrednost(niz[i])

END;

FUNCTION ArSr(var niz : NizBrojeva; duz : integer) : real;VAR i : integer; as:real;BEGIN

as := 0;FOR i := 1 TO duz DO as := as + niz[i];

ArSr:=as{Iako standard ne specificira nista osim da se promenljivoj koja je implicitno definisananazivom funkcije dodeli vrednost bar jednom, vecina prevodilaca nece dozvoliti citanje te

promenljive, bez obzira da li je inicijalizovana ili ne. Turbo Pascal ce, na primer,

prijaviti sintaksnu gresku ukoliko pokusamo da procitamo vrednost promenljive ArSr}END;

programiranje libro

Documents