Tölvunarfręši 2

Vikublaš 9


Nś veršur byrjaš aš skoša einfaldar röšunarašferšir śr Kafla 6 ķ kennslubókinni. Fariš veršur ķ Valröšun (selection sort), Innsetningarröšun (insertion sort) og Bóluröšun (bubble sort). Žessum ašferšum er aušvelt aš lżsa, en žęr eru ekki mjög hrašvirkar. Fariš veršur ķ gegnum greiningu į žeim. Byrjaš veršur aš tala um hrašvirkari (en flóknari) ašferš sem heitir Shell-röšun.

Ķ dęmatķmum veršur rętt um sķšustu heimadęmi.

Heimadęmi 8

Leysiš eftirfarandi dęmi og skiliš ķ hólf dęmatķmakennara ykkar fyrir kl 12:00 mįnudaginn 14. mars. Žeir taka ekki dęmum sem koma seinna.

  1. Dęmi 5.79 į bls. 249 ķ kennslubók.
    [Žżšing: Sżniš forröšun, innröšun, eftirröšun og lagröšun eftirfarandi tvķundartrjįa: ]

  2. Dęmi 1 į bls. 9 ķ CDSI.
    [Žżšing: Reikniš (pre-list)(Bt) žar sem Bt er skilgreint ķ Dęmi 2.1 į bls. 8. ]

  3. Dęmi 2 a) og c) į bls. 9 ķ CDSI.
    [Žżšing: Gefiš endurkvęmar skilgreiningar į eftirfarandi föllum į tvķunartré: a) depth sem skilar lengd lengsta einfalda vegar (įn hringja) frį rótinni til laufs. c) least sem skilar minnsta stakinu ķ tvķundartré sem inniheldur stök śr rašanlegtu mengi. ]

  4. Dęmi 6.3 į bls. 272 ķ kennslubók.
    [Žżšing: Śtskżriš hvernig žiš mynduš raša spilastokk meš žeirri takmörkun aš spilin verša aš liggja į hvolfi ķ röš og eina leyfilega ašgeršin er aš skoša gildi tveggja spila (ž.e. kķkja į framhliš žeirra) og e.t.v. vķxla žeim. ]

  5. Śtfęriš ķ C++ Tvķundarinnsetningarröšun (e. binary insertion sort), sem er eins og Innsetningarröšun, nema notuš er helmingunarleit (e. binary search) til aš finna rétta stašsetningu nęsta staks ķ rašaša hluta fylkisins. Beriš hraša žess saman viš Innsetningarröšunina sem gefin er ķ kennslubókinni (Forrit 6.3) į nógu stórum fylkjum meš slembitölum.
    [Visbending: Sjį sżnislausn frį žvķ ķ fyrra. ]


Žeir sem vilja fį ašeins meiri ęfingu ęttu aš reyna viš eftirfarandi dęmi. Lausnirnar į žeim öllum eru tiltękar į gömlum heimasķšum nįmskeišsins. Ef žiš viljiš fį nįnari śtskżringar į lausnunum žį getiš žiš spurt um žęr ķ dęmatķmunum.
hh (hja) hi.is, 7. mars, 2005.