Viikko 8: TMC-tehtävät

Tehtävien deadline: ma 9.11. klo 04:01

Tämän viikon tehtävä 1 liittyy ongelmanratkaisuun puissa ja loput tehtävät kekoon.

Tehtävä 1

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.

Ohjelman pitäisi silti pystyä tulostamaan kaikki palindromit alle sekunnissa

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

Tehtävä 2

Asunnonvälitystoimisto toimii seuraavasti: kullekin henkilölle määritellään jonoon liittyessä kiireellisyysarvo. Asunnon vapautuessa sen saa henkilö, jonka kiireellisyysarvo on suurin. Jos monella henkilöllä on yhtä suuri kiireellisyysarvo, asunnon saa aakkosissa ensimmäinen henkilö. Jos monella henkilöllä on sama nimi, kuka tahansa heistä voi saada asunnon.

Toteutus

Toteuta luokka Toimisto, joka tarjoaa seuraavat metodit:

void lisaaJonoon(String nimi, int kiire)
lisää henkilön nimeltä nimi jonoon kiireellisyysarvolla kiire
String annaAsunto()
palauttaa henkilön nimen, joka saa vapautuvan asunnon

Jokainen nimi muodostuu kirjaimista a..z. Nimen ensimmäinen kirjain on iso ja kaikki muut pieniä. Nimen pituus on enintään 10 kirjainta.

Kiireellisyysarvo on kokonaisluku välillä 1..10⁹. Mitä suurempi luku on, sitä kiireellisempi henkilön tilanne on.

Testauksessa metodeita kutsutaan enintään 10⁵ kertaa.

Esimerkki

Seuraava koodi testaa luokkaa:

Toimisto t = new Toimisto();
t.lisaaJonoon("Uolevi", 8);
t.lisaaJonoon("Maija", 4);
System.out.println(t.annaAsunto());
t.lisaaJonoon("Liisa", 5);
System.out.println(t.annaAsunto());
System.out.println(t.annaAsunto());

Koodin tulostuksen tulisi olla seuraava:

Uolevi
Liisa
Maija

Tehtävä 3

Tämä tehtävä käsittelee lukuja, jotka saadaan kertomalla lukuja 2 ja 3. Ensimmäiset tällaiset luvut ovat:

2
3
4 = 2·2
6 = 2·3
8 = 2·2·2
9 = 3·3
12 = 2·2·3

Tehtäväsi on selvittää järjestyksessä n. tällainen luku.

Toteutus

Toteuta seuraava metodi:

long etsiTulo(int n)

Parametri n määrittää, monesko luku metodin tulee palauttaa. Kaikissa testeissä n on välillä 1..1000 ja vastaus mahtuu long-muuttujaan.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`etsiTulo(2)`	`3`
2	`etsiTulo(20)`	`108`
3	`etsiTulo(49)`	`2304`
4	`etsiTulo(200)`	`15925248`

Tehtävä 4

Tehtaassa on koneita, joista jokainen pystyy valmistamaan yhden tuotteen tietyssä ajassa. Tehtäväsi on valmistaa mahdollisimman nopeasti annettu määrä tuotteita käyttämällä koneita parhaalla mahdollisella tavalla.

Oletetaan että koneet ovat seuraavat:

kone	toiminta-aika
A	1
B	2
C	3
D	4

Kun haluat valmistaa 10 tuotetta, yksi optimaalisista tavoista on seuraava:

ajanhetki	tapahtumat
0	Laitat käyntiin koneet A, B, C ja D.
1	Kone A saa valmiiksi tuotteen. Laitat uudestaan käyntiin koneen A. (1 tuote valmiina.)
2	Koneet A ja B saavat valmiiksi tuotteen. Laitat uudestaan käyntiin koneet A ja B. (3 tuotetta valmiina.)
3	Koneet A ja C saavat valmiiksi tuotteen. Laitat uudestaan käyntiin koneet A ja C. (5 tuotetta valmiina.)
4	Koneet A, B ja D saavat valmiiksi tuotteen. Laitat uudestaan käyntiin koneen B. (8 tuotetta valmiina.)
5	Käyt Facebookissa.
6	Koneet B ja C saavat valmiiksi tuotteen. (10 tuotetta valmiina.) Tehtävä suoritettu!

Toteutus

Toteuta seuraava metodi:

long lyhinAika(int[] koneet, int maara)

Taulukko koneet sisältää tiedon, kuinka kauan kullakin koneella menee valmistaa tuote. Koneiden määrä on välillä 1..10⁵. Jokainen taulukon arvo on kokonaisluku välillä 1..10⁹.

Kokonaisluku maara on valmistettava tuotteiden määrä. Tämä luku on välillä 1..10⁵.

Metodin tulee palauttaa pienin mahdollinen aika, jossa saat valmistettua tuotteet koneiden avulla.

Esimerkit

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

Tehtävä 5

Tehtäväsi on toteuttaa luokka, joka tarjoaa kaksi toimintoa: uuden luvun lisääminen sekä mediaanin laskeminen kaikista lisätyistä luvuista.

Mediaani tarkoittaa lukua, joka on keskimmäisenä, jos kaikki luvut järjestetään pienimmästä suurimpaan.

Jos lukujen määrä on parillinen, mediaani ei ole yksikäsitteinen. Tässä tehtävässä tulkintana on, että mediaani on silloin vasemmanpuoleinen luku kahdesta keskimmäisestä.

Toteutus

Toteuta luokka Mediaani, joka tarjoaa seuraavat metodit:

void lisaaLuku(int luku):
lisää uuden luvun (kokonaisluku väliltä 1..10⁹)
int mediaani():
palauttaa mediaanin lisätyistä luvuista

Testauksessa metodeita kutsutaan enintään 10⁵ kertaa.

Esimerkki

Seuraava koodi testaa luokkaa:

Mediaani m = new Mediaani();
m.lisaaLuku(1);
System.out.println(m.mediaani());
m.lisaaLuku(5);
m.lisaaLuku(4);
System.out.println(m.mediaani());

Koodin tulostuksen tulisi olla seuraava:

1
4