Tehtävien deadline: ma 16.11. klo 04:01
Näissä tehtävissä sovelletaan syvyys- ja leveyssuuntaista hakua.
Tee 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.
Tämän verkon vierusmatriisi:
3 /|\ 4 | 0 \|/ \ 1---2
on:
01110 10111 11000 11001 01010
ja verkko on yhtenäinen.
Tämän verkon vierusmatriisi:
3 /| 4 | 0 \| | 1 2
on:
00100 00011 10000 01001 01010
ja verkko ei ole yhtenäinen.
Saat talon pohjapiirustuksen. Tehtävänäsi on laskea, montako huonetta talossa on. Huone tarkoittaa yhtenäistä seinien rajaamaa lattiatilaa.
Toteuta metodi
int huoneet(char[][] talo),
joka
palauttaa huoneitten lukumäärän. Pohjapiirroksessa
merkki
'#'
tarkoittaa seinää ja merkki
'.'
lattiaa.
Huom: juuri kartan reunojen ulkopuolella on (implisiittiset) seinät. Siis esimerkiksi seuraavassa kartassa on kaksi huonetta:
. # .
########## #.###....# #..#####.# #...#.##.# ##########
Huoneita: 3
########## #.#...##.# #.#.#....# #.....##.# ##########
Huoneita: 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.
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..105.
Ystävät on numeroitu kokonaisluvuin 1..n.
Taulukot mista ja minne
kuvaavat ystävyyssuhteet.
Ystävyyssuhteiden määrä on 0..105.
Metodin tulee palauttaa true,
jos lahjojen jakaminen on mahdollista
Uolemin haluamalla tavalla, ja muuten false.
| # | 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 |
Tällä kertaa huoneitten laskemisen sijaan on tehtävänä laskea
huoneitten koot. 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ä.
Pohjapiirros:
########## #.###....# #..#####.# #...#.##.# ##########
Huoneiden koot: 6,6,1
Tässä talossa on kaksi huonetta, joiden koko on 6 ruutua, ja yksi huone, jonka koko on 1 ruutu.
Pohjapiirros:
########## #.#..#.#.# ######.### #..#.#.#.# ##########
Huoneiden koot: 3,2,2,1,1,1,1
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. 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).
ratsu(0,0,1,2)=1
0....... ........ .1...... ........ ........ ........ ........ ........
ratsu(0,0,7,7)=6
(samanpituisia reittejä on toki useita)
0....... ........ .1...... ...2.... .....3.. .......4 .....5.. .......6