Pakolliset tehtävät on merkitty harmalla taustavärillä. Pakollisuus tarkoittaa oikeastaan hyvin voimakasta suositusta tehtävän tekemiseen. Jos pakollisia jää tekemättä, on suuri riski, että seuraavalla viikolla esitellään asioita jotka oletetetaan jo osatuiksi ja pakollisten tehtävien kautta harjoitelluiksi.
Tässä tehtäväsarjassa tehtävän ohjelman käytössä on aineisto erään kurssin opiskelijoiden pistemääristä:
int[] pisteet = {41, 44, 25, 31, 52, 48, 40, 46, 38, 39,
34, 32, 36, 55, 59, 42, 57, 38, 24, 50};
Tämä tehtäväsarja on kokonaisuus, joten tee tehtävien metodit saman ohjelman sisään.
Ohjelmoi metodi laskeArvosana,
joka laskee arvosanan sille annetun pistemäärän perusteella.
| pistemäärä | arvosana |
|---|---|
| 0–29 | 0 |
| 30–34 | 1 |
| 35–39 | 2 |
| 40–44 | 3 |
| 45–49 | 4 |
| 50–60 | 5 |
Ohjelmamme runko on tällä hetkellä seuraava:
private static int laskeArvosana(int pisteet) {
// kirjoita koodia tähän
}
public static void main(String[] args) {
int[] pisteet = {41, 44, 25, 31, 52, 48, 40, 46, 38, 39,
34, 32, 36, 55, 59, 42, 57, 38, 24, 50};
for (int pistemaara : pisteet) {
System.out.println("pistemäärä " + pistemaara +
"antaa arvosanan " + laskeArvosana(pistemaara));
}
}
Ohjelman tulostuksen tulisi olla seuraava:
pistemäärä 41 antaa arvosanan 3 pistemäärä 44 antaa arvosanan 3 pistemäärä 25 antaa arvosanan 0 pistemäärä 31 antaa arvosanan 1 (paljon rivejä välissä) pistemäärä 50 antaa arvosanan 5
Muuta edellistä ohjelmaa niin, että eri arvosanojen lukumäärät
tallennetaan taulukkoon arvosanat.
Ideana on, että taulukossa arvosanat on 6 kohtaa,
yksi jokaiselle arvosanalle.
Esimerkiksi arvosanat[3] kertoo,
kuinka moni opiskelija on saanut arvosanan 3.
Ohjelmaan tulee kaksi uutta metodia:
Metodille selvitaArvosanat annetaan
opiskelijoiden pistemäärät taulukossa ja metodi
palauttaa toisen taulukon, joka sisältää
arvosanojen lukumäärät.
Metodin tulostaArvosanat toteutus on annettu.
Ota tästä mallia ohjelman toteutukseen:
private static int[] selvitaArvosanat(int[] pisteet) {
int[] arvosanat = new int[6];
// kirjoita koodia tähän
return arvosanat;
}
private static void tulostaArvosanat(int[] arvosanat) {
for (int i = 5; i >= 0; i--) {
System.out.println(i + ": " + arvosanat[i] + " kpl");
}
}
public static void main(String[] args) {
int[] pisteet = {41, 44, 25, 31, 52, 48, 40, 46, 38, 39,
34, 32, 36, 55, 59, 42, 57, 38, 24, 50};
int[] arvosanat = selvitaArvosanat(pisteet);
tulostaArvosanat(arvosanat);
}
Ohjelman tulostuksen tulisi olla seuraava:
5: 5 kpl 4: 2 kpl 3: 4 kpl 2: 4 kpl 1: 3 kpl 0: 2 kpl
Liitä ohjelmaan mukaan edellisen viikon metodi tulostaTahtia,
joka tulostaa annetun määrän tähtiä.
Nyt ohjelman tulostuksen tulisi olla seuraava:
5: ***** 4: ** 3: **** 2: **** 1: *** 0: **
Liitä ohjelmaan mukaan metodi hyvaksymisprosentti,
joka laskee parametrina annetun arvosanajakauman perusteella
hyväksymisprosentin (kuinka moni sai arvosanan 1–5).
Metodin runko on seuraava:
private static double hyvaksymisprosentti(int[] arvosanat) {
// kirjoita koodia tähän
}
Pääohjelman lopullinen muoto on seuraava:
public static void main(String[] args) {
int[] pisteet = {41, 44, 25, 31, 52, 48, 40, 46, 38, 39,
34, 32, 36, 55, 59, 42, 57, 38, 24, 50};
int[] arvosanat = selvitaArvosanat(pisteet);
tulostaArvosanat(arvosanat);
System.out.println("Hyväksymisprosentti: " +
hyvaksymisprosentti(arvosanat) + " %");
}
Nyt ohjelman tulostuksen tulisi olla seuraava:
5: ***** 4: ** 3: **** 2: **** 1: *** 0: ** Hyväksymisprosentti: 90.0 %
Tässä tapauksessa opiskelijoita oli kaikkiaan 20 ja arvosanan 1–5 sai 18 opiskelijaa, joten hyväksymisprosentti oli (18/20)*100 = 90.
Huomaa miten tässä monimutkainen ongelma ratkottiin pienempinä osaongelmina, jotka saatettiin yksi kerrallaan toimintakuntoon. Ohjelmointiongelmia kannattaa useimmiten lähestyä juuri tähän tyyliin!
Tämä tehtäväsarja on kokonaisuus, joten tee tehtävien metodit saman ohjelman sisään.
Tee metodi pienimmanIndeksi, joka
palauttaa taulukon pienimmän luvun indeksin
(eli luvun kohdan taulukossa).
Metodin runko on seuraava:
private static int pienimmanIndeksi(int[] taulukko) {
// kirjoita koodia tähän
}
Seuraava koodi esittelee metodin toimintaa:
// indeksit: 0 1 2 3 4
int[] luvut = {3, 2, 5, 4, 8};
System.out.println("Pienimmän indeksi: " + pienimmanIndeksi(luvut));
Pienimmän indeksi: 1
Taulukon pienin luku on 2, ja sen indeksi on 1. Muistathan, että taulukon numerointi alkaa 0:sta.
Tee metodi pienimmanIndeksiAlkaen,
joka toimii samalla tavalla kuin edellisen tehtävän metodi
mutta ottaa huomioon vain taulukon loppuosan.
Metodille annetaan taulukon lisäksi indeksi,
josta lähtien pienintä lukua etsitään.
Metodin runko on seuraava:
private static int pienimmanIndeksiAlkaen(int[] taulukko, int indeksi) {
// kirjoita koodia tähän
}
Seuraava koodi esittelee metodin toimintaa:
// indeksit: 0 1 2 3 4
int[] luvut = {3, 2, 5, 4, 8};
System.out.println(pienimmanIndeksiAlkaen(luvut, 1));
System.out.println(pienimmanIndeksiAlkaen(luvut, 2));
System.out.println(pienimmanIndeksiAlkaen(luvut, 4));
1 3 4
Esimerkissä ensimmäinen metodikutsu etsii pienimmän luvun indeksistä 1 aloittaen. Tällöin pienin luku on 2, jonka indeksi on 1. Vastaavasti toinen metodikutsu etsii pienimmän luvun indeksistä 2 aloittaen. Tällöin pienin luku on 4, jonka indeksi on 3.
Usein on tarvetta tarkistaa, mitä lukuja taulukossa on.
Tehdään sitä varten metodi tulostaTaulukko,
joka tulostaa taulukon luvut.
Metodin runko on seuraava:
private static void tulostaTaulukko(int[] taulukko) {
// kirjoita koodia tähän
}
Seuraava koodi esittelee metodin toimintaa:
int[] luvut = {3, 2, 5, 4, 8};
tulostaTaulukko(luvut);
3, 2, 5, 4, 8
Tee metodi vaihda,
jolle annetaan taulukko ja kaksi sen indeksiä.
Metodi vaihtaa indekseissä olevat luvut keskenään.
Metodin runko on seuraava:
private static void vaihda(int[] taulukko, int indeksi1, int indeksi2) {
// kirjoita koodia tähän
}
Seuraava koodi esittelee metodin toimintaa:
int[] luvut = {3, 2, 5, 4, 8};
tulostaTaulukko(luvut);
vaihda(luvut, 1, 0);
tulostaTaulukko(luvut);
vaihda(luvut, 0, 3);
tulostaTaulukko(luvut);
3, 2, 5, 4, 8 2, 3, 5, 4, 8 4, 3, 5, 2, 8
Nyt koossa on joukko hyödyllisiä metodeja, joiden avulla voimme toteuttaa järjestämisalgoritmin nimeltä vaihtojärjestäminen.
Vaihtojärjestämisen idea on seuraava:
Toisin sanoen:
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:
private static void jarjesta(int[] taulukko) {
}
Testaa metodin toimintaa ainakin seuraavalla esimerkillä:
int[] luvut = {8, 3, 7, 9, 1, 2, 4};
jarjesta(luvut);
Ohjelman tulosteen tulisi olla seuraavanlainen:
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
Huomaa, miten taulukko tulee pikkuhiljaa järjestykseen alkaen alusta ja edeten loppua kohti.
Tee ohjelma, joka heittää noppaa ja ilmoittaa silmäluvun.
Ohjelman mahdollisia tulostuksia ovat esimerkiksi seuraavat:
Silmäluku: 3
Silmäluku: 5
Tee ohjelma, joka heittää kolikkoa ja ilmoittaa tuloksen (kruuna tai klaava).
Ohjelman mahdolliset tulostukset ovat seuraavat:
Tulos: kruuna
Tulos: klaava
Tee ohjelma, joka arpoo koiralle nimen taulukosta.
Taulukko voisi olla esimerkiksi seuraava:
String [] koirat = {"Turre", "Pluto", "Ärjy", "Milou", "Peni"};
Tällöin ohjelman mahdollisia tulostuksia ovat mm. seuraavat:
Koiran nimi: Pluto
Koiran nimi: Milou
Tee ohjelma, joka arpoo käyttäjälle salasanan. Salasana muodostuu merkeistä a-z ja siinä on 8 merkkiä.
Ohjelman tulostuksia ovat esimerkiksi seuraavat:
Salasana: zitbfsnt
Salasana: wlprcusq
Tee ohjelma, joka sekoittaa taulukon sisällön. Sovella ohjelmassa satunnaisuutta haluamallasi tavalla.
Ohjelman runko on seuraava:
int[] luvut = {1, 2, 3, 4, 5, 6, 7, 8};
sekoitaTaulukko(luvut);
tulostaTaulukko(luvut);
Ohjelman tulostuksia ovat esimerkiksi seuraavat:
7, 2, 3, 5, 1, 8, 4, 6
1, 5, 6, 2, 8, 7, 3, 4
Tee ohjelma, joka kysyy käyttäjältä sanoja,
kunnes käyttäjä antaa tyhjän merkkijonon.
Sitten ohjelma tulostaa käyttäjän antamat
sanat uudestaan.
Käytä ohjelmassa ArrayList-rakennetta,
joka määritellään seuraavasti:
ArrayList<String> sanat = new ArrayList<String>();
Anna sana: Mozart Anna sana: Schubert Anna sana: Bach Anna sana: Sibelius Anna sana: Liszt Anna sana: Annoit seuraavat sanat: Mozart Schubert Bach Sibelius Liszt
Tee edellistä tehtävää vastaava ohjelma, jossa sanat tulostetaan päinvastaisessa järjestyksessä.
Anna sana: Mozart Anna sana: Schubert Anna sana: Bach Anna sana: Sibelius Anna sana: Liszt Anna sana: Annoit seuraavat sanat: Liszt Sibelius Bach Schubert Mozart
Tee edellistä tehtävää vastaava ohjelma, jossa sanat tulostetaan aakkosjärjestyksessä.
Anna sana: Mozart Anna sana: Schubert Anna sana: Bach Anna sana: Sibelius Anna sana: Liszt Anna sana: Annoit seuraavat sanat: Bach Liszt Mozart Schubert Sibelius
Tee ohjelma, joka kysyy käyttäjältä sanoja,
kunnes käyttäjä antaa saman sanan uudestaan.
Käytä ohjelmassa ArrayList-rakennetta,
joka määritellään seuraavasti:
ArrayList<String> sanat = new ArrayList<String>();
Viikolla 2 tämän tehtävän ratkaiseminen
oli työn ja tuskan takana.
ArrayList-rakenne
muuttaa tilanteen täydellisesti.
Anna sana: porkkana Anna sana: selleri Anna sana: nauris Anna sana: lanttu Anna sana: selleri Annoit saman sanan uudestaan!
Tee ohjelma, joka arpoo viikon lottonumerot.
Lottonumerot ovat väliltä 1–39 ja
niitä arvotaan 7.
Käytä ohjelmassa ArrayList-rakennetta,
joka määritellään seuraavasti:
ArrayList<Integer> numerot = new ArrayList<Integer>();
Ohjelman mahdollisia tulostuksia ovat seuraavat:
Lottonumerot: 3 5 10 14 15 27 37
Lottonumerot: 2 9 11 18 23 32 34
Tämä tehtävä toimii johdatuksena binäärihaun ideaan. Tavoitteena on tehdä tekoäly, joka arvaa käyttäjän valitseman luvun. Tekoäly olettaa, että luku on välillä 1...n, missä ohjelma kysyy aluksi käyttäjältä luvun n. Tekoäly kysyy käyttäjältä kysymyksiä muotoa "Onko lukusi suurempi kuin X?" ja päättelee oikean luvun käyttäjän vastausten perusteella.
Tekoäly saa selville nopeasti käyttäjän luvun, jos se pitää muistissa pienintä ja suurinta mahdollista lukua. Tekoäly kysyy aina, onko käyttäjän luku suurempi kuin näiden lukujen keskiarvo, jolloin joka kysymyksen jälkeen mahdollisten lukujen määrä puolittuu. Lopulta pienin ja suurin luku ovat samat, jolloin käyttäjän luku on paljastunut.
Seuraavassa esimerkissä käyttäjä valitsee luvun 44:
Anna suurin mahdollinen luku: 100 Valitse jokin luku väliltä 1...100. Esitän sinulle seuraavaksi sarjan kysymyksiä. Vastaa niihin rehellisesti. Onko lukusi suurempi kuin 50? (k/e) e Onko lukusi suurempi kuin 25? (k/e) k Onko lukusi suurempi kuin 38? (k/e) k Onko lukusi suurempi kuin 44? (k/e) e Onko lukusi suurempi kuin 41? (k/e) k Onko lukusi suurempi kuin 43? (k/e) k Valitsemasi luku on 44.
Yllä olevassa esimerkissä mahdollinen lukualue on aluksi 1...100. Kun käyttäjä kertoo, että luku ei ole yli 50, mahdollinen lukualue on 1...50. Kun käyttäjä kertoo, että luku on yli 25, mahdollinen lukualue on 26...50. Samanlainen päättely jatkuu, kunnes saavutaan lukuun 44.
Puolitus- eli binäärihaun mukaisesti tässä puolitetaan mahdollinen hakualue jokaisella
kysymyksellä, jolloin kysymyksiä tarvitaan vähän. Jopa lukuvälillä 1..1000000 pitäisi
kulua korkeintaan 20 kysymystä.
Kannattanee kirjoittaa varsinainen arvuuttelupeli omaan
static void arvausPeli(int ala, int yla)-metodiinsa.
Vihje:
Tee totuusarvon palauttava metodi, joka esittää käyttäjälle sopivan kysymyksen
ja lukee käyttäjän vastauksen. Jos käyttäjän
antama vastaus oli sopiva, niin metodi
palauttaa true ja muulloin false.
Viime viikolla teimme metodin, joka etsii, onko jokin luku taulukossa. Jos taulukko on iso, on etsiminen kohtuullisen aikaavievää. Taulukko on pahimmillaan käytävä läpi alusta loppuun.
Jos taulukon luvut on järjestetty suuruusjärjestykseen, voi etsimisen tehdä huomattavasti nopeammin.
Tarkastellaan seuraavaa taulukkoa:
// 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ä olemme etsimässä taulukosta lukua 17. Sen sijaan, että aletaan käydä taulukon lukuja läpi alusta asti, ollaan ovelia ja katsotaan, mikä luku taulukon puolessa välissä on. Taulukon puolen välin indeksi on isoin indeksi 10 jaettuna kahdella eli 5. Puoliväli on merkattu seuraavaan tähdellä:
*
// 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. Olemme etsimässä lukua 17, joten koska taulukon alkiot ovat suuruusjärjestyksessä, ei etsitty luku voi missään tapauksessa olla puolivälin vasemmalla puolella. Etsintäalue voidaan siis rajata taulukon ylempään puoliskoon. 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
Jäljelle jääneelle etsintäalueelle voidaan tehdä samalla tavalla. Mennään sen puoleen väliin ja katsotaan mikä alkio on puolessa välissä. Puoliväli löytyy ottamalla etsintäalueen pienimmän ja suurimman indeksin summa ja jakamalla se kahdella, eli (6+10)/2 = 16/2 = 8. Kohta on merkitty alle tähdellä.
*
// 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äalueen puolessa välissä on 24. Koska luvut taulukossa ovat suuruusjärjestyksessä, ei etsittävä voi missään tapauksessa olla etsintäalueen puolenvälin oikealla puolella. Etsintäalue rajautuu taas, eli 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 samalla tavalla. Etsintäalueen puoliväli löytyy ottamalla etsintäalueen pienimmän ja suurimman indeksin summa ja jakamalla se kahdella, eli (6+7)/2 = 6,5. Pyöristettynä alaspäin indeksi on 6. Kohta on merkitty alle tähdellä.
*
// 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 etsitty luku. Nyt voidaan lopettaa binäärihaku ja ilmoittaa, että etsitty luku on taulukossa. Jos luku ei olisi ollut taulukossa, etsintäalue olisi jäänyt lopulta tyhjäksi.
Simuloi kynällä ja paperilla, miten binäärihaku toimii seuraavissa tilanteissa:
Taulukkona on
// 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
Näytä, miten binäärihaku etenee, kun taulukosta etsitään seuraavia lukuja:
Jos teet seuraavan tehtävän, niin tätä ei ole pakko tehdä (saat silti merkinnän).
Tee metodi binaariHaku,
joka selvittää binäärihakua käyttäen,
onko parametrina annettu luku
parametrina annetussa järjestyksessä olevassa taulukossa.
Vihje: pidä muistissa etsintäalueen alku- ja loppukohdat. Alussa näiden arvot ovat:
int alku = 0; int loppu = taulukko.length-1;
Metodin toiminnan ydin voi olla esim seuraavanlainen:
while ( alku <= loppu ) {
int puolivali = (alku+loppu)/2;
if ( taulukko[puolivali] == etsittava )
return true;
// rajoita etsintäaluetta sopivasti
}
return false;
Ohjelman suoritus näyttää seuraavalta:
Taulukon luvut: -3, 2, 3, 4, 7, 8, 12 Anna haettava luku: 8 Luku 8 on taulukossa
Taulukon luvut: -3, 2, 3, 4, 7, 8, 12 Anna haettava luku: 99 Luku 99 ei ole taulukossa
Luonnollisen luvun n kertoma n! lasketaan kaavalla 1*2*3*...*n. Esimerkiksi 5! = 1*2*3*4*5 = 120. Lisäksi on sovittu, että 0! = 1. Seuraavassa on kertoman rekursiivinen määritelmä:
Toteuta rekursivinen metodi kertoma,
joka laskee kertoman edelliseen määritelmään perustuen.
public static void main(String[] args) {
System.out.print("Anna luku: ");
int luku = Integer.parseInt(lukija.nextLine());
System.out.print("Kertoma: " + kertoma(luku));
}
Ohjelman suoritus voi näyttää seuraavalta:
Anna luku: 5
Kertoma: 120
Toteuta rekursiivinen metodi kaanna, joka kääntää merkkijonon.
Vihje: Erota merkkijonosta ensimmäinen merkki ja loppuosa. Käännä loppuosa rekursiivisesti ja lisää sen perään ensimmäinen merkki.
public static void main(String[] args) {
System.out.print("Anna merkkijono: ");
String merkkijono = lukija.nextLine();
System.out.println("Väärinpäin: " + kaanna(merkkijono));
}
Anna merkkijono: esimerkki Väärinpäin: ikkremise
Viikolla 2 tehtiin ohjelma, joka tulostaa kaikki PIN-koodit, jotka muodostuvat numeroista 1–9 ja joiden pituus on 4 numeroa.
Ohjelman rajoituksena oli, että PIN-koodin pituus oli koodattu ohjelman sisään sisäkkäisten silmukoiden määränä. Rekursion avulla tämä rajoitus poistuu helposti.
Toteuta ohjelma, jolle annetaan PIN-koodin pituus ja suurin numero. Ohjelma tulostaa kaikki tällaiset PIN-koodit suuruusjärjestyksessä.
Koodin pituus: 3 Suurin numero: 2 111 112 121 122 211 212 221 222
Koodin pituus: 5 Suurin numero: 4 11111 11112 11113 11114 11121 ... 44444