Les og utforsk

Denne uken skal vi ha fokus på problemløsning. Vi vil se eksempler på hvordan programmering kan brukes til å løse problemer, og ha hovedfokus på å identifisere programmeringsstrukturer som if-setninger, for-løkker, og så videre.

Eksperter og ikke-eksperter

Først skal vi jobbe sammen i grupper for å løse oppgaven i denne lille teksten:

Beskriv hvordan du vil løse oppgaven med programmering. Hva er forventet input? Hva skal du skrive ut? Hvor vil du bruke for-løkker, if-setninger eller funksjoner?

Det er nok å skissere en løsning, du trenger ikke å programmere noe.

Problem 2 fra projecteuler.net

Vi skal løse Problem 2 fra projecteuler.net:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: \[1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …\] By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Prøv å skissere en løsning før du leser videre!

Dette problemet kan deles opp i to deler: først må vi finne alle tall i Fibonaccisekvensen som er mindre enn fire millioner, så summerer vi alle av disse som er partall.

For å beregne Fibonaccisekvensen må vi gjøre samme ting (å addere de to forrige tallene) mange ganger. Dette er hva en loop er til for.

Vi vet ikke hvor mange ganger vi må beregne nye tall, vi vet bare at vi skal slutte når vi får et tall som er større enn fire millioner. Derfor bruker vi en while-løkke. Vi må også lagre alle tallene på noen måte. Til dette bruker vi en liste. Så vår kode skal være noe slikt:

fib = [] # Fibonaccisekvensen

fib.append(1) # Vi må ha de første to tallen i sekvensen før løkken
fib.append(2)

while n < 4000000: # n er det seneste tallet i sekvensen
    # Beregne neste tall i sekvensen
    # Putte tallet i slutten av fib

For å beregne neste tall i sekvensen skal vi addere de to forrige tallene. Derfor må vi hele tiden lagre de to forrige tallene sånn at vi kan bruke dem i neste omgang av løkken. La (m) være tallet før (n), og la (l) være tallet før (m). Så for eksempel, i begynnelsen er ( = 1) og (m = 2). I neste omgang er (l = 2) og (m = 3) etc. Vi bruker så disse for å beregne (n). Vår kode blir da noe slikt:

fib = [] # Fibonaccisekvensen

l = 1
m = 2

fib.append(l) # Vi må ha de første to tallen i sekvensen før løkken
fib.append(m)

n = 0  # n må være definert før løkken

while n < 4000000: # n er det seneste tallet i sekvensen
    n = l + m
    fib.append(n)

    l = m # l og m må oppdateres
    m = n

Nå har vi alle tall i Fibonaccisekvensen som er mindre enn fire millioner. Nå må vi beregne summen av alle av disse som er partall.

Her passer det også å bruke en løkke fordi vi vil gå gjennom hele listen fib og gjøre noe: sjekke om tallet er partall, og (hvis det er et partall) addere det til summen.

Når vi vil gjøre noe for alle elementer i en liste bruker vi en for-løkke. Koden blir:

fib = [] # Fibonaccisekvensen

l = 1
m = 2

fib.append(l) # Vi må ha de første to tallen i sekvensen før løkken
fib.append(m)

n = 0  # n må være definert før løkken

while n < 4000000: # n er det seneste tallet i sekvensen
    n = l + m
    fib.append(n)

    l = m # l og m må oppdateres
    m = n
sum = 0 # Summen må være definert før løkken
for n in fib:
    if n % 2 == 0:
        sum += n

print(sum) # Sånn at vi får vite hva summen er

Diskuter andre løsingsforslag. Kan vi løse oppgaven uten lister? Hva er fordeler / ulemper med ulike løsninger?

Populasjonsmodell

På en liten øy finnes \(x = 400\) sauer og \(y = 20\) ulver. Uten ulver vokser antallet av sauer eksponensielt over tid. Uten sauene forsvinner alle ulvene etter en stund. Når begge finnes på øyen, går antallet ulver litt opp i hvert tidsskritt, og antallet sauer går ned avhengig av hvor mange ulver og sauer det finnes.

I vårt eksempel skal tallene forendres slikt etter et tidsskritt \(\Delta t\). \(\Delta x\) er endring i x, og \(\Delta y\) er endring i y: $$ \Delta x = \Big (\frac{2}{3} x - \frac{1}{15}xy\Big)\Delta t $$ $$ \Delta y = \Big (\frac{1}{400} xy - y\Big)\Delta t $$

På hvert tidspunkt vil vi vise hvor mange ulver og sauer vi har. Vi kan bruke print for å lage et enkel søylediagram ved å skrive ut ulike antall ‘x’ og ’ . ’ i hvert tidsskritt.

# https://en.wikipedia.org/wiki/Lotka%E2%80%93Volterra_equations

# parameters
A = 2/3
B = 1/15
C = 1/1
D = 1/400

def timestep(x, y, dt):
    """Run one timestep of the wolf-sheep system"""
    x += (A*x - B*x*y) * dt
    y += (D*x*y - C*y) * dt
    return x, y

# starting values
sheep = 400
wolf = 20
# time step size
dt = 0.2

# use _ when we don't need the loop variable later
for _ in range(500):
    # print a . for every 10 sheep
    print(f'{sheep:6.0f}', '.' * int(sheep/10))
    # print an x for every wolf
    print(f'{wolf:6.0f}', 'x' * int(wolf))
    # update the numbers
    sheep, wolf = timestep(sheep, wolf, dt)

(De som er interessert kan finne ut mer om denne typen ligningssystemer under stikkordet Lotka-Volterra equations).