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.
Skriv ut midt i algoritmen. 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.

Eksempel: Finne feilen med en sportabell

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

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.

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

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`, deretter `for i in range(1,5): s += i`	10 (feil)

Oppgaver

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

Lett(3)

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

Vis fasit

Summen fra

1

til

5

\frac{5 \cdot 6}{2} =

15

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

Vis fasit

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

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

Vis fasit

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

Middels(3)

M-41En algoritme gir $10$ når den skulle gitt $15$ . Hva er avviket?

Vis fasit

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

M-42Summen av $1$ til $100$ skal bli $5 050$ . Algoritmen gir $4 950$ . Hva mangler?

Vis fasit

$5\,050 - 4\,950 = 100$
siste ledd, altså 100, mangler

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

Vis fasit

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

Vanskelig(3)

V-41Er en algoritme som gir riktig svar, men tester alle tall opp til $n$ , god nok?

Vis fasit

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

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

Vis fasit

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

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

Vis fasit

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