Ohjelmoinnin jatkokurssi: harjoitukset s2010: 2/6 (8.11-12.11.)

(Muutettu viimeksi 8.11.2010, sivu perustettu 2.11.2010.)

Harjoitustehtävien otsikoilla on värikoodaus: Vihreät tehtävät on syytä tehdä joka tapauksessa. Värittämättömiä ei ole ihan pakko tehdä, mutta nekin ovat hyvin hyödyllisiä ja myös vaikuttavat pisteisiin. Keltaiset tehtävät ovat vähän haastavampia. Nekin lasketaan mukaan harjoituspisteitä määrättäessä, mutta ilmankin niitä harjoituksista voi saada maksimipisteet.

Huom: Jokaisen ohjelmatiedoston alkuun on kirjoitettava kommenttina harjoituskerta, tehtävän numero ja tekijän nimi tyyliin:

// 2. harjoitukset, tehtävä 2.1, Oili Opiskelija

Huom: Ohjaajien eli pajamestarien sivulta löytyy hienoja testauksen apuvälineitä tehtävien tekemisen avuksi!

Kokonaislukujoukon toteutus

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.

Kokonaislukujoukko, vaihe 1

Joukolle varatun taulukon oletuskoko löytyy julkisesta luokkavakiosta Kokonaislukujoukko.KAPASITEETTI. Jos lisäysoperaatio joutuu luomaan suuremman taulukon, uusi taulukko on Kokonaislukujoukko.OLETUSKASVATUS-vakion verran suurempi kuin vanha taulukko.

Luokan Kokonaislukujoukko määrittely alkaa seuraavasti:

public class Kokonaislukujoukko {

  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

public boolean lisaa(int luku) lisää joukkoon alkion, ellei se jo ollut siellä. Jos alkio oli uusi ja siis lisättiin, metodi palauttaa arvon true, muuten false. Vihje: Jos taulukon koko ei riitä, tämä metodi siis luo uuden suuremman taulukon ja heittää vanhan roskienkerääjän huoleksi.
public int mahtavuus() joukon koko (eli joukon alkioiden lukumäärä)
public String toString()-metodi tuottaa joukosta String-esityksen tyyliin {-3, 1, 76}.

Esittele luokan käyttöä seuraavaan tyyliin:

    ...
Kokonaislukujoukko x = new Kokonaislukujoukko();

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

Kokonaislukujoukko, vaihe 2

Ensimmäisessä vaiheessa vakiot Kokonaislukujoukko.KAPASITEETTI ja Kokonaislukujoukko.OLETUSKASVATUS- määräsivät Kokonaislukujoukko-olion sisäisen toiminnan aina sellaiseksi, että alussa luodaan viisialkoinen taulukko ja kasvatuskoko on aina viisi. Itse asiassa nämä oletusarvot olivat epärealistisen pienet testaamisen helpottamikseksi.

Kokonaislukujoukkoa 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 Kokonaislukujoukkoa tällaisen valistuneen ohjelmoijan tarpeisiin lisäämällä luokkaan konstruktorit, joilla luotavan Kokonaislukujoukko-olion oletusarvoja voidaan muuttaa.

Luokan Kokonaislukujoukko määrittely alkaa nyt seuraavaan tapaan:

public class Kokonaislukujoukko {

  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 Kokonaislukujoukko() {
    // muilta osin tämä konstruktori ohjelmoitiin jo edellisessä kohdassa:
    kasvatuskoko = OLETUSKASVATUS;
  }

  public Kokonaislukujoukko(int kapasiteetti) {
    // Annetaan oma kapasiteetti.
    // Muista tarkistaa parametrin kelvollisuus!
    // ... 
  }

  public Kokonaislukujoukko(int kapasiteetti, int kasvatuskoko) {
     // Annetaan oma kapasiteetti ja kasvatuskoko.
     // Muista tarkistaa parametrien kelvollisuus!
     // ...
  }
  // ...

Kokeile ja havainnollista uusien konstruktoreiden toimintaa sopivalla pääohjelmalla.

Kokonaislukujoukko, vaihe 3

Joukon toteutus on vielä aika köyhä. Täydennetään sitä parilla keskeisellä operaatiolla:

public boolean poista(int luku) poistaa joukosta luvun, jos se siellä sattui olemaan. Arvonaan metodi palauttaa true, jos luku todellakin poistettiin, muuten false.
public boolean kuuluu(int luku) selvittää, kuuluuko luku joukkoon.
Vihje: Tässä on paikka ahaa-elämykselle: Aimmin toteutetussa lisaa-metodissa jouduttiin jo ohjelmoimaan tutkiminen, onko jokin tarjolla oleva luku jo joukossa. Siispä kuuluu-metodin logiikan idean olet jo ohjelmoinut! Muokkaa sitä vain sopivasti. Huomaa myös, miten voit yksinkertaistaa lisaa-metodia kutsumalla sieltä tätä uutta kuuluu-metodia! Toteuta tuo yksinkertaistus.

Käyttöesimerkki:

Kokonaislukujoukko x = new Kokonaislukujoukko();
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);  // {}

Kokonaislukujoukko, vaihe 4

Syystä tai toisesta (yksi sellainen nähdään pian) lukujoukosta halutaan saada tuotettua taulukko, joka sisältää kaikki joukon alkiot. Lisää luokkaan seuraava aksessori:

public int[] toIntArray()-metodi palauttaa arvonaan kokonaislukutaulukon, joka sisältää kaikki joukon alkiot. Taulukon koko on täsmälleen sama kuin joukon alkioiden määrä. Myös nollan alkion mittainen taulukko on täysin mahdollinen

Käyttöesimerkki:

Kokonaislukujoukko x = new Kokonaislukujoukko();
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,

Kokonaislukujoukko, vaihe 5

Muokkaa edellä toteutettua Kokonaislukujoukko-luokkaa siten, että joukon alkiot pidetään taulukossa aina nousevassa suuruusjärjestyksessä ja hakuoperaatiot toteutetaan binäärihaulla.

Luonnollisestikaan Kokonaislukujoukko-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.

Joukko-operaatioita kirjastossa

Toteutetaan sitten tuttuja joukko-operaatiota Kokonaislukujoukko-olioille. Ensin public static -kirjastometodeina luokkaan JoukkoOp

Kokonaislukujoukko-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.

Yhdiste

public static Kokonaislukujoukko yhdiste(Kokonaislukujoukko a, Kokonaislukujoukko b) palauttaa arvonaan joukon, joka sisältää kaikki a:n ja b:n alkiot

Käyttöesimerkki:

Kokonaislukujoukko a, b, c;
a = new Kokonaislukujoukko();
b = new Kokonaislukujoukko();
// ....  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);

Leikkaus

public static Kokonaislukujoukko leikkaus(Kokonaislukujoukko a, Kokonaislukujoukko b) palauttaa arvonaan joukon, joka sisältää täsmälleen kaikki alkiot, jotka kuuluvat sekä joukkoon a että joukkoon b

Käyttöesimerkki:

Kokonaislukujoukko a, b, c;
a = new Kokonaislukujoukko();
b = new Kokonaislukujoukko();
// ....  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);

Erotus

public static Kokonaislukujoukko erotus(Kokonaislukujoukko a, Kokonaislukujoukko b) palauttaa arvonaan joukon, joka sisältää kaikki a:n alkiot, jotka eivät kuulu joukkoon b

Käyttöesimerkki:

Kokonaislukujoukko a, b, c;
a = new Kokonaislukujoukko();
b = new Kokonaislukujoukko();
// ....  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);

Komentotulkki

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...

Joukko-operaatiot aksessoreina

Vaihtoehto edellisen tehtäväryhmän tyylille on täydentää itse luokkaa Kokonaislukujoukko joukko-operaatioaksessoreilla.

Yhdiste

public Kokonaislukujoukko yhdiste(Kokonaislukujoukko b) palauttaa arvonaan joukon, joka sisältää kaikki this-joukon ja joukon b alkiot.

Käyttöesimerkki:

Kokonaislukujoukko a, b, c;
a = new Kokonaislukujoukko();
b = new Kokonaislukujoukko();
// ....  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);

Leikkaus

public Kokonaislukujoukko leikkaus(Kokonaislukujoukko b) palauttaa arvonaan joukon, joka sisältää täsmälleen kaikki alkiot, jotka kuuluvat sekä this-joukkoon että joukkoon b.

Käyttöesimerkki:

Kokonaislukujoukko a, b, c;
a = new Kokonaislukujoukko();
b = new Kokonaislukujoukko();
// ....  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);

Erotus

public Kokonaislukujoukko erotus(Kokonaislukujoukko b) palauttaa arvonaan joukon, joka sisältää kaikki this-joukon alkiot, jotka eivät kuulu joukkoon b

Käyttöesimerkki:

Kokonaislukujoukko a, b, c;
a = new Kokonaislukujoukko();
b = new Kokonaislukujoukko();
// ....  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);

Komentotulkki

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.

Kokonaislukujoukon toteutus käyttäen luokkaa ArrayList<Integer>

Ohjelmoidaan sitten Kokonaislukujoukko käyttäen kehittynyttä välinettä. Tosin joukotkin löytyisivät valmiina...

Kokonaislukujoukko ja ArrayList<Integer>

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:

public boolean lisaa(int luku) lisää joukkoon alkion, ellei se jo ollut siellä. Jos alkio oli uusi ja siis lisättiin, metodi palauttaa arvon true, muuten false.
public int mahtavuus() joukon koko (eli joukon alkioiden lukumäärä)
public String toString()-metodi tuottaa joukosta String-esityksen tyyliin jonka ArrayList tarjoaa.
public boolean poista(int luku) poistaa joukosta luvun, jos se siellä sattui olemaan. Arvonaan metodi palauttaa true, jos luku todellakin poistettiin, muuten false.
public boolean kuuluu(int luku) selvittää, kuuluuko luku joukkoon.
public int[] toIntArray()-metodi palauttaa arvonaan kokonaislukutaulukon, joka sisältää kaikki joukon alkiot. Taulukon koko on täsmälleen sama kuin joukon alkioiden määrä. Myös nollan alkion mittainen taulukko on täysin mahdollinen

Kokonaislukujoukko ja HashSet<Integer>

Perehdy luokkaan HashSet Javan APIn pakkauksessa java.util ja toteuta Kokonaislukujoukko siten, että se kapseloi piilossa pidetyksi tietorakenteeksi HashSet<Integer>-olion.

Joukon toteutusten vertailua

Tutki kolmen erilaisen Kokonaislukujoukko-luokan toteutuksen laatua ohjaajien laatimalla mittausohjelmalla. Anna kokonaislukujoukon ArrayList-toteutukselle nimi ArrayListJoukko ja HashSet-toteutukselle nimi HashSetJoukko.