11.1 Algoritmer og pseudokode

Hva er en algoritme, flytdiagram og pseudokode.

45 min

8 oppgaver

AlgoritmerPseudokodeFlytdiagramEuklids algoritme

Du leser den tradisjonelle versjonen

Din fremgang i kapitlet

0 / 8 oppgaver

Kapitlets plass i kurset

Brukes videre i

11.2Programmering med Python

Algoritmar og pseudokode

Har du nokon gong tenkt over at ein oppskrift på ei kake eigentleg er ein algoritme? Ein oppskrift er ei steg-for-steg-skildring av kva du skal gjera for å oppnå eit bestemt resultat. På same måten er ein algoritme ei presis oppskrift for å løysa eit problem.

I matematikk brukar vi algoritmar heile tida, til dømes når vi delar to tal med lang divisjon, eller når vi finn fellesnemnar. I dette kapitlet skal du læra:

- Kva ein algoritme er og kvifor det er nyttig
- Korleis du lagar flytdiagram
- Korleis du skriv pseudokode
- Klassiske algoritmar som Euklids algoritme

Algoritme

Ein algoritme er ei endeleg, presis skildring av ein framgangsmåte for å løysa eit problem eller utføra ei oppgåve. Ein god algoritme har desse eigenskapane: - Presis : Kvart steg er eintydig skildra - Endeleg : Algoritmen stoggar etter eit endeleg tal steg - Generell : Ho fungerer for all gyldige inndata, ikkje berre eitt spesifikt tilfelle Algoritmar kan skildra med vanleg tekst, med pseudokode eller med flytdiagram .

✏️Døme: Algoritme for å finna det største talet

Skildra ein algoritme som finn det største av tre tal $a$ , $b$ og $c$ .

Løysing:

Steg 1: Sett $\text{størst} = a$

Steg 2: Viss $b > \text{størst}$ , sett $\text{størst} = b$

Steg 3: Viss $c > \text{størst}$ , sett $\text{størst} = c$

Steg 4: $\text{størst}$ er no det største av dei tre tala

La oss testa med $a = 7$ , $b = 12$ , $c = 5$ :
- Steg 1: størst $= 7$
- Steg 2: $12 > 7$ , så størst $= 12$
- Steg 3: $5 > 12$ er usant, så størst er framleis $12$
- Svar: Det største talet er $12$ .

📝Oppgave 1

Skildra ein algoritme (med vanleg tekst) som avgjer om eit tal er positivt, negativt eller null.

Flytdiagram

Eit flytdiagram er ei grafisk framstilling av ein algoritme. Vi brukar standardiserte symbol: Symbol Tyding Oval (avrundt rektangel) Start / Stopp Rektangel Prosess / Berekning Diamant (rombe) Avgjerding (ja/nei) Parallellogram Inn-/utdata Pil Flyt / retning Flytdiagram gjer det lettare å sjå strukturen i ein algoritme og er særleg nyttige når det er forgreningar (if/else) eller løkker (gjentakingar).

Symbol	Tyding
Oval (avrundt rektangel)	Start / Stopp
Rektangel	Prosess / Berekning
Diamant (rombe)	Avgjerding (ja/nei)
Parallellogram	Inn-/utdata
Pil	Flyt / retning

✏️Døme: Flytdiagram for partal/oddetal

Skildra eit flytdiagram som avgjer om eit tal er partal eller oddetal.

Løysing:

Flytdiagrammet ser slik ut i tekstform:

1. [Start]
2. [Les inn tal n] (parallellogram)
3. [Er n deleleg med 2?] (diamant)
- Ja $\rightarrow$ [Skriv ut "Partal"] $\rightarrow$ [Stopp]
- Nei $\rightarrow$ [Skriv ut "Oddetal"] $\rightarrow$ [Stopp]

Vi sjekkar om $n$ er deleleg med 2 ved å sjå om resten ved divisjon er 0:

$n \mod 2 = 0 \implies \text{partal}$

Til dømes: $n = 14$ : $14 \mod 2 = 0$ , altso er 14 eit partal.

📝Oppgave 2

Tegn eit flytdiagram som sjekkar om eit tal er positivt, negativt eller null. Bruk diamantsymbol for avgjeringar og parallellogram for inn- og utdata.

Pseudokode

Pseudokode er ein forenkla, uformell måte å skildra ein algoritme på. Ho liknar på eit programmeringsspråk, men er skreven på vanleg språk så den er lett å forstå. Vanlege element i pseudokode: - LES / SKRIV : Inn- og utdata - SETT / LA : Tilordna verdiar - VISS ... SÅ ... ELLES : Vilkår (forgreningar) - GJENTA ... MEDAN / FOR ... TIL : Løkker (gjentakingar) - RETURNER : Gi tilbake eit resultat Pseudokode treng ikkje fylgja strenge syntaksreglar, men ho bør vera presis nok til at nokon kan omsetja ho til eit ekte programmeringsspråk.

✏️Døme: Pseudokode for summen av tal frå 1 til n

Skriv pseudokode som bereknar summen $1 + 2 + 3 + \ldots + n$ .

Løysing:

LES n
SETT sum = 0
FOR i = 1 TIL n
    SETT sum = sum + i
SLUTT FOR
SKRIV "Summen er " + sum

Test med $n = 5$ :

Steg	$i$	$\text{sum}$
Start	—	0
1	1	$0 + 1 = 1$
2	2	$1 + 2 = 3$
3	3	$3 + 3 = 6$
4	4	$6 + 4 = 10$
5	5	$10 + 5 = 15$

Summen av tala frå 1 til 5 er

15

.
Vi kan sjekka med formelen:

\displaystyle \frac{n(n+1)}{2} = \frac{5 \cdot 6}{2} = 15

\checkmark

📝Oppgave 3

Skriv pseudokode som bereknar produktet $1 \cdot 2 \cdot 3 \cdot \ldots \cdot n$ (altso $n!$ — n fakultet). Test pseudokoden din for $n = 4$ .

Skriv pseudokoden.

Test pseudokoden for $n = 4$ ved å laga ein tabell over verdiane i kvart steg.

Euklids algoritme

Ein av dei eldste kjende algoritmane er Euklids algoritme, oppkalla etter den greske matematikaren Euklid som skildra ho omkring 300 f.Kr. Denne algoritmen finn den største felles divisor (SFD) av to tal.

Den største felles divisor av to tal $a$ og $b$ er det største talet som går opp i båe. Vi skriv $\text{SFD}(a, b)$ .

Til dømes er $\text{SFD}(12, 8) = 4$ fordi 4 er det største talet som delar båe 12 og 8.

Euklids algoritme

\text{SFD}(a, b)

✏️Døme: Euklids algoritme for SFD(48, 18)

Bruk Euklids algoritme til å finna $\text{SFD}(48, 18)$ .

Løysing:

Steg	$a$	$b$	$r = a \mod b$
1	48	18	$48 \mod 18 = 12$
2	18	12	$18 \mod 12 = 6$
3	12	6	$12 \mod 6 = 0$
4	6	0	Stopp!

Når

b = 0

, er svaret

a = 6

.
Svar:

\text{SFD}(48, 18) = 6

.
Vi kan sjekka:

48 = 6 \cdot 8

18 = 6 \cdot 3

. Stemmer! \checkmark

📝Oppgave 4

Bruk Euklids algoritme til å finna den største felles divisor.

Finn $\text{SFD}(84, 36)$ .

Finn $\text{SFD}(105, 45)$ .

Finn $\text{SFD}(252, 198)$ .

Sorteringsalgoritmar

Sortering er ein av dei vanlegaste oppgåvene innan programmering. Når du søkjer etter noko på nettet, sorterer eit digitalt musikklibiotek, eller rangerer ein tabell, blir sorteringsalgoritmar brukte.

Ein enkel sorteringsalgoritme er boblsortering (bubble sort). Ideen er:
1. Gå gjennom lista og samanlikn kvart par av naboelementar
2. Viss to naboar er i feil rekkjefølgje, byt dei
3. Gjenta til heile lista er sortert

Namnet «boblsortering» kjem av at dei største verdiane gradvis «boblar» opp til rett posisjon, litt som luftbobler i vatn.

✏️Døme: Boblsortering

Sorter lista $[5, 3, 8, 1, 2]$ med boblsortering. Vis kvart steg.

Løysing:

Runde 1 (gå gjennom lista):
- Samanlikn 5 og 3: $5 > 3$ , byt $\rightarrow [3, 5, 8, 1, 2]$
- Samanlikn 5 og 8: $5 < 8$ , ok $\rightarrow [3, 5, 8, 1, 2]$
- Samanlikn 8 og 1: $8 > 1$ , byt $\rightarrow [3, 5, 1, 8, 2]$
- Samanlikn 8 og 2: $8 > 2$ , byt $\rightarrow [3, 5, 1, 2, 8]$

Runde 2:
- $3 < 5$ , ok $\rightarrow [3, 5, 1, 2, 8]$
- $5 > 1$ , byt $\rightarrow [3, 1, 5, 2, 8]$
- $5 > 2$ , byt $\rightarrow [3, 1, 2, 5, 8]$

Runde 3:
- $3 > 1$ , byt $\rightarrow [1, 3, 2, 5, 8]$
- $3 > 2$ , byt $\rightarrow [1, 2, 3, 5, 8]$

Runde 4:
- $1 < 2$ , ok. Ingen byttar $\rightarrow$ ferdig!

Svar: Sortert lista: $[1, 2, 3, 5, 8]$ .

📝Oppgave 5

Sorter lista $[7, 2, 9, 4, 1]$ med boblsortering. Skriv ned lista etter kvar runde.

📝Oppgave 6

Skriv pseudokode for ein algoritme som finn det minste talet i ei liste med $n$ tal.

Oppsummering

I dette kapitlet har du lært:

- Ein algoritme er ein presis, endeleg oppskrift for å løyse eit problem
- Flytdiagram bruker standardiserte symbol (ovalar, rektanglar, diamantar, parallellogram) for å visualisere algoritmar
- Pseudokode er ein uformell tekstbeskrivelse av ein algoritme som liknar eit programmeringsspråk
- Euklids algoritme finn største felles divisor ved gjentatt divisjon med rest
- Boblsortering sorterer ei liste ved å samanlikne og bytte naboar gjentatte gonger

Nøkkelbegrep

Begrep	Forklaring
Algoritme	Presis, endeleg fremgangsmåte for å løyse eit problem
Flytdiagram	Grafisk framstilling av ein algoritme med standardsymbol
Pseudokode	Uformell tekstbeskrivelse som liknar programmeringsspråk
SFD	Største felles divisor – det største talet som deler begge tal
Boblsortering	Sorteringsalgoritme som byttar naboar i feil rekkjefølgje

📝Oppgave 7

Skriv pseudokode for ein algoritme som sjekkar om eit tal $n$ er eit primtal. Test pseudokoden din for $n = 17$ og $n = 15$ .

Skriv pseudokoden.

Test for $n = 17$ .

Test for $n = 15$ .

📝Oppgave 8

Ei brøk $\displaystyle \frac{a}{b}$ kan forkortast ved å dele teljaren og nemnaren med $\text{SFD}(a, b)$ . Skriv ein algoritme (pseudokode eller flytdiagram) som les inn ei brøk og skriv ut den forkortede brøken. Test med $\displaystyle \frac{48}{36}$ .

📝Oppgave F1

Finn feilen! Nora har skrive pseudokode for boblsortering av ei liste med

n

tal:

FOR i = 1 TIL n
  FOR j = 1 TIL n
    VISS liste[j] > liste[j+1]
      BYTTLISTE[j] OG liste[j+1]

Ho testar med lista $[5, 3, 8, 1]$ , men programmet krasjar. Finn feilen og forklar kva som gjekk galet.

📝Oppgave S1

Sant eller usant?

Ein algoritme er det same som eit dataprogram.

📝Oppgave D1

Drøftingsoppgåve: Algoritmar styrer mykje av kvardagen vår — frå GPS-navigasjon og søkjemotorar til anbefaling på sosiale medium og strøymetjenester.

a) Gi tre døme på algoritmar du møter i kvardagen, og forklar kort kva dei gjer.

b) Diskuter fordelar og ulemper med at algoritmar tek avgjerder som påverkar menneske. Kan ein algoritme vere «urettferdig»? Gi døme.

Repetisjonsoppgåver

Din fremgang

0deloppgaver0 / 6 oppgaver

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.