Kirjautuminen
Tehtävät
Kilpailu
5. kierros:
28.11. klo 18 – 30.11. klo 23
Kirjoittaja: Antti Laaksonen
Kirjoitettu: 26.10.2006 – 26.10.2006
Tagit: algoritmit, koodi näytille, vinkki
Tässä tulee muutama esimerkki dynaamisen ohjelmoinnin käytöstä.
Dynaamisen ohjelmoinnin perusajatus on, että ongelma jaetaan pienempiin osiin, joiden ratkaisut voidaan laskea erikseen. Lisäksi pienempien ongelmien ratkaisut pannaan muistiin taulukkoon, jolloin samaa asiaa ei tarvitse laskea kahteen kertaan. Dynaaminen ohjelmointi on nerokas menetelmä, mutta sen ymmärtäminen vie oman aikansa.
* * *
Ensimmäinen tehtävä on Fibonaccin lukujen laskeminen. Luvut on määritelty rekursiivisena funktiona:
fibo(1) = 1
fibo(2) = 1
fibo(n) = fibo(n - 2) + fibo(n - 1), n > 2
Funktiolle on siis annettu kaksi alinta arvoa, ja korkeammat arvot lasketaan alempien perusteella.
Ensimmäiset Fibonaccin luvut ovat:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Selkeä ratkaisu on kirjoittaa samanlainen funktio ohjelmaan. Ongelma on vain siinä, että ohjelmasta tulee hidas suuremmilla n:n arvoilla, kun samoja funktion arvoja lasketaan uudestaan ja uudestaan. Tämän vuoksi lasketut arvot pannaan muistiin, jolloin ohjelma on hyvin nopea. Tämä on dynaamista ohjelmointia.
* * *
Toisessa tehtävässä täytyy jakaa rahamäärä kolikoiksi niin, että kolikkojen määrä on mahdollisimman pieni. Kolikkojen arvot annetaan ohjelman alussa. Esim. jos rahamäärä on 13 ja kolikot ovat 3 ja 5, tarvitaan kolme kolikkoa (5 + 5 + 3 = 13). Oikean kolikkoyhdistelmän etsiminen yksinkertaisella haulla on hidasta.
Kolikkojen määrän laskuun voidaan muodostaa rekursiivinen funktio. Jos summa on 0, kolikkoja ei tarvita yhtään. Jos summa on alle 0, tilanne on mahdoton. Muuten tarvittava kolikkomäärä on yhtä suurempi kuin pienin alempi summa, joka on yhden kolikon arvon päässä.
Tässä näkyvät pienimmät kolikkomäärät rahamäärillä 0 - 15 esimerkin kolikoilla:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 - - 1 - 1 2 - 2 3 2 3 4 3 4 3
Esim. summasta 13 päästään alempiin summiin 10 (13 - 3) ja 8 (13 - 5). Koska molempiin summiin vaaditaan 2 kolikkoa, summaan 13 vaaditaan 3 (2 + 1) kolikkoa. Summia 1, 2, 4 ja 7 ei voida muodostaa lainkaan näitä kolikoita käyttämällä.
Koska alemman summan kolikkomäärä voidaan laskea erikseen, myös tähän tehtävään sopii dynaaminen ohjelmointi. Jos halutaan lisäksi tietää, mistä kolikoista summa muodostuu, voidaan jokaisen summan kolikkomäärän lisäksi tallentaa tieto siitä, mistä alemmasta summasta tähän summaan päästiin. Saman rahamäärän jakoon voi olla useita ratkaisuja, joista näin löytyy yksi.
* * *
Ohjelmat:
1. Fibonaccin lukujen laskeminen
2. Kolikkomäärän laskeminen
3. Kolikkomäärän laskeminen ja kolikoiden näyttö
Ohjelmissa 2. ja 3. kolikkomäärä 999999 tai suurempi tarkoittaa, että summaa ei ole mahdollista muodostaa.
FIBONACCIN LUVUT
' varataan muistia funktion arvoille
DIM SHARED MUISTI(100)
PRINT FIBO1(30)
PRINT FIBO2(30)
' tavallinen rekursio
FUNCTION FIBO1 (N)
IF N = 1 OR N = 2 THEN
FIBO1 = 1
ELSE
FIBO1 = FIBO1(N - 2) + FIBO1(N - 1)
END IF
END FUNCTION
' dynaaminen ohjelmointi
FUNCTION FIBO2 (N)
' jos funktion arvo on jo laskettu,
' se voidaan palauttaa suoraan
IF MUISTI(N) <> 0 THEN
FIBO2 = MUISTI(N)
EXIT FUNCTION
END IF
IF N = 1 OR N = 2 THEN
TULOS = 1
ELSE
TULOS = FIBO2(N - 2) + FIBO2(N - 1)
END IF
' pannaan funktion arvo muistiin
MUISTI(N) = TULOS
FIBO2 = TULOS
END FUNCTIONKOLIKKOJEN VALINTA 1
' varataan muistia rekursiopinolle
STACK 5000
' käytössä olevat kolikot
DIM SHARED KOLIKOT(4)
' kolikkojen määrä
DIM SHARED MAARA
' summien pienimmät kolikkomäärät
DIM SHARED MUISTI(200)
' määritetään kolikot
KOLIKOT(1) = 3
KOLIKOT(2) = 7
KOLIKOT(3) = 13
KOLIKOT(4) = 17
MAARA = 4
' lasketaan pienin kolikkomäärä
PRINT LASKE(121)
FUNCTION LASKE (SUMMA)
' summa on 0, eli kolikoita ei tarvita
IF SUMMA = 0 THEN
LASKE = 0
EXIT FUNCTION
END IF
' summa on alle 0, mikä on mahdotonta
IF SUMMA < 0 THEN
LASKE = 999999
EXIT FUNCTION
END IF
' summa on jo laskettuna muistissa
IF MUISTI(SUMMA) <> 0 THEN
LASKE = MUISTI(SUMMA)
EXIT FUNCTION
END IF
' lasketaan pienin kolikkomäärä valitsemalla
' alemmista käytössä olevilla kolikoilla
' saavutettavista summista pienin
PIENIN = LASKE(SUMMA - KOLIKOT(1)) + 1
FOR I = 2 TO MAARA
UUSI = LASKE(SUMMA - KOLIKOT(I)) + 1
IF UUSI < PIENIN THEN
PIENIN = UUSI
END IF
NEXT
' pannaan summa muistiin
MUISTI(SUMMA) = PIENIN
LASKE = PIENIN
END FUNCTIONKOLIKKOJEN VALINTA 2
' varataan muistia rekursiopinolle
STACK 5000
' käytössä olevat kolikot
DIM SHARED KOLIKOT(4)
' kolikkojen määrä
DIM SHARED MAARA
' summien pienimmät kolikkomäärät
DIM SHARED MUISTI(200)
' mikä kolikko valittiin viimeksi
DIM SHARED VIIME(200)
' määritetään kolikot
KOLIKOT(1) = 3
KOLIKOT(2) = 7
KOLIKOT(3) = 13
KOLIKOT(4) = 17
MAARA = 4
' lasketaan pienin kolikkomäärä
TULOS = LASKE(121)
PRINT TULOS
' näytetään summan muodostavat kolikot
SUMMA = 121
WHILE VIIME(SUMMA) <> 0
PRINT VIIME(SUMMA);
SUMMA = SUMMA - VIIME(SUMMA)
WEND
FUNCTION LASKE (SUMMA)
' summa on 0, eli kolikoita ei tarvita
IF SUMMA = 0 THEN
LASKE = 0
EXIT FUNCTION
END IF
' summa on alle 0, mikä on mahdotonta
IF SUMMA < 0 THEN
LASKE = 999999
EXIT FUNCTION
END IF
' summa on jo laskettuna muistissa
IF MUISTI(SUMMA) <> 0 THEN
LASKE = MUISTI(SUMMA)
EXIT FUNCTION
END IF
' lasketaan pienin kolikkomäärä valitsemalla
' alemmista käytössä olevilla kolikoilla
' saavutettavista summista pienin
PIENIN = LASKE(SUMMA - KOLIKOT(1)) + 1
VALI = KOLIKOT(1)
FOR I = 2 TO MAARA
UUSI = LASKE(SUMMA - KOLIKOT(I)) + 1
IF UUSI < PIENIN THEN
PIENIN = UUSI
VALI = KOLIKOT(I)
END IF
NEXT
' pannaan summa muistiin
MUISTI(SUMMA) = PIENIN
' pannaan edellinen kolikko muistiin
VIIME(SUMMA) = VALI
LASKE = PIENIN
END FUNCTION10 pistettä ja papukaija merkki tästä. Vielä kun 100% ymmärtäisi kokonaan mutta eiköhän se toisella lukukerralla aukene.
miinuspisteitä basic-kielestä.
lainaus:
miinuspisteitä basic-kielestä.
Tee täysin samanlainen C-kielellä, tai C++, niin annan miinuspisteitä. Tee moinen Javalla, sama homma. Tee se Delphillä tai vastaavilla, ja taasen miinuksia. Tee asmilla, aivan sama juttu. Vaan toteuta tuo BrainFuckilla, tai vastaavalla kielellä ja saat puolikkaan plussa-pisteen..
-Grey-
Erittäin asiallista asiaa. Olen juuri tubessa MIT kurssia seuraamassa samasta aiheesta, siksi tännekin törmäsin. Heti aamulla testaan noita exoja. Mieleeni juolahti sellainen asia että kuinka käyttäytyy O-notaatiot dynaamisen koodin kanssa suhteessa periteiseen? Onko kellä kokemuksia? Pitänee sekin huomenna reistata.
kostika kirjoitti:
Kuinka käyttäytyy O-notaatiot dynaamisen koodin kanssa suhteessa periteiseen?
Kysymys on hieman outo. O-notaatio käyttäytyy ihan normaalisti, eli sillä ilmoitetaan algoritmin aika- tai tilavaativuus. Rekursioon verrattuna dynaaminen ohjelmointi yleensä pienentää aikavaativuutta ja mahdollisesti suurentaa tilavaativuutta.
Vaikka dynaamisen ohjelmoinnin käyttö on luontevaa rekursion yhteydessä, ei pidä erehtyä luulemaan, että se olisi vain optimointikikka rekursiivisiin algoritmeihin. Dynaamisen ohjelmoinnin taulukkoa voi usein myös täyttää järjestyksessä silmukalla ilman rekursiota, jolloin myös algoritmin aikavaativuus on helpompi hahmottaa.
Dynaamisen ratkaisun kohdalla pitää siis osata arvioida, montako askelta laskentaan oikeasti kuluu. Dynaamisesti toteutettujen Fibonaccin lukujen aikavaativuus (pienillä luvuilla) on O(n), koska jokainen luku lasketaan kerran, ja tilavaativuus O(n), koska jokainen luku tallennetaan.