Tietorakenteet ja algoritmit syksy 2020

Fibonaccin luvut (osa 2)

Itse asiassa todellinen syy Fibonaccin lukujen laskennan hitauteen viikolla 2 ei ollut rekursio vaan se, että rekursiota kutsutaan liian paljon.

Seuraavassa on tehokas rekursiivinen funktio, joka hyödyntää dynaamista ohjelmointia: 

function fibo(n)
    if n <= 1
        return n
    else if f[n] != 0
        return f[n]
    else
        f[n] = fibo(n-1) + fibo(n-2)
        return f[n]
Tässä rakenne f on määritelty globaalisti niin, että se on yhteinen kaikille funktion kutsuille. Jos vastaus on laskettu aiemmin, funktio palauttaa sen suoraan ilman rekursiota.

Esimerkiksi kun n = 10, funktio palauttaa arvon 55.

Toteuta algoritmi pseudokoodin perusteella Javalla tai Pythonilla ja vastaa sitten seuraaviin kysymyksiin:

Algoritmin testaus

Kun n = 20, funktio palauttaa arvon ja aikaa kuluu sekuntia.

Kun n = 30, funktio palauttaa arvon ja aikaa kuluu sekuntia.

Kun n = 40, funktio palauttaa arvon ja aikaa kuluu sekuntia.

Algoritmin toteutus

Kirjoita tähän toteuttamasi algoritmin koodi:

The deadline for this task has passed but you can still check your answers

Return to task list