Viikko 2: TMC-tehtävät

Tehtävien deadline: ma-su yö 1.2. 1:59.

Huomaathan rekursioon johdattelevan lisätehtävän. Tällä ja kaikilla muillakin viikoilla on algoritmien pystyttävä tuottamaan oikea vastaus alle yhdessä sekunnissa, ellei erikseen muuta mainita.

Tehtävä 1

Toteuta koodipohjassa oleva metodi

public static int rekursio(File kansio, String s)

Koodiasi testataan metodilla laske, joka etsii koodipohjan mukana tulevan kansion "mockfiles" ja aloittaa haun sieltä. Ethän koske metodiin laske etkä kansioon mockfiles, muuten testit eivät toimi oikein.

HUOMIO 1: Jos latasit tehtäväpohjan aikaisin, niin sinulla saattaa olla viallinen koodi metodissa laske. Metodin laske sisällön kuuluisi näyttää tältä:

File kansio = new File("test"+File.separator+"mockfiles");
return rekursio(kansio, search);
        

Esimerkit

Tehtävä 2

Toteuta metodi int laske(int n, String s), joka kertoo montako sellaista binäärijonoa on, joiden pituus on n ja joissa ei ole binäärijonoa s osajonona. Binäärijono on merkkijono, joka muodostuu merkeistä '0' ja '1'.

Pituus n on korkeintaan 20, samoin annetun merkkijonon s pituus.

Esimerkit

Esimerkiksi esimerkissä 1 käyvät kaikki muut binäärijonot, paitsi "11", joita ovat siis "00", "01", "10" ja siksi vastaus on 3. Kolmannessa esimerkissä käyvät kaikki kolmen merkin pituiset binäärijonot, joissa missään kohtaa ei merkki '0' seuraa merkkiä '1'. Täten hyväksyttävät binäärijonot ovat "111", "011", "001", "000".

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

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

Sinulla on n×m kokoinen laatta, jonka haluat leikata osiin, joiden alat ovat korkeintaan k. Sinulla on käytössäsi leikkuri, johon saat yhden yhtenäisen laatanpalan, jonka voit katkaista kahteen osaan joko pysty tai vaakasuunnassa. Leikkauksen jälkeen laatta jakautuu kahteen pienempään laattaan, ja seuraavat leikkaukset on tehtävä erikseen näihin pienempiin laattoihin. Esimerkiksi 3×4 kokoinen laatta voidaan yhdellä leikkauksella jakaa osiin, joiden mitat ovat

• 2×4 ja 1×4
• 1×4 ja 2×4
• 3×3 ja 3×1
• 3×2 ja 3×2
• 3×1 ja 3×3

Toteutus

Toteuta metodi int pieninMaara(int n, int m, int k), joka kertoo pienimmän leikkausten määrän, jolla n×m kokoinen laatta voidaan jakaa osiin, joiden alat ovat korkeintaan k. Luvut n ja m ovat korkeintaan 50.

Vinkki (näkyy maalattuna): Alkuun pääsemiseksi kannattaa vain testata kaikki mahdolliset tavat leikata laatta osiin. Sitten kun algoritmisi toimii oikein, mutta on liian hidas, niin tämä johtuu todennäköisesti siitä, että algoritmisi laskee optimaalisen leikkausten määrän useita kertoja samanlaisella suorakulmiolla. Ohjelman tehostamiseksi kannattaa siis tallentaa jo laskettuja arvoja muistiin, josta jo kerran lasketut tulokset voidaan löytää nopeasti raskaan laskemisen sijaan. Tekniikka tunnetaan nimellä 'memoisaatio', ja se liittyy vahvasti erittäin yleiseen ongelmanratkaisutekniikkaan nimeltä 'dynaaminen ohjelmointi'.

Esimerkit

Ylimääräinen lisätehtävä

Tästä tehtävästä ei saa kurssipisteitä, mutta se voi olla varsin mielenkiintoinen haasteita haluaville. Tämä tehtävä on jatkoa tehtävään 4. Lue tästä paperista luku 2.3 ja luvusta 2.4 lukujen jakamisesta kahteen joukkoon kertova osa. Näissä luvuissa kuvataan algoritmit KK ja CKK, jotka ovat heuristisia algoritmeja omenanjakotehtävän kaltaisten ongelmien ratkaisemiseksi. Tämän jälkeen yritä saada mahdollisimmat hyvät pisteet tästä tehtävästä, joka löytyy CSES-tehtäväpalvelimelta. Tehtävä eroaa tämän viikon tehtävästä 4 kahdella tavalla. Ensinnäkään nyt ei tarvitse välttämättä tuottaa parasta mahdollista jakotapaa, vaan pisteitä saa sitä enemmän, mitä paremmin jakaa omenat. Toisekseen omenoita on tällä kertaa enintään 100, joten kaikkien jakotapojen läpikäynti ei tule enää kysymykseen.

Tehtävästä on mahdollista saada täydet pisteet muuntamalla hieman paperissa esitettyä CKK-algoritmia. Ohjeet CSES-järjestelmän käyttöön löydät täältä. Jos palautat tehtävän Javalla, niin rivi

package <jotain>;