9.3 Algoritmer i matematikk

Python-kode:

a = int(input("Skriv inn a: "))
b = int(input("Skriv inn b: "))
c = int(input("Skriv inn c: "))

storst = a
if b > storst:
    storst = b
if c > storst:
    storst = c

print("Det største tallet er:", storst)

Døme: Med $a = 5$, $b = 12$ og $c = 8$:
1. storst = 5
2. Er $12 > 5$? Ja, så storst = 12
3. Er $8 > 12$? Nei, storst held fram som $12$
4. Svar: $12$

Denne algoritmen fungerer uansett kva tal vi set inn!

Algoritme:
1. Les inn talet $n$
2. Dersom $n < 2$: «Ikkje primtal»
3. For kvart tal $i$ frå $2$ til $n - 1$:
- Dersom $n$ er deleleg med $i$: «Ikkje primtal», stopp
4. Dersom vi kom gjennom heile løkka utan å finne ein delar: «Primtal»

Python-kode:

n = int(input("Skriv et tall: "))

if n < 2:
    print(n, "er ikke et primtall")
else:
    er_primtall = True
    for i in range(2, n):
        if n % i == 0:
            er_primtall = False
            break  # Trenger ikke sjekke flere

    if er_primtall:
        print(n, "er et primtall")
    else:
        print(n, "er ikke et primtall")

Døme:
- $n = 7$: Vi sjekkar $7 \div 2, 7 \div 3, 7 \div 4, 7 \div 5, 7 \div 6$ – ingen gir rest $0$, så $7$ er eit primtal $\checkmark$
- $n = 12$: Vi sjekkar $12 \div 2 = 6$ (rest $0$!) – $12$ er ikkje eit primtal

Nøkkelord: break avsluttar løkka med ein gong. Når vi finn ein delar, treng vi ikkje sjekke fleire.

Algoritme:
1. Skriv opp alle tal frå $2$ til $50$
2. Start med det minste talet ($2$). Det er eit primtal.
3. Stryk alle multiplum av $2$ (bortsett frå $2$ sjølv): $4, 6, 8, 10, \ldots$
4. Gå til neste tal som ikkje er strøke ($3$). Det er eit primtal.
5. Stryk alle multiplum av $3$ (bortsett frå $3$ sjølv): $6, 9, 12, 15, \ldots$
6. Hald fram med $5, 7, \ldots$ til du har gått gjennom alle
7. Tala som står att er primtala

Python-kode:

grense = 50
er_primtall = [True] * (grense + 1)
er_primtall[0] = False
er_primtall[1] = False

for i in range(2, grense + 1):
    if er_primtall[i]:
        # Stryk alle multipler av i
        for j in range(i * 2, grense + 1, i):
            er_primtall[j] = False

# Skriv ut alle primtall
print("Primtall opp til", grense, ":")
for i in range(2, grense + 1):
    if er_primtall[i]:
        print(i, end=" ")

Utskrift:

Primtall opp til 50:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Det er $15$ primtal mellom $2$ og $50$.

Algoritme:
1. Gå gjennom lista frå start til slutt
2. Samanlikn kvart element med neste element
3. Dersom dei er i feil rekkjefølgje, byt dei
4. Gjenta steg 1–3 til ingen byter trengst

Python-kode:

tall = [64, 25, 12, 22, 11]
print("Før sortering:", tall)

n = len(tall)
for i in range(n - 1):
    for j in range(n - 1 - i):
        if tall[j] > tall[j + 1]:
            # Bytt de to tallene
            tall[j], tall[j + 1] = tall[j + 1], tall[j]

print("Etter sortering:", tall)

Utskrift:

Før sortering: [64, 25, 12, 22, 11]
Etter sortering: [11, 12, 22, 25, 64]

Steg for steg (første gjennomgang):
- $[\mathbf{64}, \mathbf{25}, 12, 22, 11]$ → byt: $[25, 64, 12, 22, 11]$
- $[25, \mathbf{64}, \mathbf{12}, 22, 11]$ → byt: $[25, 12, 64, 22, 11]$
- $[25, 12, \mathbf{64}, \mathbf{22}, 11]$ → byt: $[25, 12, 22, 64, 11]$
- $[25, 12, 22, \mathbf{64}, \mathbf{11}]$ → byt: $[25, 12, 22, 11, 64]$

Etter første gjennomgang er det største talet ($64$) «bobla» til slutten. Vi treng fleire gjennomgangar for å sortere resten.

Steg for steg:
1. $\text{SFD}(48, 18)$: $48 \bmod 18 = 12$ → $\text{SFD}(18, 12)$
2. $\text{SFD}(18, 12)$: $18 \bmod 12 = 6$ → $\text{SFD}(12, 6)$
3. $\text{SFD}(12, 6)$: $12 \bmod 6 = 0$ → Ferdig! SFD $= 6$

Python-kode:

a = int(input("Skriv inn a: "))
b = int(input("Skriv inn b: "))

# Lagre originalverdiene for utskrift
a_orig, b_orig = a, b

while b != 0:
    rest = a % b
    a = b
    b = rest

print("SFD av", a_orig, "og", b_orig, "er:", a)

Døme:

Skriv inn a: 48
Skriv inn b: 18
SFD av 48 og 18 er: 6

Sjekk: Divisorane til $48$ er $1, 2, 3, 4, 6, 8, 12, 16, 24, 48$. Divisorane til $18$ er $1, 2, 3, 6, 9, 18$. Den største dei har felles er $6$ $\checkmark$