2.7 Algoritmer og problemløsning

Algoritmer og problemløsning

En algoritme er en trinnvis oppskrift for å løse et problem. Før du koder, bør du planlegge 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

Flytskjemaer

Symboler: Oval (start/slutt), Rektangel (prosess), Diamant (beslutning), 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 sjekkes alle n elementer.

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

- En algoritme er en steg-for-steg-oppskrift for å løse et problem.
- Algoritmisk tenkning innebærer å bryte ned problemer, finne mønstre og lage generelle løsninger.
- Pseudokode beskriver en algoritme med vanlig tekst, uten å binde seg til et spesifikt programmeringsspråk.
- Flytskjemaer visualiserer en algoritme med standardiserte symboler for start/slutt, prosess, beslutning og inn-/utdata.
- Lineært søk sjekker hvert element i rekkefølge, binært søk halverer søkeområdet (krever sortert liste).
- Boblesortering er en enkel sorteringsalgoritme som sammenligner og bytter nabopar.
- Effektivitet måles i tidskompleksitet, og for store datasett er det viktig å velge gode algoritmer.