Viikko 10: TMC-tehtävät

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

Viikon aiheena on erityisesti syklit ja vahvasti yhtenäiset komponentit. Myös viime viikon teema jatkuu osittain.

Tehtävä 1

Uolevi haluaa antaa lahjan jokaiselle ystävälleen. Uolevi ei halua antaa samaa lahjaa ystäville, jotka tuntevat toisensa, koska muuten lahja ei vaikuta henkilökohtaiselta. Toisaalta Uolevin varastossa on vain kahdenlaisia lahjoja: hän voi antaa joko kirjan tai karkkipussin. Onko Uolevin tavoite mahdollinen?

Oletetaan esimerkiksi, että Uolevin ystävät ovat A, B, C ja D. A tuntee kaikki muut ystävät, kun taas muut eivät tunne toisiaan. Nyt lahjojen jakaminen on mahdollista esimerkiksi niin, että A saa kirjan ja kaikki muut saavat karkkipussin.

Oletetaan sitten, että A ei tunne ketään, kun taas B, C ja D tuntevat kaikki toisensa. Nyt lahjojen jakaminen ei ole mahdollista, koska B:llä tulisi olla eri lahja kuin C:llä ja D:llä ja C:llä ja D:llä ei saa olla samaa lahjaa.

Toteutus

Toteuta seuraava metodi:

boolean lahjajako(int n, int[] mista, int[] minne)

Parametri n on Uolevin ystävien määrä. Se on kokonaisluku välillä 1..10⁵. Ystävät on numeroitu kokonaisluvuin 1..n.

Taulukot mista ja minne kuvaavat ystävyyssuhteet. Ystävyyssuhteiden määrä on 0..10⁵.

Metodin tulee palauttaa true, jos lahjojen jakaminen on mahdollista Uolemin haluamalla tavalla, ja muuten false.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`lahjajako(4, new int[] {1, 2, 3}, new int[] {2, 3, 4})`	`true`
2	`lahjajako(4, new int[] {1, 1, 1}, new int[] {2, 3, 4})`	`true`
3	`lahjajako(3, new int[] {1, 2, 3}, new int[] {2, 3, 1})`	`false`
4	`lahjajako(4, new int[] {1, 2, 3}, new int[] {2, 3, 1})`	`false`

Tehtävä 2

Opintosuunnittelija Keijo Kojootti suunnittelee kurssien esitietovaatimuksia. Tee hänen avukseen ohjelma, joka tarkastaa, onko esitiedoissa sykli.

Toteuta metodi public boolean sykli(Esitieto[] esitiedot), joka palauttaa true jos annetuissa esitiedoissa on sykli. Esitiedot on esitetty taulukkona Esitieto-olioita. Esitieto-oliot toimivat siten, että kurssi e.esi tulee suorittaa ennen kurssia e.kurssi.

Esimerkki

Seuraavissa esitiedoissa ei ole sykliä:

a b
b c
a d
d c
d b
c e

Seuraavissa esitiedoissa taas on sykli:

a b
b c
a d
d c
d b
c a

Tehtävä 3

Tällä kertaa tehtävänäsi on selvittää jokin käypä järjestys kurssien käymiseen, kun kurssien väliset esitiedot on annettu. Toteuta siis metodi ArrayList<String> jarjestys(Esitieto[] esitiedot). Voit olettaa että annetuissa esitiedoissa ei ole sykliä.

Esimerkki 1

Esitietojen

a b
b c
a d
d c
d b
c e

eräs käypä suoritusjärjestys on a d b c e

Esimerkki 2

Esitietojen

ohpe ohja
ohja tira
tira lama
tira tiralabra
ohja javalabra
javalabra tiralabra
ohpe ohma
tiralabra ohtuprojekti
javalabra ohtuprojekti
ohma ohtu
ohtu ohtuprojekti
lama ohtuprojekti

eräs käypä suoritusjärjestys on

ohpe ohja javalabra tira tiralabra lama ohma ohtu ohtuprojekti

Tehtävä 4

Eulerin kierrokseen ja sen löytämiseen, voit tutustua esimerkiksi kisakoodarin käsikirjasta (luku 20).

Eulerin kierros verkossa on polku, joka kulkee jokaista kaarta pitkin täsmälleen kerran ja saapuu takaisin lähtöruutuun.

Toteuta metodi ArrayList<Integer> eulerinKierros(boolean[][] verkko), joka palauttaa verkon jonkin Eulerin kierroksen. (Voit olettaa että sellainen on olemassa.) Syötteenä oleva verkko on esitetty vierusmatriisina -- samoin kuin tehtävässä 1.

Esimerkki 1

Graafi:

0--1
|  |
|  |
3--2

Vierusmatriisi:

Eräs Eulerin kierros: 0,1,2,3

Esimerkki 2

0--1
|  |
|  |
3--2--4
   |  |
   |  |
   5--6

Vierusmatriisi:

Eräs Eulerin kierros: 0,1,2,5,6,4,2,3

Esimerkki 3

  __0_____
 / / \    \
2-3  4     5  6--7
      \_____\ /_/
             1

Eräs Eulerin kierros: 0,2,3,0,4,1,7,6,1,5

Tehtävä 5

Sinulle annetaan syötteenä n-solmuisen suunnatun verkon vierusmatriisi, missä n on korkeintaan 1000. Lisäksi tiedetään, että verkossa on ainakin yksi solmu, josta on kaari itseensä. Tehtävänä on selvittää, onko olemassa jotain sellaista positiivista kokonaislukua m, jolle pätee seuraava: valitaanpa mitkä tahansa kaksi (eri) verkon solmua a ja b, niin on olemassa polku solmusta a solmuun b, jonka pituus on tasan m.

Vierusmatriisia

110
001
100

vastaava verkko on

Tässä verkossa jokaisen solmuparin välillä on reitti, jonka pituus on 4:

1->2: 1->2->3->1->2
2->1: 2->3->1->1->1
1->3: 1->1->1->2->3
3->1: 3->1->1->1->1
2->3: 2->3->1->2->3
3->2: 3->1->1->1->2

Toisaalta on selvää, ettei tehtävänannon mukaista lukua m ole esimerkiksi verkolle

100
010
001

sillä jokaisesta solmusta pääsee ainoastaan itseensä.

Toteutus

Toteuta metodi

boolean
    ratkaise(boolean[][] verkko)

, joka ratkaisee yllä kuvatun ongelman verkolle, jonka vierusmatriisi annetaan parametrina.