Vurdere og feilsøke en algoritme

En algoritme kan være GAL (gir feil svar), eller RIKTIG MEN DÅRLIG (gir riktig svar unødvendig tregt). Begge deler skal vurderes. Feilsøking gjøres systematisk, ikke ved å stirre: lag en sportabell der du følger hver variabel gjennom hver runde, og finn den FØRSTE raden der en verdi ikke er som forventet. Feilen ligger da i steget rett før. Test alltid grensetilfellene – tomt datasett, $n = 0$ , negative tall – for det er der algoritmer nesten alltid ryker.

Sum av 1 til n

$S = \frac{n(n + 1)}{2}$

Kontroll

$\text{forventet} - \text{faktisk} = 0$

Tre klassiske feiltyper
Feil	Symptom	Fiks
Feil startverdi	svaret er konstant for høyt/lavt	sjekk verdien før løkken
Løkken går én for kort	siste element mangler	sjekk grensene
Løkken stopper aldri	programmet henger	sjekk at betingelsen endres

Tips

Sammenlign svaret med en formel du kan uavhengig, som $\frac{n(n+1)}{2}$ for summen. Er avviket akkurat det siste leddet, går løkken én for kort.
En while-løkke der betingelsen aldri endres, stopper aldri. Sjekk at variabelen i betingelsen faktisk oppdateres inne i løkken.

Eksempel: Finne feilen med en sportabell

En algoritme skal summere $1$ til $5$ , men gir $10$ i stedet for $15$ . Finn feilen.

Sportabell for den feilende løkken
i	s	Kjørt?
1	1	ja
2	3	ja
3	6	ja
4	10	ja
5	15	nei – her stopper den

Løsning:

Vi vet at riktig svar er $\frac{5 \cdot 6}{2} = 15$ , men algoritmen gir $10$
avviket er $15 - 10 = 5$ , altså nøyaktig det siste leddet
det peker på at løkken stopper for tidlig, ikke at addisjonen er feil
sporer vi verdiene, går løkken $i = 1$ til $i = 4$ og summerer til $10$
$i = 5$ kjøres aldri. Feilen er at løkken går én runde for kort.

Alternativ forklaring/metode: Skriv ut midt i algoritmen

Alternativ metode – innenfor pensum, men ikke hovedmetoden her

Halveringssøk i koden

Er algoritmen lang, ikke spor den fra start til slutt. Skriv i stedet ut verdiene midtveis: er de riktige der, ligger feilen i andre halvdel, ellers i første. Gjenta i den halvdelen som er feil. Ti steg krever da tre–fire sjekker i stedet for ti. Det er samme idé som når du leter i en ordbok ved å slå opp på midten, ikke ved å bla fra første side.

Halveringssøk på den samme feilende løkken
Sjekkpunkt	Forventet s	Faktisk s	Konklusjon
Midtveis (i = 3)	6	6	Stemmer – feilen er ikke i første halvdel
Ved slutten (i = 5)	15	10	Avvik – feilen er i siste del av løkken

Alternativ forklaring/metode: La et symbolsk verktøy regne ut fasiten

Alternativ metode – innenfor pensum, men ikke hovedmetoden her

SymPy (symbolsk matematikk i Python)

I stedet for å huske eller utlede kontrollformelen selv, kan et symbolsk verktøy som SymPy regne den ut nøyaktig: sympy.summation(i, (i, 1, 5)) gir det EKSAKTE svaret $15$ , uten avrunding og uten at du selv må huske formelen $\frac{n(n+1)}{2}$ . Sammenlign så dette fasitsvaret med hva det numeriske programmet (løkken) faktisk gir – akkurat som i hovedeksempelet avslører avviket på $5$ at løkken stopper for tidlig. Forskjellen fra vanlig kode er at SymPy regner SYMBOLSK: det finner den eksakte formelen bak tallene, ikke bare ett tallsvar.

Symbolsk fasit mot numerisk løkke
Metode	Kode	Resultat
Symbolsk (SymPy)	`sympy.summation(i, (i, 1, 5))`	15
Numerisk (løkken)	`s = 0; for i in range(1,5): s += i`	10 (feil)

Oppgaver

Prøv minst én oppgave på hvert nivå.

Lett(3)

L-31Hva er summen av $1$ til $5$ ?

Vis fasit

Beregning	Resultat
Summen fra 1 til 5 er 5 gange 6 delt på 2	15

Summen fra 1 til 5 er 5 gange 6 delt på 2 = 15

L-32En løkke stopper aldri. Hva kalles det?

Vis fasit

Beregning	Resultat
En løkke som aldri stopper kalles en evig løkke

En løkke som aldri stopper kalles en evig løkke

L-33Hva kaller vi en tabell som følger variablene gjennom hver runde?

Vis fasit

Beregning	Resultat
En tabell som følger 1 verdi per runde
verdiene spores gjennom løkken
en sportabell

En tabell som følger 1 verdi per runde
verdiene spores gjennom løkken
en sportabell

Middels(3)

M-31En algoritme gir

10

når den skulle gitt

15

. Hva er avviket?

Vis fasit

Beregning	Resultat
15 minus 10	5
det er nøyaktig siste ledd
løkken går én for kort

15 minus 10 = 5
det er nøyaktig siste ledd
løkken går én for kort

M-32Summen av

1

til

100

skal bli

5 050

. Algoritmen gir

4 950

. Hva mangler?

Vis fasit

Beregning	Resultat
5 050 minus 4 950	100
siste ledd, altså 100, mangler

5 050 minus 4 950 = 100
siste ledd, altså 100, mangler

M-33En sum-algoritme starter med s = 1 i stedet for s = 0. Hva skjer?

Vis fasit

Beregning	Resultat
Start på 1 i stedet for 0
svaret blir 1 for høyt hver gang

Start på 1 i stedet for 0
svaret blir 1 for høyt hver gang

Vanskelig(3)

V-31Er en algoritme som gir riktig svar, men tester alle tall opp til

n

, god nok?

Vis fasit

Beregning	Resultat
Riktig svar, men flere steg enn nødvendig
riktig, men treg

Riktig svar, men flere steg enn nødvendig
riktig, men treg

V-32Hvilke tilfeller bør du alltid teste?

Vis fasit

Beregning	Resultat
Feil oppstår oftest i ytterkantene
test 0, tomt datasett og negative tall

Feil oppstår oftest i ytterkantene
test 0, tomt datasett og negative tall

V-33En while-løkke sjekker i < 10, men i endres aldri. Hva skjer?

Vis fasit

Beregning	Resultat
i under 10 er alltid sant når i aldri endres
løkken går evig

i under 10 er alltid sant når i aldri endres
løkken går evig