Viikko 2: TMC-tehtävät

Tehtävien deadline: 26.01.2015 01:59.

Tehtävä 1

DNA-ketju on merkkijono, joka muodostuu merkeistä A, C, G ja T.

Tehtäväsi on laskea n-merkkisten DNA-ketjujen määrä, joissa ei ole kahta samaa merkkiä peräkkäin.

Esimerkiksi jos n = 3, ketjujen määrä on 36:

Toteutus

Toteuta seuraava metodi:

int ketjumaara(int n)

Parametri n on ketjun merkkien määrä, kokonaisluku väliltä 1..10.

Metodin tulee palauttaa n-merkkisten DNA-ketjujen määrä, joissa ei ole kahta samaa merkkiä peräkkäin.

Esimerkit

Tehtävä 2

Tehtäväsi on laskea DNA-ketjujen määrä, joissa ei ole kahta samaa merkkiä peräkkäin ja jotka vastaavat annettua pohjaa.

Pohja muodostuu merkeistä A, C, G, T ja ?. Merkki ? tarkoittaa, että siihen kohtaan voi tulla mikä tahansa merkki, kunhan ketjussa ei ole missään kohtaa kahta samaa merkkiä peräkkäin.

Esimerkiksi jos pohja on A?C?, ketjuja on 6:

• AGCA
• AGCG
• AGCT
• ATCA
• ATCG
• ATCT

Toteutus

Toteuta seuraava metodi:

int ketjumaara(String pohja)

Parametri pohja on DNA-ketjun pohja yllä kuvatussa muodossa. Pohjan pituus on 1..10 merkkiä.

Metodin tulee palauttaa pohjaa vastaavien DNA-ketjujen määrä, joissa ei ole kahta samaa merkkiä peräkkäin.

Esimerkit

Tehtävä 3

Uolevi heitti noppaa ja merkitsi silmäluvut muistiin (silmäluku voi olla 1..6). Lopuksi hän laski yhteen kaikkien heittojen silmäluvut ja tuloksena oli luku x. Montako mahdollista heittosarjaa on olemassa, jotka Uolevi on voinut heittää?

Esimerkiksi jos x = 4, Uolevi on voinut heittää jonkin seuraavista sarjoista:

• 4
• 3, 1
• 2, 1, 1
• 2, 2
• 1, 1, 1, 1
• 1, 1, 2
• 1, 2, 1
• 1, 3

Vaihtoehtoja on siis 8.

Toteutus

Toteuta seuraava metodi:

int nopanheitot(int x)

Parametri x on Uolevin laskema silmälukujen summa. Parametri on positiivinen kokonaisluku.

Metodin tulee palauttaa mahdollisten heittosarjojen määrä. Voit olettaa, että tulos on enintään 10⁶.

Esimerkit

Tehtävä 4

Uolevi ja Maija löysivät pussin omenoita. Ensin he punnitsivat jokaisen omenan painon. Sitten he haluaisivat jakaa omenat keskenään niin, että molemmat saisivat mahdollisimman yhtä paljon syötävää. Voisitko auttaa heitä?

Esimerkiksi jos omenoita on 5 ja painot ovat {5, 3, 6, 2, 9}, paras ratkaisu on, että toinen saa omenat {5, 6, 2} (paino yhteensä 13) ja toinen saa omenat {3, 9} (paino yhteensä 12). Näin painojen ero on vain 1.

Toteutus

Toteuta seuraava metodi:

int jaaOmenat(int[] omenat)

Parametri omenat on taulukko, joka sisältää omenoiden painot. Jokainen paino on kokonaisluku välillä 1..1000. Omenoiden määrä on välillä 1..15.

Metodin tulee palauttaa omenoiden yhteispainon ero parhaimmassa jakotavassa.

Esimerkit

Tehtävä 5

Tehtäväsi on toteuttaa tehtävän 3 metodi tehokkaasti.

Toteutus

Toteuta seuraava metodi:

long nopanheitot(int x)

Parametri x on Uolevin laskema silmälukujen summa. Parametri on positiivinen kokonaisluku.

Metodin tulee palauttaa mahdollisten heittosarjojen määrä. Voit olettaa, että tulos on enintään 10¹⁸.

Esimerkit