Tehtävien tiedostopohjat löytyvät täältä.
Huom: tehtävien palauttaminen onnistuu vasta tiistaina 19.4.
Nämä tehtävät ovat bonustehtäviä, joilla voi korvata aiempien viikkojen tehtäviä.
Tee ohjelma Kaupungit.java,
jolle annetaan kuvaus kaupunkien välisistä teistä
ja joka etsii lyhimmän reitin
kahden kaupungin välillä.
Jokaisen kaupunkiparin välillä
on korkeintaan yksi tie,
ja jokainen tie on kaksisuuntainen.
Voit olettaa, että kaupunkien nimet muodostuvat kirjaimista A–Z ja jokaisen tien pituus on kokonaisluku välillä 1–1000. Voit lisäksi olettaa, että kaupunkeja on korkeintaan 100 ja annettujen kaupunkien välillä on olemassa jokin reitti.
Montako? 4 Anna tiet: HELSINKI TURKU 170 KOTKA HELSINKI 130 TURKU TAMPERE 160 HELSINKI TAMPERE 180 1. kaupunki: TAMPERE 2. kaupunki: KOTKA Lyhin reitti: 310
Tässä lyhin reitti on Tampere -> Helsinki -> Kotka.
Montako? 4 Anna tiet: HELSINKI TURKU 10 KOTKA HELSINKI 130 TURKU TAMPERE 10 HELSINKI TAMPERE 180 1. kaupunki: TAMPERE 2. kaupunki: KOTKA Lyhin reitti: 150
Tässä lyhin reitti on Tampere -> Turku -> Helsinki -> Kotka.
Tee ohjelma Kaukaisimmat.java,
jolle annetaan kuvaus kaupunkien välisistä teistä
ja joka etsii kaksi kaukaisinta kaupunkia.
Tämä tarkoittaa, että lyhimmän reitin pituus
kaupunkien välillä on mahdollisimman suuri.
Kaupungit kuvataan samaan tapaan kuin edellisessä tehtävässä. Voit jälleen olettaa, että kaupunkeja on korkeintaan 100. Ohjelman tulee tulostaa lyhimmän reitin pituus kaukaisimpien kaupunkien välillä.
Montako? 3 Anna tiet: HELSINKI TURKU 170 KOTKA HELSINKI 130 HELSINKI TAMPERE 180 Lyhin reitti: 350
Tässä kaukaisimmat kaupungit ovat Turku ja Tampere, joiden välisen lyhimmän reitin pituus on 350.
Montako? 4 Anna tiet: HELSINKI TURKU 170 KOTKA HELSINKI 130 TURKU TAMPERE 160 HELSINKI TAMPERE 180 Lyhin reitti: 310
Tässä kaukaisimmat kaupungit ovat Tampere ja Kotka, joiden välisen lyhimmän reitin pituus on 310.
Hamiltonin kierros on verkossa oleva polku, joka alkaa jostain solmusta, käy kaikissa muissa solmuissa tasan kerran ja palaa sitten takaisin lähtösolmuun.
Tee ohjelma HamiltoninKierros.java,
joka tutkii, onko suuntaamattomassa verkossa Hamiltonin kierrosta.
Voit olettaa, että verkon solmut on numeroitu
kokonaisluvuin 1...n ja n on korkeintaan 10.
Solmut: 4 Kaaret: 4 Anna kaaret: 1 2 1 3 3 4 4 2 Verkossa on Hamiltonin kierros.
Tässä verkko on seuraavanlainen:
1--2 | | | | 3--4
Hamiltonin kierros on esimerkiksi 1 -> 2 -> 4 -> 3 -> 1.
Solmut: 4 Kaaret: 4 Anna kaaret: 1 2 1 3 3 4 4 1 Verkossa ei ole Hamiltonin kierrosta.
Tässä verkko on seuraavanlainen:
1--2 |\ | \ 3--4
Eulerin kierros on verkossa oleva polku, joka alkaa jostain solmusta, kulkee kaikkien kaarten kautta tasan kerran ja palaa sitten takaisin lähtösolmuun.
Tee ohjelma EulerinKierros.java,
joka tutkii, onko suuntaamattomassa verkossa Eulerin kierrosta.
Voit olettaa, että verkon solmut on numeroitu
kokonaisluvuin 1...n ja n on korkeintaan 10.
Solmut: 5 Kaaret: 6 Anna kaaret: 1 4 1 5 4 5 2 3 3 5 5 2 Verkossa on Eulerin kierros.
Tässä verkko on seuraavanlainen:
1 2--3 |\ | / | \|/ 4--5
Eulerin kierros on esimerkiksi 1 -> 4 -> 5 -> 3 -> 2 -> 5 -> 1.
Solmut: 5 Kaaret: 6 Anna kaaret: 1 4 1 2 4 5 2 3 3 5 5 2 Verkossa ei ole Eulerin kierrosta.
Tässä verkko on seuraavanlainen:
1--2--3 | | / | |/ 4--5
Matkailija haluaa matkustaa Helsingistä Rovaniemelle ja takaisin käyttämällä lentoreittejä. Hän haluaa vierailla mahdollisimman monessa kaupungissa mutta jokaisessa vain kerran (paitsi Helsingissä kahdesti: matkan alussa ja lopussa). Lisäksi hän haluaa matkustaa ensin koko ajan pohjoiseen ja sitten koko ajan etelään.
Tee ohjelma Kiertomatka.java
jolle annetaan kaupungit järjestyksessä
etelästä pohjoiseen ja sitten kaupunkien väliset
lentoyhteydet.
Ohjelman tehtävänä on selvittää,
kuinka monessa kaupungissa matkailija
voi käydä parhaimmillaan.
Voit olettaa, että jokin reitti on olemassa,
kaupunkeja on korkeintaan 100 ja niiden nimet muodostuvat
kirjaimista A–Z.
Kaupungit: 4 Anna kaupungit: HELSINKI TAMPERE OULU ROVANIEMI Lentoreitit: 5 Anna lentoreitit: HELSINKI OULU TAMPERE ROVANIEMI ROVANIEMI OULU TAMPERE OULU HELSINKI TAMPERE Kaupungit: 4
Tässä matkailija pääsee käymään kaikissa neljässä kaupungissa valitsemalla reitin näin: Helsinki -> Oulu -> Rovaniemi -> Tampere -> Helsinki.
Kaupungit: 4 Anna kaupungit: HELSINKI TAMPERE OULU ROVANIEMI Lentoreitit: 5 Anna lentoreitit: HELSINKI OULU TAMPERE ROVANIEMI ROVANIEMI OULU TAMPERE OULU HELSINKI ROVANIEMI Kaupungit: 3
Tässä matkailija pääsee käymään kolmessa kaupungissa valitsemalla reitin näin: Helsinki -> Oulu -> Rovaniemi -> Helsinki. Neljässä kaupungissa ei ole mahdollista vierailla puuttuvien lentoreittien vuoksi.
Tarkastellaan seuraavaa salausmenetelmää: Merkkijonon loppuun lisätään merkki $. Sitten muodostetaan kaikki merkkijonon kierrot siirtämällä yksi kerrallaan merkkejä merkkijonon alusta loppuun. Lopuksi järjestetään kierrot aakkosjärjestykseen (merkki $ on ennen kaikkia muita järjestyksessä), jolloin salattu merkkijono saadaan lukemalla järjestyksessä olevien kiertojen viimeiset merkit ylhäältä alas.
Esimerkiksi merkkijono AVAIN
muutetaan muotoon AVAIN$ ja
sen kierrot ovat seuraavat:
AVAIN$ VAIN$A AIN$AV IN$AVA N$AVAI $AVAIN
Tässä ovat kierrot aakkosjärjestyksessä:
$AVAIN AIN$AV AVAIN$ IN$AVA N$AVAI VAIN$A
Salattu merkkijono on siis NV$AIA.
Tee ohjelma Salakirjoitus.java,
jolle annetaan salattu merkkijono ja joka
selvittää alkuperäisen merkkijonon.
Voit olettaa, että merkkijono muodostuu
merkeistä A–Z ja
että merkkijonon pituus on korkeintaan 100000 merkkiä.
Salattu merkkijono: NV$AIA Purettu merkkijono: AVAIN
Salattu merkkijono: AVVVAAAI$ Purettu merkkijono: VAIVAAVA