9.1 Hva er en algoritme? | Matematikk 1P

Lær hva algoritmer er, hvordan de brukes i hverdagen og i matematikk, og hvordan vi kan beskrive dem med flytskjema og pseudokode.

45 min

8 oppgaver

AlgoritmeFlytskjemaPseudokodeSteg-for-steg

Du leser den tradisjonelle versjonen

Din fremgang i kapitlet

0 / 8 oppgaver

Kapitlets plass i kurset

Brukes videre i

9.2Programmering med Python

Algoritmar er overalt

Kvar gong du fylgjer ein oppskrift for å lage pannekaker, bruker du ein algoritme. Når du forklarar nokon vegen til skulen, beskriver du ein algoritme. Når du sorterer ein kortstokk frå lavast til høgast, fylgjer du ein algoritme.

Ein algoritme er berre og bart ein presis, steg-for-steg-beskrivelse av korleis ein løyser eit problem eller utfører ein oppgåve. Det som gjer algoritmar spesielle, er at dei er så tydlege at alle (eller ein datamaskin) kan fylgje dei og komme fram til riktig resultat.

I dette kapitlet skal vi sjå på kva som karakteriserer ein god algoritme, og lære ulike måtar å beskrive algoritmar på.

Algoritme

Ein algoritme er ein endeleg, ordna sekvens av entydige instruksjonar som løyser eit bestemt problem eller utfører ein bestemt oppgåve. Ein algoritme har desse eigenskapane: - Endeleg : Ho stoppar etter eit bestemt tal på steg. - Entydig : Kvart steg er klart definert, utan rom for tolking. - Input : Ho kan ta inn data (men treng ikkje). - Output : Ho gir eit resultat.

Algoritmar i kvardagen

Her er nokre døme på algoritmar vi bruker dagleg, utan å tenkje over det:

Oppskrift for kokt egg:
1. Fyll ein kjele med vatn.
2. Set kjelen på plata og kok opp vatnet.
3. Legg egget forsiktig i det kokande vatnet.
4. Vent i 4 minutt (bløtkokt) eller 8 minutt (hardkokt).
5. Ta egget opp med ein skje og kjøl det under kaldt vatn.

Veibeskrivelse:
1. Gå ut døra og ta til venstre.
2. Gå rett fram i 200 meter.
3. Ta til høyre ved lyskrysset.
4. Bygningen er den tredje på venstre side.

Legg merke til at begge døma har noko til felles: dei har ein klar rekkjefølgje, kvart steg er tydleg, og dei fører til eit bestemt resultat.

✏️Døme 1: Divisjonsalgoritmen

Beskriv ein algoritme for å utføre heiltalsdivisjon av 47 med 6 (finn kor mange gongar 6 går opp i 47, og kva resten blir).

Algoritme for heiltalsdivisjon:

1. Start med dividenden (47) og divisoren (6).
2. Set tellaren til 0.
3. So lenge dividenden er større enn eller lik divisoren:
- Trekk divisoren frå dividenden: $47 - 6 = 41$
- Auk tellaren med 1.
4. Gjenta steg 3:
- $41 - 6 = 35$ , teller = 2
- $35 - 6 = 29$ , teller = 3
- $29 - 6 = 23$ , teller = 4
- $23 - 6 = 17$ , teller = 5
- $17 - 6 = 11$ , teller = 6
- $11 - 6 = 5$ , teller = 7
5. No er dividenden (5) mindre enn divisoren (6), so vi stoppar.

Svar: $47 \div 6 = 7$ med rest $5$ (fordi $7 \cdot 6 + 5 = 47$ ).

✏️Døme 2: Euklids algoritme for største felles faktor

Finn største felles faktor (GCD) av 48 og 18 ved hjelp av Euklids algoritme.

Euklids algoritme:
Gjenta følgjande: Del det største talet på det minste. Erstatt det største talet med resten. Stopp når resten er 0.

1. Del 48 på 18: $48 = 2 \cdot 18 + 12$ (rest 12)
2. Del 18 på 12: $18 = 1 \cdot 12 + 6$ (rest 6)
3. Del 12 på 6: $12 = 2 \cdot 6 + 0$ (rest 0)

Resten er 0, so vi stoppar. Det siste talet vi delte med er 6.

Svar: Største felles faktor av 48 og 18 er $\text{GCD}(48, 18) = 6$ .

Vi kan sjekke: $48 = 6 \cdot 8$ og $18 = 6 \cdot 3$ , og 8 og 3 har ingen felles faktorar.

Flytskjema

Eit flytskjema er ein visuell framstilling av ein algoritme. Vi bruker ulike symbol:

- Oval (avrunda rektangel): Start og stopp
- Rektangel: Ein handling eller berekning
- Rombe (diamant): Eit val / ein betingelse (ja/nei)
- Piler: Viser rekkjefølgja

Flytskjema gjer det lett å sjå strukturen i ein algoritme, særleg når det er val og gjentakingar involvert.

Døme: Flytskjema for å sjekke om eit tal er partall

[Start] → [Les inn talet n] → <Er n delelig med 2?>
                                    |              |
                                   Ja             Nei
                                    |              |
                              [Skriv "Partall"] [Skriv "Oddetall"]
                                    |              |
                                    → → [Stopp] ← ←

Pseudokode

Pseudokode er ein måte å skrive algoritmar på med vanlaugs tekst, utan å bruke eit bestemt programmeringsspråk. Det er ein mellomting mellom naturleg språk og programkode.

Her er pseudokode for å sjekke om eit tal er partall:

LES inn talet n
HVIS n er delelig med 2
    SKRIV "Talet er partall"
ELLERS
    SKRIV "Talet er oddetall"

Og her er pseudokode for å finne det største talet i ei liste:

LES inn ei liste med tal
SETT størst = første tal i lista
FOR kvart tal i lista:
    HVIS tal > størst
        SETT størst = tal
SKRIV størst

Pseudokode bruker innrykk for å vise kva instruksjonar som høyrer saman, akkurat som i ekte programmering.

Iterasjon og betingelser

Iterasjon (gjentaking/løkke) betyder å gjenta ei gruppe instruksjonar fleire gongar. Vi bruker ord som FOR og SO LENGE (WHILE). Betingelse (val) betyder å utføre ulike instruksjonar avhengig av om noko er sant eller usant. Vi bruker ord som HVIS ... ELLERS (IF ... ELSE). Desse to byggjesteinane, saman med sekvens (instruksjonar etter kvarandre), er alt vi treng for å beskrive kvar algoritme.

✏️Døme 3: Pseudokode for å summere tala 1 til 100

Skriv pseudokode for å berekne summen $1 + 2 + 3 + \ldots + 100$ .

Pseudokode:

SETT sum = 0
FOR n = 1 TIL 100:
    SETT sum = sum + n
SKRIV "Summen er: ", sum

Gjennomgang:
- Vi startar med sum = 0.
- Løkka køyrer for n = 1, 2, 3, ..., 100.
- For kvar verdi av n legg vi n til sum.
- Etter løkka har vi: sum $= 1 + 2 + 3 + \ldots + 100 = 5050$ .

Vi kan sjekke med formelen: $\displaystyle \frac{100 \cdot 101}{2} = 5050$ ✓

📝Oppgave 9.1

Kva av desse er døme på algoritmar?

📝Oppgave 9.2

Skriv ein algoritme (i pseudokode) for å avgjere om eit tal er positivt, negativt eller null.

📝Oppgave 9.3

Bruk Euklids algoritme til å finne største felles faktor (GCD) av 84 og 36. Vis alle stega.

Når du har skrive ein algoritme i pseudokode, er det korte vegen til å gjere ho om til eit dataprogram. Pseudokode liknar på ekte programkode, men bruker vanlaugs norsk i stad for engelske nøkkelord.

I neste kapittel skal vi lære å skrive algoritmar i programmeringsspråket Python, som er eitt av dei enklaste språka å kome i gang med.

📝Oppgave 9.4

Skriv pseudokode for ein algoritme som finn det minste talet i ei liste med fem tal. Bruk ei løkke.

Oppsummering

I dette kapitlet har du lært:

- Algoritme: Ein endeleg, ordna sekvens av entydige instruksjonar som løyser eit problem.
- Pseudokode: Ein uformell måte å skrive algoritmar på, uavhengig av programmeringsspråk.
- Flytskjema: Grafisk framstilling av ein algoritme med boksar og piler.
- Byggjesteinan: Sekvens (steg etter steg), val (viss/ellers) og iterasjon (løkker).

Nøkkelbegrep

Begrep	Forklaring
Algoritme	Steg-for-steg-oppskrift som løyser eit problem
Pseudokode	Algoritme skrive i klartekst
Iterasjon	Gjentaking (løkke)
Betingelse	Test som avgjør kva veg algoritmen tek

Døme: Euklids algoritme

- Gjenta: erstatt det største talet med resten av divisjonen, til resten er

0

. Siste divisor er største felles faktor.

Repetisjonsoppgåver

Din fremgang

0deloppgaver0 / 4 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.