Tlvunarfri 2

Vikubla 6


Vi hfum n fari yfir fyrstu rj kaflana Algorithms bkinni, a nokkrum undirkflum undanskildum. essari viku byrjum vi huglgum gagnagrindum kafla 4. ar eru skoaar tfrslur hlum (e. stack) og birum (e. queue).

nstu viku verur haldi fram me tfrslu hlum og birum.

Forritunarverkefni 1

essu fyrsta forritunarverkefni eigi i a skrifa forriti Drithfundur C++. Drithfundur les inn bk sem textaskr og "hermir" eftir eirri bk me v a skrifa slembitexta sem hefur smu tnidreifingu bkstafa og upphaflega bkin.

Tkum sem dmi a vi viljum herma eftir Njlu. Einfaldasta tgfa af Drifhfundi myndi finna tni allra bkstafa Njlu og hvert sinn velja einn bkstaf af handahfi byggt eim lkum. Til dmis, ef eya, ' ', er fimmti hver stafur a mealtali Njlu eru lkurnar v a forriti skrifi t eyu 20%. Nstalgengasti stafurinn er kannski 'a' og eru minni lkur a forriti velji hann, o.s.frv. Textinn sem kemur t hefur smu tnidreifingu bkstfunum og Njla, en lkist Njlu ekki miki.

Vi getum hins vegar haldi aeins lengra me essa hugmynd og byggt lkurnar v hvaa bkstafur kom sast. a eru til dmis mun meiri lkur bkstafnum '' ef sasti stafur var 'a', en ef hann var einhver annar stafur. etta er vegna ess a orin "a" og "a" koma va fyrir Njlu (eins og flestum rum slenskum bkum). Hr a nean er dmi um hvernig svona slembitexti gti liti t:

a Gumirg hanni ir el t di s h hrekumrastrjg heg ai Gr s. ta ll ttti a vldindir, stir

N getum vi auki fjlda eirra bkstafa sem vi mium vi, annig a vi byggjum lkurnar bkstfunum sustu k stfum sem vi notuum. Hr a ofan var k = 1, en ef vi mium vi tvo sustu stafina getum vi fengi slembitextann:

gir bjt sangbeir Gist hafli hg mr fa akarpingi st kvai. Gis a rar vorir eranga. a

Eftir v sem k er auki eim mun meira lkist slembitextinn upprunalega textanum. Ltum k = 5:

taki til Mdal. a var Mrk ba heyverkum fyrir a yfir v valda, val-Freyjur randa f

og k = 10:

r a nta sjlfdmi Gunnar." Mrur var allra kvenna fegurst og best a sr orin um a er k

Reikniriti sem i noti er ekki mjg flki. Forriti fr uppgefi gildi k, hversu langur slembitextinn a vera og nafn inntaksskrrinnar. a byrjar v a lesa alla inntaksskrnna inn streng (string breytu ea char fylki) og velur k-stafa streng af handahfi r inntakstextanum sem undanfara og prentum hann t. Vi leitum san a essum k-stafa undanfara textanum og hvert sinn sem hann finnst btum vi bkstafnum sem kemur eftir honum textanum lista. Til dmis ef k er 2 og fyrsti undanfarinn er "e" gti listinn yfir stafi sem koma fyrir eftir honum ori ['s', 't', 's', 'i', 'i', ... ]. Vi veljum san bkstaf af handahfi t essum lista. eir bkstafir sem koma oft fyrir listanum eru lklegri til a vera fyrir valinu en eir sem koma sjaldnar fyrir.
egar fyrsti slembistafurinn hefur veri valinn er hann prentaur t og undanfarinn uppfrur me v a henda burt fyrsta stafnum og setja nja stafinn aftast. Til dmis ef stafurinn 't' var fyrir valinu hr a ofan vri nsti undanfari ori "et" og vi myndum aftur ba til lista yfir alla bkstafi sem koma eftir strengnum "et" textanum".

a eru til msar gagnagrindur sem myndu gera leitina a bkstfunum sem koma eftir undanfaranum hravirkari, en essu verkefni er ng a leita bara me renna gegnum allan textann strengum hvert sinn og skr hj sr stafinn sem kemur eftir hvert sinn sem vi finnum undanfarann.

etta verkefni ekki a vera mjg erfitt. Reyni v a gera a sem mest sjlf, v annig lri i mest v. Eftir sem ur er lagi fyrir ykkur a ra um verkefni vi samnemendurna, en forist a taka vi forritskdum fr rum.

Hgt er a finna miki magn af bkum slensku heimasu Nettgfunnar. A vsu eru r allar HTML formi, en a er ekki miki af HTML skipunum skrnum, en hgt er a f hreina textaskr me v a velja allan textann (ctrl-a), afrita hann (ctrl-c) og skeyta honum svo inn textaritil (ctrl-v). Einnig er grarlega miki af bkum ensku hj Project Gutenberg.

Skili stuttri skrslu um forriti ykkar, ar sem i lsi aeins nnar hnnun forritsins og sni niurstur forritsins 2-3 mismunandi bkum fyrir gildin 1, 4, 7 og 10 k. Skili einnig tprentun af forritinu til dmatmakennara ykkar fyrir kl 18:00 fstudaginn 25. febrar. eir munu ekki taka vi verkefnum sem koma seinna.


annaing (hja) hi.is / hh (hja) hi.is, 14. febrar, 2005.