Tarvitaan nyt silmukoita,
kaiken maailman taulukoita,
eri ehtoja kummastella,
aliohjelmia aavistella.
Mitä tässä luvussa käsitellään?
· silmukat ja valintalauseet
· totuustaulut
· pöytätesti
· muuttujat
· taulukot
· osoittimet
Vaikka jatkossa keskitymmekin oliopohjaiseen ohjelmointiin, tarvitaan yksittäisen olion metodin toteutuksessa algoritmeja. Riippumatta käytettävästä ohjelmointikielestä, tarvitaan algoritmeissa aina tiettyjä samantyyppisiä rakenteita.
Käsittelemme seuraavassa tyypilliset rakenteet nopeasti lävitse. Tarvitsisimme asioille enemmänkin aikaa, mutta otamme asiat tarkemmin esille käyttämämme ohjelmointikielen opiskelun yhteydessä. Lukijan on kuitenkin asioita tarkennettaessa syytä muistaa, ettei rakenteet ole mitenkään sidottu ohjelmointikieleen. Vaikka ne näyttäisivät kielestä täysin puuttuvankin (esim. assembler), voidaan ne kuitenkin lähes aina toteuttaa.
Triviaaleja algoritmeja lukuun ottamatta algoritminen suoritus tarvitsee ehdollisia toteutuksia:
Jos kello yli puolenyön ota taksi
muuten mene linja–autolla
Ehtolauseita voi ehtoon tulla useampiakin ja tällöin on syytä olla tarkkana sen kanssa, mihin ehtoon mahdollinen muuten–osa liittyy:
Jos kello 00.00–07.00
Jos sinulla on rahaa niin ota taksi
muuten kävele
muuten mene linja–autolla
Kuva 5.1 Ehtolauseet
Tehtävä 5.1 Ajanlisäys
Jos sinulla on muuttujassa t tunnit ja muuttujassa m minuutit, niin kirjoita algoritmi miten lisäät n minuuttia kellonaikaan t:m.
Tehtävä 5.2 Postimaksu
Kirjoita algoritmi g–painoisen kirjeen postimaksun määräämiseksi (saat keksiä hinnaston itse).
Usein ehtoja kasaantuu niin paljon, että peräkkäiset ja sisäkkäiset ehtolauseet muodostavat varsin sekavan kokonaisuuden. Tällöin voi olla helpompi käyttää valintalausetta:
Auto oli enenvanhaan rekisterinumeron 1. kirjaimen mukaan rekisteröity seuraavassa läänissä:
X Keski–Suomen lääni
K Kuopion lääni
M Mikkelin lääni
A,U Uudenmaan lääni
Kuva 5.2 switch–valintalause
Tehtävä 5.3 Korvaaminen ehtolauseilla
Esitä auton rekisteröintipaikan riippuvuus rekisterin ensimmäisestä kirjaimesta sisäkkäisten ehtolauseiden avulla.
Hyvin usein algoritmi tarvitsee toistoa: Esimerkiksi ohjeet (vuokaavio) hiekkarannalla toimimiseksi jos nenä näyttää merelle päin:
Kuva 5.3 do–silmukka ja do-while–silmukka
Ehtolause voi olla silmukan alussa, tällöin on mahdollista ettei silmukan runkoa tehdä yhtään kertaa. Ehto voi olla myös silmukan jälkeen, jolloin silmukan runko tehdään vähintään yhden kerran. Joissakin kielissä on lisäksi mahdollisuus silmukan rungon keskeltä poistuminen.
Silmukoihin liittyy aina ohjelmoinnin eräs klassisimmista vaaroista: päättymätön silmukka! Tämän takia silmukoita tulee käsitellä todella huolella. Eräs oleellinen asia on aina muistaa suorittaa silmukan rungossa jokin silmukan lopetusehtoon vaikuttava toimenpide. Mitä tapahtuu muuten?
Myös silmukan suorituskertojen lukumäärän kanssa tulee olla tarkkana. Silmukka tulee helposti suoritettua yhden kerran liikaa tai yhden kerran liian vähän.
Tehtävä 5.4 Uiminen
Mitä eroa on kahdella edellä esitetyllä "uimaan–meno" –algoritmilla? Mitä ehtoja algoritmiin voisi vielä lisätä?
Tehtävä 5.5 Ynnää luvut 1–100
Kirjoita algoritmi lukujen 1–100 yhteenlaskemiseksi sekä do–while– että while –silmukan avulla.
Algoritmeissa tarvitaan usein muuttujia.
kellonaika
rahan määrä
Yksinkertaisessa tapauksessa muuttuja voi olla yksinkertaista tyyppiä kuten kellonaika (jos ilmaistu minuutteina), rahasumma jne.
Yksinkertainen luvun jaollisuuden testausalgoritmi voisi olla vaikkapa seuraavanlainen:
Jaetaan tutkittavaa lukua jakajilla 2,3,5,7...luku/2.
Jos jokin jako menee tasan, niin ei alkuluku:
0. Laita jakaja:=2, kasvatus:=1,
Jos luku=2 lopeta, alkuluku
1. Jaa luku jakajalla. Meneekö jako tasan?
– jos menee, on luku jaollinen jakajalla, lopeta
2. Kasvata jakajaa kasvatus arvolla (jakaja:=jakaja+kasvatus)
3. Kasvatus:=2; (koska parillisilla ei kannata enää jakaa)
4. Onko jakaja<luku/2?
– jos on, niin jatka kohdasta 1
– muuten lopeta, luku on alkuluku
Tehtävä 5.6 Vuokaavio
Piirrä jaollisuuden testausalgoritmista vuokaavio.
Hyvin usein algoritmi kannattaa pöytätestata. Pöytätesti alkaa kirjoittamalla sarakkeiksi kaikki algoritmissa esiintyvät muuttujat. Muuttujiksi voidaan kirjoittaa myös algoritmissa esiintyviä ehtoja. Tällainen muuttuja voi saada arvon kyllä tai ei. Pöytätestin riveiksi kirjoitetaan algoritmin eteneminen vaiheittain. Sarakkeisiin muuttujille kirjoitetaan uusia arvoja vain niiden muuttuessa.
Testataan esimerkiksi edellisen esimerkin algoritmi:
askel |
Luku |
Jakaja |
Kasvatus |
Luku/Jakaja |
Jako tasan? |
Jakaja<Luku/2? |
Tulostus |
0 |
25 |
2 |
1 |
|
|
|
|
1 |
|
|
|
12.500 |
ei |
|
|
2 |
|
3 |
|
|
|
|
|
3 |
|
|
2 |
|
|
|
|
4 |
|
|
|
|
|
3<12.5 |
|
1 |
|
|
|
8.333 |
ei |
|
|
2 |
|
5 |
|
|
|
|
|
3 |
|
|
2 |
|
|
|
|
4 |
|
|
|
|
|
5<12.5 |
|
1 |
|
|
|
5.000 |
kyllä |
|
Jaollinen 5:llä |
askel |
Luku |
Jakaja |
Kasvatus |
Luku/Jakaja |
Jako tasan? |
Jakaja<Luku/2? |
Tulostus |
0 |
23 |
2 |
1 |
|
|
|
|
1 |
|
|
|
11.500 |
ei |
|
|
2 |
|
3 |
|
|
|
|
|
3 |
|
|
2 |
|
|
|
|
4 |
|
|
|
|
|
3<11.5 |
|
1 |
|
|
|
7.667 |
ei |
|
|
2 |
|
5 |
|
|
|
|
|
3 |
|
|
2 |
|
|
|
|
4 |
|
|
|
|
|
5<11.5 |
|
1 |
|
|
|
4.600 |
ei |
|
|
2 |
|
7 |
|
|
|
|
|
3 |
|
|
2 |
|
|
|
|
4 |
|
|
|
|
|
7<11.5 |
|
1 |
|
|
|
3.286 |
ei |
|
|
2 |
|
9 |
|
|
|
|
|
3 |
|
|
2 |
|
|
|
|
4 |
|
|
|
|
|
9<11.5 |
|
1 |
|
|
|
2.556 |
ei |
|
|
2 |
|
11 |
|
|
|
|
|
3 |
|
|
2 |
|
|
|
|
4 |
|
|
|
|
|
11<11.5 |
|
1 |
|
|
|
2.091 |
ei |
|
|
2 |
|
13 |
|
|
|
|
|
3 |
|
|
2 |
|
|
|
|
4 |
|
|
|
|
|
13>11.5 |
Alkuluku |
Usein pöytätesti antaa hyviä vinkkejä myös algoritmin jatkokehittelylle. Käytännön työssä osa pöytätestistä voidaan suorittaa debuggereiden avulla. Joskus kuitenkin voi olla niin paljon esitietoa algoritmille, että tarvittavan testiohjelman rakentaminen voi olla työlästä. Pöytätestihän voidaan aloittaa minkälaisesta alkutilasta tahansa. Samoin yksi pöytätestin etuja on siitä jäävä historia. Usein debuggerit näyttävät vain yhden ajanhetken tilanteen, siis yhden pöytätestin rivin kerrallaan.
Tehtävä 5.7 Algoritmin parantaminen
Tarvitsisimmeko algoritmin kohtaa 4 lainkaan? Voitaisiinko algoritmin lopetus hoitaa muuten?
Tehtävä 5.8 Pöytätesti
Pöytätestaa edellinen algoritmi kun syöttönä on luku 121.
Pöytätestaa molemmat Ynnää luvut 1–100 –algoritmisi versiona Ynnää luvut 1–6.
Tutkikaamme aikaisempia korttipakkaesimerkkejämme! Nyt tietorakenteeksi ei enää riitäkään pelkkä yksi muuttuja. Mikäli pakasta on otettu esiin pelkät padat, tarvitsisimme 13 muuttujaa. Näiden kunkin nimeäminen erikseen olisi varsin työlästä.
Tarvitsemme siis jonkin muun tietorakenteen. Mahdollisuuksia on useita: listat, jonot, pinot ja taulukot. Ohjelmoinnin alkuvaiheessa taulukot ovat tietorakenteista helpoimpia, joten keskitymme niihin aluksi.
Varataan pöydältä tilaa leveyssuunnassa 13 kortille. Varattua tilaa voimme nimittää taulukoksi tai vektoriksi. Taulukon yksi alkio on yhdelle kortille varattu paikka. Taulukon yhden alkion sisältö on se kortti, joka on siinä paikassa.
Mikäli numeroimme varatut paikat vaikkapa 0:sta alkaen vasemmalta oikealle, on meidän korteillamme osoitteet 0–12:
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
ª |
ª |
ª |
ª |
ª |
ª |
ª |
ª |
ª |
ª |
ª |
ª |
ª |
7 |
3 |
K |
2 |
5 |
9 |
4 |
6 |
Q |
10 |
J |
A |
8 |
Nyt voimme käsitellä yksittäisiä kortteja aivan kuin ne olisivat yksittäisiä muuttujia. Viittaamme tiettyyn korttipaikkaan (taulukon alkioon) sen indeksillä (olkoon taulukon nimi kortit):
paikassa kortit[5] meillä on pata 9
paikassa kortit[8] meillä on pata akka
Minkälaisia algoritmeja tulee vastaan taulukoita käsiteltäessä? Esim. ª9:n siirtäminen taulukon viimeiseksi vaatisi ª4:en siirtämistä paikkaan 5. ª6:en siirtämistä paikkaan 6, ªQ:n siirtämistä paikkaan 7 jne. Näin loppuun saataisiin raivatuksi paikka ª9:lle.
Lajittelun ilman valtaisaa korttien siirtelyä voisimme hoitaa seuraavasti:
0. laita alku paikkaan 0
1. etsi alku paikasta lähtien pienin kortti
2. vaihda pienin ja paikassa alku oleva kortti
3. alku:=alku+1
4. mikäli alku<suurin indeksi, niin jatka 1
Sovitaan, että ässä=1. Nyt pienimmän kortin etsimisalgoritmi voisi olla seuraava:
0. Alkuarvaus: pien.paikka:=alku, tutki:=alku
1. Jos kortit[tutki] < kortit[pien.paikka]
niin pien.paikka:=tutki
2. tutki:=tutki+1
3. Jos tutki<=suurin indeksi, niin jatka 1.
Voisimme vielä pöytätestata algoritmin:
|
pien. |
|
Kortit |
[tutki]< |
tutki< |
||||||||||||
askel |
paikka |
tutki |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
[pp] |
suur.ind |
0 |
0 |
0 |
ª7 |
ª3 |
ªK |
ª2 |
ª5 |
ª9 |
ª4 |
ª6 |
ªQ |
ª10 |
ªJ |
ªA |
ª8 |
|
|
1 |
|
|
Ýt |
|
|
|
|
|
|
|
|
|
|
|
|
7<7 ei |
|
2&3 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
juu |
1 |
1 |
|
Ý |
t |
|
|
|
|
|
|
|
|
|
|
|
3<7 juu |
|
2&3 |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
juu |
1 |
|
|
|
Ý |
t |
|
|
|
|
|
|
|
|
|
|
K<3 ei |
|
2&3 |
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
juu |
1 |
3 |
|
|
Ý |
|
t |
|
|
|
|
|
|
|
|
|
2<3 juu |
|
2&3 |
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
juu |
1 |
|
|
|
|
|
Ý |
t |
|
|
|
|
|
|
|
|
5<2 ei |
|
2&3 |
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
juu |
1 |
|
|
|
|
|
Ý |
|
t |
|
|
|
|
|
|
|
9<2 ei |
|
2&3 |
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
juu |
1 |
|
|
|
|
|
Ý |
|
|
t |
|
|
|
|
|
|
4<2 ei |
|
2&3 |
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
juu |
1 |
|
|
|
|
|
Ý |
|
|
|
t |
|
|
|
|
|
6<2 ei |
|
2&3 |
|
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
juu |
1 |
|
|
|
|
|
Ý |
|
|
|
|
t |
|
|
|
|
Q<2 ei |
|
2&3 |
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
juu |
1 |
|
|
|
|
|
Ý |
|
|
|
|
|
t |
|
|
|
10<2 ei |
|
2&3 |
|
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
juu |
1 |
|
|
|
|
|
Ý |
|
|
|
|
|
|
t |
|
|
J<2 ei |
|
2&3 |
|
11 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
juu |
1 |
11 |
|
|
|
|
Ý |
|
|
|
|
|
|
|
t |
|
A<2 juu |
|
2&3 |
|
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
juu |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Ý |
t |
8<A ei |
|
2&3 |
|
13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ei |
Tehtävä 5.9 Lajittelun testaus
Oletetaan, että pienimmän etsimisalgoritmi toimii. Pöytätestaa edellä esitelty lajittelualgoritmi edellisen pöytätestin mukaisella korttien järjestyksellä.
Onko tämä insertion sort? Missä on lajiteltujen kasa ja missä lajittelemattomien?
Tehtävä 5.10 Korttien poisto
Kirjoita algoritmi kuvakorttien poistamiseksi taulukosta käyttäen indeksejä.
Edellisessä pöytätestissä merkitsimme pienen merkin niiden korttien kohdalle, joita kunakin hetkenä tutkimme. Kun tutkimme esimerkiksi paikoissa 3 ja 10 olevia kortteja (P2 ja PJ) voisimme sanoa, että muuttuja pien.paikka osoitti korttiin pata 2 ja muuttuja tutki korttiin pata jätkä. Näin ollen voisimme oikeastaan sanoa, että (indeksi)muuttujat pien.paikka ja tutki ovat osoittimia korttipakkaan. Niiden osoittamassa paikassa (indeksit 3 ja 10) on tietyt kortit (P2 ja PJ).
Lajittelualgoritmi voitaisiin lausua esimerkiksi:
0. levitä kortit rinnakkain pöydälle
osoita vasemman käden etusormella ensimmäiseen korttiin
1. etsi vasemman käden osoittamasta kohdasta alkaen oikealle
pienin kortti ja osoita sitä oikean käden etusormella
2. vaihda etusormien kohdalla olevat kortit keskenään
3. siirrä vasemman käden etusormea yksi kortti oikealle päin
4. mikäli vasen sormi vielä kortin päällä, jatka kohdasta 1.
|
|
|
|
|
|
|
|
|
|
|
|
|
ª |
ª |
ª |
ª |
ª |
ª |
ª |
ª |
ª |
ª |
ª |
ª |
ª |
7 |
3 |
K |
2 |
5 |
9 |
4 |
6 |
Q |
10 |
J |
A |
8 |
G |
|
|
|
|
|
|
|
|
|
|
G |
|
Osoittimen ja indeksin ero on siinä, että osoittimen tapauksessa emme yleensä koskaan ole kiinnostuneita itse osoittimen arvosta (osoitteesta, siitä indeksistä missä kohdin olemme menossa), vaan osoittimen osoittaman paikan sisällöstä (sormen kohdalla olevan kortin arvo tai ei korttia). Indeksejä käsitellessämme tutkimme monesti myös itse indeksin arvoa (tutki=3 –>kortit[tutki]=P2).
Osoitin voi tarvittaessa osoittaa myös itse taulukon ulkopuolelle. Mikäli kirjoittaisimme pöydälle numeroita, voisimme osoittaa sormella yhtä hyvin pöydälle kirjoitettuja numeroita (älkää hyvät ihmiset nyt töhrätkö pöytää!) kuin pöydälle levitettyjä kortteja (taulukon alkioita).
Siis indeksit liittyvät kiinteästi taulukoihin ja osoittimet voivat liittyä mihin tahansa tietorakenteisiin alkaen yksinkertaisesta muuttujasta päätyen monimutkaisen lista– tai puurakenteen alkioon.
Javassa tällä tavalla käyttäytyviä osoittimia vastaavat iteraattorit. Itse asiassa Javan kaikki "oliomuuttujat" ovat osoittimia, niitä sanotaan vaan viitteiksi. Erona esimerkiksi C++:n osoittimiin on se, että Javan viitteitä ei voi muuttaa muuta kuin osoittamaan toista alkiota. Eli Javan viitteillä käsky "siirry yksi alkio eteenpäin" on mahdotonta. Javan iteraattoreilla tämä sen sijaan onnistuu. C++:ssa on aidot osoittimet - joiden kanssa voi helposti myös möhliä laittamalla osoittimen osoittamaan paikkaan johon se ei saisi osoittaa). C++:ssa on myös viitteet (reference), joita tosin ei voi siirtää mihinkään luomisen jälkeen. C++:n iteraattorit muistuttavat jopa syntaksiltaan C++:n osoittimia ja itse asiassa C++:n osoitin käy algoritmissa paikkaan, johon tarvitaan iteraattori.
Tehtävä 5.11 Korttien poisto osoittimia käyttäen
Kirjoita algoritmi kuvakorttien poistamiseksi taulukosta käyttäen osoittimia.
Pöytätestaa algoritmi.
Yksiulotteista taulukkoa voidaan verrata rivitaloon tai ruutupaperin yhteen riviin. Kaksiulotteinen taulukko on vastaavasti kuten kapea kerrostalo tai koko ruutupaperin yksi sivu. Tarvitsemme vastaavasti useampia osoitteita (indeksejä) osoittamaan millä rivillä ja missä sarakkeessa liikumme.
Alla on esimerkki 5x7 taulukosta (ª=pata, §=Risti, ¨=ruutu, ©=hertta):
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
0 |
ª |
|
|
|
ª |
|
|
|
7 |
|
|
|
A |
|
|
1 |
|
§ |
|
© |
|
|
|
|
|
K |
|
5 |
|
|
|
2 |
|
|
¨ |
|
|
|
|
|
|
|
A |
|
|
|
|
3 |
© |
ª |
¨ |
ª |
© |
© |
¨ |
|
7 |
2 |
2 |
9 |
6 |
3 |
7 |
4 |
|
|
© |
|
|
|
© |
|
|
|
2 |
|
|
|
J |
Jos taulukon nimi on peli, niin paikassa 3,1 on kortti pata 2:
peli[3][1] = ª2
Tehtävä 5.12 Kaksiulotteisen taulukon indeksit
Kirjoita kaikkien esimerkissä olevien korttien osoitteet em. muodossa.
Kaksiulotteista taulukkoa nimitetään usein matriisiksi.
Usein taulukoiden indeksit ilmoitetaan eri järjestyksessä kuin koordinaatiston (x,y)–koordinaatit. Tämä johtuu siitä ajattelutavasta, että taulukon rivi sinänsä voidaan kuvitella yhdeksi alkioksi (rivityypiksi) ja tällöin ilmaisu
peli[3]
tarkoittaa koko riviä (©7, ª2, ¨2, ª9, ©6, ©3, ¨7), jonka indeksi on kolme. Mikäli tämän perään laitetaan vielä [1], niin tarkoitetaan ko. tietorakenteen alkiota jonka indeksi on yksi (ª2).
Tarvittaessa moniulotteiset taulukot voidaan muodostaa yksiulotteisenkin taulukon avulla. Esimerkin taulukko voitaisiin muodostaa yksiulotteisesta taulukosta siten, että yksiulotteisen taulukon 7 ensimmäistä alkiota kuvaisivat matriisin 0:ta riviä, 7 seuraavaa matriisin ensimmäistä riviä jne.
Siis mikäli yksiulotteisen taulukon nimi olisi pakka, niin voisimme käyttää samaistuksia:
peli[3][1] = pakka[7*3+1]
peli[j][i] = pakka[7*j+i]
Olemme siis numeroineet kaksiulotteisen taulukon alkiot juoksevasti. Voimmehan tehdä näin myös kerrostalon huoneistoille tai teatterin istumapaikoille.
Taulukot voivat olla myös useampiulotteisia, esimerkiksi 3x4x5 taulukko:
0 1 2 3 4
┌──┐ ┌──┐ ┌──┐ ┌──┐ ┌──┐2
0 │ ┌┴─┐ │ ┌┴─┐ │ ┌┴─┐ │ ┌┴─┐ │ ┌┴─┐1
└─┤ ┌┴─┐ └─┤ ┌┴─┐ └─┤ ┌┴─┐ └─┤ ┌┴─┐└─┤ ┌┴─┐0
└─┤ │ └─┤PJ│ └─┤ │ └─┤ │ └─┤ │
└──┘ └──┘ └──┘ └──┘ └──┘
┌──┐ ┌──┐ ┌──┐ ┌──┐ ┌──┐
1 │ ┌┴─┐ │ ┌┴─┐ │R5┴─┐ │ ┌┴─┐ │ ┌┴─┐
└─┤ ┌┴─┐ └─┤ ┌┴─┐ └─┤ ┌┴─┐ └─┤HA┴─┐ └─┤ ┌┴─┐
└─┤ │ └─┤ │ └─┤ │ └─┤ │ └─┤ │
└──┘ └──┘ └──┘ └──┘ └──┘
┌──┐ ┌──┐ ┌──┐ ┌──┐ ┌──┐
2 │ ┌┴─┐ │ ┌┴─┐ │ ┌┴─┐ │ ┌┴─┐ │ ┌┴─┐
└─┤ ┌┴─┐ └─┤ ┌┴─┐ └─┤ ┌┴─┐ └─┤ ┌┴─┐ └─┤ ┌┴─┐
└─┤ │ └─┤ │ └─┤ │ └─┤ │ └─┤ │
└──┘ └──┘ └──┘ └──┘ └──┘
┌──┐ ┌──┐ ┌──┐ ┌──┐ ┌──┐
3 │P7┴─┐ │ ┌┴─┐ │ ┌┴─┐ │ ┌┴─┐ │ ┌┴─┐
└─┤ ┌┴─┐ └─┤ ┌┴─┐ └─┤ ┌┴─┐ └─┤ ┌┴─┐ └─┤ ┌┴─┐
└─┤ │ └─┤ │ └─┤ │ └─┤ │ └─┤ │
└──┘ └──┘ └──┘ └──┘ └──┘
isopeli[0][0][1]=PJ
isopeli[2][1][2]=R5
isopeli[1][1][3]=HA
isopeli[2][3][0]=P7
Tehtävä 5.13 Sijoitus 3–ulotteiseen taulukkoon
Esitä 5 muuta sijoitusta taulukkoon.
Tehtävä 5.14 3–ulotteinen taulukko 1–ulotteiseksi
Esitä kaava miten edellä oleva 3–ulotteinen taulukko voitaisiin esittää yksiulotteisella taulukolla.
Aikaisempi satunnaisen matkaajan sanastomme on oikeastaan myös kolmiulotteinen taulukko:
0 1 2
0 minä jag i
1 sinä du you
2 hän han he
Se on kaksiulotteinen taulukko sanoista. Mitä sitten yksi sana on? Se on yksiulotteinen taulukko kirjaimista!
0 1 2 3 4
┌──┐ ┌──┐ ┌──┐ ┌──┐ ┌──┐2
0 │h┌┴─┐ │ä┌┴─┐ │n┌┴─┐ │ ┌┴─┐ │ ┌┴─┐1
└─┤s┌┴─┐ └─┤i┌┴─┐ └─┤n┌┴─┐ └─┤ä┌┴─┐└─┤ ┌┴─┐0
└─┤m │ └─┤i │ └─┤n │ └─┤ä │ └─┤ │
└──┘ └──┘ └──┘ └──┘ └──┘
┌──┐ ┌──┐ ┌──┐ ┌──┐ ┌──┐2
1 │h┌┴─┐ │a┌┴─┐ │n┌┴─┐ │ ┌┴─┐ │ ┌┴─┐1
└─┤d┌┴─┐ └─┤u┌┴─┐ └─┤ ┌┴─┐ └─┤ ┌┴─┐└─┤ ┌┴─┐0
└─┤j │ └─┤a │ └─┤g │ └─┤ │ └─┤ │
└──┘ └──┘ └──┘ └──┘ └──┘
┌──┐ ┌──┐ ┌──┐ ┌──┐ ┌──┐2
2 │h┌┴─┐ │e┌┴─┐ │ ┌┴─┐ │ ┌┴─┐ │ ┌┴─┐1
└─┤y┌┴─┐ └─┤o┌┴─┐ └─┤u┌┴─┐ └─┤ ┌┴─┐└─┤ ┌┴─┐0
└─┤i │ └─┤ │ └─┤ │ └─┤ │ └─┤ │
└──┘ └──┘ └──┘ └──┘ └──┘
Siis "you" sanan indeksi on [1][2] ja sen kirjaimen "y" indeksi on [0]. Siis kaiken kaikkiaan "you"–sanan "y"-kirjaimen indeksi olisi [1][2][0].
Taulukko voitaisiin järjestää 3–ulotteiseksi myös toisinkin. Esimerkiksi yhdessä "tasossa" olisi yksi kieli jne.
Tehtävä 5.15 3–ulotteinen taulukko
Esitä edellisessä esimerkissä kaikkien kirjainten indeksit.
Millaisella yhden kirjaimen sijoituksella muuttaisit sanan "han" sanaksi "hon"?
Tehtävä 5.16 4–ulotteinen taulukko
Mitenkä tavallinen kirja voitaisiin kuvitella 3–ulotteiseksi taulukoksi?
Miten kirja voitaisiin kuvitella 4–ulotteiseksi taulukoksi?
Piirrä edellisiin perustuen esimerkki 4–ulotteisesta taulukosta ja anna muutama esimerkkisijoitus.
Osoitinmuuttuja osoittaisi myös moniulotteisessa taulukossa yhteen alkioon kerrallaan. Esimerkiksi osoittamalla "you"–sanan "y"-kirjaimeen.
Moniulotteisen ja yksiulotteisen taulukon väliset muunnokset ovat tärkeitä, koska tietokoneen muisti (1997) on lähes aina yksiulotteinen. Siis loogisesti moniulotteiset taulukot joudutaan lopulta aina toteuttamaan yksiulotteisina. Onneksi useat kielet sisältävät moniulotteiset taulukot tietotyyppinä ja kääntäjät tekevät sitten muunnoksen. Tästä huolimatta esimerkiksi C–kielessä joudutaan usein muuttamaan moniulotteisia taulukoita yksiulotteisiksi.
Taulukko voi olla myös taulukko osoittimista. Esimerkiksi sanastomme tapauksessa kaikki sanat voisivat olla yhdessä "möykyssä":
0 1 2 3
0123456789012345678901234567890123
minä jag i sinä du you hän han he
Itse sanasto voisi sitten olla taulukko osoittimia sanojen alkupaikkoihin:
|
0 |
1 |
2 |
0 |
00 |
05 |
09 |
1 |
11 |
16 |
19 |
2 |
23 |
27 |
31 |
Siis taulukon paikasta sanasto[1][0] löytyy osoitin. Tämän osoittimen arvo on tässä esimerkissä 11. Siis osoitin viittaa sanan "sinä" alkuun. Tässä 2-ulotteinen taulukko osoittimista 1-ulotteiseen merkkitaulukkoon
// C++:lla
char *sanasto[3][3];
Tehtävä 5.17 Sanojen muuttaminen
Mitä ongelmia edellä olisi, mikäli yhdenkin sanan pituutta kasvatettaisiin?
Voitaisiinko edellä käyttää samoja sanoja uudestaan ja jos niin miten?
Osoitinmuuttujaa voitaisiin kuvitella myös seuraavasti: Olkoon meillä osoitekirja (osoitteet) jossa on sivuja:
sivu 0: |
|
sivu 1: |
|
sivu 2: |
Kassinen Katto Katto 3452 |
|
Susi Sepe - |
|
Ankka Aku Ankkalinna 1234 |
Meidän osoitekirjamme on tavallaan taulukko osoittimista (tässä tapauksessa osoitteita, älä sotke termejä!). Taulukon osoitteet paikassa 1 (sivu 1) on osoite "Sepe Sudelle". Mitä tapahtuu mikäli kirjoitamme kokonaan uuden henkilön osoitteen sivulla 1 olevan osoitteen päälle (sijoitetaan uusi arvo osoitinmuuttujalle sivu[1])?
sivu 1: |
|
C++:lla: sivu[1] = &Batman; Javalla: Sivu[1] = Batman; |
Batman Gotham City 999 |
|
Mitä tapahtuu "Sepe Sudelle"? Tuskinpa sijoitus osoitekirjassamme siirtää "Sepe Sutta" yhtään mihinkään "Perämetsästä", tai tekee edes häntä murheelliseksi! Tämä on eräs tyypillinen virhekäsitys osoitinmuuttujia käytettäessä. Osoitinmuuttujaan sijoittaminen ei muuta tietenkään itse tiedon sisältöä. Mutta sijoittaminen siihen paikkaan johon osoitinmuuttuja osoittaa (esimerkissämme "Sepe Suden" asuntoon) muuttaa tietenkin myös itse tiedon sisältöä.
// C++:lla
sivu[1] = uusi_osoite; // ei vaikuta Sepe Suteen
*sivu[1] = uusi_henkilo; // laittaa uuden henkilön Sepen osoitteeseen
// = "tähdätään osoitetta pitkin"
// Javalla
sivu[1] = uusi_osoite; // ei vaikuta Sepe Suteen
sivu[1].setNimi("Batman") // tämän lähemmäksi Javalla ei pääse
Vastaavasti jos meillä on indeksimuuttuja nimeltä snro, niin sijoitus muuttujalle
snro=2
ei muuta mitenkään itse sivun sisältöä. Vasta sijoitus
sivu[snro]=
muuttaisi sivun 2 sisältöä.
Aliohjelma on tarkempi kuvaus tietylle asialle. Tämä kuvaus esitetään jossakin toisessa kohdassa ja sitä ei suinkaan tarvitse joka kerta lukea uudelleen.
Keittokirjassa lukee:
pyöritä lihapullataikinasta pyöreitä pullia
paista pullat kauniin ruskeiksi
Miten pullat paistetaan kauniin ruskeiksi. Tämä olisi edellisen algoritmin aliohjelma. Kokenut kokki ei välitä aina (eikä edes suostuisi) joka reseptin kanssa lukea itse paistamisohjetta. Aloittelija tätä saattaisi tarvita, jottei naapuri hälyttäisi palokuntaa paikalle liian savunmuodostuksen takia. Siis toivottavasti keittokirjasta jostakin kohti löytyisi myös itse paistamisohje.
Aliohjelmille on tyypillistä, että ne saattavat suoriutua vastaavista tehtävistä eri muuttujillekin. Näitä kutsukerroista riippuvia muuttujia sanotaan parametreiksi.
Esim. lihapullan paisto–ohje saattaa semmoisenaan kelvata myös tavalliselle pullalle:
paista("paistettava","c")
Korvaa seuraavassa sana "paistettava" sillä mitä olet
paistamassa ja "c" sillä lämpötilalla, joka keittokirjan
ohjeessa ko. paistettavan kohdalla on:
0. laita "paistettavat" pellille
1. lämmitä uuni "c"–asteeseen
2. laita pelti uuniin
...
9. mikäli "paistettavat" ovat mustia mene ostamaan
kaupasta valmiita
...
Tehtävä 5.18 Lihapullan paistaminen
Täydennä edellinen paistamisalgoritmi. Onko parametrejä tarpeeksi?
Usein helpostakin tehtävästä seuraa monia eri vaihtoehtoja, joiden täydellinen hallitseminen pelkästään päässä saattaa olla ylivoimaista. Tällöin avuksi tulee totuus– ja päätöstaulut. Päätöstaulu on totuustaulun pidemmälle viety versio.
Tutkikaamme aluksi muutamaa esimerkkiä jotka eivät suoranaisesti liity ohjelmointiin, mutta joissa esiintyy täsmälleen vastaava tilanne:
Uusien opiskelijoiden lähtötasotesti 1991 (n. 20% oli osannut vastata oikein tähän tehtävään):
Tehtävä 3.4: Seisot tienhaarassa tuntemattomassa maassa. Toinen teistä vie pääkaupunkiin. Maan asukkaat joko valehtelevat aina tai puhuvat aina totta. Toisen tien alussa seisoskelee yksi heistä. Esität hänelle kyllä vai ei –kysymyksen ja saat vastauksen. Mitä kahta seuraavista neljästä kysymyksestä olisit voinut käyttää ollaksesi varma siitä, kumpi tie vie pääkaupunkiin – riippumatta siitä valehteleeko asukas vai ei?
1. Viekö tämä tie pääkaupunkiin?
2. Olisitko sanonut, että tämä tie vie pääkaupunkiin, jos olisin kysynyt sinulta sitä?
3. Onko niin, että tämä joko on tie pääkaupunkiin, tai sitten sinä puhut totta (mutta ei molemmin tavoin)?
4. Onko totta, että tämä tie vie pääkaupunkiin ja sen lisäksi sinä puhut totta?
Erotelkaamme eri kysymykset:
1 = |
A |
Viekö pääkaupunkiin? |
|
B |
Puhutko totta? (mielenkiinnon vuoksi) |
2 = |
C |
Olisitko sanonut että vie jos A? |
3 <- |
D |
Tie pääk. XOR puhut totta? |
4 <- |
E |
Tie pääk. AND puhut totta? |
Nyt voimme kirjoittaa eri vaihtoehtojen mukaan seuraavan totuustaulun (V=vastaus kun valehteleminen otetaan huomioon):
Tie vie pää- |
Puhuu |
1 |
|
2 |
|
3 |
|
|
4 |
|
kaupunkiin |
totta |
A |
B |
C |
D |
|
V |
E |
|
V |
E |
E |
K |
K |
E |
E |
|
K |
E |
|
K |
E |
K |
E |
K |
E |
K |
|
K |
E |
|
E |
K |
E |
E |
K |
K |
K |
|
E |
E |
|
K |
K |
K |
K |
K |
K |
E |
|
E |
K |
|
K |
Siis 2 ja 3 vastauksissa on järkevä korrelaatio siihen viekö tie pääkaupunkiin vai ei.
Mistä tiedämme milloin kaikki vaihtoehdot on kirjoitettu? Mikäli systeemiin vaikuttavia asioita on n kappaletta ja kukin on kyllä/ei tyyppinen (0/1), niin vaihtoehdot on helpointa saada aikaan kirjoittamalla kaikki n–bittiset binääriluvut järjestyksessä (esimerkissämme n=2) ja suorittamalla sitten tarvittavat samaistukset (esim. E=0 ja K=1). Vaihtoehtoja on tällöin 2n.
00 –> E E
01 –> E K
10 –> K E
11 –> K K
Tehtävä 5.19 Kombinaatioiden lukumäärä
Olkoon meillä tehtävä, jossa yksi muuttuja voi saada arvot K,E,tyhjä ja toinen muuttuja arvot 5 ja 10. Kirjoita kaikki ko. muuttujien kombinaatiot.
Mikäli meillä on vaihtoehtoja n kappaletta ja kukin voi saada ki eri arvoa, niin montako eri kombinaatiota saamme aikaiseksi?
Ottakaamme toinen vastaava tehtävä:
Tehtävä 4.3: Pekka valehtelee maanantaisin, tiistaisin ja keskiviikkoisin; muina viikonpäivinä hän puhuu totta. Paavo valehtelee torstaisin, perjantaisin ja lauantaisin; muina viikonpäivinä hän puhuu totta. Eräänä päivänä Pekka sanoi: "Eilen valehtelin!" Paavo vastasi: "Niin minäkin!" Mikä viikonpäivä oli?
Minä päivinä kaverukset saattaisivat sanoa ko. lausuman? Näitä päiviä on tietysti ne, jolloin joko eilen valehdeltiin ja tänään puhutaan totta TAI eilen puhuttiin totta ja tänään valehdellaan. (XOR)
|
Pekka |
valehteli eilen |
Paavo |
valehteli |
|
sunnuntai |
|
|
|
k sanoo |
|
maanantai |
V |
sanoo |
|
|
|
tiistai |
V |
k |
|
|
|
keskiviikko |
V |
k |
|
|
|
torstai |
|
k sanoo |
V |
sanoo |
<== |
perjantai |
|
|
V |
k |
|
lauantai |
|
|
V |
k |
|
sunnuntai |
|
|
|
k sanoo |
|
Totuustaulun tavoitteena on siis kerätä kaikki mahdolliset vaihtoehdot ohjelmoijan silmien eteen, ja näin kaikki mahdollisuudet voidaan analysoida ja käsitellä.
Tehtävä 5.20 BAL=kyllä?
Eräällä saarella asuu luonnonkansa. Puolet kansan asukkaista aina valehtelevat ja toinen puoli puhuu aina totta. Lisäksi heidän kielensä on tuntematon. On saatu selville, että "BAL" ja "DA" tarkoittavat "kyllä" ja "ei", muttei sitä kumpiko tarkoittaa kumpaa. He ymmärtävät suomea mutta vastaavat aina omalla kielellään. Vastaasi tulee yksi saaren asukas.
a) Mitä saat selville kysymyksellä "Tarkoittaako BAL KYLLÄ"?
b) Millä kysymyksellä saat selville mikä sana on kyllä?
Tehtävä 5.21 Kuka valehtelee?
Jälleen maahan jossa asukkaat joko valehtelevat tai puhuvat aina totta. Tapaat kolme asukasta A:n, B:n ja C:n. He sanovat sinulla
A: Me kaikki kolme valehtelemme! B: Tasan yksi meistä puhuu totta!
Mitä ovat A, B ja C?
Entä jos asukkaat sanovat:
A: Me kaikki kolme valehtelemme! B: Tasan yksi meistä valehtelee!
Entä jos:
A: Minä valehtelen mutta B ei!
Entä jos:
A: B valehtelee! B: A ja C ovat samaa tyyppiä!
Vielä yksi:
A sanoo: B ja C ovat samaa tyyppiä. C:ltä kysytään: Ovatko A ja B samaa tyyppiä?
Mitä C vastaa?
Ehtoja usein yhdistellään loogisten operaatioiden avulla:
Mikäli kello 7–20 ja et halua ulkoilla
– mene bussilla
...
Mikäli sinulla on rahaa tai saat kimpan
– ota taksi
Yksittäinen ehto antaa tulokseksi tosi (T=true) tai epätosi (F=false). Ehtojen tulosta voidaan usein myös kuvata 1 tai 0. Ehtojen yhdistämistä loogisilla operaatioilla kuvaa seuraava totuustaulu (myös C++:n loogiset operaattorit merkitty):
|
|
|
|
|
|
|
ja |
|
|
tai |
|
ehd. tai |
|
ei |
|
|
|
||
|
|
|
|
|
|
|
AND |
|
|
OR |
|
|
XOR |
|
|
NOT |
|
|
|
|
p |
|
|
q |
|
p |
&& |
q |
p |
|| |
q |
p |
^ |
q |
|
! |
p |
^ toimii jos p ja q boolean |
|
F |
|
0 |
F |
|
0 |
F |
|
0 |
F |
|
0 |
F |
|
0 |
T |
|
1 |
|
|
F |
|
0 |
T |
|
1 |
F |
|
0 |
T |
|
1 |
T |
|
1 |
T |
|
1 |
|
|
T |
|
1 |
F |
|
0 |
F |
|
0 |
T |
|
1 |
T |
|
1 |
F |
|
0 |
|
|
T |
|
1 |
T |
|
1 |
T |
|
1 |
T |
|
1 |
F |
|
0 |
F |
|
0 |
|
Huomattakoon edellä, että AND operaatio toimii kuten kertolasku ja OR operaatio kuten yhteenlasku (mikäli määritellään 1+1=1). Siis loogisia operaattoreita voidaan käyttää kuten normaaleja algebrallisia operaattoreita ja niillä operoiminen vastaa tavallista algebraa. Loogisten operaatioiden algebraa nimitetään Boolen –algebraksi.
Ehtojen sieventämisessä käytettäviä kaavoja voidaan todistaa oikeaksi totuustaulujen avulla. Todistetaan esimerkiksi de Morganin kaava (vrt. joukko–oppi, 1=true, 0=false):
NOT (p AND q) = (NOT p) OR (NOT q)
Jaetaan ensin väittämä pienempiin osiin:
NOT e1 = e2 OR e3
|
|
e1 |
e2 |
e3 |
|
|
|
p |
q |
p AND q |
NOT p |
NOT q |
NOT e1 |
e2 OR e3 |
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
1 |
|
1 |
0 |
0 |
0 |
1 |
1 |
1 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
Koska kaksi viimeistä saraketta ovat samat ja kaikki muuttujien p ja q arvot on käsitelty, on laki todistettu!
Tehtävä 5.22 de Morganin kaava
Todista oikeaksi myös toinen de Morganin kaava:
NOT (p OR q) = (NOT p) AND (NOT q)
Tehtävä 5.23 Osittelulaki
Yhteenlaskun ja kertolaskun välillähän pätee osittelulaki:
p * (q + r) = (p * q) + (p * r)
Samaistamalla * <=> AND ja + <=> OR todetaan loogisille operaatioillekin osittelulaki:
p AND (q OR r) = (p AND q) OR (p AND r)
Todista oikeaksi toinen osittelulaki (toimiiko vast. yhteenlaskulla ja kertolaskulla):
p OR (q AND r) = (p OR q) AND (p OR r)
|
|
|
e1 |
e2 |
e3 |
|
|
|
p |
Q |
r |
q AND r |
p OR q |
p OR r |
p OR e1 |
e2 AND e3 |
|
0 |
0 |
0 |
|
|
|
|
|
|
0 |
0 |
1 |
|
|
|
|
|
|
0 |
1 |
0 |
|
|
|
|
|
|
0 |
1 |
1 |
|
|
|
|
|
|
1 |
0 |
0 |
|
|
|
|
|
|
1 |
0 |
1 |
|
|
|
|
|
|
1 |
1 |
0 |
|
|
|
|
|
|
1 |
1 |
1 |
|
|
|
|
|
|
Huomaa, että totuustauluun tulee nyt 8 riviä (koska kolme muuttujaa)!
Tehtävä 5.24 Ehtojen sieventäminen
Käytä de Morganin kaavoja tai osittelulakia seuraavien ehtojen sieventämiseen:
a) ei ole totta että hinta alle 5 mk ja paino yli 10 kg
b) NOT (kello<=7 OR rahaa>50 mk)
c) ((hinta < 5) tai (rahaa>10)) ja ((hinta < 5) tai (kello>9))
Mikäli edellä esitetyt asiat tuntuvat ymmärrettäviltä, niin ohjelmoinnissa ei tule olemaan mitään vaikeuksia. Jos vastaavat asiat tuntuvat vaikeilta ohjelmoinnin kohdalla, kannattaa palata takaisin tähän lukuun ja yrittää samaistaa asioita ohjelmointikieleen.
Taulukoiden samaistaminen ruutupaperiin, korttipakkaan tai muuhun tuttuun asiaan auttaa asian käsittelyä. Osoitinmuuttuja on yksinkertaisesti jokin (vaikkapa sormi) joka osoittaa johonkin (vaikkapa yhteen kirjaimeen).
Silmukat ja ehtolauseet ovat hyvin luonnollisia asioita.
Aliohjelmat ovat vain tietyn asian tarkempi kuvaus. Tarvittaessa tiettyä asiaa ei ongelmaa tarvitse heti ratkaista, vaan voidaan määritellä aliohjelma, joka hoitaa homman ja kirjoitetaan itse aliohjelman määrittely joskus myöhemmin.
Tehtävä 5.25 Merkkijonot
C–kielessä merkkijonot tullaan esittämään taulukoina kirjaimista. Merkkijonon loppu ilmaistaan kirjaimella NUL. Siis esimerkiksi Kissa olisi seuraavan näköinen
0 |
1 |
2 |
3 |
4 |
5 |
|
K |
i |
s |
s |
a |
NUL |
|
Kirjoita seuraavat algoritmit. Erityisesti kirjoita ensin algoritmin sanallinen versio
1. Välilyöntien poistaminen jonon alusta.
2. Välilyöntien poistaminen jonon lopusta.
3. Ylimääräisten (2 tai useampia) välilyöntien poistaminen jonosta.
4. Kaikkien ylimääräisten (alku-, loppu- ja monikertaiset) välilyöntien poistaminen.
5. Jonon muuttaminen siten, että kunkin sanan 1. kirjain on iso kirjain.
6. Tietyn merkin esiintymien laskeminen jonosta.
7. Esiintyykö merkkijono toisessa merkkijonossa (kissatarha, sata –> esiintyy; kissatarha, satu –> ei esiinny).
Tehtävä 5.26 Päivämäärät
Kirjoita seuraavat algoritmit:
1. Onko vuosi karkausvuosi vai ei. (Huom! 1900 ei, 2000 on)
2. Montako karkausvuotta on kahden vuosiluvun välillä.
3. Jos 1.1 vuonna 1 oli maanantai, niin mikä viikonpäivä on 1.1 vuonna x? (Oletetaan että kalenteri olisi ollut aina samanlainen kuin nytkin. Vihje! Tutki almanakkaa peräkkäisiltä vuosilta.)
4. Onko päivämäärä pp.kk.vvvv oikeata muotoa?