Jakub Tomek
N´ahradn´ı text k cviˇcen´ı 4.11. Tento text m´ a 3 r˚ uzn´e ˇc´ asti: prvn´ı pojedn´av´a o podprogramech (funkc´ıch a procedur´ ach), jak se zapisuj´ı a pouˇz´ıvaj´ı. Druh´a ˇc´ast je struˇcn´ y popis algoritmu Eratosthenovo s´ıto. Tˇret´ı ˇc´ast je n´avod k pouˇz´ıv´an´ı debuggeru (lad´ıc´ıch prostˇredk˚ u). Omlouv´ am se za m´ısty oˇskliv´e vys´azen´ı a pˇreteˇcen´ı ˇr´adk˚ u... kdyˇz to nˇekoho bude smrtelnˇe ur´ aˇzet, dejte mi vˇedˇet a sprav´ım to.
1
Podprogramy
1.1
Pˇ r´ıklad jednoduch´ e funkce a jej´ı rozbor
Prve se pod´ıvejme na zdrojov´ y k´od, ve kter´em je deklarov´ana funkce max2, kter´ a n´ am d´ a vˇetˇs´ı ze dvou ˇc´ısel. program testmaxima; var x,y,z:integer; function max2(a,b:integer):integer; begin if (a>b) then max2:=a else max2:=b; end; begin read(x,y); z:=max2(x,y); write(z); end. Rozeberme si tuto uk´ azku: • Funkce se deklaruj´ı za promˇenn´ ymi hlavn´ıho programu a pˇred beginem hlavn´ıho programu. M˚ uˇzete jich deklarovat libovolnˇe mnoho za sebou. Pozn´ amka trochu stranou - pokud vol´ate funkci A ve funkci B, pak funkce A mus´ı b´ yt deklarov´ ana pˇred funkc´ı B. To obecnˇe nen´ı probl´em (jenom otrava), probl´em je, kdyˇz v´am vznikne cyklus (funkce A vyˇzaduje funkci B, B vyˇzaduje C a C vyˇzaduje A). Pak se neobejdete bez tzv. “forward deklarace”, coˇz by mˇelo b´ yt brzy na pˇredn´aˇsce. • Z´ apis funkce je n´ asleduj´ıc´ı:
1
– function - Kl´ıˇcov´e slovo, kter´ ym d´av´ate najevo, ˇze budete vytv´aˇret funkci. – n´ azev funkce - Zde max2. Pro n´azvy funkce plat´ı obdobn´a pravidla jako pro n´ azvy promˇenn´ ych. – seznam parametr˚ u - Zde (a,b,:integer) - tj. funkce m´a na vstupu dvˇe promˇenn´e typu integer. Tyto parametry jsou vstupem dan´e funkce (obdobnˇe jako sˇc´ıtance jsou vstupem funkce sˇc´ıt´an´ı dvou ˇc´ısel). Nˇekdy m˚ uˇze b´ yt funkce i bezparametrick´a. – :typ; - Typ n´ avratov´e hodnoty: napˇr. kdyˇz sˇc´ıt´ate 2 ˇc´ısla, tak n´avratov´a hodnota - souˇcet - je cel´e ˇc´ıslo. Nebo kdyˇz programujete spojen´ı dvou ˇretˇezc˚ u (string˚ u), tak n´avratov´a hodnota bude string. Pozor na stˇredn´ık na konci ˇr´adku, na ten se s oblibou zapom´ın´a. N´avratov´ y typ m˚ uˇze b´ yt jen jednoduch´ y typ - integer, string, real, boolean apod. Ne tˇreba pole. – var (tady zrovna nen´ı) - Jako u hlavn´ıho programu pˇred beginem m˚ uˇzete d´ at slovo var a tam definovat tzv. lok´aln´ı promˇenn´e (vizte d´ ale). – begin - k´ od funkce, end; - To, co se vykon´av´a v r´amci funkce se omez´ı, jako u hlavn´ıho programu, blokem begin-end. Ovˇsem pozor, neukonˇcuje se teˇckou, ale stˇredn´ıkem. – Jak urˇcit, co funkce vrac´ı, jak´a je tedy jej´ı n´avratov´a hodnota? Kdyˇz funkce skonˇc´ı (typicky dojde na end, kter´ y ji uzav´ır´a), pod´ıv´a se na obsah “promˇenn´e” urˇcen´ y n´azvem t´e funkce (jej´ıˇz typ jsme deklarovali za dvojteˇckou v deklaraci funkce) - v naˇsem pˇr´ıpadˇe v promˇenn´e max2 (vˇsimnˇete si, ˇze jsme ji nikde nedeklarovali, je implicitn´ı, dan´a existenc´ı funkce toho jm´ena). A tuto hodnotu vr´at´ı. • To, ˇze funkce “vrac´ı” hodnotu, znamen´a, ˇze tuto hodnotu m˚ uˇzete tˇreba uloˇzit do jin´e promˇenn´e (v naˇsem pˇr´ıpadˇe ji ukl´ad´ame do promˇenn´e z). Rozhodnˇe funkce nic sama o sobˇe nevypisuje. Kdyˇz m´ate integerovou promˇennou x, tak´e mus´ıte napsat write(x), abyste jej´ı hodnotu vypsali. A funkce s n´ avratov´ ym typem integer se v podstatˇe chov´a jako integer, jen chvilku trv´ a, neˇz se zjist´ı, jakou m´a hodnotu. • Jak vlastnˇe prob´ıh´ a zavol´an´ı funkce? V naˇsem hlavn´ım programu prve naˇcteme dvˇe ˇc´ısla a pak do promˇenn´e z uloˇz´ıme n´avratovou hodnotu funkce max2. Jak to v˚ ubec funguje? Kdyˇz se v programu dostaneme k vol´ an´ı funkce, vezmou se hodnoty promˇenn´ ych, kter´e vkl´ad´ame (zde x,y) a zkop´ıruj´ı se do pˇr´ısluˇsn´ ych lok´aln´ıch promˇenn´ ych volan´e funkce (zde a,b). Pak se projde k´ od funkce aˇz na konec a na konci se zkontroluje, co je uloˇzeno v promˇenn´e s n´azvem dan´e funkce (zde max2). Tato n´avratov´a hodnota pak “nahrad´ı” m´ısto, kde jsme funkci zavolali a uloˇz´ı se do promˇenn´e z.
2
1.2
Procedury
Procedura se zapisuje takˇrka stejnˇe jako funkce - jen kl´ıˇcov´e slovo nen´ı function, ale procedure a nic nevrac´ı. Aˇz se dostaneme k pˇred´av´an´ı parametr˚ um odkazem, uvid´ıme, ˇze procedury nejsou tak k niˇcemu, jak by se ted’ mohly zd´at.
1.3
Lok´ aln´ı a glob´ aln´ı promˇ enn´ e
V programu za slovem var se deklaruj´ı promˇenn´e glob´aln´ı - viditeln´e a platn´e po celou dobu bˇehu programu. Uvnitˇr podprogram˚ u pak m˚ uˇzete deklarovat funkce lok´ aln´ı. Hodnoty parametr˚ u pˇredan´ ych hodnotou (v pˇr´ıkladu v´ yˇse a,b) jsou tak´e lok´ aln´ı promˇenn´e. Rozd´ıl oproti glob´aln´ım promˇenn´ ym je, ˇze pamˇet’, kterou zab´ıraj´ı lok´ aln´ı promˇenn´e, je uvolnˇena po dobˇehnut´ı podprogramu, kde jsou deklarov´ any, coˇz je uˇziteˇcn´e (proˇc zab´ırat pamˇet’ zbyteˇcn´ ymi glob´aln´ımi promˇenn´ ymi, kdyˇz nejsou nutn´e?). Pozor na pouˇz´ıv´an´ı lok´aln´ıch promˇenn´ ych stejn´eho jm´ena jako m´ a nˇejak´a glob´aln´ı promˇenn´a tehdy “plat´ı” hodnota lok´aln´ı promˇenn´e. Snaˇzte se pouˇz´ıv´an´ı stejnˇe pojmenovan´ ych promˇenn´ ych radˇeji vyhnout, je-li to moˇzn´e, pˇrehlednosti programu to nepom´ah´a.
1.4
Kˇ cemu to v˚ ubec je?
Pozitiva podprogram˚ u lze shrnout zkratkou ZOMPIE1 • Znovuvyuˇzitelenost: Kdyˇz uˇz m´ate napsanou funkci, u kter´e v´ıte, jak funguje, m˚ uˇzete ji snadno pouˇz´ıt i v jin´ ych programech. Dokonce vznikaj´ı jen soubory s funkcemi (knihovny, v Pascalu se zvouc´ı unity), kter´e sdruˇzuj´ı ˇcasto pouˇz´ıvan´e funkce urˇcit´eho typu, vy pak jen ve sv´em programu d´ate poˇc´ıtaˇci najevo, ˇze chcete nˇejakou knihovnu vyuˇz´ıt a pak m´ate pˇr´ıstup k jej´ım funkc´ım (takˇze tˇreba d´ıky knihovnˇe vektorov´eho poˇc´ıt´an´ı dostanete “zadarmo” funkce, kter´e v´am poˇc´ıtaj´ı skal´arn´ı, ˇci vektorov´ y souˇcin, u ´hel mezi vektory, um´ı vektory normalizovat a ˇsk´alovat atd. - tyhle vˇeci pak nemus´ıte ps´ at sami). • Oddˇelen´e ladˇen´ı: Napsat dlouh´ y k´od a zjistit, ˇze vlastnˇe poˇr´adnˇe nefunguje, je nepˇr´ıjemn´e. Zjistit kde je chyba m˚ uˇze b´ yt obt´ıˇzn´e. Kdyˇz pouˇz´ıv´ate podprogramy, m˚ uˇzete oddˇelenˇe ladit tyto podprogramy (kter´e neb´ yvaj´ı tak rozs´ ahl´e) a kdyˇz v´ıte, ˇze funguj´ı spr´avnˇe, pak je skl´adat do dalˇs´ıch program˚ u. • M´enˇe k´ odu: Pokud ve sv´em k´odu potˇrebujete na deseti m´ıstech zjistit maximum z dvou ˇc´ısel, je ˇsetrnˇejˇs´ı jednou napsat 6 ˇr´adk˚ u funkce, kter´a v´ am to maximum poˇc´ıt´a a pak na kaˇzd´em m´ıstˇe tu funkci na jednom ˇr´adku zavolat, neˇz na kaˇzd´em z potˇrebn´ ych m´ıst vypsat 4 ˇr´adky. Tak´e, kdyˇz nepouˇz´ıv´ ate podprogramy a m´ate jeden k´od na v´ıce m´ıstech, m˚ uˇze nastat 1 Pokud m´ ate dojem, ˇ ze jsou pojmenov´ an´ı maliˇ cko ohnut´ a, abychom mˇ eli pˇ eknou zkratku, nen´ı to pouze dojem. Ale nen´ı to jeˇstˇ e tak zl´ e - jsou tˇreba “hezk´ e” zkratky, ve kter´ ych N je zkratka za “non-nonsensical” :).
3
probl´em, kdyˇz nˇeco na tˇech k´odech chcete zmˇenit. Napˇr´ıklad m˚ uˇzete jeden z tˇech k´ od˚ u opomenout, nevˇsimnout si ho, a zmˇenit jen ostatn´ı. To pak vede k dost nepˇr´ıjemn´ ym chyb´am (vˇzdyt’ vy v´ıte, ˇze jste to vˇsude zmˇenili, tak proˇc to nefunguje?). Kdyˇz m´ate takov´ y k´od ve funkci a zmˇen´ıte k´od funkce, automaticky se to projev´ı na vˇsech m´ıstech, kde funkci pouˇz´ıv´ate. • Pˇrehlednost: Pouˇz´ıv´ an´ım funkc´ı je zdrojov´ y k´od v´ yraznˇe pˇrehlednˇejˇs´ı. Pod´ıvejte se tˇreba na metodu logic (staˇc´ı d´at vyhledat “logic” a hod´ı v´ as to tam) zde: http://code.google.com/p/smart-path-unreal-2004/source/browse /Hunter/src/cz/cuni/amis/pogamut/ut2004/examples/Hunter.java?spec=svn11&r=11 Je to metoda ovl´ adaj´ıc´ı bota v Unreal Tournamentu 2004. Mˇelo by b´ yt velmi zhruba jasn´e, jak se bot m´a chovat - je celkem patrn´e, co dˇel´a. Kdyˇz byste “funkce” (v dan´em jazyce se tomu ˇr´ık´a metody) jako napˇr. canSeeEnemies(), isShooting() atd. nevolali takto, ale pˇr´ımo tam napsali jejich k´ od, bylo by to naprosto neˇciteln´e. • Izolace k´ odu: Kdyˇz dostanete funkci u kter´e v´ıte, co pˇrij´ım´a za vstupn´ı parametry a co vrac´ı, nemus´ıte v˚ ubec ˇreˇsit jej´ı vnitˇrek a m˚ uˇzete ji rovnou pouˇz´ıt. • Efektivn´ı distribuovan´e programov´an´ı: Pokud m´ate k´od, kde je potˇreba 50 funkc´ı, m˚ uˇzete kaˇzdou nechat naprogramovat jin´ ym program´atorem a pak je jen poskl´ adat (samozˇrejmˇe program´atoˇri mus´ı dodrˇzet dohodnut´a pravidla, jak funkce komunikuj´ı - co pˇrij´ımaj´ı a co vracej´ı). Pˇredstava, ˇze 50 lid´ı m´ a napsat kus surov´eho k´odu a nˇekdo to pak slep´ı dohromady, je dosti dˇesiv´ a. Maj´ı podprogramy nev´ yhody? Ano - jejich pouˇz´ıv´an´ı trochu zpomaluje bˇeh programu. Ale nen´ı to typicky nijak v´ yrazn´e a v´ yhody pˇrevaˇzuj´ı.
1.5
Pˇ red´ av´ an´ı parametr˚ u odkazem a hodnotou
Funkce a procedury jak jsme se na nˇe zat´ım d´ıvali, maj´ı dva (moˇzn´a i v´ıce) probl´emy. Napˇr´ıklad neum´ı vracet pole. To m˚ uˇze b´ yt nˇekdy dost pot´ıˇz. Dalˇs´ı probl´em je, ˇze kdyˇz funkci vol´ame, parametry se kop´ıruj´ı do lok´aln´ıch promˇenn´ ych. To nevad´ı, kdyˇz pˇred´ av´ ame dvˇe ˇc´ısla. Ale kdyˇz pˇred´av´ame velk´e pole, uˇz to m˚ uˇze zabrat nezanedbatelnˇe ˇcasu. Tyto probl´emy ˇreˇs´ı pˇred´ av´ an´ı odkazem. Pˇred promˇenn´e, kter´e chcete pˇred´avat odkazem nap´ıˇsete v seznamu parametr˚ u kl´ıˇcov´e slovo var. K ˇcemu to vede? Uˇz v´ıme, ˇze kdyˇz pˇred´ av´ ame parametr hodnotou (bez var), vezmou se hodnoty promˇenn´ ych v programu a zkop´ıruj´ı se do lok´aln´ıch promˇenn´ ych podprogramu. Oproti tomu, kdyˇz pˇred´ av´ ame promˇennou odkazem, ve skuteˇcnosti pˇred´av´ame adresu promˇenn´e v pamˇeti poˇc´ıtaˇce (ˇctyˇr, ˇci osmibytov´e ˇc´ıslo). Podprogram dan´ y odkaz pˇrijme a d´ ale s n´ım pracuje. Nic se nekop´ıruje (takˇze kdyˇz d´ate jako
4
parametr pole, probl´em s d´elkou kop´ırov´an´ı odpad´a - protoˇze pracujete rovnou na p˚ uvodn´ım poli). D´ıky tomu, ˇze pracujete na “skuteˇcn´e” promˇenn´e z hlavn´ıho programu (a ne na kopii), m˚ uˇzete ji zmˇenit. D´ıky tomu m˚ uˇzete jakoby “vracet” pole a jin´e sloˇzen´e datov´e typy - pˇred´ate je odkazem a uvnitˇr funkce je zmˇen´ıte. Ilustrujme pˇred´ av´ an´ı odkazem na pˇr´ıkladu: program testvymeny; var x,y:integer; procedure vymen(var a,b:integer); var tmp:integer; begin tmp:=a; a:=b; b:=tmp; end; begin read(x,y); vymen(x,y); write(x,’ ’,y); end. Pouˇz´ıv´ ame zde proceduru, kter´a prohod´ı obsahy dvou promˇenn´ ych (tj. pokud naˇctete do x 5 a do y 6, tak v´am program vyp´ıˇse 6 5). Jak to funguje? Naˇcteme dvˇe ˇc´ısla a pak zavol´ ame proceduru vymen. Parametry pˇred´ame odkazem, takˇze a bude to sam´e jako x a b to sam´e co y. Podstatn´e je, ˇze jde vˇzdy o dvˇe pojmenov´ an´ı t´ehoˇz m´ısta v pamˇeti. Proto kdyˇz v proceduˇre prohod´ıme a a b a pak se vr´ at´ıme do hlavn´ıho programu, zmˇena pˇretrv´a. Oproti tomu, kdybychom proceduru deklarovali bez kl´ıˇcov´eho slova var, ve chv´ıli vol´ an´ı by se obsahy x,y zkop´ırovaly do lok´aln´ıch promˇenn´ ych a,b, v r´amci procedury by se lok´ aln´ı promˇenn´e prohodily, procedura by skonˇcila, lok´aln´ı promˇenn´e by zmizely a tedy by se v hlavn´ım programu v˚ ubec nic nezmˇenilo. Pro pˇredstavu - k ˇcemu m˚ uˇze b´ yt takov´e pˇred´an´ı odkazem? Napˇr´ıklad kdyˇz chcete vyvtvoˇrit podprogram, kter´a v´am setˇr´ıd´ı pole, nem˚ uˇzete to udˇelat pomoc´ı pˇred´ av´ an´ı hodnotou a funkc´ı - funkce v´am nedovol´ı vr´atit pole, protoˇze to nen´ı jednoduch´ y datov´ y typ. Mus´ıte to pole pˇredat podprogramu (proceduˇre) odkazem, ta procedura se na poli “vyˇr´ad´ı” a aˇz skonˇc´ı, uˇcinˇen´e zmˇeny pˇretrvaj´ı. Jin´ y, abstraktn´ı, pˇr´ıklad. Ve zpr´av´ach ted’ nˇekdy ˇslo, jak jak´asi matka hroznˇe tloukla sv´e d´ıtˇe, protoˇze zlobilo - a tloukla ho, aby se uklidnila. To je matka, kter´ a sv´eho potomka pˇredala proceduˇre bij(var p:dite) odkazem - takˇze bila skuteˇcnˇe svoje d´ıtˇe. Chytr´ a program´atorsk´a matka by to d´ıtˇe pˇredala hodnotou, ˇc´ımˇz by se vytvoˇrila lok´aln´ı kopie d´ıtˇete, kterou by bila, ale po skonˇcen´ı procedury by bit´e d´ıtˇe (kter´e ani nikdy v re´alu neexistovalo) zmizelo, ale p˚ uvodn´ı d´ıtˇe by bylo v poˇr´ adku (bita byla kopie). A matka by byla vyvztekan´a. Pouˇcen´ı pokud nechcete, aby skuteˇcn´a data byla poˇskozena, pˇredejte je hodnotou. Pokud 5
je vyslovenˇe chcete zmˇenit, pˇred´avejte je naopak odkazem. D´ame-li jin´ y pˇr´ıpad s d´ıtˇetem (uˇz ne tak straˇsliv´ y), pokud d´ıtˇe kˇriˇc´ı a chce k matce, tak pro matku nem´ a cenu volat proceduru pohladDite(p:dite) - tedy ˇze se d´ıtˇe pˇred´a hodnotou. Tehdy si matka vytvoˇr´ı kopii d´ıtˇete, kterou pohlad´ı, procedura skonˇc´ı, kopie d´ıtˇete zmiz´ı...a p˚ uvodn´ı d´ıtˇe poˇr´ad ˇrve, protoˇze ho nikdo nepohladil. Chytr´a matka zde naopak pouˇzije pˇred´an´ı odkazem, tedy pohladDite(var p:dite) - a pohlazeno v dan´e proceduˇre bude skuteˇcn´e d´ıtˇe.
1.6
Nˇ ekolik pˇ r´ıklad˚ u
Trivi´ aln´ı procedura, kter´ a vyp´ıˇse zpr´avu urˇcenou parametrem a za to jeˇstˇe vyp´ıˇse hl´ aˇsku chv´ al´ıc´ı m´ıstn´ıho kr´ale (coˇz se hod´ı tˇreba kdyˇz v´am kr´al hroz´ı, ˇze v´ as poprav´ı, kdyˇz za kaˇzd´ y v´ ypis nenap´ıˇsete pochvalu jeho vzhledu a inteligence - pak je riskantn´ı pouˇz´ıvat obyˇcejn´e write a writeln, protoˇze tˇreba zapomenete tam nˇekde tu pochvalu explicitnˇe nat’ukat a...). procedure vypis(s:string); begin write(s,’, nas kral je krasny a chytry’); end; A ted’ uˇz “sloˇzitˇejˇs´ı” program - naˇcte dan´ y poˇcet prvk˚ u do pole a vˇsechny ˇ v´ yskyty maxim´ aln´ıho prvku nahrad´ı nulami. Ceho si vˇsimnout - nov´eho slova const, jak vyuˇz´ıv´ ame pˇred´ an´ı hodnotou a odkazem. A taky divnosti, ˇze kdyˇz pˇred´ ate pole odkazem, tak se v´am posunou jeho indexy. Zkuste si program proj´ıt krok po kroku a uvˇedomit si, proˇc a jak funguje. program funkcicky; const N=10; {Pred promennymi lze takto deklarovat konstanty - k cemu to je? Kdyz bych vsude v kodu misto N napsal 10 a pak se rozhodl, ze to vlastne chci pro vetsi ulohu a ma tam misto toho byt 100, tak u vetsiho kodu nebude legrace najit vsechny vyskyty. A kdyz nejaky prehlednete, muze to byt dost peklo. Mimochodem, tuto hodnotu muzete pouzit, jak vidno nize, jako urcovac velikosti pole. } var i:integer; pole:array[1..N] of integer;
function maximumVPoli(p:array of integer):integer; {Vsimnete si, ze se nedeklaruje velikost} {Vraci maximalni hodnotu v danem poli. Slo by parametr predat i odkazem, jelikoz puvodni pole nenicime, ale jenom cteme.} var j,max:integer; begin max:=p[1]; {Prvni prvek prohlasime za maximum} 6
for j:=1 to N do {A projdeme zbyvajici prvky.} begin if (pole[j]>max) then {Kdyz je nejaky prvek vetsi nez dosavadni maximum, prohlasime ho za nove maximum.} max:=pole[j]; end; maximumVPoli:=max; {Vratime maximum v danem poli.} end; procedure vynulujMax(var p:array of integer); {Vsechny vyskyty nejvetsiho cisla v posloupnosti nahradi nulami. Je to tzv. "edukativni" priklad, takze se neptejte, proc by to nekdo chtel delat :)} var k,max:integer; begin max:=maximumVPoli(p); {To je krasa - uz umime maximum, tak to pouzijeme, vubec neni treba to psat znovu.} for k:=0 to N-1 do {Kdyz predate pole odkazem, automaticky se posune, ze ma zacatek na nule (tj. z [1..10] to vyrobi [0..9]). Zda se vam to taky tak divne jako mne? Priste si rekneme neco, s cehoz pomoci tento problem obejdeme.} begin if (p[k] = max) then p[k]:=0; end end; begin {Az tady zacina vlastni hlavni program.} for i:=1 to N do {Nacteme N cisel} read(pole[i]); writeln(maximumVPoli(pole)); {Jen tak pro cvik si napiseme maximum v poli.} vynulujMax(pole); {Zde probehne vynulovani maxim.} for i:=1 to N do {A vysledne pole vypiseme, abychom videli zmenu.} write(pole[i], ’ ’); end.
2
Eratosthenovo s´ıto
Na cviˇcen´ı jsme probrali (a doma naprogramovali) jednoduch´ y algoritmus testov´an´ı prvoˇc´ıselnosti. Nen´ı to ale moˇznost jedin´a. Dejme tomu, ˇze v´ıme, ˇze program nebude pracovat s vˇetˇs´ım ˇc´ıslem, neˇz je nˇejak´e N a bude pracovat jen s kladn´ ymi ˇc´ısly. Nebylo by kr´ asn´e m´ıt pole boolean˚ u, kde by pole[x] bylo TRUE, kdyˇz x je
7
prvoˇc´ıslo a FALSE, kdyˇz nen´ı? Tj. napˇr. pro N=10 bychom mˇeli pole obsahuj´ıc´ı {FALSE,TRUE,TRUE,FALSE,TRUE,FALSE,TRUE,FALSE,FALSE,FALSE}. Odpov´ım si s´ am - kr´ asn´e by to bylo a nen´ı tˇeˇzk´e si takov´e pole pˇripravit. Proˇc to m˚ uˇze b´ yt lepˇs´ı neˇz postup, kter´ y uˇz zn´ate? D˚ uvod je jednoduch´ y - rychlost. Kdyˇz uˇz takov´eto pˇekn´e booleovsk´e pole m´ame, m˚ uˇzeme zjistit, zdali je ˇc´ıslo prvoˇc´ıslo, v podstatˇe okamˇzitˇe (pod´ıv´ame se na pˇr´ısluˇsn´ y prvek pole). Algoritmus postupn´eho testov´ an´ı dˇelitelnosti pˇreci jen chvilku trv´a. Jak tedy takov´e pole vyrobit? Mˇejme sesl´ano N. Vytvoˇr´ıme si pole [1..N] boolean˚ u a vypln´ıme ho sam´ ymi TRUE (nejdˇr´ıv “tvrd´ıme”, ˇze vˇse jsou prvoˇc´ısla, postupnˇe to budeme u nˇekter´ ych ˇc´ısel falzifikovat); jen p na prvn´ı pozici bude FALSE (1 nen´ı prvoˇc´ısslo). Pak bereme ˇc´ısla 2,3,...round (N ) a z naˇseho pole boolean˚ u vˇzdy n´ asobky tohoto ˇc´ısla vyˇskrtneme (protoˇze jsou dˇeliteln´a uvaˇzovan´ ym ˇc´ıslem). Jednon´ asobek nevyˇskrt´av´ame - prvoˇc´ıslo je sebou sam´ ym tak´e dˇeliteln´e. Po vyˇskrt´ an´ı n´ asobk˚ u jednoho ˇc´ısla vezmeme dalˇs´ı ˇc´ıslo a zase vyˇskrt´av´ame jeho n´ asobky. Pˇr´ıklad pro N=10: Pole={FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE} Ted’ (v Pascalu bychom to dˇ elali asi for cyklem) vezmeme 2 a jeho n´ asobky. Dostaneme Pole={FALSE, TRUE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE} Ted’ vezmeme 3 a vyˇ skrt´ av´ ame (nˇ eco uˇ z je vyˇ skrtnut´ e, ale to nevad´ ı), z´ ısk´ ame: Pole={FALSE, TRUE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE} A je hotovo, round(sqrt{10})=3. Argument, proˇc testujeme jen ˇc´ısla do odmocniny je zcela obdobn´ y jako v algoritmu postupn´eho dˇelen´ı - tj. algoritmu testov´an´ı prvoˇc´ıselnosti, kter´ y jsme mˇeli prve. Uˇz v´ıme, ˇze zjiˇst’ovat, zda je ˇc´ıslo prvoˇc´ıslo, s pomoc´ı takov´ehoto pole, je kr´ asa (tzn. je to rychl´e). Kde je h´aˇcek? H´aˇcek je v tom, ˇze samozˇrejmˇe nˇeco trv´a si to pole vyrobit. A vyrobit si Eratosthenovo s´ıto pro nˇejak´e N je pomalejˇs´ı neˇz libovoln´e ˇc´ıslo od 1 do N otestovat postupn´ ym dˇelen´ım. Pouˇzit´ı takov´ehoto s´ıta m´ a smysl v situaci, kdy potˇrebujeme hodnˇe ˇc´ısel od 1 do N testovat na prvoˇc´ıselnost. Protoˇze s´ıto si vyrob´ıme jen jednou a pak uˇz se pt´ame v podstatˇe zadarmo.
3
Ladˇ en´ı program˚ u
Dˇr´ıve ˇci pozdˇeji se v´ am stane, ˇze v´am program nefunguje a nen´ı hned jasn´e, proˇc tomu tak je. Propˇr´ıklad tenhle program ˇreˇs´ıc´ı u ´lohu Vyhled´av´an´ı v setˇr´ıdˇen´em poli vypad´ a pˇeknˇe:
program shled; {nacte cislo n a cislo k, pote n cisel setridenych vzestupne. Potom cte k cisel - dotazu. Pr vypise prvni pozici jeho vyskytu v nactene posloupnosti. Pokud cislo v posloupnosti neni, vypise nulu} var pole: array[1..1000000] of integer; m,n,i,k,max,min,c: integer; {dotaz, pocet prvku posloupnosti, index,
8
pocet dotazu, horni mez,dolni mez, stred} begin read(n); read(k); for i:=1 to n do {nacte n, k a posloupnost} begin read(pole[i]); end; for i:=1 to k do begin min:=1; max:=n; c:=((n+1) div 2); {cte dotazy} read(m); while ((max>=min) and (pole[c]<>m)) do {kontroluje, je-li jeste kde hledat} begin c:=((max + min) div 2); if pole[c]<m then begin if min
m then begin if max>1 then max:=(c-1); end; end; end; if pole[c]=m then {pro nalezeny dotaz snizi index} begin {vyskytu na minimum a vypise} while pole[c-1]=m do begin c:=(c-1); end; write(c,’ ’); end; if (((pole[c]<>m) and (pole[c]>min) and (pole[c]<max)) or (min>max)) then write(’0 ’); {pro nenalezeny dotaz vypise nulu} end; end.
9
Ten program i leckdy funguje, napˇr. na vstup: 8 1 2 5 6 6 6 8 9 10 6 Ale Codex d´ a 0 bod˚ u. Ono to taky leckdy nefunguje. Napˇr´ıklad na2 : 3 1 1 2 3 1 to spadne s range check error. Asi ˇclovˇek tuˇs´ı, ˇze se nˇekde d´ıv´a mimo pole. Ale kde? A k tomu pr´ avˇe slouˇz´ı lad´ıc´ı - debugovac´ı3 - n´astroje. Vytvoˇrte si z v´ yˇse uveden´eho k´odu program (FreePascalist´e norm´alnˇe mohou nakop´ırovat do v´ yvojov´eho prostˇred´ı, jino-pascalist´e necht’ uloˇz´ı k´od to textov´eho souboru a zmˇen´ı pˇr´ıponu na .pas - pak soubor m˚ uˇzete norm´alnˇe naˇc´ıst z v´ yvojov´eho prostˇred´ı). Pod´ıvejme se ted’ na nˇekter´e prvky menu Run (doporuˇcuji zn´ at jejich kl´ avesov´e zkratky, je to mnohem menˇs´ı otrava buˇsit do F7 neˇz poˇr´ ad otev´ırat menu): • Trace into: Udˇel´ a krok programu - tj. vyhodnot´ı jeden ˇr´adek a pˇresune v´ as na dalˇs´ı. Pokud vol´ate podprogram, vleze dovnitˇr a bude postupovat po ˇr´ adc´ıch podprogramu. • Step over: Velmi podobn´e jako Trace into, ale neleze dovnitˇr podprogram˚ u. • Continue: Objev´ı se aˇz pˇri krokov´an´ı (tj. kdyˇz program bˇeˇz´ı). Pˇresune program na dalˇs´ı breakpoint (vizte d´ale). • Go to cursor: Skoˇc´ı na m´ısto oznaˇcen´e kurzorem. To m´a smysl tˇreba kdyˇz nechcete milionkr´at maˇckat F7 v nˇejak´em v´ ypoˇcetnˇe n´aroˇcn´em cyklu a zaj´ım´ a v´ as aˇz stav programu po dobˇehnut´ı toho cyklu - pak m´a smysl si kurzor d´ at za onen while cyklus a d´at F4. Takto sice m˚ uˇzeme proj´ıt program krok po kroku, ale jeˇstˇe n´am nˇeco chyb´ı... chtˇeli bychom vidˇet, co je ve kter´e promˇenn´e (tzn. napˇr´ıklad kdy se pod´ıv´ame na pole[0] a proˇc se to stalo). Od toho n´am v menu Debug slouˇz´ı poloˇzka Add Watch. Po kliknut´ı na to se v´ am objev´ı ok´enko, kam zap´ıˇsete promˇennou, jej´ıˇz obsah chcete sledovat. Nedˇeste se, ˇze pˇred prvn´ım pouˇz´ıt´ım promˇenn´e tam mohou b´ yt zd´ anlivˇe nesmysly - zmiz´ı v okamˇziku prvn´ıho pouˇzit´ı. 2 Vymyslet vstup, na kter´ em v´ am to spadne je samozˇrejmˇ e trochu umˇ en´ı a pˇrijde to se zvˇ etˇsuj´ıc´ı se zkuˇsenost´ı. 3 V´ ıte proˇ c chyby v poˇ c´ıtaˇ c´ıch jsou zv´ any bugy? Poch´ az´ı to z ˇ cas˚ u, kdy poˇ c´ıtaˇ ce jeˇstˇ e byly obrovsk´ e, pˇres cel´ e m´ıstnosti, ˇ ci budovy. Kv˚ uli vˇ etr´ an´ı samozˇrejmˇ e musela m´ıstnost/budova vˇ etrat. No a nˇ ekdy dovnitˇr vletˇ el brouk - bug - kter´ y naletˇ el do obvod˚ u poˇ c´ıtaˇ ce a zp˚ usobil poruchu.
10
Seznam vˇsech sledovan´ ych promˇenn´ ych a jejich hodnot vyvol´ate kliknut´ım na Debug-Watches. Pomoc´ı watch˚ u a krokov´an´ı programu uˇz m˚ uˇzete docela jednoduˇse zjistit, kdy a proˇc v´ am program pad´a. Posledn´ı vˇec, kterou je vhodn´e zm´ınit, jsou tzv. breakpointy. Breakpoint na ˇr´ adce se zap´ın´ a pˇres Ctrl+F8, pˇr´ıpadnˇe pˇres menu Debug a poloˇzku Breakpoint. Kdyˇz d´ ate breakpoint na ˇr´ adku a spust´ıte program, program se na dan´em m´ıstˇe zastav´ı (a skrze watche m˚ uˇzete zase sledovat promˇenn´e). Pak m˚ uˇzete zase krokovat pomoc´ı Trace into, Step over atd. Continue v t´eto situaci v´as pˇresune na pozici dalˇs´ıho breakpointu.
11
