Viikko 7: TMC-tehtävät

Tehtävien deadline: ma 9.03. klo 01:59 tenttiviikon takia deadlinea siirretty viikolla eteenpäin, huomaathan kuitenkin, että tehtävissä käsiteltävät asiat kuuluvat ensimmäisen kurssikokeen alueeseen.

Viikon teemana on tasapainotetun binäärihakupuun soveltaminen. Huomaathan, että Javan valmiita toteutuksia tietorakenteista SAA käyttää.

Tehtävä 1

Uolevi on alkanut keräillä sarjakuvia ja ostaa usein uusia lehtiä kokoelmaansa. Mutta joskus Uolevi ostaa vahingossa uudestaan sellaisen numeron, joka hänellä on jo valmiina. Tehtäväsi on auttaa Uolevia laskemaan, montako eri numeroa hänen kokoelmassaan on.

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 eriNumerot()
  kertoo, montako eri lehteä Uolevin kokoelmassa on tällä hetkellä

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();
k.lisaaLehti(3);
k.lisaaLehti(4);
k.lisaaLehti(3);
System.out.println(k.eriNumerot());
k.lisaaLehti(5);
System.out.println(k.eriNumerot());
k.lisaaLehti(3);
System.out.println(k.eriNumerot());

Koodin tulostuksen tulisi olla seuraava:

2
3
3

Tehtävä 2

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:

3
3
3
9

Tehtävä 3

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:

1
1
1
4

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

Tehtävä 5

Sinulle on annettu merkkijono, joka muodostuu merkeistä A ja B. Tehtäväsi on selvittää, mikä on pisin samaa merkkiä toistava osa merkkijonossa.

Tämä on vielä helppoa, mutta lisähaasteena on, että merkkijonon merkkejä pystyy muuttamaan ja sinun täytyy pystyä etsimään pisin samaa merkkiä toistava osa tehokkaasti joka muutoksen jälkeen.

Toteutus

Toteuta luokka PisinToisto, joka tarjoaa seuraavat metodit:

• PisinToisto(String mjono)
  konstruktori, jolle annetaan merkkijonon alkusisältö mjono (1..10⁵ merkkiä, jokainen merkki A tai B)
• void muutaMerkki(int kohta)
  muuttaa kohdassa kohta olevan merkin käänteiseksi (A:sta tulee B ja B:stä tulee A)
• int pisinToisto()
  palauttaa pisimmän toiston pituuden tämänhetkisessä merkkijonossa

Metodeita muutaMerkki ja pisinToisto kutsutaan korkeintaan 10⁵ kertaa testauksessa.

Esimerkki

Seuraava koodi testaa metodeita:

PisinToisto etsija = new PisinToisto("AABBBA");
System.out.println(etsija.pisinToisto());
etsija.muutaMerkki(3); // AABABA
System.out.println(etsija.pisinToisto());
etsija.muutaMerkki(0); // BABABA
System.out.println(etsija.pisinToisto());
etsija.muutaMerkki(2); // BAAABA
System.out.println(etsija.pisinToisto());
etsija.muutaMerkki(4); // BAAAAA
System.out.println(etsija.pisinToisto());                                                                                

Koodin tulostuksen tulisi olla seuraava:

3
2
1
3
5