Viikon tavoitetehtävämäärä: 4 tehtävää
Tehtävien deadline: sunnuntaina 8.10. 23:59.
Tällä ja kaikilla muillakin viikoilla on algoritmien pystyttävä
tuottamaan oikea vastaus alle yhdessä sekunnissa, ellei erikseen muuta
mainita. Viikon aiheena on jono- ja pinorakenteen soveltaminen. Javasta läytyvät valmiit toteutukset Stack ja ArrayDeque.
Eräänä päivänä kävellessään puistossa Uolevi huomasi, että puistossa on monia hienoja kiviä. Koska Uolevi on ahkera kivien kerääjä, alkoi hän poimimaan maassa lojuvia kiviä. Hän kerää kivensä erityiseen kivikoteloon, johon kivet menevät sopivasti päällekkäin. Uusi kivi menee aina kotelon päällimmäiseksi.
Uolevi ei kuitenkaan halua kokoelmaansa useita samanlaisia kiviä, joten jos hän jossain vaiheessa huomaa, että uusi kivi on samanlainen kuin kotelon päällimmäinen kivi, heittää hän sekä kotelon päällimmäisen kiven, että uuden kiven pois. Tehtävänäsi on selvittää kuinka monta uutta kiveä Uolevilla on kävelynsä jälkeen.
Toteuta seuraava metodi:
int montakoKivea(int[] kivet)
Taulukko kivet sisältää Uolevin löytämät kivet
löytämisjärjestyksessä. Kivet ovat samanlaiset jos niitä vastaavat
kokonaisluvut ovat samat. Metodin tulee palauttaa uusien kivien määrä
kävelyn jälkeen.
Taulukon kivet pituus on korkeintaan 100000 ja sen sisältämät luvut ovat välillä 0..109.
| # | metodin kutsu | haluttu palautusarvo |
|---|---|---|
| 1 | montakoKivea(new int[]{1, 1, 1, 1}) | 0 |
| 2 | montakoKivea(new int[]{1, 1, 1}) | 1 |
| 3 | montakoKivea(new int[]{1, 2, 3, 3, 2, 1}) | 0 |
| 4 | montakoKivea(new int[]{1, 2, 3, 2, 1}) | 5 |
Sinulle on annettu merkkijono, joka muodostuu
merkeistä ( ja ). Tehtäväsi on tarkistaa,
onko merkkijono oikein sulutettu
eli voiko merkkijonon saada matemaattisesta
lausekkeesta poistamalla kaikki muut merkit paitsi sulut.
Esimerkiksi merkkijonot ((())) ja (())()
ovat oikein sulutettuja,
kun taas merkkijonot (()))( ja ())(()
eivät ole oikein sulutettuja.
Toteuta seuraava metodi:
boolean sulutus(String mjono)
Parametri mjono on sulut sisältävä merkkijono.
Sen pituus on välillä 1..105.
Metodin tulee palauttaa true,
jos merkkijono on oikein sulutettu,
ja muuten false.
| # | metodin kutsu | haluttu palautusarvo |
|---|---|---|
| 1 | sulutus("((()))") | true |
| 2 | sulutus("(())()") | true |
| 3 | sulutus("(()))(") | false |
| 4 | sulutus("())(()") | false |
Tehtäväsi on toteuttaa pinolaskin, joka suorittaa annetun ohjelman. Pinoa voi käsitellä vain sen lopusta (oikealta puolelta). Aluksi pinossa on luku 1. Ohjelman komennot suoritetaan järjestyksessä, ja mahdolliset komennot ovat:
@: lisää pinoon kopio pinon viimeisestä luvusta
+: poista pinon kaksi viimeistä lukua ja lisää niiden summa pinoon
*: poista pinon kaksi viimeistä lukua ja lisää niiden tulo pinoon
Esimerkiksi ohjelma @@+@* suoritetaan näin:
@ jälkeen sisältö on [1, 1].
@ jälkeen sisältö on [1, 1, 1].
+ jälkeen sisältö on [1, 2].
@ jälkeen sisältö on [1, 2, 2].
* jälkeen sisältö on [1, 4].
Tehtäväsi on suorittaa annettu ohjelma ja palauttaa pinon viimeinen luku ohjelman suorituksen jälkeen.
Toteuta seuraava metodi:
int laskin(String ohjelma)
Parametri ohjelma on suoritettava ohjelma.
Se muodostuu merkeistä @, + ja *,
ja sen pituus on 1..105 merkkiä.
Metodin tulee palauttaa pinon viimeinen luku ohjelman suorituksen jälkeen. Voit olettaa, että kaikki pinossa ohjelman suorituksen aikana olevat luvut, mukaan lukien viimeinen luku, ovat välillä 1..109. Pinolaskimen saama ohjelma on aina hyvin koodattu, eli kaikki operaatiot voidaan suorittaa ongelmitta, eli esimerkiksi merkin '+' kohdalla pinossa on vähintään kaksi lukua.
| # | metodin kutsu | haluttu palautusarvo |
|---|---|---|
| 1 | laskin("@@+@*") | 4 |
| 2 | laskin("@+") | 2 |
| 3 | laskin("@@**") | 1 |
| 4 | laskin("@+@+@+") | 8 |
| 5 | laskin("@@@+++") | 4 |
Läheisen yökerhon korruptoitunut ovimies on päättänyt hankkia
lisätienestejä kiristämällä jonottavia asiakkaita. Välillä hän veloittaa
x euroa jokaiselta jonossa sillä hetkellä olevalta
henkilöltä, ja koska kaikki jonottajat haluavat päästä sisään, maksavat
he ovimiehelle aina hänen pyytämänsä summan. Tehtäväsi on auttaa
ovimiestä pitämään kirjaa siitä, kuinka paljon hän on onnistunut saamaan
rahaa kultakin asiakkaalta.
Tehtävänäsi on toteuttaa tehtäväpohjassa oleva luokka Laskuri ja siihen seuraavat metodit:
Laskuri() luo tyhjän jonon.void lisaaJonoon() lisää jonon perälle uuden asiakkaan.void veloita(long x) veloittaa jokaiselta jonossa tällä hetkellä olevalta jonottajalta x euroa.long paastaSisaan() päästää jonossa
ensimmäisenä olevan asiakkaan sisään ja palauttaa tiedon siitä, kuinka
monta euroa kyseinen asiakas on joutunut maksamaan ovimiehelle jonossa
pysyäkseen.Testeissä luokan metodeja kutsutaan korkeintaan 500000 kertaa. Luku x on välillä 1..109. Jos jonossa ei ole asiakkaita, niin metodin long paastaSisaan() tulee palauttaa 0.
Sinulle on annettu taulukko kokonaislukuja, ja tehtäväsi on etsiä jokaiselle luvulle seuraava suurempi luku taulukossa.
Muodosta uusi taulukko, jonka jokainen arvo on annetun taulukon luvun seuraava suurempi luku. Jos suurempaa lukua ei ole, arvon tulee olla 0.
Esimerkiksi taulukosta {1, 5, 2, 4, 3} syntyy uusi taulukko {5, 0, 4, 0, 0}.
Toteuta seuraava metodi:
int[] suuremmat(int[] luvut)
Taulukko luvut sisältää 1..105 kokonaislukua,
joista jokainen on välillä 1..109.
Sama luku voi esiintyä taulukossa monta kertaa.
Metodin tulee palauttaa taulukko, joka sisältää jokaisesta luvusta seuraavan suuremman luvun tai arvon 0, jos suurempaa lukua ei ole olemassa.
| # | metodin kutsu | haluttu palautusarvo |
|---|---|---|
| 1 | suuremmat(new int[] {1, 2, 3, 4, 5}) | {2, 3, 4, 5, 0} |
| 2 | suuremmat(new int[] {5, 4, 3, 2, 1}) | {0, 0, 0, 0, 0} |
| 3 | suuremmat(new int[] {4, 3, 2, 1, 5}) | {5, 5, 5, 5, 0} |
| 4 | suuremmat(new int[] {1, 5, 2, 4, 3}) | {5, 0, 4, 0, 0} |