Tehtävien deadline: ma 23.3. klo 01:59
Tämän viikon tehtävät 1-3 liittyvät ongelmanratkaisuun puissa ja 4-6 kekoon.
Palindromi on merkkijono joka on sama kumminkin päin luettuna. Esimerkiksi sana anna on palindromi mutta sana talo ei. Kirjaimista A
...C
voidaan muodostaa seuraavat 3 kirjaimen pituiset palindromit:
AAA
ABA
ACA
BAB
BBB
BCB
CAC
CBC
CCC
Toteuta metodi void palindromit(int kirjaimia, int pituus)
, joka tulostaa kaikki pituus
-pituiset palindromit, jotka muodostuvat kirjaimia
kpl aakkosten ensimmäisistä kirjamesta.
Voit olettaa, että kirjaimia on korkeintaan 26 ja pituus on korkeintaan 100.
Huom! älä tee niin että generoit merkkijonon ja sitten tarkistat onko se palindromi. Kaikkia merkkijonoja on paljon enemmän kuin palindromeja. Voit nähdä tämän itse kirjoittamalla paperille kaikki pituuden 3 merkkijonot merkeistä A,B,C ja kaikki pituuden 3 palindromit merkeistä A,B,C.
Kutsu tulosta(3,3)
tulostaa:
AAA ABA ACA BAB BBB BCB CAC CBC CCC
Kutsu tulosta(2,4)
tulostaa:
AAAA ABBA BAAB BBBB
Toteuta metodi int evaluoi(String lauseke)
, joka laskee käyttäjän antaman laskutoimituksen. Laskutoimitus voi sisältää kokonaislukuja väliltä 0...1000, operaatioita + ja * sekä sulkuja. Voit olettaa, että laskutoimituksen jokainen välivaihe mahtuu int
-muuttujaan.
Ohjelmasi voi olettaa, että laskutoimituksen muoto on oikea (eli ohjelman ei tarvitse sisältää virheenkäsittelyä). Laskutoimitus muodostuu merkeistä 0–9, +, *, ( ja ), eikä siinä ole ylimääräisiä välilyöntejä.
Anna laskutoimitus: 2+5*3 Tulos: 17
Anna laskutoimitus: (1+1)*5 Tulos: 10
Anna laskutoimitus: 2*(3*(5+2)+1) Tulos: 44
Anna laskutoimitus: 100*10*10 Tulos: 10000
Vihje! Yksi algoritmi tehtävän ratkaisuun tunnetaan nimellä "shunting yard". Saattaa olla kuitenkin hauskempaa keksiä itse sopiva algoritmi!
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
Tämä tehtävä käsittelee lukuja, jotka saadaan kertomalla lukuja 2 ja 3. Ensimmäiset tällaiset luvut ovat:
Tehtäväsi on selvittää järjestyksessä n. tällainen luku.
Toteuta seuraava metodi:
long etsiTulo(int n)
Parametri n
määrittää,
monesko luku metodin tulee palauttaa.
Kaikissa testeissä n
on välillä 1..1000 ja vastaus mahtuu
long-muuttujaan.
# | metodin kutsu | haluttu palautusarvo |
---|---|---|
1 | etsiTulo(2) | 3 |
2 | etsiTulo(20) | 108 |
3 | etsiTulo(49) | 2304 |
4 | etsiTulo(200) | 15925248 |
Tehtäväsi on toteuttaa luokka, joka tarjoaa kaksi toimintoa: uuden luvun lisääminen sekä mediaanin laskeminen kaikista lisätyistä luvuista.
Mediaani tarkoittaa lukua, joka on keskimmäisenä, jos kaikki luvut järjestetään pienimmästä suurimpaan.
Jos lukujen määrä on parillinen, mediaani ei ole yksikäsitteinen. Tässä tehtävässä tulkintana on, että mediaani on silloin vasemmanpuoleinen luku kahdesta keskimmäisestä.
Toteuta luokka Mediaani
, joka tarjoaa seuraavat metodit:
void lisaaLuku(int luku)
:int mediaani()
:Testauksessa metodeita kutsutaan enintään 105 kertaa.
Seuraava koodi testaa luokkaa:
Mediaani m = new Mediaani(); m.lisaaLuku(1); System.out.println(m.mediaani()); m.lisaaLuku(5); m.lisaaLuku(4); System.out.println(m.mediaani());
Koodin tulostuksen tulisi olla seuraava:
1 4