Uke 8 — Problemløsning

Eksempler

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

Eksempel 1

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

Du jobber med et prosjekt hvor du må sortere en gruppe mennesker i to grupper: eksperter og ikke-eksperter, basert på en egenrapportert nivå av kompetanse i et biologitema fra 0 (ikke kunnskapsrik) til 5 (ekstremt kunnskapsrik). De som har sagt nivå 4 eller 5 burde bli plassert i gruppen «eksperter» mens resten av mennesker burde bli plassert i gruppen «ikke eksperter.»

Beskriv for hverande 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.

Eksempel 2

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_fibonacci.py.

Diskuter andre løsingsforslag. Kan vi løse oppgaven uten lister? Hva er fordeler / ulemper med 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"]

Løs oppgaven i fila uke08_oppgave_1.py.

Oppgave 2

I denne oppgaven skal vi løse problem nr. 14 i Project Euler.

I uke08_oppgave_2.py lag en funksjon som heter collatz_sequence. Funksjonen skal ta et positivt heltall som argument og returnere Collatz-sekvensen som en liste.

Eksempelkjøring:

>>> collatz_sequence(13)
[13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
>>> collatz_sequence(1)
[1]

Lag en ny funksjon som heter euler_14 for å løse problemet. Du kan bruke collatz_sequence. Fordi 1 million er et veldig stort tall og kan ta lang tid skal vi løse det for et litt mindre tall: ti tusen. Funksjonen skal ikke ta noen argumenter, og skal returnere det tallet under 10’000 som gir den lengste Collatz-sekvensen.

Oppgave 3

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?

1(1,2)

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

BONUS Oppgave

Denne oppgaven er ikke obligatorisk, men du kan få 2 bonuspoeng for riktig løsning.

Denne oppgaven er større enn en eksamensoppgave, men stilen er lik.

Skriv en funksjon justify som fyller ut en tekst med mellomrom slik at alle rader får samme lengd. Lengden på radene skal være et argument til funksjonen. Den justerede teksten skal returneres av funksjonen som en streng. Funksjonen skal ikke bruke print() eller input(). Her er hele spesifikasjonen:

Input: justify skal ta to argument, en str (text) og en int (line_len).

Output: funksjonen skal returnere samme tekst som i text men hvor alle rader har lengden line_len.

Vilkår:

  • Alle rader må inneholde så mange ord som er mulig innen radlengden.

  • Funksjonen får bare fylle ut med mellomrom (’ ’) mellom ordene (ikke tab eller noen annen whitespace).

  • Mellomrommen i hver rad må være så jevnt fordelt som mulig, i.e. forskjellen mellom størst antall mellomrom og minst antall mellomrom mellom orden i en rad får ikke være mer enn 1. Men du får selv velge hvordan du vil plassere ut mellomrommen så lenge dette er oppfyllt.

  • Alle rader må begynne med et tegn som ikke er whitespace.

  • Slutten på alle rader må enten være på formen 'char\n' eller 'char', hvor 'char' er et tegn som ikke er whitespace, i.e. du får ikke begynne eller slutte en rad med mellomrom.

  • Den siste raden i teksten skal ikke bli fylt ut med mellomrom. I denne raden skal det være eksakt ett mellomrom mellom alle ord.

  • Du kan anta at inget ord i text er lengre enn line_len.

Eksempel: om input til funksjonen er følgende tekst:

Alice was beginning to get very tired of sitting by her sister
on the bank, and of having nothing to do: once or twice she had peeped
into the book her sister was reading, but it had no pictures
or conversations in it, 'and what is the use
of a book,' thought Alice 'without pictures or conversation?'

og line_len er 60 skal funksjonen returnere noe slikt:

Alice was beginning to get very  tired  of  sitting  by  her
sister on the bank, and of having nothing  to  do:  once  or
twice she had peeped into the book her sister  was  reading,
but it had no pictures or conversations in it, 'and what  is
the use of a  book,'  thought  Alice  'without  pictures  or
conversation?'

(men du får selv velge hvordan du vil plassere mellomrommen, innen vilkårene).