Hovedsiden

Innholdsfortegnelse

Kodeeksempler

Løsning på utvalgte oppgaver

Trykkfeilliste

(Nettsiden er under utvikling, mer kommer etter hvert)

Se FunksjonsMax.c eller FunksjonsMax.java

10.2-2

Se Ryggsekk.c eller Ryggsekk.java. Algoritmen har kompleksitet O(2ⁿ). Fordelen er at den ikke er avhengig av at vektene er heltall.

10.2-4

Se MatriseMult.c eller MatriseMult.java.
Løsningen baserer seg på følgende:
La T_ij være antall multiplikasjoner vi trenger for å multiplisere matrisene M_i, M_i+1,..., M_j.
Vi starter med at T_ii=0 for alle i, og finner deretter T_i,i+1, T_i,i+2 osv. Den endelige løsningen er T_0,n-1 når vi har n matriser.
For å finne T_ij beregner vi antall multiplikasjoner som må til hvis vi først multipliserer M_i,...M_k, deretter M_k+1,...M_j, og til slutt multipliserer sammen de to resultatmatrisene. Så velger vi den k mellom i og j som gir det minste antall multiplikasjoner. Vi får dermed:
T_ij=min(T_ik + T_k+1,j + d_i*d_k+1*d_j+1)
der d_i er antall rader i matrise M_i og d_j+1 er antall kolonner i M_j.
Vi trenger å lagre alle T_ij'ene for j>i. Dette gjøres i øvre høyre del av en todimensjonal tabell. Vi trenger også å lagre de tilsvarende k-verdiene, dette lagrer vi i den nedre venstre delen av den samme tabellen.

10.3-3

Se Huffmantest.c eller Huffmantest.java

10-1

Se RyggsekkKont.c eller RyggsekkKont.java

10-2

Se Tur.c eller Tur.java