Tietotekniikan perusteet, syksy 1998

Harjoitus 8 (17-19.11.)

 

1. Arvioi seuraavan kuplalajittelualgoritmin suoritusaikaa syötealkioiden määrän n funktiona:

 

procedure bubblesort(A[1..n]);

begin

for i := 1 to n-1 do

for j := n downto i+1 do

if A[j] < A[j-1] then

begin

t := A[j-1];

A[j-1] := A[j];

A[j] := t

end

end {bubblesort}.

 

Lisätieto: WWW-osoitteesta http://max.cs.kzoo.edu/~abrady/java/sorting löytyy algoritmin toimintaa valaiseva Java-animaatio.

 

2. Paperin kääntöpuolella on Suomen karttaan merkitty joitakin Etelä-Suomen kaupunkeja sekä annettu niiden välinen etäisyystaulukko. Määritä jokin merkityt kaupungit kiertävä kauppamatkustajan reitti ja laske sen pituus.

 

3. Taulukkoon A[1..n] on talletettu kokonaislukuja kasvavassa suuruusjärjestyksessä (A[1] A[n]). Tehtävänä on määrittää, esiintyykö annettu luku x taulukossa. Tehtävä voidaan ratkaista joko seuraavalla peräkkäishaulla:

 

function seqsearch(A[1..n], x);

begin

for i := 1 to n do

if A[i] = x then return "Löytyi";

return "Ei löytynyt"

end {seqsearch}

 

tai seuraavalla puolitus- eli binäärihaulla:

 

function binsearch(A[1..n], x);

begin

if n = 1 then

if A[1] = x then return "Löytyi"

else return "Ei löytynyt";

m := ën/2û; /* pyöristys alaspäin */

if x A[m] then

binsearch(A[1..m], x)

else

binsearch(A[m+1..n], x)

end {binsearch}.

 

Arvioi näiden menetelmien suoritusaikaa syötealkioiden määrän n funktiona. (Vihje puolitushaun analyysiin: montako kertaa luku n täytyy puolittaa (alaspäin pyöristäen) ennen kuin tulos on 1?)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ETÄISYYSTAULUKKO:

 

Jkl Vaa Jsu Tre Hln Lti Lrt Tku Hki

Jkl 0 283 244 151 226 170 220 304 280

Vaa 238 0 482 244 319 399 458 332 417

Jsu 244 527 0 395 429 349 236 548 459

Tre 151 244 395 0 75 155 268 153 173

Hln 226 319 429 75 0 80 193 139 98

Lti 170 399 349 155 80 0 113 219 110

Lrt 220 503 236 268 193 113 0 332 223

Tku 304 332 548 153 139 219 332 0 165

Hki 280 417 459 173 98 110 223 165 0