Algoritmisk tenkning i problemløsing

Tre krav skiller en algoritme fra en løs beskrivelse: hvert steg må være ENTYDIG (ingen tolkning), rekkefølgen må være bestemt, og den må STOPPE etter endelig mange steg. «Kok opp vann» duger som oppskrift til middag, men ikke som algoritme – «varm vannet til det koker, maks $10$ minutter» gjør det. Framgangsmåten når du skal lage en: løs problemet én gang for hånd, skriv ned nøyaktig hva du gjorde, og bytt så de konkrete tallene med variabler.

abc-formelen

$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$

Diskriminanten

$D = b^2 - 4ac$

abc-formelen som algoritme
Steg	Handling
1	Les av a, b og c
2	Regn ut b² - 4ac
3	Er den negativ: stopp, ingen løsning
4	Regn ut de to x-verdiene
5	Skriv ut svaret

Tips

Test algoritmen på et tilfelle du kan svaret på FØR du bruker den på noe nytt. Finner du feilen der, sparer du deg for å mistolke et ukjent svar.
Skriv stegene i punktliste før du skriver kode. Nesten alle programmeringsfeil i 1T er egentlig tenkefeil som ble synlige først i koden.

Eksempel: Fra hånd-regning til algoritme

Beskriv en algoritme som avgjør om et helt tall $n$ er et primtall, og bruk den på $n = 91$ .

Algoritmen kjørt på n = 91
Divisor	Går opp?	Handling
2	nei	fortsett
3	nei	fortsett
5	nei	fortsett
7	ja	stopp: ikke primtall

Løsning:

Vi skal avgjøre om $n = 91$ er et primtall, og løser først for hånd: et primtall er kun delelig med $1$ og seg selv, så vi må teste divisorer
det holder å teste opp til $\sqrt{n}$ , for en større divisor må ha en mindre partner
for $n = 91$ er $\sqrt{91} \approx 9,5$ , så vi tester $2, 3, 5, 7$
$91$ er ikke delelig med $2, 3$ eller $5$ , men $91 = 7 \cdot 13$
algoritmen stopper med én gang den finner en divisor. Tallet $91$ er ikke et primtall.

Alternativ forklaring/metode: Løs én bit om gangen

Alternativ metode – innenfor pensum, men ikke hovedmetoden her

Del opp problemet (dekomponering)

Står du fast på et sammensatt problem, del det i mindre biter som hver kan løses for seg: «les inn tallene», «regn ut diskriminanten», «avgjør antall løsninger», «skriv ut svaret». Hver bit blir kort nok til å teste alene, og du finner feil i den ene biten uten å lete gjennom hele algoritmen. Det er nøyaktig samme idé som å regne en lang oppgave i delsvar i stedet for i ett jafs.

Abc-formelen delt i biter
Bit	Testes for seg
Les inn tallene	riktige a, b, c lagret?
Regn ut diskriminanten	riktig D for et kjent eksempel?
Avgjør antall løsninger	riktig gren for D<0, D=0, D>0?
Skriv ut svaret	riktig format og enhet?

Alternativ forklaring/metode: Simuler endring steg for steg

Alternativ metode – innenfor pensum, men ikke hovedmetoden her

Euler-steg for modellering

Skal du modellere noe som endrer seg over tid – en bestand, en temperatur, en saldo – kan du dele opp problemet i identiske, gjentatte steg: finn endringen akkurat NÅ, legg den til, og gjenta. Regelen er $y_{ny} = y_{gammel} + y' \cdot \Delta t$ . En bestand på $100$ dyr vokser med $10\ \%$ av bestanden per tidssteg ( $y' = 0{,}1y$ ), med $\Delta t = 1$ : steg 1 gir $y' = 0{,}1 \cdot 100 = 10$ , så $y_{ny} = 100 + 10 = 110$ → steg 2 gir $y' = 0{,}1 \cdot 110 = 11$ , så $y_{ny} = 121$ → steg 3 gir $y' = 0{,}1 \cdot 121 = 12{,}1$ , så $y_{ny} = 133{,}1$ . Samme dekomponerings-idé som abc-formelen delt i biter, bare at «biten» her gjentas mange ganger i en løkke.

Euler-steg: bestand på 100, vekst 10 % per steg
Steg	y' = 0,1 · y	y_ny = y + y'
0		100
1	10	110
2	11	121
3	12,1	133,1

Oppgaver

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

Lett(3)

L-11Må en algoritme stoppe etter endelig mange steg?

Vis fasit

Beregning	Resultat
En algoritme må terminere
ja, den må stoppe

En algoritme må terminere
ja, den må stoppe

L-12Er «regn litt til det ser riktig ut» en algoritme?

Vis fasit

Beregning	Resultat
«ser riktig ut» kan tolkes ulikt
nei, steget er ikke entydig

«ser riktig ut» kan tolkes ulikt
nei, steget er ikke entydig

L-13Hvor mange divisorer må du teste for å avgjøre om

49

er primtall?

Vis fasit

Beregning	Resultat
For 49 er kvadratroten 7
test til og med 7

For 49 er kvadratroten 7
test til og med 7

Middels(3)

M-11Er

91

et primtall?

Vis fasit

Beregning	Resultat
91 delt på 7 gir 13
nei, 91 er ikke et primtall

91 delt på 7 gir 13
nei, 91 er ikke et primtall

M-12Hvorfor holder det å teste divisorer opp til

\sqrt{n}

Vis fasit

Beregning	Resultat
Kvadratroten av n er grensen
en divisor over den har en partner under
det holder å teste opp til roten

Kvadratroten av n er grensen
en divisor over den har en partner under
det holder å teste opp til roten

M-13Hva er diskriminanten til

x^2 + 2x - 3 = 0

Vis fasit

Beregning	Resultat
a = 1, b = 2, c	-3
D = 4 - 4 gange 1 gange (-3) = 4 + 12	16

a = 1, b = 2, c = -3
D = 4 - 4 gange 1 gange (-3) = 4 + 12 = 16

Vanskelig(3)

V-11Hva bør algoritmen gjøre hvis diskriminanten er negativ?

Vis fasit

Beregning	Resultat
En negativ diskriminant gir ingen reell rot
stopp og meld ingen løsning

En negativ diskriminant gir ingen reell rot
stopp og meld ingen løsning

V-12Hva kalles det å dele et problem i mindre biter?

Vis fasit

Beregning	Resultat
Å dele 1 problem i flere små deler
hver del løses for seg
dekomponering

Å dele 1 problem i flere små deler
hver del løses for seg
dekomponering

V-13En algoritme tester ALLE tall opp til

n

for å sjekke primtall. Er den riktig, og er den god?

Vis fasit

Beregning	Resultat
Alle tall opp til n gir riktig svar, men testing til roten holder
riktig, men treg

Alle tall opp til n gir riktig svar, men testing til roten holder
riktig, men treg