Osaa käsitellä yksi- ja useampiulotteisia taulukoita, ja ymmärtää miten taulukot käyttävät tilaa tietokoneen muistissa. Kertaa indeksien käyttöä. Osaa kertoa sekä taulukoiden että hajautustaulujen eduista. Tuntee ainakin yhden järjestämisalgoritmin sekä hakualgoritmin, ja tietää miten Javan omia järjestämiseen tarkoitettuja apuvälineitä käytetään. Tuntee rajapinnan Comparable ja hyödyntää sitä olioiden järjestämisessä.
Taulukko
Olemme muutamaan otteeseen nähneet, miten merkkijono on pilkottu osiin metodia split-käyttäen. Merkkijonon osiin pilkkomisen tulokseksi on tullut String[]-tyyppinen muuttuja. Tarkastellaan nyt mistä tässä oikein on kyse.
ArrayList tarjoaa paljon ohjelmoijan elämää helpottavia valmiita metodeja ja toiminnallisuuksia. Näistä ehkäpä tärkein liittyy arvon lisäämiseen listalle: ohjelmoijan näkökulmasta listan koko ei ole rajoitettu. Todellisuudessa listat ovat olioita siinä missä muutkin oliot, ja listaa -- kuten muitakin olioita -- luodessa sille varataan rajattu tila muistista. Listan metodit ovat toteutettu siten, että rajatun tilan loppuessa metodi varaa suuremman tilan listan käyttöön.
ArrayListin helppokäyttöisyydesta huolimatta ohjelmissa on joskus tarvetta ArrayListin esi-isälle eli taulukolle.
Taulukko on olio, joka sisältää rajatun määrän numeroituja paikkoja arvoille. Taulukon pituus (tai koko) on siinä olevien paikkojen lukumäärä, eli kuinka monta arvoa taulukkoon voi laittaa. Taulukon arvoja kutsutaan taulukon alkioiksi.
Taulukon voi luoda kahdella eri tavalla. Tutustutaan ensin tapaan, jossa taulukon koko määritellään eksplisiittisesti taulukon luonnin yhteydessä. Kolme kokonaislukualkiota sisältävä taulukko-olio määritellään seuraavasti:
int[] luvut = new int[3];
Taulukkotyyppi määritellään hakasuluilla, jotka tulevat taulukon sisältämien alkioiden tyypin jälkeen (alkioidentyyppi[]). Olion luominen tapahtuu new-kutsulla, jota seuraa taulukon alkioiden tyyppi, hakasulut, sekä hakasulkujen sisään taulukon alkioiden lukumäärä.
Taulukon alkioon viittaus ja arvon asetus
Taulukon alkioihin viitataan taulukon indeksien perusteella. Alla olevassa esimerkissä luodaan kolmepaikkainen kokonaislukutaulukko, jonka jälkeen taulukon indekseihin 0 ja 2 asetetaan arvot. Tämän jälkeen arvot tulostetaan.
int[] luvut = new int[3];
luvut[0] = 2;
luvut[2] = 5;
System.out.println(luvut[0]);
System.out.println(luvut[2]);
2 5
Yksittäisen arvon asettaminen taulukon tiettyyn paikkaan tapahtuu siis kuten arvon asetus tavalliseen muuttujaan, mutta taulukkoon asetettaessa kerrotaan indeksi. Indeksi kerrotaan hakasulkeiden sisällä. Huomaat todennäköisesti myös että ArrayListin metodi get käyttäytyy hyvin samalla tavalla kuin taulukon tietystä indeksistä haku. Taulukon kohdalla vain syntaksi, eli merkintätapa, on erilainen.
Indeksi on kokonaisluku, jonka arvo on välillä [0, taulukon pituus - 1]. Esimerkiksi viiden alkion pituisessa taulukossa on indeksit 0, 1, 2, 3, ja 4.
Scanner lukija = new Scanner(System.in);
int[] luvut = new int[5];
luvut[0] = 42;
luvut[1] = 13;
luvut[2] = 12;
luvut[3] = 7;
luvut[4] = 1;
System.out.println("Mistä indeksistä haetaan? ");
int indeksi = Integer.parseInt(lukija.nextLine());
System.out.println(luvut[indeksi]);
Tehtäväpohjaan on toteutettu valmiiksi ohjelma, missä luodaan taulukko sekä tulostetaan taulukon arvot kahteen kertaan. Muokkaa ohjelmaa siten, että sen jälkeen kun taulukon arvot on tulostettu ensimmäiseen kertaan, käyttäjältä kysytään kahta indeksiä, joiden osoittamat arvot vaihdetaan taulukossa päittäin. Tämän jälkeen alkiot tulee vaihtaa päittäin ja taulukon arvot tulostaa toiseen kertaan.
1 3 5 7 9 Mitkä indeksit vaihdetaan? 2 4 1 3 9 7 5
1 3 5 7 9 Mitkä indeksit vaihdetaan? 0 1 3 1 5 7 9
Voit olettaa, että käyttäjän syöttämät indeksit löytyvät taulukosta.
Taulukon koko ja läpikäynti
Taulukko-olion koon saa selville taulukko-olioon liittyvän julkisen oliomuuttujan length avulla. Julkiseen oliomuuttujaan pääsee käsiksi kirjoittamalla olion nimi piste muuttujan nimi, eli esimerkiksi taulukko.length. Huomaa, että kyseessä ei ole metodikutsu, eli taulukko.length() ei toimi.
Taulukon alkioiden läpikäynti voidaan toteuttaa while-toistolauseen avulla.
int[] luvut = new int[4];
luvut[0] = 42;
luvut[1] = 13;
luvut[2] = 12;
luvut[3] = 7;
System.out.println("Taulukossa on " + luvut.length + " alkiota.");
int indeksi = 0;
while (indeksi < luvut.length) {
System.out.println(luvut[indeksi]);
indeksi++;
}
Taulukossa on 4 alkiota. 42 13 12 7
Yllä olevassa esimerkissä käydään indeksimuuttujan avulla läpi indeksit 0, 1, 2 ja 3, ja tulostetaan taulukon kussakin indeksissä olevan muuttujan arvo. Ensin siis tulostuu luvut[0], sitten luvut[1] jne. Taulukon läpikäynti loppuu kun muuttujan toistolauseen ehtolause indeksi < luvut.length on totta, eli kun indeksimuuttujan arvo on suurempi tai yhtäsuuri kuin taulukon pituus.
Tehtäväpohjassa on valmiina taulukko, joka sisältää lukuja. Täydennä ohjelmaa siten, että käyttäjältä kysyttyä lukua etsitään taulukosta. Jos luku löytyy taulukosta, ohjelma kertoo luvun indeksin. Jos lukua taas ei löydy taulukosta, ohjelma kertoo ettei lukua löydy.
Mitä etsitään? 3 Luku 3 löytyy indeksistä 4.
Mitä etsitään? 7 Luku 7 löytyy indeksistä 7.
Mitä etsitään? 22 Lukua 22 ei löydy.
Jos indeksillä osoitetaan taulukon ohi, eli alkioon jota ei ole olemassa, niin saadaan virheilmoitus ArrayIndexOutOfBoundsException. Virhe ArrayIndexOutOfBoundsException kertoo että taulukossa ei ole haluttua indeksiä. Taulukon ohi, eli indeksiin joka on pienempi kuin 0 tai suurempi tai yhtäsuuri kuin taulukon koko ei saa viitata.
Seuraavassa esimerkissä on ohjelma, joka kysyy käyttäjältä lukujen määrän ja joukon lukuja. Tämän jälkeen ohjelma tulostaa luvut uudestaan samassa järjestyksessä. Käyttäjän antamat luvut tallennetaan taulukkoon.
System.out.print("Kuinka monta lukua? ");
int lukuja = Integer.parseInt(lukija.nextLine());
int[] luvut = new int[lukuja];
System.out.println("Anna luvut:");
int indeksi = 0;
while (indeksi < luvut.length) {
luvut[indeksi] = Integer.parseInt(lukija.nextLine());
indeksi++;
}
System.out.println("Luvut uudestaan:");
indeksi = 0;
while (indeksi < luvut.length) {
System.out.println(luvut[indeksi]);
indeksi++;
}
Eräs ohjelman suorituskerta voisi olla seuraavanlainen:
Kuinka monta lukua? 4 Anna luvut: 4 8 2 1 Luvut uudestaan: 4 8 2 1
Taulukon alkioiden tyyppi
Taulukko-olion esittely tapahtuu kertomalla ensin taulukko-olion sisältämien alkioiden tyyppi, jota seuraa hakasulut (alkiontyyppi[]). Taulukko-olion alkiot voivat siis olla käytännössä minkä tahansa tyyppisiä. Alla muutamia esimerkkejä:
String[] kuukaudet = new String[12];
Henkilo[] ministerit = new Henkilo[14];
double[] approksimaatiot = new double[100];
kuukaudet[0] = "Tammikuu";
ministerit[0] = new Henkilo("Miina Sillanpää");
approksimaatiot[0] = 3.14;
Jokaisen ohjelmoijan on hyvä ymmärtää hieman tietokoneohjelman käytössä olevan muistin rakenteesta. Jokainen muuttuja -- on se sitten alkeistyyppinen tai viittaustyyppinen muuttuja -- tallennetaan muistiin. Jokaisella muuttujalla on myös koko, eli tietty määrä bittejä (nollia ja ykkösiä), jonka muuttuja vie muistista. Muuttujan arvo esitetään myös bitteinä.
Taulukko-olion arvo on viite eli oikeastaan tieto muistipaikasta, missä olion tiedot ovat. Sanomalla taulukko[0] viitataan taulukon ensimmäiseen alkioon. Lausekkeen taulukko[0] voi lukea muodossa "mene taulukon alkuun ja siirry eteenpäin 0 kertaa taulukon sisältämän muuttujan koko -- anna siitä kohdasta eteenpäin muuttujan koon verran tietoa". Vastaavasti taulukko[2] voidaan lukea muodossa "mene taulukon alkuun ja siirry eteenpäin 2 kertaa taulukon sisältämän muuttujan koko -- anna siitä kohdasta eteenpäin muuttujan koon verran tietoa".
Javassa int-tyyppinen muuttuja on 32-bitin kokoinen ja se voi esittää korkeintaan 232-1 kokoista lukua. Kun luodaan int-taulukko, jossa on esimerkiksi 4 paikkaa, muistista varataan kokonaislukuja varten 4*32 bittiä. Sanomalla int-tyyppiselle taulukolle taulukko[2], luetaan 32 bittiä alkaen kohdasta taulukon alku + 2 * 32 bittiä.
Osa ohjelmointikielistä pyrkii varmistamaan, ettei ohjelmoija mene "väärälle alueelle". Jos Java ei aiheuttaisi virhettä sanoessamme taulukko[-1], saisimme tietoomme ohjelman muistissa juuri ennen taulukkoa olevan tiedon. Kukaan ei tällöin myöskään estäisi kirjoittamasta ohjelmaa, joka lukisi kaiken ohjelman muistissa olevan tiedon.
Tietokoneella voi olla samaan aikaan käynnissä useita ohjelmia, mutta todellisuudessa kaikkien käynnissä olevien ohjelmien lähdekoodia ei suoriteta samaan aikaan. Tietokoneen käyttöjärjestelmä vaihtaa suoritettavaa ohjelmaa jatkuvasti, minkä kautta käyttäjälle tulee illuusio siitä, että ohjelmat olisivat samaan aikaan käynnissä.
Round-robin -algoritmia käytetään tietokoneen ohjelmien aikatauluttamiseen.
Algoritmin toimintaperiaate on yksinkertainen. Ohjelmista luodaan jono, ja ensimmäisenä jonossa olevaa ohjelmaa suoritetaan hetki, jonka jälkeen suoritettavana ollut ohjelma siirretään jonon perälle. Tämän jälkeen seuraava jonossa ollut ohjelma -- nyt jonon ensimmäinen -- päätyy suoritettavaksi, jonka jälkeen se siirretään jonon perälle jne.
Tehtäväpohjassa on viisi lukua sisältävä taulukko sekä ohjelmarunko niiden käsittelyyn. Ohjelmarunko tuntee tällä hetkellä kaksi komentoa: "lopeta" lopettaa ohjelman suorituksen ja "tulosta" tulostaa taulukon arvot.
Lisää ohjelmaan komento "siirra", joka siirtää ensimmäisenä taulukossa olevan arvon taulukon perälle sekä kaikkia muita taulukon arvoja yhden paikan eteenpäin.
tulosta 1 3 5 7 9 siirra tulosta 3 5 7 9 1 siirra siirra tulosta 7 9 1 3 5 lopeta
Taulukko metodin parametrina
Taulukkoja voidaan käyttää metodin parametrina aivan kuten kaikkia muitakin muuttujia. Koska taulukko on olio -- toisinsanoen viittaustyyppinen muuttuja -- taulukon arvo on viite taulukkoon liittyviin tietoihin. Kun taulukkoa käytetään metodin parametrina, metodin käyttöön kopioidaan viite taulukkoon.
public class Tulostaja {
public static void listaaAlkiot(int[] kokonaislukuTaulukko) {
System.out.println("taulukon alkiot ovat: ");
int indeksi = 0;
while (indeksi < kokonaislukuTaulukko.length) {
int luku = kokonaislukuTaulukko[indeksi]
System.out.print(luku + " ");
indeksi++;
}
System.out.println("");
}
}
int[] luvut = new int[3];
luvut[0] = 1;
luvut[1] = 2;
luvut[2] = 3;
new Tulostaja().listaaAlkiot(luvut);
// Koska metodilla on määre static, olisi myös kutsu
// Tulostaja.listaaAlkiot(luvut); sallittu
1 2 3
Kuten olemme aiemmin jo huomanneet, parametrin nimi metodin sisällä voi olla aivan vapaasti valittu, nimen ei tarvitse missään tapauksessa olla sama kuin kutsuvassa. Edellä taulukkoa kutsutaan metodin sisällä nimellä kokonaislukuTaulukko, metodin kutsuja taas näkee saman taulukon luvut-nimisenä.
Taulukko on olio, joten kaikki metodissa tapahtuvat taulukon sisältöön vaikuttavat muutokset ovat olemassa myös metodin suorituksen jälkeen.
Täydennä luokassa Summaaja olevaa metodia public int laskeTaulukonLukujenSumma(int[] taulukko) siten, että se laskee ja palauttaa sille parametrina annetussa taulukossa olevien lukujen summan.
Voit kokeilla lukujen summan laskemista esimerkiksi seuraavalla esimerkkikoodilla.
package summa;
public class Main {
public static void main(String[] args) {
// Tässä voit testata metodia
int[] taulukko = {5, 1, 3, 4, 2};
System.out.println(new Summaaja().laskeTaulukonLukujenSumma(taulukko));
}
}
15
Täydennä luokassa Tulostin olevaa metodia public void tulostaTaulukkoTahtina(int[] taulukko), siten, että se tulostaa jokaista taulukossa olevaa lukua vastaavan pituisen rivin tähtiä.
Voit kokeilla tulostusta esimerkiksi seuraavalla esimerkkikoodilla.
package tahdet;
public class Main {
public static void main(String[] args) {
// Tässä voit testata metodia
int[] taulukko = {5, 1, 3, 4, 2};
new Tulostin().tulostaTaulukkoTahtina(taulukko);
}
}
***** * *** **** **
Eli koska taulukon nollannessa paikassa on luku 5, tulee ensimmäiselle riville 5 tähteä. Seuraavalla 1 tähti jne.
Täydennä luokan TaulukonTulostaja metodia public void tulostaTyylikkaasti(int[] taulukko) siten, että metodi tulostaa parametrina saamansa taulukon luvut tyylikkäästi. Lukujen väliin tulee pilkku ja välilyönti. Viimeisen luvun jälkeen ei pilkkua tule.
Voit kokeilla tulostusta esimerkiksi seuraavalla esimerkkikoodilla.
package tulostus;
public class Main {
public static void main(String[] args) {
// Tässä voit testata metodia
int[] taulukko = {5, 1, 3, 4, 2};
new TaulukonTulostaja().tulostaTyylikkaasti(taulukko);
}
}
5, 1, 3, 4, 2
Täydennä luokassa LukujenKasvattaja olevaa metodia public void kasvata(int[] taulukko, int paljonko) siten, että se kasvatta jokaista parametrina saadun taulukon alkiota toisena parametrina saadun luvun arvolla.
Voit kokeilla kasvatusta esimerkiksi seuraavalla esimerkkikoodilla. Luokka Arrays tarjoaa apuvälineitä taulukoiden käsittelyyn.
package kasvattaja;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
// Tässä voit testata metodia
int[] taulukko = {5, 1, 3, 4, 2};
System.out.println(Arrays.toString(taulukko));
new LukujenKasvattaja().kasvata(taulukko, 3);
System.out.println(Arrays.toString(taulukko));
}
}
[5, 1, 3, 4, 2] [8, 4, 6, 7, 5]
Taulukko metodin paluuarvona
Koska metodit voivat palauttaa olioita, voivat ne palauttaa myös taulukkoja. Eräs merkkijonotaulukon palauttava metodi on seuraavannäköinen -- huomaa että taulukkoihin voi aivan hyvin siis laittaa myös olioita.
public class Taulukkotehdas {
public String[] annaMerkkijonoTaulukko() {
String[] opet = new String[1];
opet[0] = "Kong Fu Zi (Confucius)";
return opet;
}
}
String[] opettajat = new Taulukkotehdas().annaMerkkijonoTaulukko();
int indeksi = 0;
while (indeksi < opettajat.length) {
System.out.println(opettajat[indeksi]);
indeksi++;
}
Kong Fu Zi (Confucius)
Kopiointi
Tee luokkaan Taulukot metodi public int[] kopioi(int[] taulukko) joka luo kopion parametrina saadusta taulukosta. Vihje: koska metodin on luotava taulukosta kopio, tulee metodin sisällä luoda uusi taulukko ja kopioida vanhan taulukon sisältö uudelle taulukolle alkio alkiolta.
Seuraavassa esimerkki metodin käytöstä (koodissa myös Arrays-luokan tarjoama kätevä apuväline taulukon sisällön tulostamiseen):
public static void main(String[] args) {
int[] alkuperainen = {1, 2, 3, 4};
int[] kopio = new Taulukot().kopioi(alkuperainen);
// muutetaan kopioa
kopio[0] = 99;
// tulostetaan molemmat
System.out.println("alkup: " + Arrays.toString(alkuperainen));
System.out.println("kopio: " + Arrays.toString(kopio));
}
Kuten tulostuksesta huomaa, ei kopioon tehty muutos vaikuta alkuperäiseen:
alkup: [1, 2, 3, 4] kopio: [99, 2, 3, 4]
Kääntäminen
Tee luokkaan Taulukot metodi public int[] kaanna(int[] taulukko), joka luo käänteisessä järjestyksessä olevan kopion parametrinaan saamastaan taulukosta.
Eli jos parametrina on taulukko jossa esim. luvut 5, 6, 7 palauttaa metodi uuden taulukon jonka sisältönä luvut 7, 6, 5. Parametrina oleva taulukko ei saa muuttua.
Seuraavassa esimerkki metodin käytöstä:
public static void main(String[] args) {
int[] alkuperainen = {1, 2, 3, 4};
int[] kaannetty = new Taulukot().kaanna(alkuperainen);
// tulostetaan molemmat
System.out.println("alkup: " +Arrays.toString(alkuperainen));
System.out.println("käännetty: " +Arrays.toString(kaannetty));
}
Tulostuksesta pitäisi selvitä, että alkuperäinen taulukko on muuttumaton:
alkup: [1, 2, 3, 4] käännetty: [4, 3, 2, 1]
Taulukko oliomuuttujana
Luokka voi sisältää muiden muuttujien lisäksi myös taulukon tai taulukoita oliomuuttujina. Alla oleva esimerkki kuvaa lottoriviä, johon voidaan lisätä numeroita. Jokaisessa lottorivissä on täsmälleen 7 lukua, jotka ovat väliltä 1-40 ja luku ei saa esiintyä rivissä kahdesti.
import java.util.Arrays;
public class Lottorivi {
private int[] numerot;
private int numeroita;
public Lottorivi() {
this.numerot = new int[7];
this.numeroita = 0;
}
public void lisaa(int numero) {
if (this.numeroita >= this.numerot.length) {
System.out.println("Lottorivi on jo täysi!");
return;
}
if (this.sisaltaa(numero)) {
System.out.println("Numero on jo lottorivissä");
return;
}
this.numerot[this.numeroita] = numero;
this.numeroita++;
}
public boolean sisaltaa(int numero) {
int indeksi = 0;
while(indeksi < this.numeroita) {
if (this.numerot[indeksi] == numero) {
return true;
}
indeksi++;
}
return false;
}
public String toString() {
return Arrays.toString(this.numerot);
}
}
Pino on tietorakenne, joka tarjoaa oleellisesti kaksi toimintoa. Pinoon voidaan lisätä tietoa ja siitä voidaan ottaa tietoa. Pinoon lisääminen lisää alkion aina pinon päälle, ja ottaminen poistaa ja palauttaa pinon päällimmäisen arvon.
Pino-tietorakenne on lähes valmiiksi toteutettuna tehtäväpohjassa mukana tulevaan luokkaan Pino. Siinä on kuitenkin pieni pulma: pinon koko on rajattu. Muokkaa pinon metodia public void kasvata() siten, että sitä kutsuttaessa pinon kapasiteetti kasvaa viidellä. Tee siis niin, että luot uuden taulukon, jossa on 5 paikkaa enemmän kuin vanhassa ja kopioit vanhan taulukon arvot uuteen. Vaihda tämän jälkeen käytössä oleva taulukko kopioon.
Pino p = new Pino();
p.lisaa(" *");
p.lisaa("*********");
p.lisaa(" *******");
p.lisaa(" *****");
p.lisaa(" ***");
p.lisaa(" *");
while (p.koko() > 0) {
System.out.println(p.poista());
}
*
***
*****
*******
*********
*
Lyhyempi merkintätapa taulukon luomiseen
Merkkijono-olioiden lisäksi taulukko-olioiden luomiseen löytyy lyhyempi merkintätapa. Alla olevassa esimerkissä luodaan kolmepaikkainen kokonaislukutaulukko, johon asetetaan arvot 100, 1 ja 42.
int[] luvut = {100, 1, 42};
Taulukko-olio voidaan siis aiemmin näkemämme new-kutsun lisäksi alustaa myös lohkolla, jossa taulukkoon asetettavat arvot esitellään pilkulla eriteltyinä. Tämä toimii kaikille muuttujatyypeille: alla on esitelty ensin merkkijonoja sisältävä taulukko, jonka jälkeen esitellään liukulukuja sisältävä taulukko.
String[] merkkijonotaulukko = {"Matti L.", "Matti P.", "Matti V."};
double[] liukulukutaulukko = {1.20, 3.14, 100.0, 0.6666666667};
Lohkoalustusta käytettäessä taulukon koko on aina täsmälleen lohkossa määriteltyjen arvojen määrä. Lohkossa määritellyt arvot asetetaan taulukkoon järjestestyksessä siten, että ensimmäinen arvo asetetaan nollanteen indeksiin, toinen arvo ensimmäiseen indeksiin jne.
// indeksi 0 1 2 3 4 5 6 7
int[] luvut = {100, 1, 42, 23, 1, 1, 3200, 3201};
System.out.println(luvut[0]); // tulostaa luvun taulukon indeksistä 0, eli luvun 100
System.out.println(luvut[2]); // tulostaa luvun taulukon indeksistä 2, eli luvun 42
Kaksiulotteinen taulukko
Aiemmat taulukkoesimerkkimme ovat käsitelleet yksiulotteisia taulukoita, missä indeksi kertoo sijainnin yhdessä ulottuvuudessa. Taulukon voi luoda myös useampiulotteisena, jolloin taulukossa olevaa tietoa voi tarkastella useamman indeksin avulla. Tämä on kätevää esimerkiksi silloin, jos tieto on useampiulotteista kuten esimerkiksi koordinaatistossa.
Kaksiulotteinen taulukko, jossa on kaksi riviä ja kolme saraketta, luodaan seuraavasti:
int rivit = 2;
int sarakkeet = 3;
int[][] kaksiulotteinenTaulukko = new int[rivit][sarakkeet];
Yllä luomme taulukon, jonka jokainen rivi viittaa taulukkoon, jossa on tietty määrä sarakkeita. Kaksiulotteisen taulukon läpikäynti onnistuu kahden sisäkkäisen while-toistolauseen avulla seuraavasti:
int rivit = 2;
int sarakkeet = 3;
int[][] kaksiulotteinenTaulukko = new int[rivit][sarakkeet];
int y = 0;
while (y < kaksiulotteinenTaulukko.length) {
int x = 0;
while (x < kaksiulotteinenTaulukko[y].length) {
int arvo = kaksiulotteinenTaulukko[y][x];
System.out.println("arvo kohdassa (" + x + ", " + y + "): " + arvo);
x++;
}
y++;
}
Ylläolevan ohjelman tulostus on seuraava.
arvo kohdassa (0, 0): 0 arvo kohdassa (1, 0): 0 arvo kohdassa (2, 0): 0 arvo kohdassa (0, 1): 0 arvo kohdassa (1, 1): 0 arvo kohdassa (2, 1): 0
Saatoit yllättyä. Selityksenä tulostukselle on se, että int-tyyppisten muuttujien oletusarvo on 0.
Voimme muuttaa taulukon arvoja kuten ennenkin. Alla asetamme kahteen kohtaan uudet arvot.
int rivit = 2;
int sarakkeet = 3;
int[][] kaksiulotteinenTaulukko = new int[rivit][sarakkeet];
kaksiulotteinenTaulukko[0][1] = 4;
kaksiulotteinenTaulukko[1][1] = 1;
kaksiulotteinenTaulukko[1][0] = 8;
int y = 0;
while (y < kaksiulotteinenTaulukko.length) {
int x = 0;
while (x < kaksiulotteinenTaulukko[y].length) {
int arvo = kaksiulotteinenTaulukko[y][x];
System.out.println("arvo kohdassa (" + x + ", " + y + "): " + arvo);
x++;
}
y++;
}
Nyt tulostus näyttää seuraavalta:
arvo kohdassa (0, 0): 0 arvo kohdassa (1, 0): 4 arvo kohdassa (2, 0): 0 arvo kohdassa (0, 1): 8 arvo kohdassa (1, 1): 1 arvo kohdassa (2, 1): 0
Kaksiulotteinen taulukko on oikeastaan matriisi. Matriiseja käytetään muunmuassa tietokonegrafiikassa, missä yksittäiset pikselit esitetään matriisin avulla.
Tehtäväpohjaan on toteutettu graafinen sovellus, mikä sisältää kaksiulotteisen taulukon. Tehtävänäsi on muuttaa sovelluksen toimintaa siten, että kun käyttäjä painaa hiirtä sovelluksessa tai liikuttaa hiirtä kun nappi on pohjassa, ikkunaan piirretään.
Tee tätä varten kaksi asiaa: (1) muuta sovelluksessa olevan taulukon "piirrettava" arvoja sopivasti kun käyttäjä käyttää hiirtä, ja (2) piirrä komentoa piirturi(x, y, 2, 2) käyttäen ne alkiot, joiden arvo on 1. Käytä koordinaatteina x, y taulukon indeksejä.
Kun sovellus toimii, voit käyttää sitä vaikkapa seuraavanlaisen taideteoksen tekemiseen. Tehtävässä ei ole testejä.
Toteutimme aiemmin Game of Life -pelin logiikan sisäkkäisiä hajautustauluja käyttäen. Tarkastellaan nyt samaa kaksiulotteisten taulukkojen avulla.
Game of Life on neljää yksinkertaista sääntöä seuraava soluautomaatti:
- Jos elävän solun naapureina on alle kaksi elävää solua, se kuolee alikansoituksen takia.
- Jos elävän solun naapureina on kaksi tai kolme elävää solua, se jää henkiin.
- Jos elävän solun naapureina on yli kolme elävää solua, se kuolee ylikansoituksen takia.
- Jos kuolleen solun naapureina on tasan kolme elävää solua, se syntyy eli muuttuu eläväksi.
Peli ei sisällä minkäänlaisia liikkumissääntöjä, mutta se silti luo tilanteita, missä erilaiset hahmot liikkuvat ruudulla. Katso pelin keksineen John Conwayn mietteitä pelistä sekä sääntöjen selitys.
Tässä tehtävässä toteutetaan oleellisilta osin Game of Life-pelin säännöt. Toteutusta varten tehtäväpohjassa on luokka GameOfLife, joka sisältää kaksiulotteisen taulukon, sekä luokka GameOfLifeSovellus, jota voidaan käyttää pelin visualisointiin.
Elossa olevien naapurien lukumäärä
Täydennä luokassa GameOfLife olevaa metodia public int elossaOleviaNaapureita(int[][] taulukko, int x, int y) siten, että se laskee annetun x, y -koordinaatin elossa olevien naapureiden lukumäärän. Naapuri on elossa jos sen arvo on 1.
Naapureita ovat kaikki ne alkiot, jotka ovat kulman tai sivun kautta yhteydessä alkioon.
Huomaa, että metodin tulee varoa ArrayIndexOutOfBounds-virhettä. Indeksissä -1 ei esimerkiksi voi olla ketään. Vastaavasti taulukon leveyden tai korkeuden yli ei voi mennä (esim. taulukko[taulukko.length][0] tai taulukko[0][taulukko[0].length]).
Voit kokeilla metodiasi muunmuassa seuraavilla esimerkeillä.
GameOfLife gol = new GameOfLife(3, 3);
int[][] taulukko = new int[3][3];
taulukko[0][0] = 1;
taulukko[0][1] = 1;
taulukko[1][1] = 1;
taulukko[2][2] = 1;
System.out.println(gol.elossaOleviaNaapureita(taulukko, 0, 0));
System.out.println(gol.elossaOleviaNaapureita(taulukko, 1, 0));
System.out.println(gol.elossaOleviaNaapureita(taulukko, 1, 1));
System.out.println(gol.elossaOleviaNaapureita(taulukko, 2, 2));
2 3 3 1
GameOfLife gol = new GameOfLife(4, 4);
int[][] taulukko = {{1, 1, 1, 1}, {1, 1, 1, 1}, {1, 0, 1, 0}, {0, 1, 0, 1}};
System.out.println(gol.elossaOleviaNaapureita(taulukko, 0, 0));
System.out.println(gol.elossaOleviaNaapureita(taulukko, 1, 1));
System.out.println(gol.elossaOleviaNaapureita(taulukko, 2, 2));
System.out.println(gol.elossaOleviaNaapureita(taulukko, 3, 3));
3 7 5 1
Kehittyminen
Täydennä seuraavaksi GameOfLife-luokan metodia public void kehity() siten, että se käy yhden Game of Life -pelin askeleen.
Toteuta toiminnallisuus niin, että luot toisen taulukon, jonka koko on sama kuin alkuperäisen taulukon. Käy tämän jälkeen alkuperäistä taulukkoa läpi alkio alkiolta siten, että seuraat seuraavia sääntöjä:
- Jos alkuperäisen taulukon alkion arvo on 1 ja sillä on alle kaksi elävää naapuria, kopioon asetetaan alkion arvoksi 0.
- Jos alkuperäisen taulukon alkion arvo on 1 ja sillä on kaksi tai kolme elävää naapuria, kopioon asetetaan alkion arvoksi 1.
- Jos alkuperäisen taulukon alkion arvo on 1 ja sillä on yli kolme elävää naapuria, kopioon asetetaan alkion arvoksi 0.
- Jos alkuperäisen taulukon alkion arvo on 0 ja sillä on tasan kolme elävää naapuria, kopioon asetetaan alkion arvoksi 1.
Käytä naapureiden lukumäärän selvittämisessä edellisessä osassa tehtyä metodia. Kun olet käynyt koko taulukon läpi, vaihda kopio taulukon paikalle.
Kokeile tämän jälkeen sovelluksen toimintaa graafisen käyttöliittymän kautta. Sovelluksen pitäisi käynnistyä -- yksi mahdollinen hetkellinen tila on seuraavanlainen.
Taulukon toiminnallisuutta vastaavan toiminnallisuuden pystyy toteuttamaan hajautustaulun avulla. Eikö hajautustaulun käyttö olisi yleisesti ottaen parempi vaihtoehto, sillä sitä ei esimerkiksi tarvitse kasvattaa lainkaan?
Kun hajautustaulusta haetaan tietoa tietyllä avaimella, metodin hashCode perusteella selvitetään paikka, mistä tietoa haetaan. Samassa paikassa voi olla useampi arvo (listassa), jolloin haettavaa avainta verrataan jokaiseen listalla olevaan arvoon equals-metodia käyttäen. Kun taulukosta haetaan arvoa tietyllä avaimella -- eli indeksillä -- ei vastaavaa toiminnallisuutta tarvitse tehdä. Taulukossa joko on arvo tai arvoa ei ole. Taulukkoon liittyy pieni tehokkuushyöty ohjelman suorituskyvyn kannalta.
Tämä tehokkuushyöty kuitenkin tulee lisääntyneen virhealttiuden sekä työmäärän kustannuksella. Hajautustauluun on valmiiksi toteutettuna sisäisen taulukon kasvattaminen ja sen toiminnallisuutta on testattu hyvin laajasti. Taulukkoa käytettäessä tällaista etua ei ole -- uutta toiminnallisuutta toteuttaessa saattaa päätyä virheisiin, mikä kasvattaa työmäärää. Virheet ovat toki luonnollinen osa ohjelmistokehitystä.
Kun ajattelemme muistin käyttöä, hajautustaululla voi olla -- tapauksesta riippuen -- pieni etu. Kun taulukko luodaan, muistista varataan heti tila koko taulukolle. Mikäli taulukon jokaiseen indeksiin ei tarvitse lisätä tietoa, on osa tästä tiedosta varattuna turhaan. Hajautustaululla taas tällaista muistin varaamista ei ennakkoon tehdä -- hajautustaulun kokoa kasvatetaan tarvittaessa.
Muita menetelmiä taulukon tulostamiseen
Käytimme esimerkeissä while-toistolausetta taulukon arvojen. Tulostamiseen voi käyttää myös virtaa sekä for-toistolausetta.
Virta
Javan luokka Arrays tarjoaa metodin taulukon käsittelyyn virtana. Kutsumalla luokan metodia stream(taulukko), joka saa parametrinaan taulukon, luodaan käsiteltävä virta.
int[] luvut = {1, 8, 10, 3, 5};
Arrays.stream(luvut).forEach(luku -> System.out.println(luku));
1 8 10 3 5
int[] luvut = {1, 8, 10, 3, 5};
Arrays.stream(luvut)
.filter(luku -> luku <= 5)
.forEach(luku -> System.out.println(luku));
1 3 5
Sama onnistuu myös kaksi- ja useampiulotteisessa taulukossa. Tällöin ensimmäinen stream-kutsu luo yksiulotteisia taulukoita sisältävän syötevirran. Jokainen yksiulotteinen taulukko voidaan myös muuntaa arvoja sisältäväksi syötevirraksi.
int rivit = 2;
int sarakkeet = 3;
int[][] kaksiulotteinenTaulukko = new int[rivit][sarakkeet];
Arrays.stream(kaksiulotteinenTaulukko)
.forEach(taulukko -> {
Arrays.stream(taulukko).forEach(alkio -> System.out.print(alkio + " "));
System.out.println();
});
For-toistolause
For-toistolause on kätevä erityisesti indeksoitavien joukkojen kuten taulukoiden käsittelyn yhteydessä. Seuraavassa tulostetaan for-toistolauseen avulla luvut 0, 1 ja 2:
for (int i = 0; i < 3; i++) {
System.out.println(i);
}
Yllä oleva esimerkki toimii lähes samalla tavalla kuin alla oleva esimerkki. Ainoa ero on se, että alla muuttuja i on olemassa myös toistolauseen jälkeen.
int i = 0; // toistossa käytettävän muuttujan alustus
while (i < 3) { // toistoehto
System.out.println(i);
i++; // toistossa käytettävän muuttujan päivitys
}
Toistolause for, kuten yllä esitelty for (int i = 0; i < 3; i++) sisältää kolme osaa: (1) muuttujien alustus; (2) toistoehto; ja (3) muuttujien päivitys.
-
Ensimmäisessä osassa luodaan toistolauseessa käytettävät muuttujat. Yllä olevassa esimerkissä luodaan muuttuja
ilauseellaint i = 0. Ensimmäinen osa suoritetaan vain kerran, for-lauseen alussa. -
Toisessa osassa määritellään toistoehto, joka määrittelee mihin asti toistolauseen yhteydessä olevassa koodilohkossa olevaa koodia suoritetaan. Esimerkissämme toistoehto oli
i < 3. Toistoehdon voimassaolo tarkastetaan ennen jokaista toistokertaa. Toistoehto toimii täsmälleen samoin kuin while-toistolauseen toistoehto. -
Kolmas osa, joka esimerkissämme on
i++suoritetaan kerran jokaisen koodilohkon suorituksen jälkeen.
Toistolause for on hieman while-toistolausetta selkeämpi tapa toteuttaa toistoja, joissa toistojen määrä perustuu esimerkiksi laskurin kasvatukseen. Taulukkojen läpikäynnissä tilanne on yleensä juuri tämä. Seuraavassa tulostetaan taulukon luvut sisältö for-toistolauseella.
int[] luvut = {1, 3, 5, 9, 17, 31, 57, 105};
for(int i = 3; i < 7; i++) {
System.out.println(luvut[i]);
}
Toistolauseen muuttuja voi saada arvokseen muutakin kuin nollan, ja läpikäynti voi edetä esimerkiksi "ylhäältä alas". Taulukon indekseissä 6, 5, 4, ja 3 olevat alkiot voidaan tulostaa seuraavasti.
int[] luvut = {1, 3, 5, 9, 17, 31, 57, 105};
for(int i = 6; i > 2; i--) {
System.out.println(luvut[i]);
}
Toistolause for toimii myös kaksi- ja useampiulotteisilla taulukoilla.
int rivit = 2;
int sarakkeet = 3;
int[][] kaksiulotteinenTaulukko = new int[rivit][sarakkeet];
kaksiulotteinenTaulukko[0][1] = 4;
kaksiulotteinenTaulukko[1][1] = 1;
kaksiulotteinenTaulukko[1][0] = 8;
for (int y = 0; y < kaksiulotteinenTaulukko.length; y++) {
for (int x = 0; x < kaksiulotteinenTaulukko[y].length; x++) {
int arvo = kaksiulotteinenTaulukko[y][x];
System.out.println("arvo kohdassa (" + x + ", " + y + "): " + arvo);
}
}
CrowdSorcerer ja vapaa tehtävä
Tässä kohtaa pääset toteuttamaan vapaan, itse keksimäsi tehtävän tulevia sukupolvia varten. Mikäli et ole CrowdSorcereria aiemmin, käy katsomassa CrowdSorcererin opasvideo toisen osan materiaalista.
Keksi ohjelmointitehtävä. Tehtävän aihealuetta ei ole rajattu, eli tehtävä on hyvin vapaa. Saat käyttää tehtävässä listoja, hajautustauluja, taulukoita sekä Scanneria.
Huom! Tässä sinun täytyy todennäköisesti syöttää jokaiselle testitapaukselle useampi syöte. Useamman syötteen saat annettua, kun laitat rivinvaihdon \n jokaisen syötteen väliin.
Esimerkiksi jos haluat antaa testisyötteeksi "kissa", "koira", "lopeta", syötä input-kenttään teksti kissa\nkoira\nlopeta.
Muista merkitä malliratkaisurivit ohjelmaan -- näin ratkaisu ei tule suoraan käyttäjälle näkyvään tehtävänantoon.
Tiedon hakeminen ja järjestäminen
Tiedon nopea hakeminen ja näyttäminen on oleellinen osa ohjelmistojen käytettävyyttä. Jos ohjelman käyttäjä joutuu odottamaan kymmeniä sekunteja kun ohjelma etsii käyttäjän haluamaa tietoa, saattaa ohjelman käyttäjä lopettaa ohjelman käyttämisen kokonaan. Vastaavasti televisio-ohjelmistoja selaava käyttäjä ei hyödy televisio-ohjelman tiedoista mitään jos tiedot latautuvat vasta ohjelman katsomisen jälkeen.
Laajemmin voidaan ajatella, että nopeasti tapahtuva tiedon hakeminen ja näyttäminen on oleellista oikeastaan lähes missä tahansa sovelluksessa. Tutustutaan seuraavaksi tiedon hakemiseen ja järjestämiseen liittyviin algoritmeihin. Vaikka esimerkit käyttävät taulukoita, algoritmit toimivat myös muilla tiedon tallentamiseen tarkoitetuilla tietorakenteilla kuten listoilla.
Peräkkäishaku
Peräkkäishaku on hakualgoritmi, joka etsii tietoa taulukosta käymällä taulukkoa läpi alkio alkiolta. Heti kun haettu alkio löytyy, sen indeksi palautetaan. Jos alkiota ei löydy, palautetaan tieto siitä ettei haettavaa alkiota löytynyt -- tämä kerrotaan tyypillisesti palauttamalla indeksin sijaan arvo -1.
public class Algoritmit {
public int perakkaishaku(int[] taulukko, int haettava) {
for (int i = 0; i < taulukko.length; i++) {
if (taulukko[i] == haettava) {
return i;
}
}
return -1;
}
}
Pahimmassa tapauksessa, eli tilanteessa missä alkiota ei lödy, algoritmi tekee taulukon koon verran vertailuja. Vaikkapa 10 miljoonaa arvoa sisältävässä taulukossa tämä tarkoittaa kymmentä miljoonaa vertailua. Jos tietoa haetaan useampia kertoja, kannattaa tehokkuutta yrittää parantaa.
Valintajärjestäminen
Jos tieto ei noudata minkäänlaista järjestystä tai sääntöä, on tiedon hakeminen tyypillisesti työlästä. Tarvitsemme siis järjestystä!
Ohjelmoijan yleissivistykseen kuuluu ainakin yhden järjestämisalgoritmin (eli tavan järjestää taulukko) tuntemus. Tutustutaan erääseen "klassiseen" järjestämisalgoritmiin, valintajärjestämiseen. Tutustuminen tapahtuu harjoitustehtävien avulla.
Pienimmän arvon etsiminen
Tee luokkaan Valintajarjestaminen metodi pienin, joka palauttaa metodille parametrina annetun kokonaislukutaulukon pienimmän luvun.
Metodin runko on seuraava:
public int pienin(int[] taulukko) {
// kirjoita koodia tähän
}
Seuraava esimerkki esittelee metodin toimintaa:
int[] luvut = {6, 5, 8, 7, 11};
System.out.println("Pienin: " + new Valintajarjestaminen().pienin(luvut));
Pienin: 5
Pienimmän arvon indeksi
Tee luokkaan Valintajarjestaminen metodi pienimmanIndeksi, joka palauttaa sille parametrina annetun taulukon pienimmän luvun indeksin.
Metodin runko on seuraava:
public int pienimmanIndeksi(int[] taulukko) {
// kirjoita koodia tähän
}
Seuraava koodi esittelee metodin toimintaa:
// indeksit: 0 1 2 3 4
int[] luvut = {6, 5, 8, 7, 11};
System.out.println("Pienimmän indeksi: " + new Valintajarjestaminen().pienimmanIndeksi(luvut));
Pienimmän indeksi: 1
Taulukon pienin luku on 5, ja sen indeksi eli sijaintipaikka taulukossa on 1. Muistathan, että taulukon numerointi alkaa 0:sta.
Pienimmän arvon indeksi taulukon loppuosassa
Tee luokkaan Valintajarjestaminen metodi pienimmanIndeksiAlkaen, joka toimii samalla tavalla kuin edellisen tehtävän metodi, mutta ottaa huomioon vain taulukon loppuosan jostain indeksistä alkaen. Metodille annetaan parametrina taulukon lisäksi aloitusindeksi, josta lähtien pienintä lukua etsitään.
Metodin runko on seuraava:
public int pienimmanIndeksiAlkaen(int[] taulukko, int aloitusIndeksi) {
// kirjoita koodia tähän
}
Seuraava koodi esittelee metodin toimintaa:
Valintajarjestaminen algoritmi = new Valintajarjestaminen();
// indeksit: 0 1 2 3 4
int[] luvut = {-1, 6, 9, 8, 12};
System.out.println(algoritmi.pienimmanIndeksiAlkaen(luvut, 0));
System.out.println(algoritmi.pienimmanIndeksiAlkaen(luvut, 1));
System.out.println(algoritmi.pienimmanIndeksiAlkaen(luvut, 2));
0 1 3
Esimerkissä ensimmäinen metodikutsu etsii pienimmän luvun indeksin aloittaen indeksistä 0. Indeksistä 0 alkaen pienin luku on -1, ja sen indeksi on 0. Toinen metodikutsu etsii pienimmän luvun indeksiä indeksistä 1 aloittaen. Tällöin pienin luku on 6, ja sen indeksi on 1. Kolmas kutsu etsii pienimmän luvun indeksiä aloittaen indeksistä 2. Indeksistä 2 alkaen pienin luku on 8, ja sen indeksi on 3.
Lukujen vaihtaminen
Tee luokkaan Valintajarjestaminen metodi vaihda, jolle annetaan taulukko ja kaksi sen indeksiä. Metodi vaihtaa indekseissä olevat luvut keskenään.
Metodin runko on seuraava:
public void vaihda(int[] taulukko, int indeksi1, int indeksi2) {
// kirjoita koodia tähän
}
Seuraavassa estellään metodin toimintaa. Taulukon tulostamisessa käytetään apuna taulukon merkkijonoksi muotoilevaa Arrays.toString-metodia:
int[] luvut = {3, 2, 5, 4, 8};
System.out.println(Arrays.toString(luvut));
vaihda(luvut, 1, 0);
System.out.println(Arrays.toString(luvut));
vaihda(luvut, 0, 3);
System.out.println(Arrays.toString(luvut));
[3, 2, 5, 4, 8] [2, 3, 5, 4, 8] [4, 3, 5, 2, 8]
Järjestäminen
Nyt koossa on joukko hyödyllisiä metodeja, joiden avulla voimme toteuttaa järjestämisalgoritmin nimeltä valintajärjestäminen.
Valintajärjestämisen idea on seuraava:
- Siirretään taulukon pienin luku indeksiin 0.
- Siirretään taulukon toiseksi pienin luku indeksiin 1.
- Siirretään taulukon kolmanneksi pienin luku indeksiin 2.
- Jne.
Toisin sanoen:
- Tarkastellaan taulukkoa indeksistä 0 alkaen. Vaihdetaan keskenään indeksissä 0 oleva luku sekä taulukon pienin luku indeksistä 0 alkaen.
- Tarkastellaan taulukkoa indeksistä 1 alkaen. Vaihdetaan keskenään indeksissä 1 oleva luku sekä taulukon pienin luku indeksistä 1 alkaen.
- Tarkastellaan taulukkoa indeksistä 2 alkaen. Vaihdetaan keskenään indeksissä 2 oleva luku sekä taulukon pienin luku indeksistä 2 alkaen.
- Jne.
Toteuta metodi jarjesta, joka perustuu yllä olevaan ideaan. Metodissa on syytä olla silmukka, joka käy läpi taulukon indeksejä. Metodeista pieninIndeksiAlkaen ja vaihda on varmasti hyötyä. Tulosta myös taulukon sisältö ennen järjestämistä ja jokaisen kierroksen jälkeen, jotta voit varmistaa algoritmin toimivan oikein.
Metodin runko on seuraava:
public void jarjesta(int[] taulukko) {
}
Testaa metodin toimintaa ainakin seuraavalla esimerkillä:
int[] luvut = {8, 3, 7, 9, 1, 2, 4};
new Valintajarjestaminen().jarjesta(luvut);
Ohjelman tulosteen tulisi olla seuraavanlainen. Huomaa että sinun tulee tulostaa taulukon sisältö jokaisen vaihtamisen jälkeen!
[8, 3, 7, 9, 1, 2, 4] [1, 3, 7, 9, 8, 2, 4] [1, 2, 7, 9, 8, 3, 4] [1, 2, 3, 9, 8, 7, 4] [1, 2, 3, 4, 8, 7, 9] [1, 2, 3, 4, 7, 8, 9] [1, 2, 3, 4, 7, 8, 9]
Huomaat, miten taulukko tulee pikkuhiljaa järjestykseen alkaen alusta ja edeten loppua kohti.
Valmiiden järjestämisalgoritmien hyödyntäminen
Java tarjoaa merkittävän määrän valmiita järjestysalgoritmeja. Taulukot voi järjestää (luonnolliseen järjestykseen) luokan Arrays tarjoamalla metodilla sort, ja listat voi järjestää (luonnolliseen järjestykseen) luokan Collections tarjoamalla metodilla sort.
int[] luvut = {8, 3, 7, 9, 1, 2, 4};
System.out.println(Arrays.toString(luvut));
Arrays.sort(luvut);
System.out.println(Arrays.toString(luvut));
[8, 3, 7, 9, 1, 2, 4] [1, 2, 3, 4, 7, 8, 9]
ArrayList<Integer> luvut = new ArrayList<>();
luvut.add(8);
luvut.add(3);
luvut.add(7);
System.out.println(luvut);
Collections.sort(luvut);
System.out.println(luvut);
[8, 3, 7] [3, 7, 8]
Valmiit järjestämisalgoritmit toimivat sekä alkeistyyppisille muuttujille, että joillekin viittaustyyppisille muuttujille kuten String. Omien luokkiemme järjestämistä varten joudumme antamaan Javalle hieman lisävinkkejä, sillä luokat eivät sisällä tietoa siitä, miten niistä luodut oliot pitäisi järjestää.
Järjestämisessä käytettävä rajapinta Comparable
Javan valmis rajapinta Comparable määrittelee metodin compareTo, jota käytetään olioiden vertailuun.
Jos olio on vertailujärjestyksessä ennen parametrina saatavaa olioa, tulee metodin palauttaa negatiivinen luku. Jos taas olio on järjestyksessä parametrina saatavan olion jälkeen, tulee metodin palauttaa positiivinen luku. Muulloin palautetaan luku 0. Tätä compareTo-metodin avulla johdettua järjestystä kutsutaan luonnolliseksi järjestykseksi (natural ordering).
Tarkastellaan tätä ensin kerhossa käyvää lasta tai nuorta kuvaavan luokan Kerholainen avulla. Jokaisella kerholaisella on nimi ja pituus. Kerholaisten tulee mennä syömään pituusjärjestyksessä, joten toteutetaan kerholaisille rajapinta Comparable. Comparable-rajapinta ottaa tyyppiparametrinaan luokan, johon vertaus tehdään. Käytetään tyyppiparametrina samaa luokkaa Kerholainen.
public class Kerholainen implements Comparable<Kerholainen> {
private String nimi;
private int pituus;
public Kerholainen(String nimi, int pituus) {
this.nimi = nimi;
this.pituus = pituus;
}
public String getNimi() {
return this.nimi;
}
public int getPituus() {
return this.pituus;
}
@Override
public String toString() {
return this.getNimi() + " (" + this.getPituus() + ")";
}
@Override
public int compareTo(Kerholainen kerholainen) {
if (this.pituus == kerholainen.getPituus()) {
return 0;
} else if (this.pituus > kerholainen.getPituus()) {
return 1;
} else {
return -1;
}
}
}
Rajapinnan vaatima metodi compareTo palauttaa kokonaisluvun, joka kertoo vertausjärjestyksestä. Koska compareTo()-metodista riittää palauttaa negatiivinen luku, jos this-olio on pienempi kuin parametrina annettu olio ja nolla, kun pituudet ovat samat, voidaan edellä esitelty metodi compareTo toteuttaa myös seuraavasti.
@Override
public int compareTo(Kerholainen kerholainen) {
return this.pituus - kerholainen.getPituus();
}
Kerholaisten järjestäminen on nyt suoraviivaista.
List<Kerholainen> kerholaiset = new ArrayList<>();
kerholaiset.add(new Kerholainen("mikael", 182));
kerholaiset.add(new Kerholainen("matti", 187));
kerholaiset.add(new Kerholainen("ada", 184));
kerholaiset.stream().forEach(k -> System.out.println(k);
System.out.println();
// tulostettavan virran järjestäminen (listaa ei järjestetä)
kerholaiset.stream().sorted().forEach(k -> System.out.println(k);
kerholaiset.stream().forEach(k -> System.out.println(k);
// listan järjestäminen
Collections.sort(kerholaiset);
kerholaiset.stream().forEach(k -> System.out.println(k);
mikael (182) matti (187) ada (184) mikael (182) ada (184) matti (187) mikael (182) matti (187) ada (184) mikael (182) ada (184) matti (187)
Koska Kerholainen toteuttaa rajapinnan Comparable, voi sen järjestää virran sorted-metodilla. Toisin sanoen, minkä tahansa Comparable-rajapinnan toteuttavan luokan oliot voi järjestää virran sorted-metodilla. Huomaa kuitenkin, että virta ei järjestä alkuperäistä listaa, vaan vain virrassa olevat alkiot ovat järjestyksessä.
Mikäli ohjelmoija haluaa järjestää alkuperäisen listan, on Collections-luokan metodi sort hyödyllinen.
Saat valmiin luokan Ihminen. Ihmisellä on nimi- ja palkkatiedot. Muokkaa Ihminen-luokasta Comparable-rajapinnan toteuttava niin, että compareTo-metodi lajittelee ihmiset palkan mukaan järjestykseen isoimmasta palkasta pienimpään.
Saat valmiin luokan Opiskelija. Opiskelijalla on nimi. Muokkaa Opiskelija-luokasta Comparable-rajapinnan toteuttava niin, että compareTo-metodi lajittelee opiskelijat nimen mukaan aakkosjärjestykseen.
Vinkki: Opiskelijan nimi on String, ja String-luokka on itsessään Comparable. Voit hyödyntää String-luokan compareTo-metodia Opiskelija-luokan metodia toteuttaessasi. String.compareTo kohtelee kirjaimia eriarvoisesti kirjainkoon mukaan, ja tätä varten String-luokalla on myös metodi compareToIgnoreCase joka nimensä mukaisesti jättää kirjainkoon huomioimatta. Voit käyttää opiskelijoiden järjestämiseen kumpaa näistä haluat.
Luokka voi toteuttaa useamman rajapinnan. Useamman rajapinnan toteuttaminen tapahtuu erottamalla toteutettavat rajapinnat toisistaan pilkuilla (public class ... implements RajapintaEka, RajapintaToka ...). Toteuttaessamme useampaa rajapintaa, tulee meidän toteuttaa kaikki rajapintojen vaatimat metodit.
Oletetaan, että käytössämme on seuraava rajapinta Tunnistettava.
public interface Tunnistettava {
String getTunnus();
}
Haluamme luoda Henkilön, joka on sekä tunnustettava että järjestettävä. Tämä onnistuu toteutttamalla molemmat rajapinnat. Alla esimerkki.
public class Henkilo implements Tunnistettava, Comparable<Henkilo> {
private String nimi;
private String henkilotunnus;
public Henkilo(String nimi, String henkilotunnus) {
this.nimi = nimi;
this.henkilotunnus = henkilotunnus;
}
public String getNimi() {
return this.nimi;
}
public String getHenkilotunnus() {
return this.henkilotunnus;
}
@Override
public String getTunnus() {
return getHenkilotunnus();
}
@Override
public int compareTo(Henkilo toinen) {
return this.getTunnus().compareTo(toinen.getTunnus());
}
}
Järjestämismetodi lambda-lausekkeena
Oletetaan, että käytössämme on seuraava luokka Henkilo.
public class Henkilo {
private int syntymavuosi;
private String nimi;
public Henkilo(int syntymavuosi, String nimi) {
this.syntymavuosi = syntymavuosi;
this.nimi = nimi;
}
public String getNimi() {
return nimi;
}
public int getSyntymavuosi() {
return syntymavuosi;
}
}
Sekä henkilöolioita listalla.
ArrayList<Henkilo> henkilot = new ArrayList<>();
henkilot.add(new Henkilo("Ada Lovelace", 1815));
henkilot.add(new Henkilo("Irma Wyman", 1928));
henkilot.add(new Henkilo("Grace Hopper", 1906));
henkilot.add(new Henkilo("Mary Coombs", 1929));
Haluamme järjestää listan ilman, että henkilo-olion tulee toteuttaa rajapinta Comparable.
Sekä luokan Collections metodille sort että virran metodille sorted voidaan antaa parametrina lambda-lauseke, joka määrittelee järjestämistoiminnallisuuden. Tarkemmin ottaen kummallekin metodille voidaan antaa Comparator-rajapinnan toteuttama olio, joka määrittelee halutun järjestyksen -- lambda-lausekkeen avulla luodaan tämä olio.
ArrayList<Henkilo> henkilot = new ArrayList<>();
henkilot.add(new Henkilo("Ada Lovelace", 1815));
henkilot.add(new Henkilo("Irma Wyman", 1928));
henkilot.add(new Henkilo("Grace Hopper", 1906));
henkilot.add(new Henkilo("Mary Coombs", 1929));
henkilot.stream().sorted((h1, h2) -> {
return h1.getSyntymavuosi() - h2.getSyntymavuosi();
}).forEach(h -> System.out.println(h.getNimi()));
System.out.println();
henkilot.stream().forEach(h -> System.out.println(h.getNimi()));
System.out.println();
Collections.sort(henkilot, (h1, h2) -> return h1.getSyntymavuosi() - h2.getSyntymavuosi());
henkilot.stream().forEach(h -> System.out.println(h.getNimi()));
Ada Lovelace Grace Hopper Irma Wyman Mary Coombs Ada Lovelace Irma Wyman Grace Hopper Mary Coombs Ada Lovelace Grace Hopper Irma Wyman Mary Coombs
Merkkijonoja vertailtaessa voimme käyttää String-luokan valmista compareTo-metodia. Metodi palauttaa sille annetun parametrina annetun merkkijonon sekä metodia kutsuvan merkkijonon järjestykstä kuvaavan kokonaisluvun.
ArrayList<Henkilo> henkilot = new ArrayList<>();
henkilot.add(new Henkilo("Ada Lovelace", 1815));
henkilot.add(new Henkilo("Irma Wyman", 1928));
henkilot.add(new Henkilo("Grace Hopper", 1906));
henkilot.add(new Henkilo("Mary Coombs", 1929));
henkilot.stream().sorted((h1, h2) -> {
return h1.getNimi().compareTo(h2.getNimi());
}).forEach(h -> System.out.println(h.getNimi()));
Ada Lovelace Grace Hopper Irma Wyman Mary Coombs
Käytetään jälleen edellisessä osassa käytettyä UNESCOn avointa dataa lukutaidosta. Data sisältää tilastot eri maiden arvioiduista tai raportoiduista lukutaidoista viimeisen kahden vuoden ajalta. Tehtäväpohjassa mukana oleva tiedosto lukutaito.csv sisältää arviot sekä yli 15-vuotiaiden naisten että yli 15-vuotiaiden miesten lukutaidosta. Tiedoston lukutaito.csv yksittäisen rivin muoto on seuraava: teema, ikäryhmä, sukupuoli, maa, vuosi, lukutaitoprosentti. Alla on esimerkkinä tiedoston viisi ensimmäistä riviä.
Adult literacy rate, population 15+ years, female (%),United Republic of Tanzania,2015,76.08978 Adult literacy rate, population 15+ years, female (%),Zimbabwe,2015,85.28513 Adult literacy rate, population 15+ years, male (%),Honduras,2014,87.39595 Adult literacy rate, population 15+ years, male (%),Honduras,2015,88.32135 Adult literacy rate, population 15+ years, male (%),Angola,2014,82.15105
Kirjoita ohjelma, joka lukee tiedoston lukutaito.csv ja tulostaa tiedoston sisällön pienimmästä lukutaidosta suurimpaan. Tulostus tulee muotoilla seuraavan esimerkin näyttämään muotoon. Esimerkki näyttää tulostuksen ensimmäiset 5 odotettua riviä.
Niger (2015), female, 11.01572 Mali (2015), female, 22.19578 Guinea (2015), female, 22.87104 Afghanistan (2015), female, 23.87385 Central African Republic (2015), female, 24.35549
Tehtävä on kahden pisteen arvoinen.
Vinkki! Merkkijonon saa pilkottua taulukoksi pilkun kohdalta seuraavalla tavalla.
String mjono = "Adult literacy rate, population 15+ years, female (%),Zimbabwe,2015,85.28513";
String[] palat = mjono.split(",");
// nyt palat[0] sisältää "Adult literacy rate"
// palat[1] sisältää " population 15+ years"
// jne.
Tee ohjelma, joka lukee käyttäjältä kirjoja ja niiden minimikohdeikiä. Minimikohdeiällä tarkoitetaan pienintä ikää vuosina, jolle kyseistä kirjaa suositellaan.
Ohjelma kysyy uusia kirjoja kunnes käyttäjä syöttää tyhjän merkkijonon kirjan nimen kohdalla (eli painaa rivinvaihtoa). Täämän jälkeen ohjelma tulostaa syötettyjen kirjojen lukumäärän sekä kirjat.
Kirjojen lukeminen ja tulostaminen
Toteuta ensin kirjojen lukeminen ja niiden listaaminen. Tässä vaiheessa kirjojen järjestyksellä ei ole vielä väliä.
Syötä kirjan nimi, tyhjä lopettaa: Soiva tuutulaulukirja
Syötä kirjan pienin kohdeikä: 0
Syötä kirjan nimi, tyhjä lopettaa: Kurkkaa kulkuneuvot
Syötä kirjan pienin kohdeikä: 0
Syötä kirjan nimi, tyhjä lopettaa: Lunta tupaan
Syötä kirjan pienin kohdeikä: 12
Syötä kirjan nimi, tyhjä lopettaa: Litmanen 10
Syötä kirjan pienin kohdeikä: 10
Syötä kirjan nimi, tyhjä lopettaa:
Yhteensä 4 kirjaa.
Kirjat:
Soiva tuutulaulukirja (0 vuotiaille ja vanhemmille)
Kurkkaa kulkuneuvot (0 vuotiaille ja vanhemmille)
Lunta tupaan (12 vuotiaille ja vanhemmille)
Litmanen 10 (10 vuotiaille ja vanhemmille)
Kirjojen järjestäminen kohdeiän perusteella
Täydennä toteuttamaasi ohjelmaa siten, että kirjat järjestetään tulostuksen yhteydessä kohdeiän perusteella. Jos kahdella kirjalla on sama kohdeikä, näiden kahden kirjan keskinäinen järjestys saa olla mielivaltainen.
Syötä kirjan nimi, tyhjä lopettaa: Soiva tuutulaulukirja
Syötä kirjan pienin kohdeikä: 0
Syötä kirjan nimi, tyhjä lopettaa: Kurkkaa kulkuneuvot
Syötä kirjan pienin kohdeikä: 0
Syötä kirjan nimi, tyhjä lopettaa: Lunta tupaan
Syötä kirjan pienin kohdeikä: 12
Syötä kirjan nimi, tyhjä lopettaa: Litmanen 10
Syötä kirjan pienin kohdeikä: 10
Syötä kirjan nimi, tyhjä lopettaa:
Yhteensä 4 kirjaa.
Kirjat:
Soiva tuutulaulukirja (0 vuotiaille ja vanhemmille)
Kurkkaa kulkuneuvot (0 vuotiaille ja vanhemmille)
Litmanen 10 (10 vuotiaille ja vanhemmille)
Lunta tupaan (12 vuotiaille ja vanhemmille)
Kirjojen järjestäminen kohdeiän ja nimen perusteella
Täydennä edellistä ohjelmaasi siten, että saman kohdeiän kirjat tulostetaan aakkosjärjestyksessä.
Syötä kirjan nimi, tyhjä lopettaa: Soiva tuutulaulukirja
Syötä kirjan pienin kohdeikä: 0
Syötä kirjan nimi, tyhjä lopettaa: Kurkkaa kulkuneuvot
Syötä kirjan pienin kohdeikä: 0
Syötä kirjan nimi, tyhjä lopettaa: Lunta tupaan
Syötä kirjan pienin kohdeikä: 12
Syötä kirjan nimi, tyhjä lopettaa: Litmanen 10
Syötä kirjan pienin kohdeikä: 10
Syötä kirjan nimi, tyhjä lopettaa:
Yhteensä 4 kirjaa.
Kirjat:
Kurkkaa kulkuneuvot (0 vuotiaille ja vanhemmille)
Soiva tuutulaulukirja (0 vuotiaille ja vanhemmille)
Litmanen 10 (10 vuotiaille ja vanhemmille)
Lunta tupaan (12 vuotiaille ja vanhemmille)
Binäärihaku (puolitushaku)
Kun tieto on järjestyksessä, hakeminen voidaan toteuttaa paljon peräkkäishakua tehokkaammin.
Tutkitaan binäärihaun ideaa seuraavan järjestyksessä olevan taulukon avulla.
// indeksit 0 1 2 3 4 5 6 7 8 9 10 // luvut -7 -3 3 7 11 15 17 21 24 28 30
Oletetaan että haluamme löytää luvun 17 indeksin. Hyödynnetään tietoa siitä että taulukon arvot ovat järjestyksessä. Sen sijaan, että kävisimme taulukon lukuja läpi taulukon alusta lähtien, tarkastelemme arvoa taulukon puolivälissä. Taulukon puolivälissä olevan alkion indeksi on isoin indeksi 10 jaettuna kahdella eli 5. Keskimmäinen alkio on merkattu seuraavaan tähdillä:
// indeksit 0 1 2 3 4 *5* 6 7 8 9 10 // luvut -7 -3 3 7 11 15 17 21 24 28 30
Puolessa välissä on luku 15, joka ei ollut hakemamme luku (eli luku 17). Koska taulukko on järjestyksessä (tässä suuruusjärjestyksessä), ei etsitty luku voi missään tapauksessa olla luvun 15 vasemmalla puolella. Voimme siis päätellä että kaikki indeksit, jotka ovat pienempiä tai yhtäsuuria kuin 5, eivät missään nimessä sisällä hakemaamme arvoa.
Alue, jolta etsimme haettavaa lukua voidaan nyt rajata lukuihin, jotka sijaitsevat indeksin 5 oikealla puolella, eli indekseihin välillä [6, 10] (6, 7, 8, 9, 10). Seuraavassa on merkitty harmaalla se osa taulukkoa jossa etsitty ei voi olla:
// indeksit 0 1 2 3 4 5 6 7 8 9 10 // luvut -7 -3 3 7 11 15 17 21 24 28 30
Tutkitaan seuraavaksi jäljellä olevan etsintäalueen, eli indeksien 6-10 keskimmäistä indeksiä. Keskimmäinen indeksi löytyy laskemalla etsintäalueen pienimmän ja suurimman indeksin summan ja jakamalla se kahdella, eli (6+10)/2 = 16/2 = 8. Indeksi 8 on merkitty alle tähdillä.
// indeksit 0 1 2 3 4 5 6 7 *8* 9 10 // luvut -7 -3 3 7 11 15 17 21 24 28 30
Indeksissä 8 oleva luku on 24, joka ei ollut hakemamme luku. Koska luvut taulukossa ovat suuruusjärjestyksessä, ei etsittävä luku voi missään nimessä olla luvun 24 oikealla puolella. Voimme siis päätellä että kaikki indeksit, jotka ovat suurempia tai yhtäsuuria kuin 8, eivät missään nimessä sisällä hakemaamme arvoa. Etsintäalue rajautuu taas, harmaat alueet on käsitelty:
// indeksit 0 1 2 3 4 5 6 7 8 9 10 // luvut -7 -3 3 7 11 15 17 21 24 28 30
Etsintä jatkuu. Tutkitaan jäljellä olevan etsintäalueen, eli indeksien 6-7, keskimmäistä indeksiä. Keskimmäinen indeksi löytyy taas ottamalla etsintäalueen pienimmän ja suurimman indeksin summa ja jakamalla se kahdella, eli (6+7)/2 = 6,5, joka pyöristyy alaspäin luvuksi 6. Kohta on merkitty alle tähdillä.
// indeksit 0 1 2 3 4 5 *6* 7 8 9 10 // luvut -7 -3 3 7 11 15 17 21 24 28 30
Indeksissä 6 on luku 17, joka on sama kuin hakemamme luku. Voimme lopettaa haun ja ilmoittaa että etsitty luku on taulukossa. Jos luku ei olisi ollut taulukossa -- esimerkiksi jos haettava luku olisi ollut 16, etsintäalue olisi jäänyt lopulta tyhjäksi.
// indeksit 0 1 2 3 4 5 *6* 7 8 9 10 // luvut -7 -3 3 7 11 15 17 21 24 28 30
Jotta binäärihaun idea tulee sinulle tutuksi, simuloi kynällä ja paperilla miten binäärihaku toimii kun taulukkona on alla oleva taulukko ja haet lukua 33. Kokeile tämän jälkeen binäärihakua vielä siten, että etsit lukua 1.
// indeksit 0 1 2 3 4 5 6 7 8 9 10 11 12 13 // luvut -5 -2 3 5 8 11 14 20 22 26 29 33 38 41
Peräkkäishaun pahimmassa tapauksessa -- eli kun haettavaa ei löydy -- käydään kaikki taulukon arvot läpi. Miljoona alkiota sisältävässä taulukossa tämä tarkoittaa miljoonan alkion tarkastelua.
Binäärihaun pahimmassa tapauksessa tutkittava alue jaetaan kahteen osaan kunnes osan koko on yksi. Alkioita tarkastellaan huomattavasti vähemmän kuin peräkkäishaussa. Tarkastellaan tätä hieman tarkemmin.
Taulukko, jossa on 16 alkiota, voidaan jakaa kahteen osaan korkeintaan 4 kertaa, eli 16 -> 8 -> 4 -> 2 -> 1.
Toisaalta, taulukko, jossa on miljoona alkiota voidaan jakaa kahteen osaan korkeintaa 20 kertaa, eli 1000000 -> 500000 -> 250000 -> 125000 -> 62500 -> 31250 -> 15625 -> ~7813 -> ~3907 -> 1954 -> ~977 -> ~489 -> ~245 -> ~123 -> ~62 -> ~31 -> ~16 -> ~8 -> ~4 -> ~2 -> ~1.
Mitä tämä tarkoittaa? Binäärihakua käyttäen miljoona alkiota sisältävästä taulukosta tulee pahimmassa tapauksessa tarkastella noin kahtakymmentä alkiota, kun peräkkäishaussa tarkasteltavia alkioita on miljoona.
Koska haettavien alkioiden määrä puolittuu binäärihaussa jokaisen tarkastelun yhteydessä, voi binäärihaun tehokkuutta tarkastella kaksikantaisen logaritmin avulla. Kaksikantainen logaritmi (log2) annetusta luvusta kertoo kuinka monta kertaa luku voidaan puolittaa. Esimerkiksi kaksikantainen logaritmi luvusta 16777216 (log2 16777216) on 24, ja luvun 4294967296 kaksikantainen logaritmi, (log2 4294967296) on 32. Tämä tarkoittaa että 4294967296 eri arvoa sisältävästä järjestyksessä olevasta taulukosta hakeminen vaatisi binäärihaulta korkeintaan 32 eri alkion tarkastamista.
Collections-luokkakirjasto tarjoaa valmiiksi toteutetun binäärihakualgoritmin. Kerholainen-luokkamme vertaa pituuksia compareTo()-metodissaan, eli listasta etsiessä etsisimme samanpituista kerholaista.
List<Kerholainen> kerholaiset = new ArrayList<>();
kerholaiset.add(new Kerholainen("mikael", 182));
kerholaiset.add(new Kerholainen("matti", 187));
kerholaiset.add(new Kerholainen("joel", 184));
Collections.sort(kerholaiset);
Kerholainen haettava = new Kerholainen("Nimi", 180);
int indeksi = Collections.binarySearch(kerholaiset, haettava);
if (indeksi >= 0) {
System.out.println("180 senttiä pitkä löytyi indeksistä " + indeksi);
System.out.println("nimi: " + kerholaiset.get(indeksi).getNimi());
}
haettava = new Kerholainen("Nimi", 187);
int indeksi = Collections.binarySearch(kerholaiset, haettava);
if (indeksi >= 0) {
System.out.println("187 senttiä pitkä löytyi indeksistä " + indeksi);
System.out.println("nimi: " + kerholaiset.get(indeksi).getNimi());
}
187 senttiä pitkä löytyi indeksistä 2 nimi: matti
Esimerkissä kutsuttiin myös metodia Collections.sort() sillä binäärihakualgoritmi ei toimi jos käsiteltävä lista ei ole valmiiksi järjestyksessä.
Huom! Älä kuitenkaan toteuta mahdolliseen ohjelmaasi hakutoiminnallisuutta siten, että lista järjestetään jokaisen haun yhteydessä -- järjestäminen itsessään on hitaampaa kuin peräkkäishaku eli listan läpikäynti alkio kerrallaan. Binäärihaun hyödyt tulevatkin esille vasta useamman samaan taulukkoon tai listaan tehdyn haun jälkeen.
Järjestämisen ja hakemisen lisäksi luokkakirjaston Collections avulla voi etsiä esimerkiksi minimi- (min-metodi) tai maksimialkioita (max-metodi), vaikkapa kääntää listan (reverse-metodi).
List<Kerholainen> kerholaiset = new ArrayList<>();
kerholaiset.add(new Kerholainen("mikael", 182));
kerholaiset.add(new Kerholainen("matti", 187));
kerholaiset.add(new Kerholainen("ada", 184));
kerholaiset.stream().forEach(k -> System.out.println(k));
Collections.sort(kerholaiset);
Collections.reverse(kerholaiset);
System.out.println();
kerholaiset.stream().forEach(k -> System.out.println(k));
System.out.println();
System.out.println(Collections.max(kerholaiset));
mikael (182) matti (187) ada (184) matti (187) ada (184) mikael (182) matti (187)
Harjoitellaan taas ohjelman rakenteen omatoimista suunnittelua. Käyttöliittymän ulkomuoto ja vaadittu toiminnallisuus on määritelty ennalta, rakenteen saat toteuttaa vapaasti. Tehtävä on neljän yksittäisen tehtäväpisteen arvoinen.
Huom: jotta testit toimisivat, ohjelmasi saa luoda vain yhden käyttäjän syötteen lukemiseen käytettävän Scanner-olion.
Mäkihyppy on suomalaisille erittäin rakas laji, jossa pyritään hyppäämään hyppyrimäestä mahdollisimman pitkälle mahdollisimman tyylikkäästi. Tässä tehtävässä toteutetaan simulaattori mäkihyppykilpailulle.
Simulaattori kysyy ensin käyttäjältä hyppääjien nimiä. Kun käyttäjä antaa tyhjän merkkijonon (eli painaa enteriä) hyppääjän nimeksi siirrytään hyppyvaiheeseen. Hyppyvaiheessa hyppääjät hyppäävät yksitellen käänteisessä pistejärjestyksessä. Hyppääjä, jolla on vähiten pisteitä kerättynä hyppää aina kierroksen ensimmäisenä, toiseksi vähiten pisteitä omaava toisena jne, ..., eniten pisteitä kerännyt viimeisenä.
Hyppääjän yhteispisteet lasketaan yksittäisten hyppyjen pisteiden summana. Yksittäisen hypyn pisteytys lasketaan hypyn pituudesta (käytä satunnaista kokonaisluku väliltä 60-120) ja tuomariäänistä. Jokaista hyppyä kohden annetaan 5 tuomariääntä (satunnainen luku väliltä 10-20). Tuomariääniä laskettaessa otetaan huomioon vain kolme keskimmäistä ääntä: pienintä ja suurinta ääntä ei oteta huomioon. Esimerkiksi jos Mikael hyppää 61 metriä ja saa tuomariäänet 11, 12, 13, 14 ja 15, on hänen hyppynsä yhteispisteet 100.
Satunnaisen luvun luomiseen voi käyttää Javan valmista luokkaa Random. Sen parametrillinen metodi nextInt antaa satunnaisen luvun väliltä 0...luku-1. Satunnaisen luvun väliltä 10-20 saa arvottua seuraavasti:
Random arpoja = new Random();
int luku = arpoja.nextInt(11) + 10;
Kierroksia hypätään niin monta kuin ohjelman käyttäjä haluaa. Kun käyttäjä haluaa lopettaa tulostetaan lopuksi kilpailun lopputulokset. Lopputuloksissa tulostetaan hyppääjät, hyppääjien yhteispisteet ja hyppääjien hyppäämien hyppyjen pituudet. Lopputulokset on järjestetty hyppääjien yhteispisteiden mukaan siten, että eniten pisteitä kerännyt on ensimmäinen.
Tehtävän tekemisessä on hyötyä muun muassa metodeista Collections.sort ja Collections.reverse. Kannattaa aluksi hahmotella minkälaisia luokkia ja olioita ohjelmassa voisi olla. On myös hyvä pyrkiä tilanteeseen, jossa käyttöliittymäluokka on ainut luokka joka kutsuu tulostuskomentoa.
Kumpulan mäkiviikot
Syötä kilpailun osallistujat yksi kerrallaan, tyhjällä merkkijonolla siirtyy hyppyvaiheeseen.
Osallistujan nimi: Mikael
Osallistujan nimi: Mika
Osallistujan nimi:
Kilpailu alkaa!
Kirjoita "hyppaa" niin hypätään, muuten lopetetaan: hyppaa
1. kierros
Hyppyjärjestys:
1. Mikael (0 pistettä)
2. Mika (0 pistettä)
Kierroksen 1 tulokset
Mikael
pituus: 95
tuomaripisteet: [15, 11, 10, 14, 14]
Mika
pituus: 112
tuomaripisteet: [14, 12, 18, 18, 17]
Kirjoita "hyppaa" niin hypätään, muuten lopetetaan: hyppaa
2. kierros
Hyppyjärjestys:
1. Mikael (134 pistettä)
2. Mika (161 pistettä)
Kierroksen 2 tulokset
Mikael
pituus: 96
tuomaripisteet: [20, 19, 15, 13, 18]
Mika
pituus: 61
tuomaripisteet: [12, 11, 15, 17, 11]
Kirjoita "hyppaa" niin hypätään, muuten lopetetaan: hyppaa
3. kierros
Hyppyjärjestys:
1. Mika (260 pistettä)
2. Mikael (282 pistettä)
Kierroksen 3 tulokset
Mika
pituus: 88
tuomaripisteet: [11, 19, 13, 10, 15]
Mikael
pituus: 63
tuomaripisteet: [12, 19, 19, 12, 12]
Kirjoita "hyppaa" niin hypätään, muuten lopetetaan: lopeta
Kiitos!
Kilpailun lopputulokset:
Sija Nimi
1 Mikael (388 pistettä)
hyppyjen pituudet: 95 m, 96 m, 63 m
2 Mika (387 pistettä)
hyppyjen pituudet: 112 m, 61 m, 88 m
Huom1: Testien kannalta on oleellista että käyttöliittymä toimii kuten yllä kuvattu, esim. rivien alussa olevien välilyöntien määrän on oltava oikea. Rivien alussa oleva tyhjä pitää tehdä välilyönneillä, testit eivät toimi jos tyhjä on tehty tabulaattoreilla. Ohjelman tulostamat tekstit kannattaneekin copypasteta ohjelmakoodiin joko tehtävänannosta tai testien virheilmoituksista.
Huom2: älä käytä luokkein nimissä skandeja, ne saattavat aiheuttaa ongelmia testeihin!
Ohjelman tulee käynnistyä kun tehtäväpohjassa oleva main-metodi suoritetaan, muistutuksena vieltä, että tehtävässä saa luoda vain yhden Scanner-olion.