Viikko 4: TMC-tehtävät

Tehtävien deadline: ma 9.2. klo 01:59

Viikon teemana on linkitetty lista ja pinorakenteen soveltaminen ongelmien ratkaisuun.

Tehtävä 1

Tehtäväpohjan mukana tulee luokka Node, joka esittää yhteen suuntaan linkitetyn listan solmua.

Toteuta luokkaan Operaatioita seuraavat metodit:

• Node reverse(Node root) kääntää listan, jonka juurisolmu annetaan ja palauttaa käännetyn listan juurialkion.
• Node cut(Node root, int i) katkaisee linkin listan (i-1):nnen ja i:nnen solmujen väliltä. Metodi palauttaa i:nnen solmun, joka on juuri katkaisussa syntyvälle alkuperäisen listan loppuosalle. Jos i=0, niin metodin on palautettava alkuperäinen lista muuttumattomana. Esimerkki:

          // Rakennetaan lista [6,7,8,9,10]
          Node root = new Node(6,new Node(7, new Node(8, new Node(9, new Node(10)))));
          // Katkaistaan indeksistä 2
          Node loppu_root = Operaatioita.cut(lista, 2);
          // Nyt loppu_root on [8,9,10] ja root on [6,7]

Huom! Kummankaan metodin ei tule allokoida uusia solmuja, vaan annetun listan solmut tulee uudelleenkäyttää! Kummassakaan metodissa ei siis tarvitse olla yhtään new Node -kutsua!

Huom! Testit testaavat että pitkänkin listan kääntämiseen menee alle 20ms.

Tehtävä 2

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:

1. Aluksi pinon sisältö on [1].
2. Komennon @ jälkeen sisältö on [1, 1].
3. Komennon @ jälkeen sisältö on [1, 1, 1].
4. Komennon + jälkeen sisältö on [1, 2].
5. Komennon @ jälkeen sisältö on [1, 2, 2].
6. Komennon * jälkeen sisältö on [1, 4].

Tehtäväsi on suorittaa annettu ohjelma ja palauttaa pinon viimeinen luku ohjelman suorituksen jälkeen.

Toteutus

Toteuta seuraava metodi:

int laskin(String ohjelma)

Parametri ohjelma on suoritettava ohjelma. Se muodostuu merkeistä @, + ja *, ja sen pituus on 1..10⁵ 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..10⁹.

Esimerkit

Tehtävä 3

Sinulle on annettu merkkijono, joka muodostuu merkeistä A ja B. Saat poistaa merkkijonosta merkkipareja, joissa on kaksi samaa merkkiä peräkkäin, ja jatkaa tätä niin kauan kuin mahdollista. Pystytkö tyhjentämään merkkijonon poistamalla sen kaikki merkit?

Esimerkiksi jos merkkijono on ABBABB, tyhjentäminen on mahdollista. Voit poistaa ensin ensimmäisen merkkiparin BB, jolloin tuloksena on AABB. Tämän jälkeen voit poistaa merkkiparin AA, jolloin tuloksena on BB, ja lopulta merkkiparin BB, jolloin olet saanut tyhjennettyä merkkijonon.

Vastaavasti merkkijonon ABABAB tyhjentäminen ei ole mahdollista, koska siitä ei pysty poistamaan edes yhtä merkkiparia.

Toteutus

Toteuta seuraava metodi:

bool tyhjennys(String mjono)

Parametri mjono on merkkijono, joka koostuu merkeistä A ja B. Merkkijonon pituus on välillä 1..10⁵.

Metodin tulee palauttaa true, jos merkkijono on mahdollista tyhjentää, ja muuten false.

Esimerkit

Tehtävä 4

Junaradan vasemmassa laidassa on n vaunua, jotka on numeroitu kokonaisluvuin 1..n. Vaunut voivat olla missä tahansa järjestyksessä. Tehtäväsi on siirtää vaunut radan oikeaan laitaan niin, että ne ovat oikeassa järjestyksessä.

Saat siirtää vaunuja vain oikealle, mutta pystyt vaihtamaan vaunujen järjestystä, koska rata haarautuu kahteen osaan:

     /-----\
-----       -----
     \-----/
                     

Sekä radan vasempaan ja oikeaan laitaan että molempiin keskiosiin mahtuu rajattomasti vaunuja. Onko tehtäväsi mahdollinen?

Esimerkiksi tilanteessa

     /-----\
1324-       -----
     \-----/
                     

siirtäminen on mahdollista seuraavasti:

1. Vaunu 4 siirretään oikeaan laitaan jommankumman haaran kautta:

        /-----\
   132--       ----4
        \-----/
                            

2. Vaunu 2 siirretään odottamaan ylempään haaraan:

        /---2-\
   13---       ----4
        \-----/
                            

3. Vaunu 3 siirretään oikeaan laitaan alahaaran kautta:

        /---2-\
   1----       ---34
        \-----/
                            

4. Vaunu 2 siirretään ylähaarasta oikeaan laitaan:

        /-----\
   1----       --234
        \-----/
                            

5. Vaunu 1 siirretään oikeaan laitaan jommankumman haaran kautta:

        /-----\
   -----       -1234
        \-----/
                            

Toteutus

Toteuta seuraava metodi:

bool vaunusiirto(int[] vaunut)

Taulukko vaunut sisältää vaunujen järjestyksen radan vasemmassa laidassa. Taulukossa on n lukua, ja jokainen luku 1..n esiintyy tasan kerran. Luku n on välillä 1..10⁵.

Metodin tulee palauttaa true, jos vaunujen järjestäminen on mahdollista, ja muuten false.

Esimerkit

Tehtävä 5

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

Toteutus

Toteuta seuraava metodi:

int[] suuremmat(int[] luvut)

Taulukko luvut sisältää 1..10⁵ kokonaislukua, joista jokainen on välillä 1..10⁹. 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.

Esimerkit