Helsingin yliopisto, University of Helsinki
MOOC.FI

Viikko 9

Näissä tehtävissä sovelletaan syvyys- ja leveyssuuntaista hakua.

Tehtävä 1

Toteutus

Toteuta metodi: boolean tietoverkko(boolean[][] verkko), jolle annetaan kuvaus tietoverkosta ja joka tarkistaa, pystyvätkö kaikki verkon koneet viestimään keskenään. Toisin sanoen ohjelman tulee tarkistaa, onko verkko yhtenäinen.

Verkossa on n konetta, jotka on numeroitu kokonaisluvuin 0...n-1. Voit olettaa, että n on korkeintaan 1000.

Verkon kuvaus on vierusmatriisi, eli kaksiulotteinen taulukko verkko, jossa verkko[i][j] on true jos koneitten i ja j välillä menee yhteys.

Esimerkit

Esimerkki 1

Verkon

  3
 /|\
4 | 0
 \|/ \
  1---2
		

vierusmatriisi on:

01110
10111
11000
11001
01010

ja verkko on yhtenäinen.

Esimerkki 2

Verkon

  3
 /|
4 | 0
 \| |
  1 2
		

vierusmatriisi on:

00100
00011
10000
01001
01010

ja verkko ei ole yhtenäinen.

Tehtävä 2

Saat talon pohjapiirustuksen. Tehtävänäsi on laskea, montako huonetta talossa on. Huone tarkoittaa yhtenäistä seinien rajaamaa lattiatilaa.

Toteutus

Toteuta metodi: int huoneet(char[][] talo), joka palauttaa huoneitten lukumäärän. Pohjapiirroksessa merkki '#' tarkoittaa seinää ja merkki '.' lattiaa.

Huom! Kartan reunojen ulkopuolella on (implisiittiset) seinät. Siis esimerkiksi seuraavassa kartassa on kaksi huonetta.

.
#
.
		

Esimerkit

Esimerkki 1

##########
#.###....#
#..#####.#
#...#.##.#
##########

Huoneita: 3

Esimerkki 2

##########
#.#...##.#
#.#.#....#
#.....##.#
##########

Huoneita: 1

Tehtävä 3

Tällä kertaa huoneitten laskemisen sijaan on tehtävänä laskea huoneitten koot.

Toteutus

Toteuta metodi ArrayList<Integer> koot(char[][] talo) joka palauttaa huoneitten koot (jossain järjestyksessä) ArrayListissä.

Talon pohjapiirros annetaan ohjelmalle samassa muodossa kuin edellisessä tehtävässä.

Esimerkit

Esimerkki 1

##########
#.###....#
#..#####.#
#...#.##.#
##########

Huoneiden koot: 6, 6, 1. Tässä talossa on kaksi huonetta, joiden koko on 6 ruutua, ja yksi huone, jonka koko on 1 ruutu.

Esimerkki 2

##########
#.#..#.#.#
######.###
#..#.#.#.#
##########

Huoneiden koot: 3, 2, 2, 1, 1, 1, 1.

Tehtävä 4

Ratsu liikkuu shakkilaudalla kulkemalla kaksi ruutua johonkin suuntaan (vasen, oikea, ylös, alas), ja sitten yhden ruudun edellisen suunnan kanssa suorassa kulmassa olevaan suuntaan. Seuraavassa on piirretty ratsun (R) kaikki mahdolliset seuraavat ruudut (x):

........
........
..x.x...
.x...x..
...R....
.x...x..
..x.x...
........
		

Tehtävänäsi on etsiä ratsun lyhin reitti annetusta 8x8 shakkilaudan ruudusta toiseen.

Toteutus

Toteuta metodi: int ratsu(int x0, int y0, int x1, int y1), joka palauttaa lyhimmän reitin pituuden lähtöruudusta (x0,y0) maaliruutuun (x1,y1).

Esimerkit

Esimerkki 1

Metodikutsun ratsu(0,0,1,2) pitäisi palauttaa luku 1.

0.......
........
.1......
........
........
........
........
........

Esimerkki 2

Metodikutsun ratsu(0,0,7,7) pitäisi palauttaa luku 6. Samanpituisia reittejä on useita.

0.......
........
.1......
...2....
.....3..
.......4
.....5..
.......6

Tehtävä 5

HUOMAUTUS! Ennen tämän tehtävän tekemistä kannattaa tutustua Floyd-Warshallin algoritmiin. Se on kätevä tapa laskea tarpeeksi pienien verkkojen lyhimmät etäisyydet kaikille verkon solmupareille. Tämän tehtävän toteutus leveyshaulla on huomattavasti ikävämpää kuin käyttäen Floyd-Warshallia. Voit lukea algoritmista esimerkiksi kisakoodarin käsikirjan luvusta 17.

Uolevi on kokenut lentomatkaaja ja kertoo usein tarinoita matkoistaan. Mutta Maijan mielestä jotkin Uolevin tarinat kuulostavat epäilyttäviltä.

Tehtäväsi on selvittää, mitkä Uolevin tarinoista voivat pitää paikkansa ja mitkä ovat varmasti valetta.

Oletetaan esimerkiksi, että lentoasemia on 4 ja lentoyhteyksiä on 2: asemalta 1 pystyy lentämään asemille 2 ja 3. Uolevi väittää:

  1. "Lensin asemalta 1 asemalle 2 käyttäen 1 lentoa."
  2. "Lensin asemalta 1 asemalle 1 käyttäen 4 lentoa."
  3. "Lensin asemalta 1 asemalle 2 käyttäen 2 lentoa."
  4. "Lensin asemalta 1 asemalle 4 käyttäen 3 lentoa."

Väite 1 voi olla totta, koska asemalta 1 on lentoyhteys asemalle 2. Väite 2 voi myös olla totta, koska Uolevi on voinut lentää 1 -> 2 -> 1 -> 2 -> 1 käyttäen 4 lentoa. Väite 3 on valetta, koska asemalle 2 voi päästä 1 tai 3 lennolla mutta ei 2 lennolla. Väite 4 on valetta, koska asemalle 4 ei pääse mitenkään, erityisesti ei 3 lentoa käyttäen.

Toteutus

Tehtäväsi on toteuttaa luokka Lentoreitit, joka tarjoaa seuraavat metodit:

  • Lentoreitit(int n, int[] mista, int[] minne)
    konstruktorille annetaan tiedot kaikista lentoreiteistä
  • boolean mahdollinen(int alku, int loppu, int lennot)
    metodin tulee tutkia Uolevin väite: "lähdin liikkeelle paikasta alku ja saavuin lennot lennon jälkeen paikkaan loppu"

Lentoasemien määrä n on välillä 1..100, ja asemat on numeroitu kokonaisluvuin 1..n. Lentoyhteyksien määrä on välillä 1..105. Kaikki yhteydet ovat kaksisuuntaisia.

Uolevin väitteitä on välillä 1..105, ja jokaisessa väitteessä alku ja loppu ovat lentoasemien numerot ja lennot on kokonaisluku välillä 1..109. Jos väite voi olla totta, metodin tulee palauttaa true, ja jos väite on varmasti valetta, metodin tulee palauttaa false.

Esimerkit

Seuraava koodi testaa luokkaa:

Lentoreitit x = new Lentoreitit(4, new int[] {1, 1}, new int[] {2, 3});
System.out.println(x.mahdollinen(1, 2, 1));
System.out.println(x.mahdollinen(1, 1, 4));
System.out.println(x.mahdollinen(1, 2, 2));
System.out.println(x.mahdollinen(1, 4, 3));

Koodin tulostuksen tulisi olla seuraava:

true
true
false
false