2.7 Algoritmer og problemløsning

Algoritmar og problemløysing

Ein algoritme er ei trinnvis oppskrift for å løyse eit problem. Før du kodar, bør du planleggje med pseudokode eller flytskjema.

Pseudokode

ALGORITME: Finn største tall
1. Sett største = første element
2. For hvert tall i resten av listen:
   a. Hvis tall > største: sett største = tall
3. Returner største

def finn_storste(liste):
    storste = liste[0]
    for tall in liste[1:]:
        if tall > storste:
            storste = tall
    return storste

Flytskjema

Symbol: Oval (start/slutt), Rektangel (prosess), Diamant (avgjerd), Parallellogram (inn-/utdata), Piler (flyt).

Lineært søk

def lineaert_sok(liste, maal):
    for i in range(len(liste)):
        if liste[i] == maal:
            return i
    return -1

print(lineaert_sok([4, 7, 2, 9], 9))  # 3

I verste fall blir alle n element sjekka.

Boblesortering

def boblesortering(liste):
    n = len(liste)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if liste[j] > liste[j + 1]:
                liste[j], liste[j + 1] = liste[j + 1], liste[j]
    return liste

print(boblesortering([64, 34, 25, 12]))  # [12, 25, 34, 64]

Boblesortering er enkel men ineffektiv. I praksis bruker vi sorted().

Oppsummering

- Ein algoritme er ei steg-for-steg-oppskrift for å løyse eit problem.
- Algoritmisk tenking inneber å bryte ned problem, finne mønster og lage generelle løysingar.
- Pseudokode skildrar ein algoritme med vanleg tekst, utan å binde seg til eit spesifikt programmeringsspråk.
- Flytskjema visualiserer ein algoritme med standardiserte symbol for start/slutt, prosess, avgjerd og inn-/utdata.
- Lineært søk sjekkar kvart element i rekkjefølgje, binært søk halverer søkjeområdet (krev sortert liste).
- Boblesortering er ein enkel sorteringsalgoritme som samanliknar og byter nabopar.
- Effektivitet blir målt i tidskompleksitet, og for store datasett er det viktig å velje gode algoritmar.