Ohjelmointitehtävät, viikko 1

1. Kertoma

Luonnollisen luvun n kertoma lasketaan kaavalla 1 · 2 · 3 · ... · n. Esimerkiksi luvun 5 kertoma on 1 · 2 · 3 · 4 · 5 = 120. Lisäksi on sovittu, että luvun 0 kertoma on 1. Ratkaisun tulee toimia nopeasti myös isoilla syötteillä.

Tee ohjelma Kertoma.java, joka kysyy käyttäjältä luvun ja tulostaa sitten sen kertoman. Voit olettaa, että tuloksena oleva kertoma mahtuu int-tyyppiseen kokonaislukumuuttujaan.

Esimerkki

Anna luku: 5
Kertoma: 120

Esimerkissä punaisella väritetyt kohdat vastaavat käyttäjän kirjoittamaa tekstiä. Toteuta ohjelma tarkalleen esimerkin mukaisesti, koska ohjelma tarkistetaan automaattisesti.

HUOMMikäli testien suorituksessa on ongelmia, tarkistathan että sinulla on uusin TMC plugin asennettuna. Voit tarkastaa sen NetBeanssissa seuraavasti Help - Check for updates. Mikäli päivityksiä on saatavilla, asennathan ne.

2. Suuri kertoma

Javan tavalliset kokonaislukumuuttujat eivät voi sisältää kovin suuria lukuja. Esimerkiksi int-tyyppisen muuttujan suurin sallittu arvo on 2147483647 (reilut kaksi miljardia). Jos ohjelmassa on tarpeen käsitellä suuria kokonaislukuja, apuun tulee luokka BigInteger. Ratkaisun tulee toimia nopeasti myös isoilla syötteillä.

Tee ohjelma SuuriKertoma.java, joka toimii edellisen ohjelman tavoin, mutta se laskee tarvittaessa suuriakin kertomia.

Esimerkki

Anna luku: 25
Kertoma: 15511210043330985984000000

Löydät tietoa luokasta BigInteger Googlella: hakusanat "java biginteger api" vievät Javan dokumentaatioon ja hakusanat "java biginteger example" antavat esimerkkejä. Samalla tavalla voi etsiä tietoa mistä tahansa Javan luokasta.

3. Palindromi

Palindromi on sana, joka on sama alusta loppuun ja lopusta alkuun luettuna. Esimerkiksi sanat ala ja enne ovat palindromeja.

Tee ohjelma Palindromi.java, joka lukee käyttäjältä sanan ja ilmoittaa, onko se palindromi. Voit olettaa, että sana muodostuu kirjaimista a–z.

Esimerkki 1

Anna sana: enne
Sana on palindromi.

Esimerkki 2

Anna sana: aika
Sana ei ole palindromi.

4. Pienin ja suurin

Tee ohjelma PieninSuurin.java, joka lukee käyttäjältä joukon kokonaislukuja ja tulostaa lopuksi pienimmän ja suurimman luvun. Jokainen kokonaisluku mahtuu int-muuttujaan. Ohjelma kysyy ensin, kuinka monta lukua käyttäjä antaa. Voit olettaa, että käyttäjä antaa ainakin yhden ja korkeintaan miljoona lukua.

Esimerkki

Kuinka monta? 5
Anna luvut:
-5
2
-1
7
3
Pienin: -5
Suurin: 7

5. Kirjainneliö

Tee ohjelma Kirjainnelio.java, joka tulostaa annetun kokoisen kirjainneliön seuraavien esimerkkien mukaisesti. Voit olettaa, että kirjainneliön koko (kerrosten määrä) on 1–26.

Esimerkki 1

Anna koko: 3
AAAAA
ABBBA
ABCBA
ABBBA
AAAAA

Esimerkki 2

Anna koko: 4
AAAAAAA
ABBBBBA
ABCCCBA
ABCDCBA
ABCCCBA
ABBBBBA
AAAAAAA

Ohjelmointitehtävät, viikko 2

1. Anagrammit

Tee ohjelma Anagrammit.java, joka tarkistaa, ovatko kaksi sanaa anagrammeja. Sanat ovat anagrammeja, jos jokainen kirjain esiintyy niissä yhtä monta kertaa. Esimerkiksi sanat talo ja lato ovat anagrammeja. Voit olettaa, että sanat muodostuvat kirjaimista a–z.

Esimerkki 1

Anna 1. sana: talo
Anna 2. sana: lato
Annoit anagrammit.

Esimerkki 2

Anna 1. sana: talo
Anna 2. sana: altto
Et antanut anagrammeja.

2. Alkusummia

Tehtävänäsi on etsiä annetusta lukujonosta sellainen alkuosa jonka summa on haluttu. Ohjelmalle annetaan lukujono jonka jälkeen suoritetaan monta kyselyä.

• Toteuta luokka Etsin jonka konstruktorille Etsin(int[] luvut) annetaan taulukollinen positiivisia kokonaislukuja
• Toteuta metodi Etsin.etsi(int haluttuSumma) joka kutsulla etsi(x) palauttaa indeksin i konstruktorille annettuun taulukkoon luvut siten, että

  luvut[0] + luvut[1] + ... + luvut[i] = x

  Palauta -1 jos tällaista indeksiä ei löydy.

Tee ohjelmastasi salamannopea. Testit testaavat että 10 000 kyselyä 100 000 luvun taulukosta vie alle 50ms.

Huom! Testit eivät testaa pääohjelmaa (main) vaan suoraan luokkaa Etsin!

Vihje! binäärihaku

Esimerkki 1

Montako lukua?
3
Anna luvut:
1
2
3
Mikä summa?
1
Indeksi: 0
Mikä summa?
3
Indeksi: 1
Mikä summa?
6
Indeksi: 2
Mikä summa?
5
Indeksi: -1

Esimerkki 2

Montako lukua?
10
Anna luvut:

10
20
4
7
7
5
7
7
10
1
Mikä summa?
48
Indeksi: 4

3. Fibonaccin luvut

Fibonaccin luvut voidaan määritellä seuraavasti:

• F(0) = 0
• F(1) = 1
• F(n) = F(n - 2) + F(n - 1), kun n > 1

Ensimmäiset Fibonaccin luvut ovat seuraavat:

• F(0) = 0
• F(1) = 1
• F(2) = 1
• F(3) = 2
• F(4) = 3
• F(5) = 5
• F(6) = 8
• F(7) = 13
• F(8) = 21
• F(9) = 34
• F(10) = 55

Esimerkiksi F(5) = F(3) + F(4) = 2 + 3 = 5. Tee ohjelma Fibonacci.java, joka laskee luvun F(n). Voit olettaa, että n on ainakin 0 ja korkeintaan 46, jolloin tulos mahtuu int-muuttujaan. Tee ohjelmasta niin tehokas, että se laskee luvun F(46) salamannopeasti.

Esimerkki 1

n: 5
F(n): 5

Esimerkki 1

n: 9
F(n): 34

4. Puuttuva luku

Tee ohjelma PuuttuvaLuku.java, joka toimii seuraavasti: Käyttäjä antaa ensin ohjelmalle kokonaisluvun n ja sitten kaikki kokonaisluvut väliltä 1...n yhtä lukuun ottamatta. Ohjelman tehtävänä on selvittää, mikä on puuttuva luku. Voit olettaa, että käyttäjä antaa ainakin yhden luvun ja korkeintaan miljoona lukua. Tee ohjelmasta niin tehokas, että se käsittelee miljoona lukua muutamassa sekunnissa. Testit testaavat ajankäytön.

Esimerkki 1

Suurin luku? 5
Anna luvut:
3
1
5
4
Puuttuva luku: 2

Esimerkki 2

Suurin luku? 5
Anna luvut:
3
1
2
4
Puuttuva luku: 5

Vihje: Tehtävään on olemassa ratkaisualgoritmi, jonka aikavaativuus on O(n) ja tilavaativuus on O(1).

5. Suurin summa

Tee ohjelma SuurinSumma.java, joka selvittää suurimman peräkkäisten lukujen summan käyttäjän antamissa luvuissa. Ohjelma kysyy ensin, kuinka monta lukua käyttäjä antaa.

Tässä tehtävässä summaan täytyy kuulua ainakin yksi luku. Voit olettaa, että suurin summa on positiivinen.

Voit olettaa, että käyttäjä antaa ainakin yhden luvun ja korkeintaan miljoona lukua. Lisäksi voit olettaa, että jokainen luku on kokonaisluku väliltä -1000...1000, jolloin kaikki summat mahtuvat int-muuttujiin. Tee ohjelmasta niin tehokas, että se käsittelee miljoona lukua muutamassa sekunnissa. Huom! Ohjelmasi on oltava tehokas. Testit tarkastavat asian.

Esimerkki 1

Kuinka monta? 5
Anna luvut:
1
-2
5
2
-1
Suurin summa: 7

Esimerkki 2

Kuinka monta? 5
Anna luvut:
4
-2
5
2
-1
Suurin summa: 9

Esimerkki 3

Kuinka monta? 4
Anna luvut:
4
3
-5
6
Suurin summa: 8

Esimerkissä 1 suurin summa saadaan laskemalla yhteen luvut 5 ja 2. Esimerkissä 2 suurin summa saadaan laskemalla yhteen luvut 4, -2, 5 ja 2. Esimerkissä 3 suurin summa saadaan laskemalla kaikki luvut yhteen.

Vihje: Tehtävään on olemassa ratkaisualgoritmi, jonka aikavaativuus on O(n) ja tilavaativuus on O(1).

Ohjelmointitehtävät, viikko 3

1. Polynomi

Tehtäväpohjassa on luokka Polynomi, joka esittää polynomia linkitetyn listan avulla. Täydennä toteutusta metodilla summaa joka laskee kahden polynomin summan.

Esimerkkejä polynomien yhteenlaskuista:

3x^2 + 5x + 1
+
7x^3 + 7x^2
=
7x^3 + 10x^2 + 5x + 1


7x^100 + x^49 + 1
+
18x^100 + x^50 + 1
=
25x^100 + x^50 + x^49 + 1

2. DNA, osa 1

DNA on oleellisesti ottaen pitkä merkkijono, joka koostuu merkeistä A, C, G ja T.

Tehtävänäsi on tulostaa kaikki annetun mittaiset DNA:t. Esimerkiksi pituuden 2 DNA:t ovat:

AA
AC
AG
AT
CA
CC
CG
CT
GA
GC
GG
GT
TA
TC
TG
TT

Vastaavasti pituuden 3 DNA:t ovat (välilyönnein eroteltuina):

AAA AAC AAG AAT ACA ACC ACG ACT
AGA AGC AGG AGT ATA ATC ATG ATT
CAA CAC CAG CAT CCA CCC CCG CCT
CGA CGC CGG CGT CTA CTC CTG CTT
GAA GAC GAG GAT GCA GCC GCG GCT
GGA GGC GGG GGT GTA GTC GTG GTT
TAA TAC TAG TAT TCA TCC TCG TCT
TGA TGC TGG TGT TTA TTC TTG TTT

Toteuta tehtäväpohjaan metodi tulostaKaikkiDNAt(int pituus) joka tulostaa kaikki annetun pituiset DNAt.

Vihje! Tämä hoituu helposti rekursiolla.

3. DNA, osa 2

Nytkin tuotamme DNA:ta, mutta lisärajoituksella. Haluamme kaikki annetun pituiset DNA-sekvenssit joissa ei esiinny kahta samaa kirjainta peräkkäin.

Pituus 2:

AC
AG
AT
CA
CG
CT
GA
GC
TC
TG

Pituus 3:

ACA ACG ACT AGA AGC AGT ATA ATC ATG
CAC CAG CAT CGA CGC CGT CTA CTC CTG
GAC GAG GAT GCA GCG GCT GTA GTC GTG
TAC TAG TAT TCA TCG TCT TGA TGC TGT

Toteuta tehtäväpohjaan metodi tulostaDNAt(int pituus) joka tulostaa kaikki annetun pituiset DNA-merkkijonot joissa ei esiinny samaa merkkiä kahta kertaa peräkkäin. %p Voit tulostaa DNA:t missä tahansa järjestyksessä. Erottele DNA:t joko rivinvaihdoilla tai välilyönneillä.

4. Samat summat

Toteuta ohjelman SamatSummat metodi boolean samatSummat(int[] luvut), joka tarkistaa, voiko käyttäjän antamat luvut jakaa kahteen ryhmään niin, että molemmissa ryhmissä lukujen summa on sama. Jokaisen luvun on siis kuuluttava jompaan kumpaan ryhmään, ja lisäksi yksi luku ei voi kuulua molempiin ryhmiin. Voit olettaa, että käyttäjä antaa ainakin yhden ja korkeintaan 20 lukua. Lisäksi voit olettaa, että jokainen luku on positiivinen kokonaisluku ja mahtuu mahtuu int muuttujaan.

Vihjeitä ohjelman tekemiseen on luentomateriaalin sivuilla 95-96.

Vihje! suoraviivainen rekursiivinen algoritmi riittää tässä tehtävässä!

Esimerkki 1

Kuinka monta? 3
Anna luvut:
4
2
6
Jako on mahdollinen.

Esimerkki 2

Kuinka monta? 3
Anna luvut:
4
2
5
4
Jako ei ole mahdollinen.

Esimerkissä 1 toiseen ryhmään voidaan valita luvut 4 ja 2 ja toiseen ryhmään luku 6. Tällöin kummassakin ryhmässä lukujen summa on 6.

Esimerkissä 2 jako ei ole mahdollinen. Parittomia lukuja on tasan yksi, joten missä tahansa jakotavassa toisen ryhmän summa on parillinen ja toisen ryhmän summa on pariton.

Triviaa

Tällaisia kahteen ryhmään jakoja kutsutaan myös osituksiksi (engl. partition). Tämä ongelma on varsinainen klassikko, ja se tunnetaan yksinkertaisesti nimellä PARTITION. Ongelma on erikoistapaus vielä kuuluisammasta ongelmasta SUBSET-SUM. Kummatkin ongelmat ovat lisäksi NP-täydellisiä. Tässä tehtävässä ei kuitenkaan tarvitse toteuttaa monimutkaista ja tehokasta internetistä löytämääsi ratkaisua vaan suoraviivainen rekursiivinen algoritmi riittää

5. Linkitetty lista

Tehtäväpohjan mukana tulee luokka Node, joka esittää yhteen suuntaan linkitetyn listan solmua:

public class Node {

    private Node next = null;
    private int value;

    public Node(int value, Node next) {
        this.next=next;
        this.value=value;
    }

    public Node(int value) {
        this.value=value;
    }

    public int getValue() {
        return value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Node setValue(int value) {
        this.value = value;
    }
}

Toteuta luokkaan Operaatioita seuraavat metodit:

• Node reverse(Node list) kääntää annetun listan
• Node cut(Node list, int i) "leikkaa" listan indeksin i kohdalta ja palauttaa loppuosan. Esimerkki:

// Rakennetaan lista [6,7,8,9,10]
Node lista = new Node(6,new Node(7, new Node(8, new Node(9, new Node(10)))));
// Katkaistaan indeksistä 2
Node loppu = Operaatioita.cut(lista, 2);
// Nyt loppu on [8,9,10] ja lista on [6,7]

Huom! Kummankaan metodin ei tule allokoida uusia solmuja, vaan annetun listan solmut tulee uudelleenkäyttää! Kummassakaan metodissa ei siis tarvitse olla yhtään new Node -kutsua!

Huom! Testit testaavat että pitkänkin listan kääntämiseen menee alle 20ms.

Ohjelmointitehtävät, viikko 4

1. Kuka on viimeinen?

Tarkastellaan peliä, jossa joukko henkilöitä on asettunut rinkiin. Pelissä henkilöitä käydään läpi myötäpäivään ja joka toinen henkilö joutuu poistumaan ringistä. Ensimmäinen poistuja on toisena oleva. Lopulta ringissä on jäljellä enää yksi henkilö, josta tulee pelin voittaja.

Esimerkiksi jos henkilöitä on viisi, tilanne on seuraavanlainen:

Henkilöt käydään läpi seuraavasti:

• Henkilö 1 saa jäädä rinkiin.
• Henkilö 2 joutuu poistumaan.
• Henkilö 3 saa jäädä rinkiin.
• Henkilö 4 joutuu poistumaan.
• Henkilö 5 saa jäädä rinkiin.
• Henkilö 1 joutuu poistumaan.
• Henkilö 3 saa jäädä rinkiin.
• Henkilö 5 joutuu poistumaan.

Pelin voittaja on henkilö 3, joka jää rinkiin viimeisenä.

Toteuta ohjelmaan Viimeinen metodi int viimeinen(int montako), joka selvittää yllä kuvatun pelin voittajan, kun pelissä on annettu määrä henkilöitä.

Huom! Suunnittele ohjelma niin, että se on tehokas myös miljoonan henkilön tapauksessa. Ratkaisun tulee olla O(1) ja O(n log n) välillä.

Esimerkki 1

Kuinka monta? 5
Voittaja: 3

Esimerkki 2

Kuinka monta? 6
Voittaja: 5

2. Kaikki palindromit

Palindromi on merkkijono joka on sama kumminkin päin luettuna. Esimerkiksi sana anna on palindromi mutta sana talo ei. Kirjaimista A...C voidaan muodostaa seuraavat 3 kirjaimen pituiset palindromit:

• AAA
• ABA
• ACA
• BAB
• BBB
• BCB
• CAC
• CBC
• CCC

Toteuta metodi void palindromit(int kirjaimia, int pituus), joka tulostaa kaikki pituus-pituiset palindromit, jotka muodostuvat kirjaimia kpl aakkosten ensimmäisistä kirjamesta.

Voit olettaa, että kirjaimia on korkeintaan 26 ja pituus on korkeintaan 100.

Huom! älä tee niin että generoit merkkijonon ja sitten tarkistat onko se palindromi. Kaikkia merkkijonoja on paljon enemmän kuin palindromeja. Voit nähdä tämän itse kirjoittamalla paperille kaikki pituuden 3 merkkijonot merkeistä A,B,C ja kaikki pituuden 3 palindromit merkeistä A,B,C.

Esimerkki 1

Kutsu tulosta(3,3) tulostaa:

AAA
ABA
ACA
BAB
BBB
BCB
CAC
CBC
CCC

Esimerkki 2

Kutsu tulosta(2,4) tulostaa:

AAAA
ABBA
BAAB
BBBB

3. Puita

Tehtäväpohjassa on binääripuun toteutus. Puun solmut esitetään luokan Node avulla:

public class Node {

    private Node left;
    private Node right;
    private int value;

    public Node(int value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public Node(int value) {
        this.value = value;
        // left ja right ovat null
    }

    public Node getLeft() {
        return left;
    }

    public Node getRight() {
        return getRight;
    }

    public int getValue() {
        return value;
    }

}

Toteuta luokkaan Puita seuraavat metodit:

• int countLeaves(Node tree) laskee puun lehtien määrän kun sille annetaan puun juurisolmu
• int treeHeight(Node tree) laskee puun korkeuden kun sille annetaan puun juurisolmu
• int sum(Node tree) laskee puun solmuissa olevien arvojen (value) summan

Esimerkki

Tämän puun:

1
   / \
  2   3
 / \   \
4   5   6
       / \
      7   8

• lehtien lukumäärä on 4 (lehtiä ovat solmut 4, 5, 7 ja 8)
• korkeus on 3
• arvojen summa on 1+2+3+4+5+6+7+8 = 36

Tämän puun:

0
 / \
1   0
   / \
  0   1
 / \
1   0
   / \
  1   1

• lehtien lukumäärä on 5 (lehtiä ovat solmut joitten arvo on 1)
• korkeus on 4
• arvojen summa on 0+1+0+0+1+1+0+1+1 = 5

4. Paras reitti alas

Tarkastellaan seuraavaa lukupyramidia:

4
    3   2
  1   3   5
3   4   1   1

Tehtävänä on etsiä reitti pyramidin huipulta alas, jossa joka vaiheessa siirrytään alavasemmalla tai alaoikealla olevaan lukuun ja jossa lukujen summa on mahdollisimman suuri. Voit kuitenkin olettaa, että lukujen lopullinen summa mahtuu int-muuttujaan.

Tässä tapauksessa paras reitti aloittaa huipulta (4), liikkuu alavasemmalle (3), liikkuu alaoikealle (3) ja liikkuu alavasemmalle (4). Lukujen summa reitillä on 14, ja millään muulla reitillä summa ei ole yhtä suuri.

Seuraava kuva vastaa reittiä:

4
    3   2
  1   3   5
3   4   1   1

Toteuta tehtäväpohjan ohjelmaan ParasReitti.java metodi public static int parasReitti(int[][] pyramidi), joka etsii parhaan reitin lukupyramidin huipulta alas ja ilmoittaa lukujen summan kyseisellä reitillä.

Metodi saa syötteenä kaksiulotteisen taulukon pyramidi siten, että pyramidi[i][j] on pyramidin (ylhäältä laskien, nollasta lähtien) i:nnen rivin (vasemmalta laskien, nollasta lähtien) j:nnes numero.

Ohjelma voi olettaa, että pyramidissa on korkeintaan sata kerrosta. Tällöinkin ohjelman toiminnan tulee olla tehokas. Aikavaativuuden tulee olla kutakuinkin O(n^2)

Esimerkki 1

Anna koko: 4
Anna luvut:
4
3 2
1 3 5
3 4 1 1
Paras: 14

Esimerkki 2

Anna koko: 5
Anna luvut:
7
2 9
1 5 2
3 1 4 2
7 8 3 1 4
Paras: 30

Vihje! Tässä tehtävässä saattaa olla iloa ohjelmontitekniikasta nimeltä dynaaminen ohjelmointi (dynamic programming).

5. Laskutoimitus

Toteuta metodi int evaluoi(String lauseke), joka laskee käyttäjän antaman laskutoimituksen. Laskutoimitus voi sisältää kokonaislukuja väliltä 0...1000, operaatioita + ja * sekä sulkuja. Voit olettaa, että laskutoimituksen jokainen välivaihe mahtuu int-muuttujaan.

Ohjelmasi voi olettaa, että laskutoimituksen muoto on oikea (eli ohjelman ei tarvitse sisältää virheenkäsittelyä). Laskutoimitus muodostuu merkeistä 0–9, +, *, ( ja ), eikä siinä ole ylimääräisiä välilyöntejä.

Esimerkki 1

Anna laskutoimitus: 2+5*3
Tulos: 17

Esimerkki 2

Anna laskutoimitus: (1+1)*5
Tulos: 10

Esimerkki 3

Anna laskutoimitus: 2*(3*(5+2)+1)
Tulos: 44

Esimerkki 4

Anna laskutoimitus: 100*10*10
Tulos: 10000

Vihje! Yksi algoritmi tehtävän ratkaisuun tunnetaan nimellä "shunting yard". Saattaa olla kuitenkin hauskempaa keksiä itse sopiva algoritmi!

Ohjelmointitehtävät, viikko 5

1. Binäärihakupuu

Tehtäväpohjassa on binäärihakupuun toteutus. Puun solmut esitetään luokan Node avulla. Luokka node tulee tehtäväpohjan mukana.

Esitämme puun Tree-luokalla, joka sisältää viitteen juurisolmuun.

Ensimmäisenä tehtävänäsi on toteuttaa luokkaan Hakupuu metodi public static Object search(Tree tree, int key), joka hakee annettua avainta vastaavan arvon annetusta binääripuusta.

Toisena tehtävänäsi on toteuttaa metodi public static void insert(Tree tree, int key, Object value), joka lisää annetun arvon annetulla avaimella puuhun. Jos avain on jo käytössä, päivitetään sitä vastaava arvo.

Huom! tässä tehtävässä törmäät tyhjiin puihin. Tyhjä puu on Tree-olio jonka root on null.

Apua löydät luentokalvojen sivuilta 169-171.

Operaatioidesi tulee toimia alle 50 millisekunnissa isoillakin puilla.

Esimerkkejä

Lisätään tyhjään puuhun järjestyksessä avaimet 3,7,5,2,0,8,6. Tässä ovat puun vaiheet:

    3
    3
     \
      7
    3
     \
      7
     /
    5
    3
   / \
  2   7
     /
    5
    3
   / \
  2   7
 /   / \
0   5   8
    3
   / \
  2   7
 /   / \
0   5   8
     \
      6

2. Tekstianalyysiä

Toteuta luokka SanaTilasto, joka laskee annetun tekstin sanojen frekvenssit (eli esiintymiskerrat). Toteutuksesi tulee olla seuraavan pohjan mukainen:

public class SanaTilasto {
     public SanaTilasto(Scanner lukija) {
          // lue sanat käyttäen lukija.next()iä
     }
     public int frekvenssi(String sana) {
          // palauttaa annetun sanan frekvenssin
     }
     public int eriSanojenLukumaara() {
          // palauttaa _eri_ sanojen lukumäärän
     }

}

Käytä tehtävässä Javan valmista hajautustaulua HashMap.

3. Binääripuun tulostus

Tehtävänäsi on tulostaa binääripuu seuraavalla tavalla. Puu:

       1
      / \
     2   3
    / \   \
   4   5   6
          / \
         7   8

Tulostus:

_1_
_2_ 3_
4 5 _6_
7 8

Puun solmut siis tulostetaan tasojärjestyksessä ja lisäksi jokaiseen solmuun merkitään onko sillä vasenta ja/tai oikeaa lasta.

Toteuta tehtäväpohjaan metodi print(Tree tree) joka tekee tulostuksen. Luokat Tree ja Node ovat samat kuin tehtävässä 1. Tulosta puun solmuista vain avain, arvon (value) voit unohtaa.

Vihje! Javan ArrayDeque-luokka (jono) saattaa auttaa.

4. Onko puu AVL-puu?

Tehtäväsi on tunnistaa annetusta binäärihakupuusta täyttääkö se AVL-ehdon (ks. luentokalvojen sivut 202 ja 294). Toteuta metodi public static boolean isAVL(Tree tree).

Huom! puuhun ei ole tallennettu alipuitten korkeuksia, joten sinun täytyy laskea ne itse.

Huom! sinun ei tarvitse tarkistaa, onko annettu puu hakupuu! Et siis tarvitse solmujen avaimia tai arvoja mihinkään.

Esimerkkejä AVL-ehdon täyttävistä puista:

     o              o             o
    / \            / \           / \
   o   o          o   o         o   o
  /\   /\        /   / \       / \  |\
 o  o o  o      o   o   o     o   o o o
        / \          \       / \ / \
       o   o          o      o o o o

Esimerkkejä puista jotka eivät täytä AVL-ehtoa:

     o               o            o
    / \             / \          / \
   o   o           o   o        o   o
  /\   /\         /   / \      / \   \
 o  o o  o       o   o   o    o   o   o
        / \     /     \      / \ / \ / \
       o   o   o       o     o o o o o o
        \
         o

5. Jälkijärjestys

Tarkastellaan seuraavaa binääripuuta:

      7
     / \
    9   2
   / \
  3   5

Luentomateriaalin sivuilla 161-168 määritellään esijärjestys, sisäjärjestys ja jälkijärjestys.

Puun solmut esijärjestyksessä: 79352

Puun solmut sisäjärjestyksessä: 39572

Puun solmut jälkijärjestyksessä: 35927

Tee ohjelma metodi int[] jalkijarjestys(int[] esi, int[] sisa), jolle annetaan binääripuun esijärjestys ja sisäjärjestys ja joka muodostaa niiden perusteella binääripuun jälkijärjestyksen.

Huom! Voit olettaa että sama solmun numero ei toistu puussa.

Esimerkki 1

E: 7 9 3 5 2
S: 3 9 5 7 2
J: 3 5 9 2 7

Esimerkki 2

Tämän esimerkin puu on:

     0
    / \
   /   \
  1     2
 / \   / \
3   4 7   8
   / \    |
  5   6   9
  |
  10

E: 0 1 3 4 5 10 6 2 7 8 9
S: 3 1 10 5 4 6 0 7 2 9 8
J: 3 10 5 6 4 1 7 9 8 2 0

Ohjelmointitehtävät, viikko 6

Ensimmäiset 4 tehtävää kannattaa tehdä ennen tenttiä, ne liittyvät vielä koealueeseen. Loput voit tehdä vaikka väliviikolla!

1. Syklin tunnistus

Tehtävänäsi on tarkistaa, löytyykö linkitetystä listasta sykli eli silmukka. Tehtäväpohjassa on linkitetyn listan toteutus tutulla Node-luokalla:

Toteuta metodi int sykli(Node alku) joka palauttaa annetusta listasta löytyvän syklin pituuden tai 0 jos sykliä ei löydy.

Tähän tehtävään on monia erilaisia ratkaisuita. Ratkaisusi ei tarvitse olla erityisen tehokas, mutta ongelmaan on olemassa ratkaisu jonka aikavaativuus on O(n) ja tilavaativuus O(1).

Huom! syklin tunnistamiseksi pitää tarkastella Nodejen yhtäsuuruutta, pelkkä Nodeissa olevien arvojen tarkasteleminen ei riitä.

Esimerkkejä

Luodaan seuraavanlainen lista:

1 --> 2 --> 3 --> 1 --> 5 --> 1 --> 900
                  ^__________________|

Javakoodina:

Node vika = new Node(900);
Node sykli = new Node(1, new Node(5, new Node(1, vika)));
vika.setNext(sykli);
Node lista = new Node(1, new Node(2, new Node(3, sykli)));

Nyt kutsu sykli(lista) palauttaisi 4

2. Puumuunnos

Saat syötteenä binääripuun. Muodosta lähes täydellinen binääripuu , jonka esijärjestys on sama kuin syötteenä olevan binääripuun. Lähes täydellinen binääripuu tarkoittaa binääripuuta, jonka kaikki lehdet ovat kahdella vierekkäisellä tasolla, ja lisäksi lehdet on pakattu vasemmalle. Lisäksi kaikilla lehtitasoja korkeammilla tasoilla olevilla solmuilla on kaksi lasta.

Lähes täydellinen binääripuu on siis täydellinen binääripuu jolta on poistettu osa sen oikeanpuolimmaisista lehdistä. Lähes täydellinen binääripuu vastaa luentokalvojen sivun 339 ehtoa K1.

Kirjoita metodi Node muunna(Node tree) joka tekee tämän muunnoksen.

Esimerkkejä lähes täydellisistä binääripuista

    o          o        o        o       o      
   / \        / \      / \      / \     / \  
  o   o      o   o    o   o    o   o   o   o 
 / \ / \    / \ /    / \      /       / \ / \
o  o o  o  o  o o   o   o    o       o  o o  o
                                    / \
                                   o   o

Esimerkkejä muunnoksen toiminnasta

         Syöte           Tulos

    1                      1
     \                    / \
      2                  2   5
       \                / \ /
        3               3 4 6
         \
          4
           \
            5
             \
              6

        Syöte            Tulos

          8                8
         / \              / \
        3   9            3   7
       / \   \          / \ / \
      2   6  10        2  5 9 10
     /   / \          / \
    1   5   7        1   6

3. Kuningattaret

Shakissa kuningatar voi liikkua vaaka-, pysty- tai vinosuuntaisesti. Tehtävänäsi on laskea, kuinka monella tavalla kaksi kuningatarta voidaan sijoittaa n x n -shakkilaudalle niin, että ne eivät uhkaa toisiaan.

Esimerkiksi tapauksessa n = 3 mahdollisuudet ovat:

K..  K..  .K.  .K.  ..K  ..K  ...  ...
..K  ...  ...  ...  K..  ...  K..  ..K
...  .K.  K..  ..K  ...  .K.  ..K  K..

Tapauksessa n = 10 mahdollisuuksia on jo 3480.

Huomaa että isommilla syötteillä tulos ei mahdu Int -muuttujaan.

Toteuta luokan Kuningattaretmetodi long kuningatarLaskija(int leveys)joka laskee kuningatarten määrän.

Esimerkki 1

Anna koko: 3 Vastaus: 8

Esimerkki 2

Anna koko: 10
Vastaus: 3480

4. Kiertopeli

Kiertopelissä 3x3-ruudukko sisältää luvut 1–9. Tavoitteena on saattaa ruudukon luvut seuraavaan järjestykseen:

1 2 3
4 5 6
7 8 9

Ruudukon lukujen paikkoja voi muuttaa kiertojen avulla. Yksi kierto kohdistuu johonkin 2x2-aliruudukkoon ja kiertää sen sisällä olevia lukuja askeleen myötä- tai vastapäivään.

Tarkastellaan esimerkiksi seuraavaa pelitilannetta:

2 8 3
1 4 5
7 9 6

Kierretään ensin ylävasemmalla olevaa 2x2-ruudukkoa myötäpäivään:

2 8 3        1 2 3
1 4 5   =>   4 8 5
7 9 6        7 9 6

Kierretään sitten alaoikealla olevaa 2x2-ruudukkoa vastapäivään:

1 2 3        1 2 3
4 8 5   =>   4 5 6
7 9 6        7 8 9

Tässä tapauksessa siis kaksi kiertoa riitti kiertopelin ratkaisuun.

Tee ohjelma Kiertopeli.java, jolle annetaan kiertopelin aloitustilanne ja joka tulostaa pienimmän kiertojen määrän, joilla ruudukon luvut saa järjestykseen.

Tee ohjelmastasi sellainen, että se ratkaisee minkä tahansa kiertopelin aloitustilanteen silmänräpäyksessä.

Esimerkki 1

Anna ruudukko:

  2 8 3
  1 4 5
  7 9 6

Tulos: 2

Esimerkki 2

Anna ruudukko:

  1 6 5
  8 7 2
  3 4 9

Tulos: 4

5. Opiskelijanumero

Opiskelijanumeron viimeinen numero on tarkistusnumero, joka saadaan laskemalla yhteen alkuosan numerot, jotka on kerrottu luvuilla 1, 3, 7, 1, 3, 7, ..., 1, 3 ja 7. Tarkistusnumero on etäisyys näin saadusta luvusta seuraavaan tasakymmeneen.

Huom! kertoimet tasataan vasemmalle. Viimeisen numeron kerroin on siis aina 7.

Esimerkiksi jos opiskelijanumeron alkuosa on 01274913, lasketaan 3*0 + 7*1 + 1*2 + 3*7 + 7*4 + 1*9 + 3*1 + 7*3 = 91, josta on matkaa tasakymmeneen 9. Tämän vuoksi tarkistusnumero on 9 ja koko opiskelijanumero on 012749139.

Tee metodi int tarkiste(String alkuosa), jolle annetaan opiskelijanumeron alkuosa ja joka laskee sen tarkistusnumeron. Opiskelijoitten määrän kasvamisen varalta tee metodistasi sellainen joka tukee kaikenmittaisia opiskelijanumeroita.

Vihje! Character.digit-metodi on hyödyllinen.

Esimerkki 1

Alkuosa:
01274913
Tarkistusnumero: 9

Esimerkki 2

Alkuosa:
01525594
Tarkistusnumero: 7

Esimerkki 3

Alkuosa:
1
Tarkistusnumero: 3

Alkuosa:
001
Tarkistusnumero: 3

Esimerkki 4

Alkuosa:
1234567891011121314151617181920
Tarkistusnumero: 4

6. Stirlingin luvut

Stirlingin luvut ovat sukua laskareissa käsitellyille binomikertoimille. Stirlingin luvun S(n,k) voi laskea kaavalla:

S(n+1,k) = k*S(n,k) + S(n,k-1)

Reunaehdot ovat:

S(0,0) = 1,
S(n,0) = S(0,k) = 0

Toteuta metodi long stirling(long n, long k) joka laskee luvun S(n,k).

Huom! long on javan kokonaislukutyyppi, johon mahtuu paljon suurempia lukuja kuin tyyppiin int.

Vihje! Tämä on helppoa rekursiolla!

7. Kirjainruudukko

Tarkastellaan seuraavaa kirjainruudukkoa:

RIRA
ATIA
TATR

Sana TIRA voidaan lukea ruudukosta neljällä tavalla:

RI..
AT..
....

.IRA
.T..
....

..RA
.TI.
....

..RA
..I.
..T.

Tee metodi int kirjainRuudukko(char[][] ruudukko, String sana), jolle annetaan kirjainruudukko ja etsittävä sana ja joka ilmoittaa, kuinka monella tavalla sana voidaan lukea ruudukosta. Sanan lukemisen saa aloittaa mistä tahansa ruudusta, ja jokaisen kirjaimen jälkeen siirrytään askel ylös, alas, vasemmalle tai oikealle. Sama ruudukon kirjain voi esiintyä monta kertaa sanassa.

Voit olettaa, että ruudukon leveys ja korkeus ovat korkeintaan 100, sanan pituus on korkeintaan 20, kaikki kirjaimet ovat joukossa A...Z ja sana esiintyy ruudukossa korkeintaan 1000000 kertaa.

Esimerkki 1

Anna korkeus:
3
Anna leveys:
4
Anna ruudukko:
RIRA
ATIA
TATR
Anna sana:
TIRA
Tulos: 4

Esimerkki 2

Anna korkeus:
2
Anna leveys:
2
Anna ruudukko:
AA
AA
Anna sana:
AAAAAAAAAA
Tulos: 2048

8. Sudoku

Tee metodi void ratkaise(int[][] sudoku), joka ratkaisee annetun sudokun. Sudoku annetaan kaksiulotteisena int-taulukkona. Taulukossa 0 tarkoittaa tyhjää paikkaa ja numerot 1-9 tarkoittavat numeroita 1-9. Metodin pitäisi muokata annettua taulukkoa niin että se on oikein täytetty sudoku, eli:

• Yksikään taulukon paikka ei ole 0.
• Taulukon jokaisella rivillä esiintyvät luvut 1-9, jokainen tasan kerran.
• Taulukon jokaisessa sarakkeessa esiintyvät luvut 1-9, jokainen tasan kerran.
• Kun taulukko jaetaan yhdeksään 3x3 neliöön, jokaisessa neliössä esiintyvät luvut 1-9, jokainen tasan kerran.

Voit olettaa, että metodille annettuun sudokuun on olemassa yksikäsitteinen ratkaisu.

Suomalainen Arto Inkala on laatinut "maailman vaikeimman Sudokun":

• Maths whiz creates hardest Sudoku yet (The Sun)

Tee ohjelmastasi sellainen, että se ratkaisee kyseisen sudokun (ja muutkin löytämäsi sudokut) silmänräpäyksessä.

Vihje! Luentokalvojen kuningattaret shakkilaudalla -esimerkki.

Esimerkki: Helppo sudoku

(Tämän pitäisi ratketa hyvin nopeasti)

Anna sudoku:

8??93???2
??9????4?
7?21??96?
2??????9?
?6?????7?
?7???6??5
?27??84?6
?3????5??
5???62??8
Ratkaisu:
846937152
319625847
752184963
285713694
463859271
971246385
127598436
638471529
594362718

Esimerkki: "Maailman vaikein" sudoku

Anna sudoku:
??53?????
8??????2?
?7??1?5??
4????53??
?1??7???6
??32???8?
?6?5????9
??4????3?
?????97??
Ratkaisu:
145327698
839654127
672918543
496185372
218473956
753296481
367542819
984761235
521839764

Esimerkki: Toinen vaikea sudoku

Anna sudoku:
?????????
?????3?85
??1?2????
???5?7???
??4???1??
?9???????
5??????7?
??2?1????
????4???9
Ratkaisu:
237658914
469173285
851924367
123567498
784239156
695481732
546392871
972815643
318746529

Ohjelmointitehtävät, viikko 7

1. Etsintä 1

Toteuta metodi boolean etsi(int[] taulukko, int k) joka tutkii onko taulukossa kahta lukua, joiden summa on k. Sama taulukon luku ei saa kuulua summaan kahta kertaa. Ratkaisusi tulee olla tehokas.

Huom! syötteessä voi olla myös negatiivisia lukuja!

Vihje! on olemassa ajassa O(n log n) toimiva ratkaisu.

2. Etsintä 2

Toteuta metodi boolean etsi(int[] taulukko, int k) joka tutkii onko taulukossa neljää lukua, joiden summa on k. Tässä tehtävässä sama taulukon luku saa kuulua summaan useamman kerran. Ratkaisusi tulee olla tehokas.

Huom! syötteessä voi olla myös negatiivisia lukuja!

Vihje! on olemassa ajassa O(n ² log n) toimiva ratkaisu.

Esimerkkejä

Kaikissa näissä esimerkeissä k=10.

Näille taulukoille etsi palauttaa true:

  {2,3}
  {1,2,3,4}
  {4,2,3,1}
  {4,4,1,1,1,6,6}
  {4,3,1,5,5,6,6}

Näille taulukoille etsi palauttaa false:

  {5}
  {1,1,1,1}
  {4,6,5,5}
  {6,4,5,5}
  {6,6,6,4}
  {9,1,1,1,1,5,6}

3. Young-etsintä

Tämä tehtävä käsittelee Youngin taulukoita, joista oli tehtävä viimeuoden laskareissa, kts. https://www.cs.helsinki.fi/u/floreen/tira2012/teht07.pdf tehtävä 5

Mikäli youngin taulukko ei ole tuttu, kts. https://en.wikipedia.org/wiki/Young_tableau

Tehtävänäsi on toteuttaa metodi boolean etsi(int[][] young, int k), joka tutkii löytyykö luku k annetusta Youngin taulukosta. Ratkaisusi aikavaativuuden tulisi olla O(m+n), jossa m ja n ovat Youngin taulukon leveys ja korkeus.

4. Odotushuone

Joukko ihmisiä jonottaa lääkärin vastaanotolle. Kun ihminen saapuu odotushuoneeseen, sairaanhoitaja arvioi hänen hoidontarpeensa. Hoidontarvetta kuvaa kokonaisluku 1-1 000 000. Kun lääkäri on vapaa, valitsee hän hoidettavakseen sen odottajan, jolla on suurin hoidontarve .

Toteuta luokka Odotushuone, jonka olioilla on metodit:

• void lisaa(String nimi, int tarve) lisää odotushuoneeseen odottajan
• String seuraavaPotilas() palauttaa odotushuoneen suurimman hoidontarpeen omaavan potilaan nimen ja poistaa potilaan odotushuoneesta

Kummankin metodin täytyy toimia hyvin nopeasti.

Voit olettaa, ettei tyhjästä odotushuoneesta koiteta hakea potilasta, ja että kahdella potilaalla ei ole samaa nimeä.

Vihje! Javasta löytyy luokka PriorityQueue. Tarvinnet myös rajapintaa Comparator tai Comparable.

Esimerkki

Odotushuone o = new Odotushuone();
o.lisaa("Pekka",3);
o.lisaa("Liisa",4);
System.out.println(o.seuraavaPotilas());
o.lisaa("Simo",1);
o.lisaa("Kerttu",99);
System.out.println(o.seuraavaPotilas());
System.out.println(o.seuraavaPotilas());
System.out.println(o.seuraavaPotilas());

Ylläoleva koodi tulostaa:

Liisa
Kerttu
Pekka
Simo

5. Vankilapako

Tehtävänäsi on paeta vankilasta hiippailemalla ja kaivamalla tunneleita. Vankila on kaksiulotteinen ruudukko jossa on muureja (#), käytäviä (.) ja yksi aloituspaikka (X). Tässä on esimerkki vankilasta:

#..##
#.#.#
##X#.
#..##
.##.#

Vanki aloittaa aloituspaikasta ja voi liikkua neljään pääilmansuuntaan. Muuriruutuun liikkuminen on kaivautumista ja käytäväruutuun liikkuminen hiippailemista. Tehtävänäsi on etsiä paras reitti aloituspaikasta ruudukon reunalle. Paras reitti on sellainen jossa on

1. Ensisijaisesti vähiten kaivamista.
2. Toissijaisesti vähiten hiippailemista.

Tämä tarkoittaa että kahdesta reitistä parempi on se jossa on vähemmän kaivamista. Jos kahdessa reitissä on saman verran kaivamista, on niistä parempi se jossa on vähemmän hiippailemista (eli kumpi on lyhempi). Parhaita reittejä voi olla useita.

Toteuta metodi char[] pakene(char[][] vankila) joka laskee lyhimmän reitin. Syötteenä on kaksiulotteinen char-taulukko joka kuvaa vankilaa ( '.' on käytävä, '#' on muuri, 'X' on aloituspaikka). Algoritmin tulee palauttaa lyhin reitti char-taulukkona joka kuvaa reittiä: 'Y' on ylöspäin liikkuminen, 'A' alaspäin liikkuminen, 'V' ja 'O' vasemmalle ja oikealle liikkumisia.

Huom! ratkaisun tehokkuudella ei tässä tehtävässä ole niin väliä. Suurin syöte on kokoa 10x10.

Esimerkki 1

Vankila:

###.#
#...#
#.###
#..X#
#####

Paras reitti (ei kaivautumista):

VVYYOOY

Esimerkki 2

#.###
#.#.#
##X##
#..##
.##.#

AA

Esimerkki 3

#########
#########
###.#...#
###.#####
###..X###
#########
#########
#########

YYOOO

Ohjelmointitehtävät, viikko 8

1. Henkilörekisteri

Toteuta luokka Henkilorekisteri, jolla on metodit

• void lisaa(String etu, String suku, int ika) lisää henkilön
• boolean kysele(String etu, String suku, int ika) tarkistaa onko kyseinen henkilö rekisterissä
• ArrayList<String> haeKaikki() palauttaa kaikkien lisättyjen henkilöitten kuvaukset muodossa "Etu Suku ikä". Kuvaukset tulee palauttaa seuraavassa järjestyksessä:
  • Ensisijaisesti sukunimen mukaan aakkosjärjestyksessä
  • Jos kahdella henkilöllä on sama sukunimi, järjestetään heidät etunimiensä mukaan
  • Jos kahdella henkilöllä on sama etu- ja sukunimi, järjestetään heidät ikiensä mukaan

Vihje! käytä jotain valmista tietorakennetta!

2. Nopeaa järjestämistä

Tehtävänäsi on järjestää luvuista -100 - +100 koostuva taulukko lineaarisessa ajassa. Toteuta siis metodi sort(int[] taulukko).

3. k:nneksi suurin luku

Toteuta metodi int suurin(int k, int[] luvut), joka palauttaa taulukon luvut k:nneksi suurimman luvun.

Ratkaisusi täytyy olla nopea sekä n:n (taulukon pituus) että k:n suhteen. On olemassa useita luokkaa O(nlog k) olevia ratkaisuita.

Voit olettaa että taulukossa ei toistu mikään luku.

Vihje! valitse sopiva tietorakenne johon "keräät" lukuja.

Vihje! luokkaa O(nlog n) oleva ratkaisu (esim. järjestäminen) ei riitä!

4. Suoran löytäminen

Saat joukon koordinaatteja. Tehtävänäsi on tutkia, ovatko jotkin kaksi koordinaattia samalla origon (eli pisteen (0,0)) kautta kulkevalla suoralla. Ratkaisusi tulisi olla luokkaa O(nlog n).

Tehtävän yksinkertaistamiseksi voit olettaa, että kaikki x- ja y- arvot ovat positiivisia kokonaislukuja.

Toteuta metodi boolean suora(int[][] pisteet), joka saa parametrinaan n pistettä ja palauttaa true jos suora löytyi. Pisteet esitetään kaksiulotteisena int-taulukkona siten, että ensimmäisen pisteen koodrinaatit ovat (pisteet[0][0],pisteet[0][1]), toisen pisteen (pisteet[1][0],pisteet[1][1]), jne.

Selvennys: pisteet[i][0] sisältää pisteen nro i x-koordinaatin ja pisteet[i][1] vastaavasti y-koordinaatin

Vihje! järjestäminen!

5. Suurin neliö

Suorakulmion muotoinen peltoalue muodostuu neliöruuduista. Alueelle halutaan rakentaa mahdollisimman suuri neliön muotoinen luistinrata. Kuitenkin joissakin peltoalueen ruuduissa on puu, joiden kohdalle luistinrataa ei voi rakentaa.

Tee metodi int suurinNelio(boolean[][] kartta), jolle annetaan peltoalueen kuvaus ja joka laskee suurimman neliön sivun pituuden. Peltoalue esitetään kaksiulotteisena boolean-taulukkona, jossa true tarkoittaa vapaata kohtaa ja false tarkoittaa puuta.

Tarkastellaan esimerkiksi seuraavaa tilannetta:

...P..
.P....
P....P
.P...P

Tässä peltoalueen koko on 4 x 6 ruutua. Merkki . tarkoittaa tyhjää ruutua ja merkki P tarkoittaa puuta. Tässä tapauksessa suurimman luistinradan koko on 3 x 3 ruutua. Seuraavassa luistinrataa kuvaa merkki L:

...P..
.PLLL.
P.LLLP
.PLLLP

Voit olettaa, että peltoalueen koko on korkeintaan 1000 x 1000 ruutua. Tee ohjelmastasi tehokas: aikavaativuuden olisi syytä olla O(n · m), jossa n on alueen korkeus ja m on alueen leveys. Käytännössä ohjelmasi tulisi siis käydä peltoalueen ruudut kerran läpi ja ilmoittaa sitten vastaus.

Esimerkki 1

Korkeus:
4
Leveys:
6
Anna kuvaus:

  ...P..
  .P....
  P....P
  .P...P

Tulos: 3

Esimerkki 2

Korkeus:
5
Leveys:
3
Anna kuvaus:

  ...
  ...
  .P.
  ...
  ...

Tulos: 2

.
#
.

##########
#.###....#
#..#####.#
#...#.##.#
##########

##########
#.#...##.#
#.#.#....#
#.....##.#
##########

##########
#.###....#
#..#####.#
#...#.##.#
##########

##########
#.#..#.#.#
######.###
#..#.#.#.#
##########

........
........
..x.x...
.x...x..
...R....
.x...x..
..x.x...
........

0.......
........
.1......
........
........
........
........
........

0.......
........
.1......
...2....
.....3..
.......4
.....5..
.......6

##########
#.#...##.#
#.#P#...P#
#.....##.#
##########

##########
#5#123##1#
#4#P#321P#
#32123##1#
##########

##########
#.#...##P#
#.#P#P...#
#P....##.#
##########

Osasumma o = new Osasumma(new int[] {5,2,6,2,4});
System.out.println(o.osasumma(1,3));
System.out.println(o.osasumma(0,1));
System.out.println(o.osasumma(2,2));
System.out.println(o.osasumma(0,4));

10
7
6
19

Osasumma o = new Osasumma(new int[][]
  {{3,1,7,6},
   {2,8,5,2},
   {5,2,5,4}});
System.out.println(o.osasumma(1,0,2,2));
System.out.println(o.osasumma(1,2,2,3));
System.out.println(o.osasumma(0,2,0,2));
System.out.println(o.osasumma(0,0,2,3));

27
16
7
50

    2   3
     \ /
  5   1
   \ /
    4

    2   3            3
     \ /            /
  5   1    =>  5   1    =>  5   1  =>  5    =>  5
   \ /          \ /          \ /        \
    4            4            4          4

HashMap<Integer, HashSet<Integer>> kuvaus(ArrayList<Integer> kuvaus)

1: 2 3 4
2: 1
3: 1
4: 1 5
5: 4

1: 2 3
2: 1
3: 1 4 5
4: 3 6 7
5: 3
6: 4
7: 4

1--2
|  |
|  |
3--0

1--2
|\
| \
3--0