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] thenbinsearch(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