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

Ohjelmointitehtävät, viikko 9

1. Huoneitten laskeminen

Saat talon pohjapiirustuksen. Tehtävänäsi on laskea, montako huonetta talossa on. Huone tarkoittaa yhtenäistä seinien rajaamaa lattiatilaa.

Toteuta metodi int huoneet(char[][] talo), joka palauttaa huoneitten lukumäärän. Pohjapiirroksessa merkki '#' tarkoittaa seinää ja merkki '.' lattiaa.

Huom: juuri kartan reunojen ulkopuolella on (implisiittiset) seinät. Siis esimerkiksi seuraavassa kartassa on kaksi huonetta:

.
#
.

Esimerkki 1

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

Huoneita: 3

Esimerkki 2

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

Huoneita: 1

2. Huoneiden koot

Tällä kertaa huoneitten laskemisen sijaan on tehtävänä laskea huoneitten koot. Toteuta metodi ArrayList<Integer> koot(char[][] talo) joka palauttaa huoneitten koot (jossain järjestyksessä) ArrayListissä.

Talon pohjapiirros annetaan ohjelmalle samassa muodossa kuin edellisessä tehtävässä.

Esimerkki 1

Pohjapiirros:

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

Huoneiden koot: 6,6,1

Tässä talossa on kaksi huonetta, joiden koko on 6 ruutua, ja yksi huone, jonka koko on 1 ruutu.

Esimerkki 2

Pohjapiirros:

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

Huoneiden koot: 3,2,2,1,1,1,1

3. Ratsu

Huom! testissä ollut 5,5,4,4-tapaus korjattu!

Ratsu liikkuu shakkilaudalla kulkemalla kaksi ruutua johonkin suuntaan (vasen, oikea, ylös alas), ja sitten yhden ruudun edellisen suunnan kanssa suorassa kulmassa olevaan suuntaan. Seuraavassa on piirretty ratsun (R) kaikki mahdolliset seuraavat ruudut (x):

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

Tehtävänäsi on etsiä ratsun lyhin reitti annetusta 8x8 shakkilaudan ruudusta toiseen. Toteuta metodi int ratsu(int x0, int y0, int x1, int y1), joka palauttaa lyhimmän reitin pituuden lähtöruudusta (x0,y0) maaliruutuun (x1,y1).

Esimerkkejä

ratsu(0,0,1,2)=1

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

ratsu(0,0,7,7)=6 (samanpituisia reittejä on toki useita)

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

4. Putkirikko

Talossa on hajonnut vesiputkia. Tee ohjelma. Tehtävänäsi on laskea, kuinka kauan kestää, ennen kuin koko talo (kaikki lattiaruudut) on veden vallassa.

Talon pohjapiirros annetaan samassa muodossa kuin aiemmissa tehtävissä, mutta merkki P tarkoittaa hajonnutta putkea. Vesi etenee talossa niin, että jos tietyssä lattiaruudussa on vettä, seuraavalla kierroksella myös kaikissa ruudun naapuriruuduissa on vettä.

Toteuta metodi int putkirikko(char[][] talo), joka laskee montako kierrosta menee kaikkien lattiaruutujen peittymiseen.

Voit olettaa, että hajonneista putkista on yhteys kaikkiin talon lattiaruutuihin.

Esimerkki 1

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

Kesto: 5

Seuraavaan kuvaan on merkitty ajanhetket, joina vesi saavuttaa talon lattiaruudut yllä olevassa tapauksessa:

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

Esimerkki 2

Pohjapiirros:

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

Kesto: 2

5. Tehokas osasumma

Huom!! tässä tehtävässä on tarkoitus tehdä ratkaisu jonka muistinkäyttö on alle O(n^2). Triviaali ratkaisu jossa taulukoidaan kaikki osasummat erikseen ei siis toimi. On olemassa yksinkertainen ratkaisu joka käyttä O(n) muistia.

Tehtävänä on suunnitella yksiulotteisen taulukon tapainen tietorakenne. Kuitenkin vaatimuksena on, että käytettävissä on tehokas komento osasumma(a, b), jolle annetaan alku- ja loppukohta taulukossa ja joka palauttaa vastaavien lukujen summan. Komennon aikavaativuuden tulee olla O(1). Tietorakenteen sisältö ei tule muuttumaan sen luonnin jälkeen.

Tarkastellaan esimerkiksi seuraavaa taulukkoa:

5

2

6

2

4

Nyt esimerkiksi komento osasumma(1, 3) palauttaa taulukon lukujen summan kohdasta 1 kohtaan 3. Tuloksen tulisi olla 2 + 6 + 2 = 10. Taulukon indeksointi alkaa siis tässä nollasta.

Tee luokka Osasumma, jolla on:

• Konstruktori Osasumma(int[] taulukko)
• Metodi get(int i), joka palauttaa taulukon i:nnen alkion
• Metodi osasumma(int a, int b), joka palauttaa taulukon alkioissa a,a+1,...,b olevien arvojen summan.

Voit olettaa että taulukossa on korkeintaan miljoona int-lukua ja että summa mahtuu int-tyyppiseen muuttujaan.

Huom! Ohjelmasta tulee aivan liian hidas, jos taulukko tallennetaan sellaisenaan ja jokainenosasumma-kutsu käy läpi taulukon annetun kohtien välillä. Silloinhan aikavaativuus on O(n), mutta vaativuuden tulisi olla O(1).

Esimerkki

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));

Tulostus:

10
7
6
19

6. Tehokas osasumma II

Huom! samoin kuin ed. tehtävässä, käytä muistia säästeliäästi, t.s. O(mn), missä m on taulukon korkeus ja n leveys.

Tee luokka Osasumma, jonka toiminta vastaa edellistä tehtävää, mutta tällä kertaa taulukko on kaksiulotteinen. Komennon osasumma tulee palauttaa minkä tahansa taulukon osana olevan suorakulmion lukujen summa ajassa O(1). Voit olettaa että taulukon korkeus ja leveys ovat korkeintaan 1000 ja pyydetyt summat mahtuvat int-tyyppiseen muuttujaan.

Tarkastellaan esimerkiksi seuraavaa taulukkoa:

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

Nyt esimerkiksi komento osasumma(1, 0, 2, 2) palauttaa taulukon lukujen summan suorakulmiossa, jonka vasen ylänurkka on kohdassa (1, 0) ja oikea alanurkka on kohdassa (2, 2). Tuloksen tulisi olla 2 + 8 + 5 + 5 + 2 + 5 = 27. Tässä taulukon kohdan esitysmuoto on (y, x), eli ensin tulee rivi ja sitten sarake.

Esimerkki

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));

Tulostus:

27
16
7
50

PS. Osaatko yleistää tekniikan niin, että osasumma toimii ajassa O(1) minkä tahansa ulotteisilla taulukoilla?

7. Verkon kuvaus

Tarkastellaan yhtenäistä syklitöntä verkkoa, jossa on n solmua. Verkon solmujen tunnukset ovat 1...n. Tällaiselle verkolle voidaan muodostaa lyhyt kuvaus poistamalla sen solmut tietyssä järjestyksessä.

Ideana on poistaa verkosta yksi kerrallaan solmuja, joiden asteluku on 1 (eli solmusta lähtee vain yksi kaari). Jos vaihtoehtoja on useita, valitaan solmu, jonka tunnus on pienin. Poistamista jatketaan, kunnes verkossa on jäljellä enää yksi solmu. Joka poistamisen yhteydessä merkitään muistiin poistettavan solmun viereisen solmun tunnus, ja tästä muodostuu verkon kuvaus.

Tarkastellaan esimerkiksi seuraavaa verkkoa:

    2   3
     \ /
  5   1
   \ /
    4

Kuvaus verkon rakenteesta muodostuu seuraavasti:

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

Jokaisessa vaiheessa punaisella on merkitty poistettavan solmun viereinen solmu. Näistä muodostuu verkon kuvaus eli tässä tapauksessa1 1 4 5.

Tee metodi

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

jolle annetaan yllä kuvattu kuvaus verkosta ja joka palauttaa verkon vieruslistaesityksen. Vierulistaesitys tarkoittaa tässä tapauksessa sitä että kun kuvaus palauttaa HashMapin hm, on hm.get(i) solmun i naapureitten (tunnisteitten) joukko.

Esimerkki 1

Kuvaus: 1 1 4 5

Vieruslistat:

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

Esimerkki 2

Kuvaus: 1 3 3 4 4 7

Vieruslistat:

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

8. Hamiltonin kierros

Hamiltonin kierros on verkossa oleva polku, joka alkaa jostain solmusta, käy kaikissa muissa solmuissa tasan kerran ja palaa sitten takaisin lähtösolmuun.

Tee metodi boolean hamilton(TreeMap<Integer, TreeSet<Integer>> verkko), joka tutkii, onko suuntaamattomassa verkossa Hamiltonin kierrosta. Verkko esitetään kuten ed. tehtävässä mappina jonka sisällä on settejä. Voit olettaa, että verkon solmut on numeroitu kokonaisluvuin 0... n-1 ja n on korkeintaan 10.

Esimerkki 1

Tässä verkossa on hamiltonin kierros:

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

Hamiltonin kierros on esimerkiksi 1 -> 2 -> 0 -> 3 -> 1.

Esimerkki 2

Tässä verkossa ei ole Hamiltonin kierrosta:

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

Ohjelmointitehtävät, viikko 10

1. Tietoverkko

Tee metodi boolean tietoverkko(boolean[][] verkko), jolle annetaan kuvaus tietoverkosta ja joka tarkistaa, pystyvätkö kaikki verkon koneet viestimään keskenään. Toisin sanoen ohjelman tulee tarkistaa, onko verkko yhtenäinen.

Verkossa on n konetta, jotka on numeroitu kokonaisluvuin 0...n-1. Voit olettaa, että n on korkeintaan 1000.

Verkon kuvaus on vierusmatriisi, eli kaksiulotteinen taulukko verkko, jossa verkko[i][j] on true jos koneitten i ja j välillä menee yhteys.

Esimerkki 1

Tämän verkon vierusmatriisi:

    3
   /|\
  4 | 0
   \|/ \
    1---2

on:

01110
10111
11000
11001
01010

ja verkko on yhtenäinen.

Esimerkki 2

Tämän verkon vierusmatriisi:

    3
   /|
  4 |   0
   \|   |
    1   2

on:

00100
00011
10000
01001
01010

ja verkko ei ole yhtenäinen.

2. Esitiedot 1

Opintosuunnittelija Keijo Kojootti suunnittelee kurssien esitietovaatimuksia. Tee hänen avukseen ohjelma, joka tarkastaa, onko esitiedoissa sykli.

Toteuta metodi public boolean sykli(Esitieto[] esitiedot), joka palauttaa true jos annetuissa esitiedoissa on sykli. Esitiedot on esitetty taulukkona Esitieto-olioita. Esitieto-oliot toimivat siten, että kurssi e.esi tulee suorittaa ennen kurssia e.kurssi.

Esimerkki

Seuraavissa esitiedoissa ei ole sykliä:

a b
b c
a d
d c
d b
c e

Seuraavissa esitiedoissa taas on sykli:

a b
b c
a d
d c
d b
c a

3. Esitiedot 2

Tällä kertaa tehtävänäsi on selvittää jokin käypä järjestys kurssien käymiseen, kun kurssien väliset esitiedot on annettu. Toteuta siis metodi ArrayList<String> jarjestys(Esitieto[] esitiedot). Voit olettaa että annetuissa esitiedoissa ei ole sykliä.

Esimerkki 1

Esitietojen

a b
b c
a d
d c
d b
c e

eräs käypä suoritusjärjestys on a d b c e

Esimerkki 2

Esitietojen

ohpe ohja
ohja tira
tira lama
tira tiralabra
ohja javalabra
javalabra tiralabra
ohpe ohma
tiralabra ohtuprojekti
javalabra ohtuprojekti
ohma ohtu
ohtu ohtuprojekti
lama ohtuprojekti

eräs käypä suoritusjärjestys on

ohpe ohja javalabra tira tiralabra lama ohma ohtu ohtuprojekti

4. Eulerin kierros

Eulerin kierros verkossa on polku, joka kulkee jokaista kaarta pitkin täsmälleen kerran ja saapuu takaisin lähtöruutuun.

Toteuta metodi ArrayList<Integer> eulerinKierros(boolean[][] verkko), joka palauttaa verkon jonkin Eulerin kierroksen. (Voit olettaa että sellainen on olemassa.) Syötteenä oleva verkko on esitetty vierusmatriisina -- samoin kuin tehtävässä 1.

Esimerkki 1

Graafi:

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

Vierusmatriisi:

0101
1010
0101
1010

Eräs Eulerin kierros: 0,1,2,3

Esimerkki 2

0--1
|  |
|  |
3--2--4
   |  |
   |  |
   5--6

Vierusmatriisi:

0101000
1010000
0101110
1010000
0010001
0010001
0000110

Eräs Eulerin kierros: 0,1,2,5,6,4,2,3

Esimerkki 3

  __0_____ 
 / / \    \ 
2-3  4     5  6--7
      \_____\ /_/
             1

00111100
00001111
10010000
10100000
11000000
11000000
01000001
01000010

Eräs Eulerin kierros: 0,2,3,0,4,1,7,6,1,5

1 2 3 4 5
      2 1 3 3 6
      3 3 9 3 9
      4 3 2 4 7
      5 7 5 9 6

s -> v[0] -> v[1] -> ... -> v[n] -> t

kurssit[v[0]][s] * kurssit[v[1]][v[0]] * ... * kurssit[t][v[n]]

X    2.1  3.0
0.4  X    1.5
0.3  0.6  X

      Anna luku: 10
      Seuraava alkuluku: 11
      

      Anna luku: 123
      Seuraava alkuluku: 127
      

Anna luku:
      10
      Seuraava alkuluku: 11

Anna luku:
      123
      Seuraava alkuluku: 127

Ohjelmointitehtävät, viikko 12

1. Tieverkosto

Saat kuvauksen pienen itäeurooppalaisen maan tieverkostosta ja tehtävänäsi on tuottaa kaikkien kaupunkien väliset lyhimmät etäisyydet.

Tieverkosto kuvataan kaksiulotteisena talukkona int[][] tiet, jossa tiet[i][j] = 0 jos kaupunkien nro i ja j välillä ei ole tietä, ja tiet[i][j] = x kun kaupunkien välillä on tie jonka pituus on x kilometria.

Sinun tulee tuottaa kaksiulotteinen taulukko etaisyydet, jossa etaisyydet[i][j] on kaupunkien i ja j välisen lyhimmän reitin pituus, tai 0 jos kaupunkien välillä ei ole reittiä.

Esimerkki 1

Syöte:

0 1 0
1 0 2
0 2 0

Tuloste:

0 1 3
1 0 2
3 2 0

Tämä vastaa seuraavaa verkkoa:

   1km     2km
0 ----- 1 ----- 2

Esimerkki 2

Syöte:

0 1 0 0
1 0 0 0
0 0 0 2
0 0 2 0

Tuloste:

0 1 0 0
1 0 0 0
0 0 0 2
0 0 2 0

Tämä vastaa seuraavaa verkkoa:

   1km            2km
0 ----- 1      2 ----- 3

Esimerkki 3

Syöte:

0 1 7 0 0
1 0 0 4 2
7 0 0 1 0
0 4 1 0 1
0 2 0 1 0

Tuloste:

0 1 5 4 3
1 0 4 3 2
5 4 0 1 2
4 3 1 0 1
3 2 2 1 0

Tämä vastaa seuraavaa verkkoa:

     1km      2km
  0 ------ 1 ----- 4
   \        \     /
7km \    4km \   / 1km
     \        \ /
      2 ------ 3
         1km

2. Tieverkosto 2

Tässä tehtävässä laajennetaan edellistä siten, että myös kaupunkien väliset lyhimmät reitit saadaan laskettua.

Toteuta luokka Tieverkosto, jolla on:

• konstruktori Tieverkosto(int[][] tiet)
• metodi int etaisyys(int i, int j), joka palauttaa lyhimmän etäisyyden kaupunkien i ja j välillä.
• metodi ArrayList<Integer> reitti(int i, int j), joka palauttaa lyhimmän reitin kaupunkien i ja j välillä

Metodien etaisyys ja reitti tulisi toimia nopeasti. Laske kaikki tarvittava informaatio konstruktorissa.

Vihje älä kuitenkaan luo arrayListejä konstruktorissa - vaan laske kaikki niiden nopeaan luontiin vaadittava konstruktorissa.

Esimerkki

Edellisen tehtävän esimerkin verkolle:

     1km      2km
  0 ------ 1 ----- 4
   \        \     /
7km \    4km \   / 1km
     \        \ /
      2 ------ 3
         1km

Lyhin reitti solmusta 0 solmuun 2 on 0, 1, 4, 3, 2

3. Robotti-imuri

Kaupoissa on ollut jo muutaman vuoden robotti-imureita, jotka imuroivat huoneiston automaattisesti. Tarkastellaan seuraavaa yksinkertaista robotti-imurin tehtävää

Imuroitavan huoneiston pohjapiirros esitetään ruukukkona

.E..
      .S..
      ..S.
      .E..

Jossa

• . tarkoittaa lattiaa
• S tarkoittaa seinää tai muuta estettä, joka robotti-imurin on kierrettävä
• E tarkoittaa söhköpistoketta, jossa robotti voi käydä lataamassa akkuaan. (ruudussa vierailun voidaan ajatella lataavan robotin akun täyteen)

Robotissa on näet akku, jonka kapasiteetti on A energiayksikköä. Robotti voi siirtyä nykyisestä ruudustaan naapuriruutuihin, ei kuitenkaan kulmittain. Jokainen siirtymä kuluttaa akusta yhden energiayksikön. Jos akku pääsee tyhjentymään, sammuu robotti, eikä se enää pysty jatkamaan siivoamista.

Toteuta luokkaan RobottiImuri metodi public boolean loytyykoReitti(int x, int y) , joka tarkastaa, onko robotin mahdollista imuroida koko huoneisto, siten että robotti aloittaa liikkumisen parametrinä annetusta ruudusta, jossa on sähköpistoke, kiertää koko huoneiston ja palaa takaisin lähtöruutuun. Metodi palauttaa true, mikäli tällainen reitti löytyy. Robotti saa konstruktoriinsa parametrina Huoneiston pohjapiirroksen ja akkukeston.