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

Algoritmer og pseudokode

Har du noen gang tenkt over at en oppskrift på en kake egentlig er en algoritme? En oppskrift er en steg-for-steg-beskrivelse av hva du skal gjøre for å oppnå et bestemt resultat. På samme måte er en algoritme en presis oppskrift for å løse et problem.

I matematikk bruker vi algoritmer hele tiden, for eksempel når vi deler to tall med lang divisjon, eller når vi finner fellesnevner. I dette kapittelet skal du lære:

- Hva en algoritme er og hvorfor det er nyttig
- Hvordan du lager flytdiagrammer
- Hvordan du skriver pseudokode
- Klassiske algoritmer som Euklids algoritme

Algoritme

En algoritme er en endelig, presis beskrivelse av en fremgangsmåte for å løse et problem eller utføre en oppgave. En god algoritme har disse egenskapene: - Presis : Hvert steg er entydig beskrevet - Endelig : Algoritmen stopper etter et endelig antall steg - Generell : Den fungerer for alle gyldige inndata, ikke bare ett spesifikt tilfelle Algoritmer kan beskrives med vanlig tekst, med pseudokode eller med flytdiagrammer .

✏️Eksempel: Algoritme for å finne det største tallet

Beskriv en algoritme som finner det største av tre tall $a$ , $b$ og $c$ .

Løsning:

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

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

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

Steg 4: $\text{størst}$ er nå det største av de tre tallene

La oss teste 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 fortsatt $12$
- Svar: Det største tallet er $12$ .

📝Oppgave 1

Beskriv en algoritme (med vanlig tekst) som avgjør om et tall er positivt, negativt eller null.

Flytdiagram

Et flytdiagram er en grafisk fremstilling av en algoritme. Vi bruker standardiserte symboler: Symbol Betydning Oval (avrundet rektangel) Start / Stopp Rektangel Prosess / Beregning Diamant (rombe) Beslutning (ja/nei) Parallellogram Inn-/utdata Pil Flyt / retning Flytdiagrammer gjør det lettere å se strukturen i en algoritme og er spesielt nyttige når det er forgreninger (if/else) eller løkker (gjentakelser).

Symbol	Betydning
Oval (avrundet rektangel)	Start / Stopp
Rektangel	Prosess / Beregning
Diamant (rombe)	Beslutning (ja/nei)
Parallellogram	Inn-/utdata
Pil	Flyt / retning

✏️Eksempel: Flytdiagram for partall/oddetall

Beskriv et flytdiagram som avgjør om et tall er partall eller oddetall.

Løsning:

Flytdiagrammet ser slik ut i tekstform:

1. [Start]
2. [Les inn tall n] (parallellogram)
3. [Er n delelig med 2?] (diamant)
- Ja $\rightarrow$ [Skriv ut "Partall"] $\rightarrow$ [Stopp]
- Nei $\rightarrow$ [Skriv ut "Oddetall"] $\rightarrow$ [Stopp]

Vi sjekker om $n$ er delelig med 2 ved å se om resten ved divisjon er 0:

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

For eksempel: $n = 14$ : $14 \mod 2 = 0$ , altså er 14 et partall.

📝Oppgave 2

Tegn et flytdiagram som sjekker om et tall er positivt, negativt eller null. Bruk diamantsymboler for beslutninger og parallellogrammer for inn- og utdata.

Pseudokode

Pseudokode er en forenklet, uformell måte å beskrive en algoritme på. Den ligner på et programmeringsspråk, men er skrevet på vanlig språk slik at den er lett å forstå. Vanlige elementer i pseudokode: - LES / SKRIV : Inn- og utdata - SETT / LA : Tilordne verdier - HVIS ... SÅ ... ELLERS : Betingelser (forgreninger) - GJENTA ... MENS / FOR ... TIL : Løkker (gjentakelser) - RETURNER : Gi tilbake et resultat Pseudokode trenger ikke følge strenge syntaksregler, men den bør være presis nok til at noen kan oversette den til et ekte programmeringsspråk.

✏️Eksempel: Pseudokode for summen av tall fra 1 til n

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

Løsning:

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 tallene fra 1 til 5 er

15

.
Vi kan sjekke med formelen:

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

\checkmark

📝Oppgave 3

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

Skriv pseudokoden.

Test pseudokoden for $n = 4$ ved å lage en tabell over verdiene i hvert steg.

Euklids algoritme

En av de eldste kjente algoritmene er Euklids algoritme, oppkalt etter den greske matematikeren Euklid som beskrev den rundt 300 f.Kr. Denne algoritmen finner den største felles divisor (SFD) av to tall.

Den største felles divisor av to tall $a$ og $b$ er det største tallet som går opp i begge. Vi skriver $\text{SFD}(a, b)$ .

For eksempel er $\text{SFD}(12, 8) = 4$ fordi 4 er det største tallet som deler både 12 og 8.

Euklids algoritme

\text{SFD}(a, b)

✏️Eksempel: Euklids algoritme for SFD(48, 18)

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

Løsning:

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 sjekke:

48 = 6 \cdot 8

18 = 6 \cdot 3

. Stemmer! \checkmark

📝Oppgave 4

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

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

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

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

Sorteringsalgoritmer

Sortering er en av de vanligste oppgavene i programmering. Når du søker etter noe på nettet, sorterer et digitalt musikkbibliotek, eller rangerer en tabell, brukes sorteringsalgoritmer.

En enkel sorteringsalgoritme er boblsortering (bubble sort). Ideen er:
1. Gå gjennom listen og sammenlign hvert par av naboelementer
2. Hvis to naboer er i feil rekkefølge, bytt dem
3. Gjenta til hele listen er sortert

Navnet "boblsortering" kommer av at de største verdiene gradvis "bobler" opp til riktig posisjon, litt som luftbobler i vann.

✏️Eksempel: Boblsortering

Sorter listen $[5, 3, 8, 1, 2]$ med boblsortering. Vis hvert steg.

Løsning:

Runde 1 (gå gjennom listen):
- Sammenlign 5 og 3: $5 > 3$ , bytt $\rightarrow [3, 5, 8, 1, 2]$
- Sammenlign 5 og 8: $5 < 8$ , ok $\rightarrow [3, 5, 8, 1, 2]$
- Sammenlign 8 og 1: $8 > 1$ , bytt $\rightarrow [3, 5, 1, 8, 2]$
- Sammenlign 8 og 2: $8 > 2$ , bytt $\rightarrow [3, 5, 1, 2, 8]$

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

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

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

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

📝Oppgave 5

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

📝Oppgave 6

Skriv pseudokode for en algoritme som finner det minste tallet i en liste med $n$ tall.

Oppsummering

I dette kapittelet har du lært:

- En algoritme er en presis, endelig oppskrift for å løse et problem
- Flytdiagrammer bruker standardiserte symboler (ovaler, rektangler, diamanter, parallellogrammer) for å visualisere algoritmer
- Pseudokode er en uformell tekstbeskrivelse av en algoritme som ligner et programmeringsspråk
- Euklids algoritme finner største felles divisor ved gjentatt divisjon med rest
- Boblsortering sorterer en liste ved å sammenligne og bytte naboer gjentatte ganger

Nøkkelbegreper

Begrep	Forklaring
Algoritme	Presis, endelig fremgangsmåte for å løse et problem
Flytdiagram	Grafisk fremstilling av en algoritme med standardsymboler
Pseudokode	Uformell tekstbeskrivelse som ligner programmeringsspråk
SFD	Største felles divisor – det største tallet som deler begge tall
Boblsortering	Sorteringsalgoritme som bytter naboer i feil rekkefølge

📝Oppgave 7

Skriv pseudokode for en algoritme som sjekker om et tall $n$ er et primtall. Test pseudokoden din for $n = 17$ og $n = 15$ .

Skriv pseudokoden.

Test for $n = 17$ .

Test for $n = 15$ .

📝Oppgave 8

En brøk $\displaystyle \frac{a}{b}$ kan forkortes ved å dele teller og nevner med $\text{SFD}(a, b)$ . Skriv en algoritme (pseudokode eller flytdiagram) som leser inn en brøk og skriver ut den forkortede brøken. Test med $\displaystyle \frac{48}{36}$ .

📝Oppgave F1

Finn feilen! Nora har skrevet pseudokode for boblesortering av en liste med

n

tall:

FOR i = 1 TIL n
  FOR j = 1 TIL n
    HVIS liste[j] > liste[j+1]
      BYTT liste[j] OG liste[j+1]

Hun tester med listen $[5, 3, 8, 1]$ , men programmet krasjer. Finn feilen og forklar hva som gikk galt.

📝Oppgave S1

Sant eller usant?

En algoritme er det samme som et dataprogram.

📝Oppgave D1

Drøftingsoppgave: Algoritmer styrer mye av hverdagen vår — fra GPS-navigasjon og søkemotorer til anbefalinger på sosiale medier og strømmetjenester.

a) Gi tre eksempler på algoritmer du møter i hverdagen, og forklar kort hva de gjør.

b) Diskuter fordeler og ulemper med at algoritmer tar beslutninger som påvirker mennesker. Kan en algoritme være «urettferdig»? Gi eksempler.

Repetisjonsoppgaver

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.