Nämä harjoitukset liittyvät lähinnä oppimateriaalin lukuihin 2-6.
Kaikki harjoitustehtävät on syytä tehdä. Jotkin tehtävät on merkitty keltaisella värillä. Ne ovat ehkä hieman muita haastavampia. Ilman niitäkin harjoituksista voi saada maksimipisteet, mutta ne lasketaan silti mukaan harjoituspisteitä määrättäessä – ne voivat siis korvata joitakin haasteettomampia tehtäviä tms. Mutta ennen kaikkea noista keltaisista tehtävistä sitä vasta oppiikin!
Huom:
// 2. harjoitukset, tehtävä 2.3, Oili Opiskelija
Yksi opiskelija valitteli, ettei ensimmäisen viikon hienoa MyStringiä käytetty mihinkään varsinaiseen sovellukseen. Korjataan asia!
Laadi sovellus, joka komentotulkkilogiikalla tarjoaa yksirivisen tekstin editoinnin. Kyseessä on siis alkeellinen editori. Ohjelman keskeisenä tietorakenteena käytetään itse ohjelmoitua MyStringluokan ilmentymää.
Seuraava esimerkki havainnollistaa, mitä ja miten sovellus osaa. (Koneen tekstit ovat kursiivilla.)
Komennot ovat # = lopetus, + = lisää, - = poista + Mihin kohtaan lisätään? 3 Suurin sallittu indeksi on 0. + Mihin kohtaan lisätään? 0 Mitä lisätään? Xyz Rivi on: Xyz + Mihin kohtaan lisätään? 4 Suurin sallittu indeksi on 3. + Mihin kohtaan lisätään? 3 Mitä lisätään? kissa Rivi on: Xyzkissa + Mihin kohtaan lisätään? 3 Mitä lisätään? ** Rivi on: Xyz**kissa - Mistä kohdasta poistetaan? 7 Rivi on: Xyz**kisa Ähäkutti! Mites tästä selviät? Komennot ovat # = lopetus, + = lisää, - = poista - Mistä kohdasta poistetaan? 4 Rivi on: Xyz*kisa #
Neuvoja:
[Tässä harjoitellaan vasta myöhemmin opittavia asioita joita siis saa oppia jo nytkin jos tahtoo...;-]
Ei ole kovin kivaa, että rivieditori kaatuu muodoltaan virheelliseen numeeriseen syötteeseen. On monia tapoja varustautua myös tuohon virheeseen. Yksi on ns. poikkeuksen ns. sieppaaminen vaikkapa seuraavaan tapaan:
...
int luku;
...
try {
luku = lukija.nextInt();
}
catch (NumberFormatException e) {
... hoitele virhetilanne ...
}
Ohjelmoi ensin työkalu, joka lukee kokonaislukusyötteen eikä anna periksi ennen kuin saa muodoltaan kelvollisen kokonaisluvun. Parantele sitten tällä uudella välineellä rivieditori entistä ehommaksi.
Javan APIssa on valmiita välineitä joukon toteutukseksi. Mutta kuten jo viime viikolla nähtiin, tällaisten dynaamisilta vaikuttavien välineiden toteuttaminen itse - omin käsin - on hyvin opettavaista.
Ensimmäisen viikon tehtävissä jo perehdyttiin vaihtelevanmittaisen merkkijonon toteuttamiseen. Puutteena tuon tyypin dynaamisuudessa oli kiinteä yläraja pisimmälle mahdolliselle merkkijonolle. Tämäkin puute korjataan nyt oman kokonaislukujoukon toteutuksessa.
Tälläkin kertaa rakenteen elementit – nyt kokonaisluvut – talletetaan taulukon alkuun ja käytössä olevien taulukon alkioiden lukumäärä muistetaan muuttujan avulla. Mutta nyt menetellään lisäksi siten, että jos uusi alkio ei enää mahtuisi taulukkoon, luodaan uusi isompi taulukko, jonka alkuun ensin kopioidaan vanhan taulukon sisältö ja vasta sitten toteutetaan lisäysoperaatio.
Joukolle varatun taulukon oletuskoko löytyy julkisesta luokkavakiosta
IntJoukko.KAPASITEETTI. Jos lisäysoperaatio joutuu
luomaan suuremman taulukon, uusi taulukko on
IntJoukko.OLETUSKASVATUS-vakion verran suurempi kuin
vanha taulukko.
Luokan IntJoukko määrittely alkaa seuraavasti:
public class IntJoukko {
public final static int KAPASITEETTI = 5, // aloitustalukon koko
OLETUSKASVATUS = 5; // luotava uusi taulukko on
// näin paljon isompi kuin vanha
private int[] taulukko; // Joukon luvut säilytetään taulukon alkupäässä.
private int alkioidenLkm; // Tyhjässä joukossa alkioiden_määrä on nolla.
// ...
Ohjelmoi luokkaan parametriton konstruktori ja aksessorit
Neuvo: Ohjelmoi lisaa-metodi aluksi ilman uuden talukon luontia. Saat mallia MyString-luokan metodien toteutuksesta. Nyt vain on pidettävä huoli siitä, ettei taulukkoon viedä lukua, jos se jo siellä on. Lisää taulukon korvaaminen isommalla vasta kun olet saanut luvun lisäämisen logiikan toimimaan.
Esittele luokan käyttöä seuraavaan tyyliin:
...
IntJoukko x = new IntJoukko();
System.out.println("Joukko on: " +x); // {}
x.lisaa(57); // Huomaa miten luontevaa "lausekelauseen" käyttäminen lauseena on:
x.lisaa(-32); // Jos ei kiinnosta, oliko lisäys aito vai turha, jätetään vain
x.lisaa(12); // tuo boolean-palautusarvo huomiotta.
System.out.println("Joukko on: " +x); // {57, -32, 12}
x.lisaa(57); // on jo, ei pitäisi lisätä!
System.out.println("Joukko on: " +x); // {57, -32, 12}
x.lisaa(60);
x.lisaa(-31);
System.out.println("Joukko on: " +x); // {57, -32, 12, 60, -31}
System.out.println("Joukon koko on " + x.mahtavuus()); // 5
// nyt se kriittiinen kohta; osaako tehdä isomman taulukon:
x.lisaa(16);
System.out.println("Joukko on: " +x); // {57, -32, 12, 60, -31, 16}
System.out.println("Joukon koko on " + x.mahtavuus()); // 6
Ensimmäisessä vaiheessa vakiot
IntJoukko.KAPASITEETTI ja
IntJoukko.OLETUSKASVATUS-
määräsivät IntJoukko-olion sisäisen toiminnan
aina sellaiseksi, että alussa luodaan viisialkoinen taulukko
ja kasvatuskoko on aina viisi.
Nämä oletusarvot olivat epärealistisen pienet
testaamisen helpottamikseksi.
IntJoukkoa käyttävän sovelluksen laatija voi tietää, että hänen tilanteessaan joukot ovat "yleensä sen ja sen kokoisia". Hän saattaa myös osata arvella jotakin siitä, mitä tapahtuu siinä tilanteessa, kun joukko on tavanomaista isompi: miten paljon "suuret joukot tapaavat kasvaa".
Laajenna IntJoukkoa tällaisen valistuneen ohjelmoijan tarpeisiin lisäämällä luokkaan konstruktorit, joilla luotavan IntJoukko-olion oletusarvoja voidaan muuttaa.
Luokan IntJoukko määrittely alkaa nyt seuraavaan tapaan:
public class IntJoukko {
public final static int KAPASITEETTI = 5, // aloitustalukon koko
OLETUSKASVATUS = 5; // luotava uusi taulukko on
// näin paljon isompi kuin vanha
private int kasvatuskoko; // Uusi taulukko on tämän verran vanhaa suurempi.
private int[] taulukko; // Joukon luvut säilytetään taulukon alkupäässä.
private int alkioidenLkm; // Tyhjässä joukossa alkioiden_määrä on nolla.
public IntJoukko() {
// muilta osin tämä konstruktori ohjelmoitiin jo edellisessä kohdassa:
kasvatuskoko = OLETUSKASVATUS;
}
public IntJoukko(int kapasiteetti) {
// Annetaan oma kapasiteetti.
// Muista tarkistaa parametrin kelvollisuus!
// ...
}
public IntJoukko(int kapasiteetti, int kasvatuskoko) {
// Annetaan oma kapasiteetti ja kasvatuskoko.
// Muista tarkistaa parametrien kelvollisuus!
// ...
}
// ...
Kokeile ja havainnollista uusien konstruktoreiden toimintaa sopivalla pääohjelmalla.
Joukon toteutus on vielä aika köyhä. Täydennetään sitä parilla keskeisellä operaatiolla:
Käyttöesimerkki:
IntJoukko x = new IntJoukko();
x.lisaa(57);
x.lisaa(-32);
x.lisaa(12);
x.lisaa(60);
System.out.println("Joukko on: " +x); // {57, -32, 12, 60}
System.out.println(x.kuuluu(22)); // false
System.out.println(x.kuuluu(12)); // true
if (x.kuuluu(12))
System.out.println("12 kuuluu joukkoon"); // tämä!
else
System.out.println("12 ei kuulu joukkoon");
x.poista(12);
System.out.println("Joukko on: " +x); // {57, -32, 60}
if (x.kuuluu(12))
System.out.println("12 kuuluu joukkoon");
else
System.out.println("12 ei kuulu joukkoon"); // tämä!
x.poista(48);
System.out.println("Joukko on: " +x); // {57, -32, 60}
System.out.println(x.poista(48)); // false
System.out.println(x.poista(60)); // true ja joukko on {57, -32}
x.poista(57); // {-32}
x.poista(-32); // {}
x.poista(23); // {}
Syystä tai toisesta (yksi sellainen nähdään pian) lukujoukosta halutaan saada tuotettua taulukko, joka sisältää kaikki joukon alkiot. Lisää luokkaan seuraava aksessori:
Käyttöesimerkki:
IntJoukko x = new IntJoukko();
x.lisaa(57);
x.lisaa(-32);
x.lisaa(12);
x.lisaa(60);
System.out.println("Joukko on: " +x); // {57, -32, 12, 60}
int[] taulukkona = x.toIntArray();
for (int alkio: taulukkona)
System.out.print(alkio + ", ");
System.out.println(); // 57, -32, 12, 60,
Edellä IntJoukko toteutettiin vaiheittain, minkä seurauksena ohjelmaan syntyi paikoin "turhaa" algoritminpätkien kertaamista ja ehkä muutakin rakenteellista epäselvyyttä. Esimerkiksi vaiheessa 1 ohjelmoitu lisaa-metodi joutuu tutkimaan, ettei lukua lisätä, jos se jo kuuluu joukkoon. Tuo sama joukkkoon kuuluminen ohjelmoitiin omaksi metodikseen kuuluu vaiheessa 3.
Muokkaa IntJoukko-luokan toteutusta siten, että lisaa-aksessori käyttää hyväkseen kuuluu-aksessoria sen sijaan, että omin voimin tuon tutkimuksen tekisi. Huomaa siis, että aksessorit voivat vallan mainiosti kutsua toisia aksessoreita! Ellet jo ole huomannut...
Keksitkö muita tapoja virtaviivaistaa luokan toteutusta?
Ohjelmarakenteen muuttamista selkeämmäksi ohjelman toimintaa muuttamatta kutsutaan hienolla sivistyssanalla refaktoroinniksi. Sitä tehdään, jotta ohjelman ylläpitäminen helpottuisi.
Muokkaa edellä toteutettua IntJoukko-luokkaa siten, että joukon alkiot pidetään taulukossa aina nousevassa suuruusjärjestyksessä ja hakuoperaatiot toteutetaan binäärihaulla.
Luonnollisestikaan IntJoukko-olioiden toiminta ei saa muuttua tämän tehostamisen seurauksena — lukuunottamatta sitä, että toStringin tuottamassa merkkiesityksessä alkiot ovat järjestyksessä.
Voisit toki ohjelmoida järjestämisalgoritminkin, mutta toteutuksesta tulee tehokkaampi, jos muutat lisäämisalgoritmia siten, että lisättävä luku viedään heti oikeaan kohtaansa taulukossa. Tällöin erillistä järjestämistä ei tarvita. Muista että aksessoreille voi mainiosti ohjelmoida "pikku apulaisia" yksityisinä ilmentymämetodeina.
Toteutetaan sitten tuttuja joukko-operaatiota IntJoukko-olioille. Ensin public static -kirjastometodeina luokkaan JoukkoOp
IntJoukko-luokan aksessoreita käyttäen ohjelmonnin ei pitäisi olla kovin työlästä. Erityisesti tarvitset toIntArray()-aksessoria joukon alkioiden läpikäymiseen. Muutkin aksessorit helpottanevat ohjelmointia.
public static IntJoukko yhdiste(IntJoukko a, IntJoukko b) palauttaa arvonaan joukon, joka sisältää kaikki a:n ja b:n alkiot
Käyttöesimerkki:
IntJoukko a, b, c;
a = new IntJoukko();
b = new IntJoukko();
// .... a:han ja b:hen viedään kaikenlaisia lukuja
c = JoukkoOp.yhdiste(a, b);
System.out.println("a = " + a);
System.out.println("b = " + b);
System.out.println("c = " + c);
public static IntJoukko leikkaus(IntJoukko a, IntJoukko b) palauttaa arvonaan joukon, joka sisältää täsmälleen kaikki alkiot, jotka kuuluvat sekä joukkoon a että joukkoon b
Käyttöesimerkki:
IntJoukko a, b, c;
a = new IntJoukko();
b = new IntJoukko();
// .... a:han ja b:hen viedään kaikenlaisia lukuja
c = JoukkoOp.leikkaus(a, b);
System.out.println("a = " + a);
System.out.println("b = " + b);
System.out.println("c = " + c);
public static IntJoukko erotus(IntJoukko a, IntJoukko b) palauttaa arvonaan joukon, joka sisältää kaikki a:n alkiot, jotka eivät kuulu joukkoon b
Käyttöesimerkki:
IntJoukko a, b, c;
a = new IntJoukko();
b = new IntJoukko();
// .... a:han ja b:hen viedään kaikenlaisia lukuja
c = JoukkoOp.erotus(a, b);
System.out.println("a = " + a);
System.out.println("b = " + b);
System.out.println("c = " + c);
Havainnollista näiden kirjastometodien käyttöä esimerkkiohjelmalla, joka perustuu komentotulkin käyttöön.
Käyttöesimerkki: (koneen tekstit ovat kursiivilla)
Tervetuloa joukkolaboratorioon!
Käytössäsi ovat joukot A, B ja C.
Komennot ovat lisää, poista, kuuluu, yhdiste ja leikkaus.
Joukon nimi komentona tarkoittaa pyyntöä tulostaa joukko.
?> lisää
Mihin joukkoon? A
Mikä luku lisätään? 57
?> A
A = {57}
?> lisää
Mihin joukkoon? A
Mikä luku lisätään? -32
?> lisää
Mihin joukkoon? A
Mikä luku lisätään? 12
?> A
A = {57, -32, 12}
?> lisää
Mihin joukkoon? B
Mikä luku lisätään? 47
?> B
A = {47}
?> yhdiste
1. joukko? A
2. joukko? B
A yhdiste B = {57, -32, 12, 47}
?> kuuluu
Mihin joukkoon? A
Mikä luku? -32
- 32 kuuluu joukkoon A
?> kuuluu
Mihin joukkoon? A
Mikä luku? 29
29 ei kuulu joukkoon A
... jne...
Jos haluat lisähaasteita, voit kehitellä yksirivisiä komentoja, jotka eivät erikseen kysele mitään. Ja jos tämäkään ei riitä, voit ottaa mukaan sijoitukset joukkomuuttujille. Ja lopulta tässä päädyttäisiin ohjelmointikieleen, jonka lauseet ja lausekkeet käsittelevät joukkoja...
Vaihtoehto edellisen tehtäväryhmän tyylille on täydentää itse luokkaa IntJoukko joukko-operaatioaksessoreilla.
IntJoukko-luokan aksessoreita käyttäen ohjelmonnin ei pitäisi olla kovin työlästä. Erityisesti tarvitset toIntArray()-aksessoria joukon alkioiden läpikäymiseen. Muutkin aksessorit helpottanevat ohjelmointia.
public IntJoukko yhdiste(IntJoukko b) palauttaa arvonaan joukon, joka sisältää kaikki this-joukon ja joukon b alkiot.
Käyttöesimerkki:
IntJoukko a, b, c;
a = new IntJoukko();
b = new IntJoukko();
// .... a:han ja b:hen viedään kaikenlaisia lukuja
c = a.yhdiste(b);
System.out.println("a = " + a);
System.out.println("b = " + b);
System.out.println("c = " + c);
public IntJoukko leikkaus(IntJoukko b) palauttaa arvonaan joukon, joka sisältää täsmälleen kaikki alkiot, jotka kuuluvat sekä this-joukkoon että joukkoon b.
Käyttöesimerkki:
IntJoukko a, b, c;
a = new IntJoukko();
b = new IntJoukko();
// .... a:han ja b:hen viedään kaikenlaisia lukuja
c = a.leikkaus(b);
System.out.println("a = " + a);
System.out.println("b = " + b);
System.out.println("c = " + c);
public IntJoukko erotus(IntJoukko b) palauttaa arvonaan joukon, joka sisältää kaikki this-joukon alkiot, jotka eivät kuulu joukkoon b
Käyttöesimerkki:
IntJoukko a, b, c;
a = new IntJoukko();
b = new IntJoukko();
// .... a:han ja b:hen viedään kaikenlaisia lukuja
c = a.erotus(b);
System.out.println("a = " + a);
System.out.println("b = " + b);
System.out.println("c = " + c);
Muokkaa tehtävän 2.4 komentotulkista sellainen, jossa joukko-operaatiot on toteutettu aksessorein (siis käyttäen juuri tämän 3. tehtäväsarjan tapaa joukko-operaatioiden toteutuksessa). Tämä tehtävä on itse asiassa melko vaivattomasti muokattavissa tehtävän 2.4 ratkaisusta.
Ohjelmoidaan sitten IntJoukko käyttäen Javan valmista kalustoa.
Toteuta IntJoukko-luokka käyttäen kapseloituna tietorakenteena ArrayList<Integer>-oliota. ArrayListin aksessorit tekevät operaatioiden toteutuksen aika sujuvaksi. Ja nyt ei tarvita kuin parametriton konstruktori, koska ArrayList osaa itse kasvaa ja pienetä tarpeen mukaan.
API on melkein sama kuin aiemmin:
Nyt se sitten alkaa! Nyt on aika ruveta ihan omin päin tutustumaan Javan valmiiseen kalustoon: Perehdy luokkaan HashSet Javan APIn pakkauksessa java.util ja toteuta IntJoukko-luokkasi siten, että se kapseloi piilossa pidetyksi tietorakenteeksi HashSet<Integer>-olion.
Tutki kolmen erilaisen IntJoukko-luokan toteutuksen nopeutta ohjaajien laatimalla mittausohjelmalla. Anna kokonaislukujoukon ArrayList-toteutukselle nimi IntJoukkoAL ja HashSet-toteutukselle nimi IntJoukkoHS.