Tietorakenteet ja algoritmit syksy 2020

Fibonaccin luvut (osa 1)

Viikolla 2 laskimme Fibonaccin lukuja rekursiolla, mikä oli hidasta. Nyt on aika toteuttaa laskenta tehokkaasti dynaamisella ohjelmoinnilla.

Seuraava funktio laskee Fibonaccin lukuja dynaamisella ohjelmoinnilla:

function fibo(n)
    f[0] = 0
    f[1] = 1
    for i = 2 to n
        f[i] = f[i-1] + f[i-2]
    return f[n]

Esimerkiksi kun n = 10, funktio palauttaa arvon 55.

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

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.

Kirjoita tähän toteuttamasi algoritmin koodi:

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