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: .. math:: 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 :math:`m` være tallet før :math:`n`, og la :math:`l` være tallet før :math:`m`. Så for eksempel, i begynnelsen er :math:`l=1` og :math:`m=2`. I neste omgang er :math:`l=2` og :math:`m=3` etc. Vi bruker så disse for å beregne :math:`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: :download:`eksempel_fibonacci.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: .. math:: \begin{align*} &n \rightarrow n/2 &(\text{n is even}) \\ &n \rightarrow 3n + 1 &(\text{n is odd}) \end{align*} Using the rule above and starting with 13, we generate the following sequence: .. math:: 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 :math:`n < 1000000` skal vi beregne sekvensen som begynner på :math:`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 :math:`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 :math:`x=400` sauer og :math:`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 :math:`\Delta t`: .. math:: \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 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: :download:`wolf_sheep.py`. .. .. literalinclude:: 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: .. math:: \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} 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: .. math:: \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} Write a program that prompts users to pick either a seat or a price. Mark sold seats by changing the price to :math:`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] 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).