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.
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.
Toteuta metodi
int kierros(int[][] et)Syötteenä annettu taulukko
et
sisältää tiedon kaupunkien välisistä etäisyyksistä. Kaupunkien i ja j välinen etäisyys on et[i][j] == et[j][i]
. Kun siirrytään kaupungista i suoraan kaupunkiin j käymättä missään muussa kaupungissa, on reitin pituus et[i][j]
, vaikka olisikin epäsuora reitti, joka olisi lyhyempi.
Kaupunkien määrä n
on korkeintaan 10. Matriisin et
sisältämät luvut ovat välillä 0..106.
Olkoon matriisi et
seruaavanlainen:
0321 3042 2404 1240Matriisin kuvaama verkko näyttää siis tältä:
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.
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:
Voit olettaa, että metodille annettuun sudokuun on olemassa yksikäsitteinen ratkaisu.
Suomalainen Arto Inkala on laatinut "maailman vaikeimman Sudokun":
Tee ohjelmastasi sellainen, että se ratkaisee kyseisen sudokun (ja muutkin löytämäsi sudokut) silmänräpäyksessä.
Vihje! Luentokalvojen kuningattaret shakkilaudalla -esimerkki.
(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
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
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
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.
Toteuta luokka Toimisto
, joka tarjoaa seuraavat metodit:
void lisaaJonoon(String nimi, int kiire)
nimi
jonoon
kiireellisyysarvolla kiire
String annaAsunto()
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..109. Mitä suurempi luku on, sitä kiireellisempi henkilön tilanne on.
Testauksessa metodeita kutsutaan enintään 105 kertaa.
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
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:
kone | toiminta-aika |
---|---|
A | 1 |
B | 2 |
C | 3 |
D | 4 |
Kun haluat valmistaa 10 tuotetta, yksi optimaalisista tavoista on seuraava:
ajanhetki | tapahtumat |
---|---|
0 | Laitat käyntiin koneet A, B, C ja D. |
1 |
Kone A saa valmiiksi tuotteen. Laitat uudestaan käyntiin koneen A. (1 tuote valmiina.) |
2 |
Koneet A ja B saavat valmiiksi tuotteen. Laitat uudestaan käyntiin koneet A ja B. (3 tuotetta valmiina.) |
3 |
Koneet A ja C saavat valmiiksi tuotteen. Laitat uudestaan käyntiin koneet A ja C. (5 tuotetta valmiina.) |
4 |
Koneet A, B ja D saavat valmiiksi tuotteen. Laitat uudestaan käyntiin koneen B. (8 tuotetta valmiina.) |
5 |
Käyt hesarin nettisivulla lukemassa päivän fingerporin. |
6 |
Koneet B ja C saavat valmiiksi tuotteen. (10 tuotetta valmiina.) Tehtävä suoritettu! |
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..105.
Jokainen taulukon arvo on kokonaisluku
välillä 1..109.
Kokonaisluku maara
on valmistettava
tuotteiden määrä. Tämä luku on välillä 1..105.
Metodin tulee palauttaa pienin mahdollinen aika, jossa saat valmistettua tuotteet koneiden avulla.
# | metodin kutsu | haluttu palautusarvo |
---|---|---|
1 | lyhinAika(new int[] {1}, 5) | 5 |
2 | lyhinAika(new int[] {1, 1, 1}, 6) | 2 |
3 | lyhinAika(new int[] {5, 1, 1}, 6) | 3 |
4 | lyhinAika(new int[] {1, 2, 3, 4}, 10) | 6 |
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?
Toteuta metodi
long pieninAita(long[] a, long[] b, long[] h)joka selvittää pienimmän mahdollisen aidan pinta-alan, kun asukkaiden toiveet on annettu syötteenä tulevissa taulukoissa. Taulukoiden
a
, b
ja h
pituudet ovat samat, ja yhden toiveen tiedot saadaan kolmikosta a[i], b[i], h[i]
.
Taulukoiden a
, b
ja h
pituudet ovat korkeintaan 105, ja niiden sisältämät luvut välillä 0..109. Voit olettaa, että a[i]<b[i]
.
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}Nyt toiveita voi visualisoida seuraavalla tavalla:
ja seuraavassa kuvassa on merkitty pienin nämä toiveet toteuttava aita sinisellä:
tämän aidan pinta-ala on selvästi 14, joka onkin haettu vastaus.