TMC BONUSVIIKKO

Tehtävien deadline: ma 16.3. klo 01:59

Tehtävä 1

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. Aikavaativuuden tulisi olla O(n), missä n on listan pituus. 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).

Tehtävä 2

Sinulle on annettu taulukko kokonaislukuja ja tehtäväsi on järjestää se pienimmästä suurimpaan. Ainoa sallittu operaatio on kahden vierekkäisen luvun järjestyksen kääntäminen. Kuinka monta kääntöä tarvitset vähintään taulukon järjestämiseksi?

Esimerkiksi jos taulukko on {1, 5, 2, 4, 3}, riittää tehdä 4 kääntöä:

1. kääntö 5<->2, tulos {1, 2, 5, 4, 3}
2. kääntö 4<->3, tulos {1, 2, 5, 3, 4}
3. kääntö 5<->3, tulos {1, 2, 3, 5, 4}
4. kääntö 5<->4, tulos {1, 2, 3, 4, 5}

Toteutus

Toteuta seuraava metodi:

int laskeKaannot(int[] luvut)

Taulukko luvut sisältää 1..1000 kokonaislukua väliltä 1..10⁹.

Metodin tulee palauttaa pienin kääntöjen määrä, jolla taulukon saa järjestykseen.

Esimerkit

Tehtävä 3

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

      4
    3   2
  1   3   5
3   4   1   10

      4
    3   2
  1   3   5
3   4   1   10

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), missä n on pyramidin korkeus.

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

Tehtävä 4

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

Tehtävä 5

Tehtäväsi on toteuttaa tehtävän 2 metodi tehokkaasti.

Toteutus

Toteuta seuraava metodi:

long laskeKaannot(int[] luvut)

Taulukko luvut sisältää 1..10⁵ kokonaislukua väliltä 1..10⁹.

Huomaathan että vastaus voi olla niin suuri, ettei se mahdu int -muuttujaan. Käytä siis longeja!

Vinkki: lomitusjärjestäminen.