Viikko 10: TMC-tehtävät

Tehtävien deadline: ma 23.11. klo 04:01

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

Tehtävä 1

Opintosuunnittelija Kjell Kurhila 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ä 2

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
otm javalabra
ohpe otm
tiralabra ohtuprojekti
javalabra ohtuprojekti
otm ohtu
ohtu ohtuprojekti
lama ohtuprojekti

eräs käypä suoritusjärjestys on

ohpe ohja otm javalabra tira tiralabra lama ohtu ohtuprojekti

Tehtävä 3

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

Esimerkki 1

Graafi:

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

Vierusmatriisi:

0101
1010
0101
1010

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

Esimerkki 2

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

Vierusmatriisi:

0101000
1010000
0101110
1010000
0010001
0010001
0000110

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

Esimerkki 3

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

00111100
00001111
10010000
10100000
11000000
11000000
01000001
01000010

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

Tehtävä 4

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

• 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

100
010
001

Toteutus