- COMP.CS.300
- 5. STL-kirjasto
- 5.6 Session activity
Session activity¶
Aktiviteetit¶
Tehtävä 1 - Ternäärihaku¶
BINSEARCH-proseduuri etsii järjestetystä taulukosta A[1..n] numeroa key käyttäen binäärihakua. Binäärihaussa aloitustaulukko A[L..R] jaetaan kahdeksi lähes yhtä suureksi alitaulukoksi jokaisella iteraatiolla (tai rekursion tasolla): A[L..mid] ja A[(mid+1)..R]. Vertaamalla jakopisteen elementtiä voidaan päätellä, tulisiko etsintää jatkaa vasemmalla vai oikealla puoliskolla (ellei jakopisteessä ole etsittävää elementtiä).
Ternäärihaussa (ternary search) käytetään samankaltaista lähestymistapaa, paitsi että jokaisella iteraatiolla (tai rekursion tasolla) aloitustaulukko A[L..R] jaetaan kolmeksi lähes yhtä suureksi alitaulukoksi: A[L..mid1], A[(mid1+1)..mid2] ja A[(mid2+1)..R]. Numero key voi esiintyä vain yhdessä näistä kolmesta alitaulukosta, ja siksi muut kaksi voidaan jättää huomioimatta.
Kirjoita TERNSEARCH-proseduuri käyttäen ternaarihakua, jonka saat muuttamalla BINSEARCH-pseudokoodia olennaisilta kohdilta.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | BINSEARCH(A,L,R,key)
input A[1..n] is an array containing numbers; L and R are the
leftmost and rightmost indices that concern us; key is the value
we want to find
output: the index at which key occurs in A, or -1 if it doesn't
/* The numbers in A must be in order from smallest to largest.
We search in array A[L..R] for key. If key is found, we return
its location, otherwise we return -1.*/
if L == R then
if A[L] == key then
return L
else
return -1
end
else
mid = floor( (L+R)/2 )
if key <= A[mid] then
return BINSEARCH(A,L,mid,key)
else
return BINSEARCH(A,mid+1,R,key)
end
end
|
Tehtävä 2 - Luonnollinen mergesort¶
Tässä ongelmassa esimerkkitaulukkona on käytössä A[12, 14, 5, 3, 7, 20, 16, 9] , indeksi i on välillä 1-8. Tavoite on kirjoittaa pseudokoodi luonnolliselle mergesortille, joka järjestää A:n alkiot pienimmästä suurimpaan. Jotta luonnollisen mergesortin toiminnan voisi ymmärtää, tulee ensin ymmärtää käsitteet vähenevä inversio ja sarja (tässä kontekstissa). Järjestettävässä taulukossa on laskeva inversio paikassa i, kun A[i] > A[i+1]. Sarja on taas jokin alitaulukko, jonka alkiot ovat kasvavassa järjestyksessä. Sarjan lopussa on aina vähenevä inversio.
Esimerkkitaulukko voidaan jakaa sarjoihin seuraavasti:
sarja alkiot
1 [12,14]
2 [5]
3 [3, 7, 20]
4 [16]
5 [9]
Luonnollisessa mergesortissa ensin lomitetaan sarjat 1 ja 2 yhteen, sitten sarjat 3 ja 4, sitten sarjat 5 ja 6, kunnes viimeinen sarja on saavutettu. Tämän jälkeen sarjojsa pitäisi olla jäljellä n. puolet alkuperäisestä määrästä. Sarjoja lomitetaan yhteen, kunnes niitä on vain yksi jäljellä.
Kuvaus luonnollisen mergesortin toiminnasta on annettu myös algoritmissa NATMERGESORT:
NATMERGESORT(*A*)
1. Aloita etsimään laskevien inversioiden sijainteja kohdasta *A[1]*
lähtien. Näiden sijaintien perusteella etsitään alku- ja loppukohdat sarjoille.
2. Lomita peräkkäiset sarjat, kunnes lomitettavia sarjoja ei ole lisää.
3. Toista kohtaa 2, kunnes vain yksi sarja on jäljellä.
Jos NATMERGESORT suoritettaisiin esimerkkitaulukolle, se näyttäisi vaihe vaiheelta tältä:
Taso askel muodostetut sarjat
1 1 [12,14], [5], [3, 7, 20], [16], [9]
2 2 [5, 12,14], [3, 7, 16, 20], [9]
3 2 [3, 5, 7, 12,14, 16, 20], [9]
4 2 [3, 5, 7, 9, 12, 14, 16, 20]
Kirjoita pseudokoodi algoritmille NATMERGESORT.
A+ esittää tässä kohdassa tehtävän palautuslomakkeen.