INFORMATICA 1/1S7S TRETJE REPUBLOSKO TE K-MO VANJE SREDNJEŠOLCEV S PODROČJA RACUNALN JŠTVA iVi. MARTBNEC UDK: 371.3:681.3 SLOVENSKO DRUŠTVO INFORMATIKA, LJUBLJANA Povzetek. Prispevek predstavlja poroBilo o tretjem republiškem tekmovanju srednješolcev iz podrotija rafiunaln iSt vat ki ga je organiziralo Slovensko druStvo Informatika v aprilu 1979. V prispevku so vse naloge zrešitvan^i in pregled rezultatov tekmovanja. THIRD COHPUTER SCIENCE CONTEST FOR HIGH-SCHOOL STUOENTS. The article represents a report on third Computer Science Contest. It includes the complete set of problems with their solutions and a short overwiev of contest results. I. Uvod Ena od rednih dejavnosti Slovenskega druStva Informatika je tudi popularizacija računalništva in informatike med srednjeSolsko mladino. Komisija za popularizacijo računalništva je zato organizirala ie tretje republiSko; tekmo­ vanje srednješolcev iz podroCja ratiunal n i Stva . Tekmovanje je bilo 21. aprila na Fakulteti za elektrotehniko v Ljubljanii udelei!ilo pa se ga je rekordno Število tekmovalcev! 56 po prvem letu pouka in 36 po drugem letu pouka računal­ ništva. Pri organizaciji letoSnjega tekmovanja so poleg DruStva in Fakultete za elektrotehniko i;odelovali Se InStitut Joi!ef Štefani sodelavci koordinativne delovne skupine za izvedbo projekta Pouk ratiunaln iSt va v usmerjenem i zobraifevan jut finanCno pa so tekmovanje podprli Elektrotehna - TOZD Digitali Iskra - TOZD RaBunalnikii Intertradei Republiški račun­ ski center in Hotel Lev. Tekmovanje je otvoril rektor Univerze E. Kardelja v Ljubljani prof. dr. Slavko HodSari tekmovalce pa so pozdravili: predsednik Sloven­ skega druStva Informatika prof. dr. Anton P. Seleznikari dekan Fakultete za elektrotehniko prof. dr. Jernej Virant in predsednik komisije za popularizacijo raBunalniStva Roman Dorn. Primarni cilj tekmovanja je popularizacija raljunaln iSt va I obenem pa se uKenci srednjih Sol seznanijo z mo!!nostmi Študija na podroUju ratiunalniStva. Ker vefiino tekmovalcev spremljajo utll tel j i ratiunaln iStvai je tekmovanje tudi priloSfnost za. izmenjavo izkuSenj in mnenj. Zato je potekal vzporedno s tekmovanjem tudi pogovor o pouku raKunaln iStva v usmerjenem i zgbratfevan ju < računalniških poklicihi ratiunal n iSk i opremi za srodnje Šole in kadrovskih potrebah. Na tem pogovoru so se sreBati predstavniki viSjih in visokih Boli predstavniki izobraSevalne skup­ nosti in uporabniki iz razliUnih delovnih organizacij. Po tekmovanju so si udeleifenci organizirano ogledali bliiJnje ratiunaln i Ske centrei predstav­ niki viSjih in visokih Sol iz obeh slovenskih univerz pa so jih podrobneje seznaniti s Študi­ jem in utinimi nafirt i svojih organizacij. Sledila je razglasitev rezultatovi na kateri so prvouvrStien i tekmovalci prejeli plakete in knjižne nagrade. II. Naloge za ubence po prvem letu pouka ratiunal n iSt va . tias reševanja je 2 uri in 30 minut. Dovoljena je uporaba vse literature. Ena naloga od petih je neobvezna. 1. NapiSi programi ki izpiSe naslednjo tabelo Števil: ... D00 1000 ... ... O O 1 1 1 O O ... ... O 1 2 3 2 i O ... ... 1 3 6 7 6 3 i ... V tabeli je prva vrstica sestavljena iz samih nitielt le srednje Število je ii vsako Število v naslednjih vrsticah pa je enako vsoti treh nad njim teiietiih Števil iz prejSnje vrstice. Tabela naj se izpiSe v 21 stolpcihi izpis pa se naj kontiai ko so vsa izpisana Števila v zadnji vrsti razlitina od n i t!. 2. Imamo tako ozek mosti da se na njem dva avtomobila ne moreta sretiati. Na vsakem koncu mostu je postavljen semafor in tipalo ki povei tie pred mostom tiaka kak avtomobil. Tudi sam most je opremljen z instrumeniom i ki povei te je na mostu kak avtomobil. NapiSi postopek za krmiljenje semaforjevi ki bo skrbeli da nihtie ne tiaka po nepotrebnem in da se promet v konicah odvija izmeniCno (mosl je zelo kratek). Naprave ob mostu krmilimo z naslednjima podprogramoma in podprogramsko funkc i jo: 77 ODPRKstr) ZAPRKstr) TIPALO(t) str j stran povzr stran str j mostu imeno t ozn radi avto. t ipal mostu mostu povei zazna ga za DA> s e oznaka ene i i mostu. ODPRI ot! i I da se na i odpre semafo e spet oznaka . ZAPRI zapre van i sirani i aHujei katero vpragalii Be v t lahko oznat! 0 na eni izmed 1 ali pa tipal . TIPALO je fu Be imenovano va kakiien avto znavai je njen icer pa NE. zmed imenovan i r i stran i semafor na tipalo bi idi kak uj e bodi s i stran i ona nkc i j a I ki t ipalo mob i I. tie a vrednost Imeni strani mostu sta A in Bt ime tipala na mostu pa je M. Ai Bi Hi DA in NE so vnaprej definirane konstante. Primerii OOPRI(A) ZAPRI(B) TIPALO(M) TIPALO(B) Odpre semafor na strani A. Zapre semafor na,strani B. loa vrednost DA i tie je na mostu kak avto. Ima vrednost NEi tie na strani B n i voz i I, 3. Definirani imamo naslednji funkciji (n ja naravno St evilo)s s( fn gj. a95 Deljenje je ce lo£t ev i I tinoi n mod 10 pa pomeni ostanek pri deljenju n z 10. p9! a) IzraBunaj s<1532'r) in p(1532'^). b) Kaj raUuna funkcija s (razloiti). Neobveznol c) DokaiJii da za vsako naravno število n velja p(n) je ostanek pri deljenju n z 9. ^. Neki programer sumljivih kvalitet nam je prinesel naslednji programi C program obrne podatke INTE6ER Tl I I T I- ->l I + + se ustavi se ne ustavi A) Predpostavil da bi imelj tak program T. S pretvorbamii ki so izvedljivei ga spremeni v drugatien programi ki gotovo ne obstoja, tie so pretvorbe zanesljivo izvedljivei potem T ne obstoj a. B) Programi ki naj bi se po enem razmisleku ustavil in se po drugatinem razmis leku - ne bii zanesljivo ne obstoja. III. Naloge za uBence po drugem letu pouka raBunaln iStva. (Pogoji so isti kot za tekmovelce po prvem letu pouka.) 1. n otrok se hoBe loviti. Poznajo izStevanko z m besedami. NapiSi programi ki povei kateri od otrok lovi. Otroke oStevilBimo s Številkami od 1 do n in zaBnemo iziitevati pri prvem otroku. Lovi tistii ki zadnji ostanel v krogu. 2. Neko informacijo imamo natisnjeno na papirju v posebni kodi. Na papirju so izmenitino Brni in beli pasovi. Tanki pasovi (tako tirni kot beli) pomenijo niBloi debeli pa enico. Debeli pasovi so dvakrat debelejši od tankih. NapiSi postopeki ki bo izpisal zaporedje nibel in enici ki je zakodirano na papirju. S tiitalnikom se premikamo po.papirju s konstantno hitrostjo. Za ugotovitev hitrosti imamo pred informacijo na papirju en tanek lirn pas. Za Bitanje imamo na voljo naslednji funkc i j i: BARVA povei kakSna barva je trenutno pod glavo ti i taln ika. BAS nam pove Bas v mi I isekundahi ki je pretekel od zaBetka programa. Primeri I 00 I o I 000 I OO I 00 I OOOO t 00 I o I < 00 I KakSen bi bil algoritemi ki bi se prilagajal spremenljivi realni hitrosti odBitavanja? 3. Za nenegativna Števila n imamo definirane funkcije fi g in h takole: ?3 f (n) C O gjL n^O i 1 £e. n=l L f (n-l) + f (n-2) fle. n>li f a Ve_ n=0! •( b ge. n=U \,h(b,a+b>n-l) h(aibin) g H£. n>l) a) Izratfunaj f(S) in g(S). b) Pokadil da za vsak ai b> c; d in E volja: hiI F0RMAT(tXilQI10) CALL EXIT END program t(inputloutput)t var i 1 j ) z lint egeri ai arravCl..lOtl..103 of integeri begi n f or i ! = 1 t_o_ 10 do f or j I =1 12. 10 do readCaC i I j])i f or i '=1 Lo. 10 da. for i;=1 to 10 do begi n z:=aC i t j 3 i aC i 1j3! = aC jii 3 i aCjIi3i=z endi for i 1 = 1 to. 10 dO: begi n for j ! = 1 t_o 10 do uriteCaCiIj3> i wr i t e I n end end. Izojisli si primerne podatke za ta program in zapisi podatke in rezultate. Ali lahko uganeSi kaj je imel programer v mislih in popraviš program takot kot misliS« da bi moral delovat i 7 D* OS 06 C7 07 09 10 089 073 074 073 073 072 069 ti 063 12 13 14 14 061 059 057 1 037 flarjan HorvatiBi Gimnazija Novo mesto Ester Zimici So "Vojvodina" - gimnazija Tolm i n Bojan Cestniki I. gimnazija Ljubljana - Bežigrad Andrej Brodniki I. gimnazija Ljubljana - Bežigrad Tomi Dolenc« I. gimnazija Ljubljana - Bežigrad Dario NedoSi Gimnazija Koper Nada žagan Gimnazija in ekonomska Solai Trbovlje Gorazd Plani nSifli I. gimnazija Ljubljana - Bežigrad Jana Padežniki Gimnazija MiloSa ZidanSka - Maribor MiloS Požari Gimnazija Nova Gor i ca Simona Jaklitii I. gimnazija Ljubljana - Bežigrad Metod Purgari Center srednjih So I - Jesen i ce PO drugem letu pouka raBunalniStva Mesto i St. toBk 01 1 02 03 04 05 06 07 08 09 10 10 12 13 14 0S3 031 077 069 064 054 033 051 047 046 046 043 1 042 i 039 14 039 Ist a na loga kot 3. 1. letu pouka. naloga za tekmovalce po I Tekmovalec' -+ Mark PleSkoi VII. gimnazija Vitf - Ljubljana Kazimir GomilSeki Gimnazija MitoSa ZidanSka - Maribor Matjaž Lampei I-. gimnazija Ljubljana - Bežigrad Cveto Gregoroi I. gimnazija Ljubljana - Bežigrad Milan Bizanti Gimnazija Ljubijana - Šentvid Darko Hanželi I. gimnazija Ljubljana - Bežigrad Janez Bontiai I. gimnazija Ljubljana - Bežigrad Sreeko StariCi Gimnazija Novo mesto Rado Juvani Gimnazija-ekonoraska Solai TrbovI j e Marko AhBani VII. gimnazija Vi B - Ljubi j ana Branko Prerazeli TehniSka elektroi strojna in tekstilna Bola Maribor Cveto BrkiCi Gimnazija Novo mesto Borut Starihai Prva gimnazijai Maribor Nada Lilieni Šolski center Idrija - gimnazija Jurija Vege Miran Ulbini Gimnazija MiloBa ZidanSka - Maribor IV, Rezultati prvih petnajstih tekmovalcev v V^^Ki skupini PO prvem letu pouka raBunal n iiftva Mesto I St. toBk ITekmovaleo I Mirjam LeSniki I. gimnazija I Ljubljana - Bežigrad I Anton VerbovSeki I. gimnazija I Ljubljana - Bežigrad I UroS Kunaveri I. gimnazija I Ljubljana - Bežigrad 01 02 03 111 104 103 V. ReSitve nalog za uCence po prvem letu pouka raBunalniStva 1. Program za izpis tabele najprej v fortranui nato pa v pascalu: C program tab INTEGER X(21)iY(21)iIiP C Sestavimo prvo vrstico DO 1 I=li21 X(I)=0 1 CONTINUE X(11)=l C Dokler ni prvo Število v vrsti razlIBno C od O ponavI j amo 79 2 C 3 C C 4 C 3 CONTINUE Izpis vrst(oe gRITE(3i3>(X(I)iI=ti21) F0RMAT(21X6) P je prvo Število v izpisani vrsti P=X(1) Izrabunamo novo vrsto ... Y(l)-X(t)+X(2) Y<21)=X(20)+X(21) DO A I»2i20 Y(I> = X(l-'l)+X for i 1=1 ti m« do xCi3i=QI iCmi div 2+131=1! < Dolder ni prvo Btevilo v vrsti razliHno od D ponavI j amo } pageI repeat < izpišemo vrsto > f or i i =1 Le. mx do write(xCi3!i)I wr i t eIn i < p je prvo število v zs izpisani vrsti > pi>'xC13 I < izračunamo novo vrsto ... > yC13i=xC13+xC23l yCmx3i=xCmx-13+xCmx3J for i!=2 li mx-l do 'y[:i3! = iCi-13 + iCi3 + iCi+lDi { ... in jo prepišemo v staro > f or i 1 = 1 to. mx do xCi3>=yCi3i until pOOI • nd. 2. ReSitev zapiSemo (skoraj) v pascalu. Iz pascala se postopek tako jasno vidii da ji zapis v slovenStiini nepotreben. program mostfoutput)I tvpe pr isot en<=(DAiNE) I tol!ka°(AiBin) I < ukazi za krmiljenje naprav na mostu > procedure odpri(x» toBka)! extBrnl procedure zaprl(xi toOks)! ex tern I funotion tipalo(xi toBka)! prisotenl B»ternt procedure Drehod(iiyi toCka)! < Be je na strani i.kakSen avtoi potem enega spusti Bez most. > feeaio. repeat until tipalo(M)°NEI if tip8lo(x)=DA then beg in zapr i(y)1 odpri < X)J repeat until tlpalo(M)°DA end • tndi fegajjl {most> zapri(A)! zapriCB)! rppeaV prehod(AiB)I prehod(BtA) '• wntil false end . a) s(1532A) = 5(1532)+'. = sC153)+2+4 = s(15)+3 + 2+4 •= B(1)+5 + 3+2+A = 1+5+3 + 2+'. = n p(1532A) - plsdSSi*)) = p(15) = p(s(15)) = p(6) = fe, b) s IzraSuna vsoto cifer (v desetiškem zapisu) svojega argumenta. Utemeljitevi vsota cifer enomestnega Števila (t. j. Števila, ki je manjBe od 10) je to Število samo. Vsoto cifer veBmestnega Števila pa dobimo takoi da zadnji cifri prištejemo vsoto cifer tega Števila brez zadnje cifre, n mod 10 je oBitno zadnja cifra Števila n v desetiškem sestavui n / 10 (celoStevi IBno) pa je Število n brez zadnje cifre. o) Trditev oBitno velja za n9. Naj trditev velja za vse n9i velja p(k) = p(5(k)). Ker je k>9i je s(k) (vsota cifer v Številu k) gotovo manjSa od ki zato lahko uporabimo hipotezoi da trditev velja za vse nNiM 1 F0RMAT(2I2) C vsi otroci so v krogu C predpostavljamo 10 DO 2 I=liN 0TR0CI(I)=1 2 CONTINUE C zaBnemo s prvim P=0 C N-1 jih mora izpasti DO 5 l=2iN C vsakokrat moramo Šteti do H 00 A J=liM C Izpadlih otrok ne smemo Šteti 3 CONTINUE P=P + -1 C Štejemo v krogu (za n-tim sledi C prvi otrok) IF(P.6T.N)P=1 IF(0TROCI(P).EQ.O)60 TO 3 i> CONTINUE C otrok P Izpade OTROCI(P)=0 5 CONTINUE C poiSBemo edinega neizpadlega otroka P=l 6 IF(OTROCI(P).NE.O)GO TO 7 P=P + 1 60 TO 6 7 CONTINUE C Izpis WRITE(3i8)Ntt1iP B FORMATClStevi lo otrok'iI10/ ' doiaina izStevanke'113/ •Dlovi otrok'ilt3) CALL EXIT END program izstevanka(1nputloutpui)I const mx=30l var mmiiijipiintegeri otroci:arrayCl..mx3of boolean) begin readln(nim)) { ttitanje > < vsi otroci so v krogu > < predpostavljamo l0 f or ii = l i_o_ n do. ot roc iC f 3 i.= true I < zaBnemO s prvim > pi=OI < n-1 otrok mora izpasti > f or i 1 = 1 io. n-1 do begin < viiakokrat moramo Šteti do m > for i;=l to m do < izpadlih otrok ne smemo Šteti > pepeat p:=p+li i Štejemo v krogui n-temu s I e-d i prvi > i f p>n then p!=li unt i I otrociCp]! < otrok p izpade > otroo i Cp3:=f al se endi < poiSBemo edinega neizpadlega otroka } pi°ll whi le not otrociCpl do. pi=p+li { izpis > page(output)! vritelnC Število otrok" i n s 10) I writeln(" dolžina izStevanke"im:5)I wr1telnI writeln(" lovi olrok"ip!l3) end. 2. Postopek zapiSemo (skoraj) v pascalui kar ne more Škoditi preglednosti. program barcode(output)i tvpe Bb=(BrnaibeI a)! var titOizakasc integerl b! Bbi podat: 0..1 i functIon barva! Bbi ex t ern i funct ion Bas! integeri e» t ern i i begin < ignoriramo belino vse do zaBetka > repeat unt i I barva = Brnai < izmerimo Širino prvega Urnega pasu } ti=Basi repeat un t i I barva=bela! tO!=Bas-ti < tO je Bas za prelet nlBte > < pravo Bitanje se zaBenja > repeat t!=Bas5 bi=barvai < poBakamoi da Bitalnlk pride do spremembe barve } repeat unt 1 I barvaObi zakas!=Bas-t i < zakas je Bas potovanja Bez zadnji pas } < odloBImo sei ali je to D ali 1 > 1f zakas>1.5*t0 then begin podat:=11 < popravimo vzorBnI Bas > tO!-zakas/2 end else beg i n podat:=0I < popravimo vzorBni Bas > tO!=zakas endi wri te(podat) unt i I fatse end. Osnovni postopeki ki bi deloval le pri konstantni hitrostii ne potrebuje popravljanja vzorBnega Basa. V program bi lahko vgradili Se test za kongo podatkov (npr. Be se barva zelo dolgo ne spremeni) i vendar tega naloga ne zahteva. a) f(5) = f(A)+f(3) = f(3)+f(2)+f(3) = f(2)+f(l)+f(2)+f(3) = f(l)+f(0)+f(l)+f(2)+f(3) = 1+0+1+f(l)+f(0)+f(3) = 1+0+1+1+O+f(2)+f(1) 1+0+1+1+O+f(l)+f(0)+t(l) = 1+0+1+1+0+1+0+1 S.' kar se seveda laSlje IzraBunai Be zapiSemo tabeloi 81 n I O + f(n) I O 1 2 + 1 1 6 7. . . + + - 3 -13, . . 0(5) = h(0ili5) = hCl.1.4) = h( 1.2.3) = h<2.3.2) = h(3.5.1) = 5 b) t)s so as b) C in d. e poljubna nenegativna cela ittevilag je treba dokazati, da velja f(aibie) + fb+c+dik-l)i h(a+oib+d)k) = h(b + dia + o+b+d.k-1) . S tem je trditev dokazana. c) Dokazati moramo, da za vsak nenegativen cel n velja f(n) = gl.k-2) = h(1.2>k-2) g(k) = h(O.l.k) = hCl.l.k-l) = h(1.2.k-2) Prepritiali smo se. da tako f kot g raCunats fibonacci jeva Števila. Opazimo lahko, da js pri tem g v primerjavi z f mnogo uSinkovitejBa. i,. Program preKita ce I oB t ev i I bno matriko velikosti 10x10. IzpiBe jo nespremenjeno. Programer je hotel verjetno matriko transponirati. kar bi dosegel. Be bi program popravil takole! DO 3 1=1.10 DO 2 J=l!l 2=A(1.J) f or i i =1 to. 10 do for j i =1 ta i -1 do b e g i n ge laSJJB pa je odstraniti zanke in zamenjati indekse pri izpisui REA0<2.1)((A(l.J).J=.. 1 FORMAT ... HRITE(3.4)((A(J.I).J=. I . . . IreadCaCi tj3)I I { zank i za izpis } I wr i le(aCj.i 3 i I . . . (Veljavno refiitev dobimo tudi. De si mislimo, da je programer hotel kaj drugega, le program je treba pravilno popraviti.) 5. Glej 5. nalogo pri nalogah za uCence po enem letu pouka. TABELA 18 Število udBležencev na vseh treh t ekmovan j ih I 1977 I 1978 I 1979, I + + + -r - + po 1. letu I 7 I 52 I 56 I + +-- + + po 2. letu I 7 I 27 I 36 I + + + + skupaj I 47 I 79 I 92 I + + + +• Opomba! V letu 1977 tekmovanje ni bilo loCeno na dve skupini. TABELA 2i Število tekmovalcev In povprefien uspeh po Bolah Bola at. t ekmovaloev in povpreBno St. toBk po 1. letu po 2. letu St . pri j avl jen ih tekmovalcev Center srednjih Sol - Jesenice CSS Brnoraelj - gimnazija sploSne smeri Ekonomska srednja Bola Brnomelj Elektrotehniška srednja Šola KrSko Elektrotehniška Šola v Ljubljani Gimnazija "Boris Ziherl" Skofja loke ^Gimnazija KoHevje Gimnazija Koper Gimnazija Ljubljana - Šentvid Gimnazija MiloSa ZidanSka - Maribor Gimnazija Nova Gorica Gimnazija IMovo mesto Gimnazija Trbovlje I. gimnazija LJubljana - Bsifigred Prva gimnazija Maribor Bo Idrija - gimnazija Jurija Vege Se "Vojvodina" - gimnazija Tolmin Tehniška el. str. in tekstilna Šola Maribor Tehniška strojna In elektro gola« Trbovlje Tehniška tekstilna Bola. Kranj VII. gimnazija Ljubljana ViB 51.00 18.00 7.50 2 1 7 4 2 3 2 2 « 3 4 a 0 0 1 0 7 1 0 21 19 24 9 26 39 35 51 45 54 42 82 - - 75 - 20 40 - 50 00 29 50 50 00 00 50 00 33 25 50 -- — 00 -- .00 00 -- 0 0 4 0 1 2 3 0 4 1 5 6 1 1 3 D 0 3 14,50 34.00 41.50 48.00 33.50 47.00 57.40 26.50 23.00 39.00 23.33 49.67 2 2 20 10 3 12 8 6 5 10 7 13 6 1 2 3 B t 3 Skupaj 56 40.00 36 34.50 137 Število Sol Število gimnaz i j Število tehniških srednjih Sol 17 11 6 13 11 2 21 14 7