Uke 8 — Problemløsning¶

Eksempler¶

Vi skal se på noen eksempler på hvordan man kan løse problemer ved hjelp av programmering.

Eksempel 1¶

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.

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 \(l=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

Du kan finne hele koden her: eksempel_1.py.

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

Eksempel 2¶

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

The following iterative sequence is defined for the set of positive integers:

\[\begin{split}\begin{align*} &n \rightarrow n/2 &(\text{n is even}) \\ &n \rightarrow 3n + 1 &(\text{n is odd}) \end{align*}\end{split}\]

Using the rule above and starting with 13, we generate the following sequence:

\[13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1\]

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

Note: Once the chain starts the terms are allowed to go above one million.

Vi skal beregne nesten en million sekvenser: for hvert tall \(n < 1000000\) skal vi beregne sekvensen som begynner på \(n\). Så skal vi beregne lengden på alle disse sekvensene og se hvilken startverdi som produserer den lengste listen.

Dette kan vi dele opp i ulike deler. Én del er koden som beregner sekvensen fra en startverdi.

Når vi beregner en sekvens vil vi gjøre samme ting mange ganger. Derfor skal vi bruke en løkke. Siden vi ikke vet hvor mange ganger løkken skal kjøres, men vi vet når den skal avsluttes (når vi kommer til \(1\)), bruker vi en while-løkke. Vi lagrer sekvensen i en liste, slik som i eksempel 1. Koden blir:

def colz_seq(n):
    seq = []
    seq.append(n) # n er startverdien

    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
        seq.append(n)
    return seq

Vi vil nå beregne lengden av sekvensen for alle startverdier under én million. Dette gjør vi med en for-løkke over range() og lagrer alle lengdene i en liste (vi må ikke lagre alle sekvensene, bare lengdene):

lengths = []

for n in range(1, 1000000):
    lengths.append(
        len(colz_seq(n))
    )  # colz_seq(n) er en funksjon som beregner sekvensen fra startverdien n

Vi vil nå vite hvilken startverdi som gir lengst lengde. Derfor må vi beregne maksimum av lengths og finne startverdien som gav den lengden. Startverdien er én mer enn index av lengden i listen lengths. Vi kan bruke .index() for å finne index for maksimum i listen lengths. Koden blir:

m = max(lengths)
start_value = (
    lengths.index(m) + 1
)  # Om flere startverdier gir samme lengde får vi her bare det første av disse tallene

Du får nå selv sette dette sammen til en kodefil som gir deg svaret på spørsmålet. Hva er svaret?

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

Eksempel 3¶

Her skal vi lage en enkel simulasjon av en 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\):

\[\begin{split}\Delta x = \left( \frac{2}{3}x - \frac{1}{15}xy \right) \Delta t\\ \\ \Delta y = \left( \frac{1}{400}xy - y \right) \Delta t\end{split}\]

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.

Prøv å skissere en løsning, og diskuter med andre i din gruppe.

Så kan du se på vårt løsningsforslag her: wolf_sheep.py.

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

Oppgaver¶

Oppgave 1¶

Dette er oppgave 3.46 fra boken Python for Everyone 1:

A minivan has two sliding doors. Each door can be opened by either a dashboard switch, its inside handle, or its outside handle. However, the inside handles do not work if a child lock switch is activated. In order for the sliding doors to open, the gear shift must be in park, and the master unlock switch must be activated.

Your task is to simulate a portion of the control software for the vehicle. The input is a sequence of values for the switches and the gear shift, in the following order:

Dashboard switches for left and right sliding door, child lock, and master unlock (0 for off or 1 for activated).

Inside and outside handles on the left and right sliding doors (0 or 1).

The gear shift setting (one of P N D 1 2 3 R).

A typical input would be 0 0 0 1 0 1 0 0 P.

Print ’left door opens’ and/or ’right door opens’ as appropriate. If neither door opens, print ’both doors stay closed’.

Vi skal modifiere denne oppgaven litt.

Du skal lage en funksjon door_open() som tar som argument en streng med alle de forskjellige innstillingene i samme orden som det står i boken, men uten mellomrom mellom tallene.

Input er altså på denne formen:

\[\begin{split}\begin{matrix} \text{Left} & \text{Right} & \text{Child} & \text{Master} & \text{Left} & \text{Left} & \text{Right} & \text{Right} & \text{Gear} \\ \text{dashboard} & \text{dashboard} & \text{lock} & \text{unlock} & \text{inside} & \text{outside} & \text{inside} & \text{outside} & \text{shift} \\ \text{switch} & \text{switch} & & & \text{handle} & \text{handle} & \text{handle} & \text{handle} & \\ \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow \\ "0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & P" \end{matrix}\end{split}\]

så strengen "00010100P" betyr at ’master unlock’ og håndtaket på utsiden av den venstre døren er aktivert, og at ’gear shift’ er på ’park’. I dette tilfellet skal den venstre døren åpnes.

Funksjonen skal returnere en liste med alle dører som skal åpnes:

[] om ingen dør skal åpnes,
["left"] om den venstre døren skal åpnes,
["right"] om den høyre døren skal åpnes,
["left", "right"] om begge dørene skal åpnes.

Så om funksjonen får strengen "00010100P" som argument skal den returnere listen ["left"]

Oppgave 2¶

Dette er oppgave 6.27 fra boken Python for Everyone 1:

A theater seating chart is implemented as a table of ticket prices, like this:

\[\begin{split}\begin{matrix} 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 \\ 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 \\ 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 \\ 10 & 10 & 20 & 20 & 20 & 20 & 20 & 20 & 10 & 10 \\ 10 & 10 & 20 & 20 & 20 & 20 & 20 & 20 & 10 & 10 \\ 10 & 10 & 20 & 20 & 20 & 20 & 20 & 20 & 10 & 10 \\ 20 & 20 & 30 & 30 & 40 & 40 & 30 & 30 & 20 & 20 \\ 20 & 30 & 30 & 40 & 50 & 50 & 40 & 30 & 30 & 20 \\ 30 & 40 & 50 & 50 & 50 & 50 & 50 & 50 & 40 & 30 \end{matrix}\end{split}\]

Write a program that prompts users to pick either a seat or a price. Mark sold seats by changing the price to \(0\). When a user specifies a seat, make sure it is available. When a user specifies a price, find any seat with that price.

Denne oppgaven skal du løse helt fra begynnelsen, og den blir ikke rettet automatisk. Du kan velge selv hvordan du deler opp oppgaven i funksjoner, og hvordan du skal få input og hvordan du vil gi output. Hva synes du er best?

Last opp resultatet som vanlig på git. Neste uken får du mulighet å invitere andre til prosjektet og dere kan kommentere og diskutere de ulike løsningene.

1(1,2): Horstmann, Cay S., and Rance D. Necaise. Python for Everyone. Hoboken, NJ: John Wiley & Sons, Inc, 2019.

Uke 8 — Problemløsning¶

Eksempler¶

Eksempel 1¶

Eksempel 2¶

Eksempel 3¶

Oppgaver¶

Oppgave 1¶

Oppgave 2¶

Table of Contents

Forrige tittel

Neste emne

Denne siden