Viikko 5: TMC-tehtävät

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

Viikon teemana on hajautusrakenteiden ja yleisemmin hajautuksen soveltaminen.


Tehtävä 1

Sinulle on annettu taulukko kokonaislukuja, ja tehtäväsi on selvittää, onko taulukossa kahta lukua, joiden summa on x.

Esimerkiksi jos taulukko on {3, 4, 2, 8} ja x on 5, voidaan valita luvut 3 ja 2.

Toteutus

Toteuta seuraava metodi:

boolean etsiSumma(int[] luvut, int x)

Taulukko luvut sisältää 1..105 kokonaislukua väliltä –109..109. Luku x on kokonaisluku väliltä –109..109.

Metodin tulee palauttaa true, jos summan saa kahdesta luvusta, ja muuten false.

Esimerkit

#metodin kutsuhaluttu palautusarvo
1etsiSumma(new int[] {1, 2, 3}, 5)true
2etsiSumma(new int[] {1, 2, 3}, 6)false
3etsiSumma(new int[] {1, 3, 3}, 6)true
4etsiSumma(new int[] {1, 2, 3}, 6)false

Tehtävä 2

Uolevi on äärettömässä ruudukossa ja lähtee liikkeelle ruudusta (0, 0). Hän kulkee joka askeleella yhden ruudun vasemmalle, oikealle, ylöspäin tai alaspäin. Milloin Uolevi palaa ruutuun, jossa hän on ollut aiemmin (mihin tahansa matkan varrella olleeseen ruutuun)?

Toteutus

Toteuta seuraava metodi:

int reitinPituus(String reitti)

Parametri reitti kuvaa Uolevin reitin. Se sisältää järjestyksessä suunnat, joihin Uolevi liikkuu. Jokainen suunta on yksi merkeistä V, O, Y ja A. Merkkijonon pituus on 1..105 merkkiä.

Metodin tulee palauttaa, montako askelta Uolevi liikkuu, ennen kuin hän palaa uudestaan samaan ruutuun. Jos Uolevi ei palaa koskaan samaan ruutuun reitin aikana, metodin tulee palauttaa 0.

Esimerkit

#metodin kutsuhaluttu palautusarvo
1reitinPituus("YYVVAAOO")8
2reitinPituus("YVAOYVAO")4
3reitinPituus("YYYYYYYY")0
4reitinPituus("OYVVAOOO")6

Tehtävä 3

Sinulle on annettu taulukko sanoja, ja tehtäväsi on etsiä siitä suurin mahdollinen ryhmä anagrammeja eli sanoja, joissa on jokaista kirjainta yhtä monta.

Esimerkiksi jos sanat ovat {"talo", "katu", "lato"}, suurin ryhmä on {"talo", "lato"} ja siinä on kaksi sanaa.

Toteutus

Toteuta seuraava metodi:

int suurinRyhma(String[] sanat)

Sanojen määrä on 1..105, ja jokaisessa sanassa on 1..10 kirjainta väliltä a..z.

Metodin tulee palauttaa suurimman ryhmän koko.

Esimerkit

#metodin kutsuhaluttu palautusarvo
1suurinRyhma(new String[] {"apina", "banaani", "cembalo"}1
2suurinRyhma(new String[] {"talo", "katu", "lato"}2
3suurinRyhma(new String[] {"ab", "ab", "ba", "ba"}4
4suurinRyhma(new String[] {"iines", "otto", "sieni", "toto"}2

Tehtävä 4

Sinulle on annettu DNA-ketju, joka muodostuu merkeistä A, C, G ja T. Tehtäväsi on selvittää, kuinka pitkä on lyhin DNA-ketju, joka ei ole annetun ketjun osajonona.

Esimerkiksi DNA-ketju ACGTACGT sisältää osajonona kaikki 1:n pituiset DNA-ketjut eli A, C, G ja T. Kahden pituiset osajonot ovat järjestyksessä AC, CG, GT, TA, AC, CG ja GT, eli esimerkiksi ketju AA puuttuu osajonoista. Niinpä lyhimmän ketjun pituus on 2.

Toteutus

Toteuta seuraava metodi:

int lyhinPuuttuva(String mjono)

Merkkijono mjono on DNA-ketju, jonka pituus on 1..105 merkkiä.

Metodin tulee palauttaa lyhimmän ketjun pituus, joka ei ole osajonona annetussa ketjussa.

Esimerkit

#metodin kutsuhaluttu palautusarvo
1lyhinPuuttuva("CCCCCCCC")1
2lyhinPuuttuva("ACGTACGT")2
3lyhinPuuttuva("ACAAGCAG")1
4lyhinPuuttuva("ACACACGT")2

VINKKI: javan String.substring(beginIndex, endIndex) metodista saattaa olla hyötyä.


Tehtävä 5

Sinulle on annettu DNA-ketju, ja tehtäväsi on etsiä siitä pisin osajono, jossa on yhtä monta jokaista merkkiä A, C, G ja T.

Esimerkiksi ketjussa ACGTACGT pisin osajono on koko ketju, jossa on 2 kertaa jokaista merkkiä. Vastaavasti ketjussa TTATCGTT pisin osajono on ATCG, jossa on kerran jokaista merkkiä.

Toteutus

Toteuta seuraava metodi:

int pisinTasainen(String mjono)

Merkkijono mjono sisältää DNA-ketjun, jonka pituus on 1..105 merkkiä.

Metodin tulee palauttaa pisimmän osajonon pituus, jossa on jokaista merkkiä yhtä monta. Jos mitään tällaista osajonoa ei ole, metodin tulee palauttaa 0.

Esimerkit

#metodin kutsuhaluttu palautusarvo
1pisinTasainen("ACGTACGT")8
2pisinTasainen("CAATGTCG")8
3pisinTasainen("TTATCGTT")4
4pisinTasainen("AAAAAAAA")0