Helsingin yliopisto, University of Helsinki
MOOC.FI

Viikko 5

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 metodi: boolean etsiSumma(int[] luvut, int x)

Taulukko luvut sisältää 1..10 5 kokonaislukua väliltä –10 9 ..10 9 . Luku x on kokonaisluku väliltä –10 9 ..10 9 .

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

Esimerkit

# metodin kutsu haluttu palautusarvo
1 etsiSumma(new int[] {1, 2, 3}, 5) true
2 etsiSumma(new int[] {1, 2, 3}, 6) false
3 etsiSumma(new int[] {1, 3, 3}, 6) true
4 etsiSumma(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 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..10 5 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 kutsu haluttu palautusarvo
1 reitinPituus("YYVVAAOO") 8
2 reitinPituus("YVAOYVAO") 4
3 reitinPituus("YYYYYYYY") 0
4 reitinPituus("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 metodi: int suurinRyhma(String[] sanat)

Esimerkit

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

Metodin tulee palauttaa suurimman ryhmän koko.

# metodin kutsu haluttu palautusarvo
1 suurinRyhma(new String[] {"apina", "banaani", "cembalo"} 1
2 suurinRyhma(new String[] {"talo", "katu", "lato"} 2
3 suurinRyhma(new String[] {"ab", "ab", "ba", "ba"} 4
4 suurinRyhma(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 metodi: int lyhinPuuttuva(String mjono)

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

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

Esimerkit

# metodin kutsu haluttu palautusarvo
1 lyhinPuuttuva("CCCCCCCC") 1
2 lyhinPuuttuva("ACGTACGT") 2
3 lyhinPuuttuva("ACAAGCAG") 1
4 lyhinPuuttuva("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 metodi: int pisinTasainen(String mjono)

Merkkijono mjono sisältää DNA-ketjun, jonka pituus on 1..10 5 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 kutsu haluttu palautusarvo
1 pisinTasainen("ACGTACGT") 8
2 pisinTasainen("CAATGTCG") 8
3 pisinTasainen("TTATCGTT") 4
4 pisinTasainen("AAAAAAAA") 0