Viikko 8: TMC-tehtävät

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

Tehtävissä 1 ja 2 käsitellään ongelmanratkaisua puissa. Tehtävien 3-5 aiheena on keko, jolle löytyy valmis toteutus PriorityQueue javassa.

Tehtävä 1

Kauppamatkustaja haluaa käydä n kaupungissa, joiden väliset etäisyydet on tallennettu n×n matriisiin (eli kaksiulotteiseen taulukkoon) et. Kauppamatkustaja haluaa kiertää kaikki kaupungit läpi mahdollisimman nopeasti. Hän aloittaa kierroksensa kaupungista 0, käy kaikissa muissa kaupungeissa tasan kerran ja palaa lopuksi kaupunkiin 0. Auta kauppamatkustajaa selvittämään lyhimmän mahdollisen kierroksen pituus.

Toteutus

Toteuta metodi

int kierros(int[][] et)

Kaupunkien määrä n on korkeintaan 10. Matriisin et sisältämät luvut ovat välillä 0..10⁶.

Esimerkki

Olkoon matriisi et seruaavanlainen:

0321
3042
2404
1240

Nyt yksi esimerkki lyhimmästä mahdollisesta kierroksesta käy kaupungit läpi järjestyksessä 0->2->1->3->0. Tämän reitin pituus on 2+4+2+1=9, joka on haettu vastaus.

Tehtävä 2

Tee metodi void ratkaise(int[][] sudoku), joka ratkaisee annetun sudokun. Sudoku annetaan kaksiulotteisena int-taulukkona. Taulukossa 0 tarkoittaa tyhjää paikkaa ja numerot 1-9 tarkoittavat numeroita 1-9. Metodin pitäisi muokata annettua taulukkoa niin että se on oikein täytetty sudoku, eli:

• Yksikään taulukon paikka ei ole 0.
• Taulukon jokaisella rivillä esiintyvät luvut 1-9, jokainen tasan kerran.
• Taulukon jokaisessa sarakkeessa esiintyvät luvut 1-9, jokainen tasan kerran.
• Kun taulukko jaetaan yhdeksään 3x3 neliöön, jokaisessa neliössä esiintyvät luvut 1-9, jokainen tasan kerran.

Voit olettaa, että metodille annettuun sudokuun on olemassa yksikäsitteinen ratkaisu.

Suomalainen Arto Inkala on laatinut "maailman vaikeimman Sudokun":

• Maths whiz creates hardest Sudoku yet (The Sun)

Tee ohjelmastasi sellainen, että se ratkaisee kyseisen sudokun (ja muutkin löytämäsi sudokut) silmänräpäyksessä.

Vihje! Luentokalvojen kuningattaret shakkilaudalla -esimerkki.

Esimerkki: Helppo sudoku

(Tämän pitäisi ratketa hyvin nopeasti)

Anna sudoku:
          
          8??93???2
          ??9????4?
          7?21??96?
          2??????9?
          ?6?????7?
          ?7???6??5
          ?27??84?6
          ?3????5??
          5???62??8
          Ratkaisu:
          846937152
          319625847
          752184963
          285713694
          463859271
          971246385
          127598436
          638471529
          594362718

Esimerkki: "Maailman vaikein" sudoku

Anna sudoku:
          ??53?????
          8??????2?
          ?7??1?5??
          4????53??
          ?1??7???6
          ??32???8?
          ?6?5????9
          ??4????3?
          ?????97??
          Ratkaisu:
          145327698
          839654127
          672918543
          496185372
          218473956
          753296481
          367542819
          984761235
          521839764

Esimerkki: Toinen vaikea sudoku

Anna sudoku:
          ?????????
          ?????3?85
          ??1?2????
          ???5?7???
          ??4???1??
          ?9???????
          5??????7?
          ??2?1????
          ????4???9
          Ratkaisu:
          237658914
          469173285
          851924367
          123567498
          784239156
          695481732
          546392871
          972815643
          318746529

Tehtävä 3

Asunnonvälitystoimisto toimii seuraavasti: kullekin henkilölle määritellään jonoon liittyessä kiireellisyysarvo. Asunnon vapautuessa sen saa henkilö, jonka kiireellisyysarvo on suurin. Jos monella henkilöllä on yhtä suuri kiireellisyysarvo, asunnon saa aakkosissa ensimmäinen henkilö. Jos monella henkilöllä on sama nimi, kuka tahansa heistä voi saada asunnon.

Toteutus

Toteuta luokka Toimisto, joka tarjoaa seuraavat metodit:

• void lisaaJonoon(String nimi, int kiire)
  lisää henkilön nimeltä nimi jonoon kiireellisyysarvolla kiire
• String annaAsunto()
  palauttaa henkilön nimen, joka saa vapautuvan asunnon

Jokainen nimi muodostuu kirjaimista a..z. Nimen ensimmäinen kirjain on iso ja kaikki muut pieniä. Nimen pituus on enintään 10 kirjainta.

Kiireellisyysarvo on kokonaisluku välillä 1..10⁹. Mitä suurempi luku on, sitä kiireellisempi henkilön tilanne on.

Testauksessa metodeita kutsutaan enintään 10⁵ kertaa.

Esimerkki

Seuraava koodi testaa luokkaa:

Toimisto t = new Toimisto();
t.lisaaJonoon("Uolevi", 8);
t.lisaaJonoon("Maija", 4);
System.out.println(t.annaAsunto());
t.lisaaJonoon("Liisa", 5);
System.out.println(t.annaAsunto());
System.out.println(t.annaAsunto());

Koodin tulostuksen tulisi olla seuraava:

Uolevi
Liisa
Maija

Tehtävä 4

Tehtaassa on koneita, joista jokainen pystyy valmistamaan yhden tuotteen tietyssä ajassa. Tehtäväsi on valmistaa mahdollisimman nopeasti annettu määrä tuotteita käyttämällä koneita parhaalla mahdollisella tavalla.

Oletetaan että koneet ovat seuraavat:

Kun haluat valmistaa 10 tuotetta, yksi optimaalisista tavoista on seuraava:

Toteutus

Toteuta seuraava metodi:

long lyhinAika(int[] koneet, int maara)

Taulukko koneet sisältää tiedon, kuinka kauan kullakin koneella menee valmistaa tuote. Koneiden määrä on välillä 1..10⁵. Jokainen taulukon arvo on kokonaisluku välillä 1..10⁹.

Kokonaisluku maara on valmistettava tuotteiden määrä. Tämä luku on välillä 1..10⁵.

Metodin tulee palauttaa pienin mahdollinen aika, jossa saat valmistettua tuotteet koneiden avulla.

Esimerkit

Tehtävä 5

Asuinalueen ohi kulkevan tien laitaan ollaan rakentamassa meluestettä, jotta liikenteen aiheuttama melu vähenisi. Ajattelemme tässä tietä yksiulotteisena janana, jolla on jokin alkupiste 0. Kohdalla k, missä k on jokin kokonaisluku, viitataan siihen kohtaan tietä, johon päädytään kulkemalla tietä eteenpäin alkukohdasta k metrin verran.

Alueen asukkaat ovat esittäneet toiveita meluesteestä. Nämä toiveet ovat muotoa "kohtien a ja b välillä meluesteen tulisi olla vähintään h metriä korkea". Mikä on pienimmän mahdollisen sellaisen aidan pinta-ala, joka toteuttaa kaikkien asukkaiden toiveet?

Toteutus

Toteuta metodi

long pieninAita(long[] a, long[] b, long[] h)

Taulukoiden a, b ja h pituudet ovat korkeintaan 10⁵, ja niiden sisältämät luvut välillä 0..10⁹. Voit olettaa, että a[i]<b[i].

Esimerkit

Tarkastellaan koodipohjan mukana tulevaa esimerkkiä numero 2, jossa siis syöte on

a={0, 1, 4, 5}
b={4, 3, 6, 7}
h={1, 2, 3, 2}