Viikko 7: TMC-tehtävät

Deadline 2.11 04:01

Viikon teemana on tasapainotetun binäärihakupuun soveltaminen, sekä puut ongelmanratkaisussa. Huomaathan, että Javan valmiita toteutuksia tietorakenteista SAA käyttää. Javassa tasapainotettua binäärihakupuuta soveltavat esim. TreeMap ja TreeSet

Tehtävä 1

Uolevi on alkanut keräillä sarjakuvia ja ostaa usein uusia lehtiä kokoelmaansa. Joskus Uolevi haluaisi lukea lehden numeron, joka puuttuu hänen kokoelmastaan. Silloin hän valitsee lehden, jonka numero on mahdollisimman lähellä haluttua numeroa. Tehtäväsi on auttaa Uolevia lehden valinnassa.

Toteutus

Toteuta luokka Kokoelma, joka tarjoaa seuraavat metodit:

void lisaaLehti(int numero)
Uolevi ostaa lehden, jonka numero on numero (kokonaisluku väliltä 1..10⁹)
int valitseLehti(int numero)
palauttaa Uolevin kokoelmassa olevan lehden, jonka numero on mahdollisimman lähellä parametria numero (kokonaisluku väliltä 1..10⁹)

Aluksi Uolevin kokoelmassa ei ole yhtään lehteä.

Testauksessa metodeita kutsutaan yhteensä enintään 10⁵ kertaa. Metodia valitseLehti ei kutsuta ennen kuin lehtiä on ainakin yksi. Jos vaihtoehtoja on kaksi, valitse niistä pienempi.

Esimerkki

Seuraava koodi testaa luokkaa:

Kokoelma k = new Kokoelma();
k.lisaaLehti(3);
System.out.println(k.valitseLehti(4));
System.out.println(k.valitseLehti(8));
k.lisaaLehti(9);
System.out.println(k.valitseLehti(4));
System.out.println(k.valitseLehti(8));

Koodin tulostuksen tulisi olla seuraava:

Tehtävä 2

Aiemmin julkaistut lehdet ovat Uolevin mielestä parhaita, minkä vuoksi hän haluaisi saada kokoelmansa täydelliseksi ainakin niiden osalta. Auta Uolevia selvittämään, mikä on pienin kokoelmasta puuttuva numero.

Toteutus

Toteuta luokka Kokoelma, joka tarjoaa seuraavat metodit:

void lisaaLehti(int numero)
Uolevi ostaa lehden, jonka numero on numero (kokonaisluku väliltä 1..10⁹)
int pieninPuuttuva()
palauttaa pienimmän lehden numeron, joka puuttuu vielä Uolevin kokoelmasta

Aluksi Uolevin kokoelmassa ei ole yhtään lehteä.

Testauksessa metodeita kutsutaan yhteensä enintään 10⁵ kertaa.

Esimerkki

Seuraava koodi testaa luokkaa:

Kokoelma k = new Kokoelma();
System.out.println(k.pieninPuuttuva());
k.lisaaLehti(3);
System.out.println(k.pieninPuuttuva());
k.lisaaLehti(2);
System.out.println(k.pieninPuuttuva());
k.lisaaLehti(1);
System.out.println(k.pieninPuuttuva());

Koodin tulostuksen tulisi olla seuraava:

Tehtävä 3

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!

Tehtävä 4

Maahan on pudonnut omenoita, ja tehtäväsi on kerätä ne koreihin. Tiedät jokaisesta omenasta, kuinka painava se on. Voit laittaa jokaiseen koriin 1 tai 2 omenaa. Lisäksi omenoiden paino korissa ei saa ylittää annettua rajaa. Kuinka monta koria tarvitset vähintään?

Esimerkiksi jos omenoiden painot ovat {1, 2, 3, 4, 5} ja korin painoraja on 5, tarvitset 3 koria: {1, 4}, {2, 3} ja {5}.

Toteutus

Toteuta seuraava metodi:

int korienMaara(int[] omenat, int raja)

Taulukko omenat sisältää omenoiden painot. Omenoiden määrä on välillä 1..10⁵ ja jokainen paino on välillä 1..10⁹.

Parametri raja on suurin sallittu korin omenoiden paino. Raja on välillä 1..10⁹, ja minkään omenan paino ei ole tätä suurempi.

Metodin tulee palauttaa pienin mahdollinen korien määrä.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`korienMaara(new int[] {1, 2, 3, 4, 5}, 5)`	`3`
2	`korienMaara(new int[] {2, 2, 3, 4, 5}, 5)`	`4`
3	`korienMaara(new int[] {1, 1, 1, 1, 1}, 5)`	`3`
4	`korienMaara(new int[] {3, 3, 3, 3, 3}, 5)`	`5`
5	`korienMaara(new int[] {5, 5, 5, 5, 5}, 5)`	`5`

Tehtävä 5

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