Helsingin yliopisto, University of Helsinki
MOOC.FI

Viikko 2

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:

ACA CAC GAC TAC
ACG CAG GAG TAG
ACT CAT GAT TAT
AGA CGA GCA TCA
AGC CGC GCG TCG
AGT CGT GCT TCT
ATA CTA GTA TGA
ATC CTC GTC TGC
ATG CTG GTG TGT

Toteutus

Toteuta 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

# metodin kutsu haluttu palautusarvo
1 ketjumaara(3) 36
2 ketjumaara(1) 4
3 ketjumaara(2) 12
4 ketjumaara(5) 324

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 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

# metodin kutsu haluttu palautusarvo
1 ketjumaara("A?C?") 6
2 ketjumaara("???") 36
3 ketjumaara("AGAG") 1
4 ketjumaara("A???T") 20

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 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 6 .

Esimerkit

# metodin kutsu haluttu palautusarvo
1 nopanheitot(4) 8
2 nopanheitot(2) 2
3 nopanheitot(3) 4
4 nopanheitot(1) 1
5 nopanheitot(12) 1936

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 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

# metodin kutsu haluttu palautusarvo
1 jaaOmenat(new int[] {5, 3, 6, 2, 9}) 1
2 jaaOmenat(new int[] {2, 2}) 0
3 jaaOmenat(new int[] {999}) 999
4 jaaOmenat(new int[] {999, 1, 1, 1}) 996

Tehtävä 5

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

Toteutus

Toteuta 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 18 .

Esimerkit

# metodin kutsu haluttu palautusarvo
1 nopanheitot(4) 8
2 nopanheitot(30) 437613522
3 nopanheitot(44) 6386990736226
4 nopanheitot(39) 207991012832
5 nopanheitot(60) 366861197229128136