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)

Eksempel: 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 forblir $12$
4. Svar: $12$

Denne algoritmen fungerer uansett hvilke tall vi setter inn!

Algoritme:
1. Les inn tallet $n$
2. Hvis $n < 2$: «Ikke primtall»
3. For hvert tall $i$ fra $2$ til $n - 1$:
- Hvis $n$ er delelig med $i$: «Ikke primtall», stopp
4. Hvis vi kom gjennom hele løkken uten å finne en deler: «Primtall»

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")

Eksempler:
- $n = 7$: Vi sjekker $7 \div 2, 7 \div 3, 7 \div 4, 7 \div 5, 7 \div 6$ – ingen gir rest $0$, så $7$ er et primtall $\checkmark$
- $n = 12$: Vi sjekker $12 \div 2 = 6$ (rest $0$!) – $12$ er ikke et primtall

Nøkkelord: break avslutter løkken umiddelbart. Når vi finner en deler, trenger vi ikke sjekke flere.

Algoritme:
1. Skriv opp alle tall fra $2$ til $50$
2. Start med det minste tallet ($2$). Det er et primtall.
3. Stryk alle multipler av $2$ (unntatt $2$ selv): $4, 6, 8, 10, \ldots$
4. Gå til neste tall som ikke er strøket ($3$). Det er et primtall.
5. Stryk alle multipler av $3$ (unntatt $3$ selv): $6, 9, 12, 15, \ldots$
6. Fortsett med $5, 7, \ldots$ til du har gått gjennom alle
7. Tallene som gjenstår er primtallene

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$ primtall mellom $2$ og $50$.

Algoritme:
1. Gå gjennom listen fra start til slutt
2. Sammenlign hvert element med neste element
3. Hvis de er i feil rekkefølge, bytt dem
4. Gjenta steg 1–3 til ingen bytter trengs

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]$ → bytt: $[25, 64, 12, 22, 11]$
- $[25, \mathbf{64}, \mathbf{12}, 22, 11]$ → bytt: $[25, 12, 64, 22, 11]$
- $[25, 12, \mathbf{64}, \mathbf{22}, 11]$ → bytt: $[25, 12, 22, 64, 11]$
- $[25, 12, 22, \mathbf{64}, \mathbf{11}]$ → bytt: $[25, 12, 22, 11, 64]$

Etter første gjennomgang er det største tallet ($64$) «boblet» til slutten. Vi trenger flere gjennomganger 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)

Eksempel:

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

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