Exempel på rekursion

Tre exempel på rekursiva funktioner

def fakultet(n):
    if n == 0 : return 1
    else : 
        return n*fakultet(n-1)
 
def artitmetisk_summa(n, d):
    if n == 0 : return 0
    else : return n*d+artitmetisk_summa(n-1, d)
    
   
def binar_sokning(a, l, min, max):
    if l[max] == a : i=max
    else :
        mitt = (min+max) // 2
        if a > l[mitt] : i=binar_sokning(a,l, mitt, max)
        else : i=binar_sokning(a,l, min, mitt)
    return i

print("Fakultet " + str(fakultet(5)))
print("Summa " + str(artitmetisk_summa(4, 2)))
lista=[1, 3, 5, 8, 9, 10, 12, 16]
print("Sökning " + str(binar_sokning(16, lista, 0, 7)))

En rekursiv funktion kallar på sig själv tills ett begränsande villkor är uppfyllt. Fakultetsberäkningen ovan kan beskrivas med denna bild:

 

Först byggs stacken av funktionsanrop upp tills fakultet(0) returnerar 1. När detta sker vänder det och stacken krymper då varje steg returnerar sina värden. Slutligen returnerar fakultet(5) sitt värde till print som skriver ut det.

Uppgift 3.3
Skriv och testa en rekursiv funktion för att beräkna en geometrisk summa. (Du kan använda ** för upphöjt i Python.)

Rörelse och interaktion

Automatisk rörelse

Tkinter har metoden after( tid, funktion) som anropar en funktion efter tiden tid som anges i millisekunder. Denna kan användas för att skapa rörelse i ett grafisk program.

Övning 3.9
Skriv in och testa programmet nedan:

from tkinter import *


class Dot_Canvas(Canvas):
    
    def __init__(self, root):
        super().__init__(root, width=400, height=300, bg="white")
        self.running=False
        self.bind("<Button-1>", self.start_stop)
        self.x=30
        self.y=30
        self.dx=5
        self.dy=5
        self.photo = PhotoImage(file="../greendot.gif")
        self.dot_id=self.create_image(self.x, self.y, image=self.photo)
        self.pack()
    
    def start_stop(self, event):
        if not self.running :
            self.running=True
            self.move_dot()
        else :
            self.running=False
        
    def move_dot(self):
        self.move(self.dot_id, self.dx, self.dy)
        self.x=self.x+self.dx
        self.y=self.y+self.dy
        if self.x < 10 or self.x > 390 : 
            self.dx=-self.dx
        if self.y < 10 or self.y > 290 : 
            self.dy=-self.dy
        if self.running :
            self.after(50, self.move_dot)

root = Tk()
root.title('Moving dot')
Dot_Canvas(root)
mainloop()

Notera funktionen hos programmet. När användaren klickar på musen sätts variabeln running till sant och metoden move_dot kallas på. Sist i metoden move_dot finns raden self.after(50, self.move_dot) denna kallar på move_dot efter 1/20 sekund. Alltså kommer move_dot att köras varje 1/20 sekund. En funktion eller metod som kallar på sig själv kallas rekursiv. När användaren klickar på musen igen blir running falskt och metoden move_dot slutar att kalla på sig själv.

 En mask

Genom att skapa en lista av gröna punkter och deras positioner man göra en studsande mask:

Övning 3.10
Skriv och testa:

from tkinter import *


class Dot_Canvas(Canvas):
    
    def __init__(self, root):
        super().__init__(root, width=400, height=300, bg="white")
        self.running=False
        self.bind("<Button-1>", self.start_stop)
        self.x=[10,20,30,40,50]
        self.y=[10,20,30,40,50]
        self.dx=[5,5,5,5,5]
        self.dy=[5,5,5,5,5]
        self.photo = PhotoImage(file="../greendot.gif")
        self.dot_id=[]
        for i in range(len(self.x)) :
            self.dot_id.append(self.create_image(self.x[i], self.y[i], image=self.photo))
        self.pack()
    
    def start_stop(self, event):
        if not self.running :
            self.running=True
            self.move_dot()
        else :
            self.running=False
        
    def move_dot(self):
        for i in range(len(self.dot_id)) :
            self.move(self.dot_id[i], self.dx[i], self.dy[i])
            self.x[i]=self.x[i]+self.dx[i]
            self.y[i]=self.y[i]+self.dy[i]
            if self.x[i] < 10 or self.x[i] > 390 : 
                self.dx[i]=-self.dx[i]
            if self.y[i] < 10 or self.y[i] > 290 : 
                self.dy[i]=-self.dy[i]
        if self.running :
            self.after(50, self.move_dot)

root = Tk()
root.title('Mask')
Dot_Canvas(root)
mainloop()

 Dra saker med musen

Genom att skilja på händelserna när man trycker ner och drar med musknappen nedtryckt kan man dra saker över en Canvas med musen. Programmet nedan använder också metoden find_closest för att välja den närmaste av de två punkterna.

Övning 3.11
Skriv och testa:

from tkinter import *


class Dot_Canvas(Canvas):
    
    def __init__(self, root):
        super().__init__(root, width=200, height=200, bg="white")
        self.dra_id=None
        self.dra_x=0
        self.dra_y=0
        self.bind("<ButtonPress-1>", self.ned)
        self.bind("<B1-Motion>", self.dra)
        self.photo = PhotoImage(file="../greendot.gif")
        self.create_image(40, 40, image=self.photo)
        self.create_image(160, 160, image=self.photo)
        self.pack()
    
    def ned(self, event):
        self.dra_id = self.find_closest(event.x, event.y)    
        self.dra_x=event.x
        self.dra_y=event.y
        
    def dra(self, event):
        dx=event.x-self.dra_x
        dy=event.y-self.dra_y
        self.move(self.dra_id, dx, dy)
        self.dra_x=event.x
        self.dra_y=event.y

root = Tk()
root.title('Dot')
Dot_Canvas(root)
mainloop()

Inlämningsuppgift 3.2
Skriv något av följande program och lämna in:

1) En analog klocka. Använd create_line och coords för att få visarna att vridas. Kan kompletteras med möjlighet att ställa klockan med musen.

2) Femtonspel - användaren klickar på den siffra hen vill flytta. Programmet utför flytten om det är möjligt och upptäcker om siffrorna är i rad.

3) Masken - Användaren styr en mask med knapp för sväng 90 grader höger eller vänster. Masken blir längre och längre. Man får inte krocka med väggar eller sig själv. Hinder kan införas och mm.

En målarduk

För att visa olika former av grafik finns objektet Canvas.  Canvas använder ett koordinatsystem med origo i övre vänstra hörnet och en pixel per enhet. Y-axeln är riktad nedåt.

Exempel:

from tkinter import *

root = Tk()

w = Canvas(root, width=200, height=100, bg="white")
w.pack()

w.create_line(0, 0, 200, 100)
w.create_line(0, 100, 200, 0, fill="red", dash=(4, 4))

w.create_rectangle(50, 25, 150, 75, fill="blue")

mainloop()

Metoder för att skapa objekt på en Canvas är:

• create_line
• create_rectangle
• create_arc
• create_oval
• create_polygon
• create_text
• create_window
• create_bitmap
• create_image

Se sida 209-210 i boken samt här.

Som synes ovan kan du även konfigurera utseendet på olika objekt med hjälp av angivelser av färger (bg i koden ovan står för background colour) och andra attribut.

Uppgift 3.2
Rita en smiley med tkinters Canvas

Saker som rör sig och att reagera på musklick

Genom att binda en  händelsehanterare till en Canvas kan du göra olika saker vid musklick eller annat som användaren gör. Bindandet gör med metoden .bind("Namn", funktion).
Namn anger händelsen som ska bindas till funktionen. Se här för lista. Se även boken sid. 238-245
funktion är den funktion som ska köras vid händelsen. Alla händelsefunktioner har argumentet event som är en referens till händelseobjektet som innehåller data om händelsen.

Objekten som ritas på en Canvas kan modifieras och förflyttas efter att de ritats. Detta är möjlig då varje objekt ges ett unikt id-nummer i och med att det skapas. Vid förändringarna hänvisas till dessa id-nummer. Se även boken sid. 213-220

Nedanstående exempel ritar ut en bild med en grön prick. Om användaren klickar på musknappen flyttas pricken 10 pixlar snett nedåt.

from tkinter import *

root = Tk()
root.title('Dot')

def klick_b1(event):
    w.move(dot_id, 10, 10)

w = Canvas(root, width=200, height=200, bg="white")
w.bind("<Button-1>", klick_b1)
photo = PhotoImage(file="../greendot.gif")
dot_id=w.create_image(30, 30, image=photo)
w.pack()
mainloop()

Övning 3.7

Skriv in programmet ovan och testa. Bilden på den gröna pricken laddar du ner och placerar i din projektmapp:

  

Global eller klass

Funktioner kan normalt endast läsa globala variabler, inte ändra dem. Detta är ett problem för händelsebindningar i Python. Du skulle behöva skicka med informationen till funktionen som körs vid händelsen men tyvärr går inte det på ett enkelt sätt då man endast anger funktionens namn. Det finns två olika lösningar på problemet:

global

För att kunna ändra globala variabler i en funktion måste de deklareras först i funktionen med nyckelordet global. Ex:

from tkinter import *

root = Tk()
root.title('Dot')
x=30
y=30
dx=10
dy=10

def klick_b1(event):
    global x, y
    w.move(dot_id, dx, dy)
    x=x+dx
    y=y+dy
    print(str(x)+","+str(y))

w = Canvas(root, width=200, height=200, bg="white")
w.bind("<Button-1>", klick_b1)
photo = PhotoImage(file="../greendot.gif")
dot_id=w.create_image(x, y, image=photo)
w.pack()
mainloop()

Klass
Att använda global passar bra i mindre program men det är bättre att hantera objekt när programmen blir lite större. Genom att skapa en egen underklass till Canvas kan du lägga till de data och funktioner du behöver och hantera dessa. Denna lösning ger ser ut så här:

from tkinter import *


class Dot_Canvas(Canvas):
    
    def __init__(self, root):
        super().__init__(root, width=200, height=200, bg="white")
        self.bind("<Button-1>", self.klick_b1)
        self.x=30
        self.y=30
        self.dx=10
        self.dy=10
        self.photo = PhotoImage(file="../greendot.gif")
        self.dot_id=self.create_image(self.x, self.y, image=self.photo)
        self.pack()
        
    def klick_b1(self, event):
        self.move(self.dot_id, self.dx, self.dy)
        self.x=self.x+self.dx
        self.y=self.y+self.dy
        print(str(self.x)+","+str(self.y))

root = Tk()
root.title('Dot')
Dot_Canvas(root)
mainloop()

Lösningen med klass är som synes  "klumpigare" för små testprogram men har stora fördelar då programmen blir större. Den nya klassen Dot_Canvas innehåller allt den behöver för sin funktion och kan skapas enkelt i huvudprogrammet.

Använd valfri metod för att lösa nedanstående:

Övning 3.8

Ändra i programmet ovan så att punkten ser ut att studsa när den når sidorna på fönstret.


Uppgift 3.3
Händelseinformationen som finns i objektet event i koden ovan innehåller bland annat information om var muspekaren var när händelsen inträffade. Detta är lagrat som event.x och event.y. Använd exemplet ovan som grund till ett program som placerar den gröna pricken där användaren klickar.

Textrutan Entry

Entry är en textruta för att skriva in enradstexter. Innehållet i textrutan sparas i en angiven variabel som är ett objekt av typen StringVar().  För att komma åt texten i textrutan används metoden get på textvariabeln. Se ex:

from tkinter import *

def ny_text(): 
    lbl.config(text=en1_text.get())
        
root=Tk()
root.title('Textruta')
root.minsize(200, 60)
en1_text = StringVar() #Variabeln som innehåller textrutans text
en1=Entry(root, textvariable=en1_text).pack(fill=X)
btn = Button(root, text ="Skriv", command = ny_text)
btn.pack(fill=X)
lbl = Label(root, text = "")
lbl.pack(fill=X)

root.mainloop()

För att ställa in texten i textrutan används metoden set("min text") på textvariabeln.

Övning 3.6
Ändra i programmet ovan så att knappen tömmer textrutan samtidigt som texten skrivs i etiketten.

Inlämningsuppgift 3.1
Använd ovanstående samt Övning 2.4 för att göra en grafisk version av ett program som löser andragradsekvationer och skriver ut svaret.

Knappar som gör något

För att något ska hända när du trycker på en knapp anges vilket kommando (vanligen en funktion) som ska köras. Se exempel:

from tkinter import *

def sag_haj(): 
    lbl.config(text="Hej!")
        
root=Tk()
root.title('Count')
root.minsize(200, 100)
btn = Button(root, text ="Säg hej", command = sag_haj)
btn.pack(fill=X)
lbl = Label(root, text = "")
lbl.pack(fill=X)

root.mainloop()

Övning 3.4
Skriv in ovanstående program och testa,

Notera
I Python anges namnet på funktionen som skall köras. Den anropas inte. Där av endast namnet sag_haj utan () efter.

Global

För att kunna ändra globala variabler i en funktion måste du ange att du vill använda den globala variabeln mednyckelordet global anges före du utför ändringen. Detta är användbart när vi ska få knappar att göra saker om vi inte vill skapa objekt. Se nedan.

from tkinter import *

n=0

def oka_ett(): 
    global n
    n=n+1
    lbl.config(text=str(n))
        
root=Tk()
root.title('Count')
root.minsize(200, 100)
btn = Button(root, text ="+1", command = oka_ett)
btn.pack(fill=X)
lbl = Label(root, text = str(n))
lbl.pack(fill=X)

root.mainloop()

Genom att tala om att vi ska använda den globala variabeln n i funktionen oka_ett() kan vi utföra ändringen med kommandot från knappen.

Övning 3.5
Lägg till en knapp  i ovanstående program som minskar värdet på n med ett.

Placering i rutnät

Placering av etiketter och andra widgets i rutnät är en vanlig layoutmetod.

Nedanstående exempel skapar följande layout:

from tkinter import *

root = Tk()
root.title("tk")
root.minsize(200, 200)
#Skapar etiketter med ram
l1 = Label(root, text="Uppe Vänster", relief=RIDGE)
l2 = Label(root, text="Mitten Vänster", relief=RIDGE)
l3 = Label(root, text="Stor", relief=RIDGE)
l4 = Label(root, text="En längre text under", relief=RIDGE)
#Placerar in dem i rutnätet och anger att de ska fylla rutan
l1.grid(row=1, column=1, sticky=W+E+N+S)
l2.grid(row=2, column=1, sticky=W+E+N+S)
l3.grid(row=1, column=2,  columnspan=2, rowspan=2, sticky=W+E+N+S)
l4.grid(row=3, column=1, columnspan=3, sticky=W+E+N+S)

# Hur rader och columner ska uppföra sig vid ändring av fönsterstorleken
root.grid_columnconfigure(1, weight=1)
root.grid_columnconfigure(2, weight=1)
root.grid_columnconfigure(3, weight=1)
root.grid_rowconfigure(1, weight=1)
root.grid_rowconfigure(2, weight=1)
root.grid_rowconfigure(3, weight=1)

root.mainloop()

Se även boken sid. 165-166

Uppgift 3.1
Ändra i programmet ovan så att resultatet blir som i bilden nedan.

Inroduktion till grafiskt gränssnitt

Vi använder det grafiska standardbiblioteket Tkinter. De objekt som det innehåller kallas widgets.

För att förenkla skapar vi en standardmodul som vi kan använda som mall när vi skapar våra objekt. Modulen sköter en del av det bakgrundsarbete som behövs.

Övning 3.1
En standardkod för att skapa grafiska objekt:

from tkinter import *

class myapp_tk(Tk):
    def __init__(self,parent):
        Tk.__init__(self,parent)
        self.parent = parent
        self.initialize()

    def initialize(self):
        pass #Här skrivs den kod som skapar de olika objekten i fönstret.

if __name__ == "__main__":
    app = myapp_tk(None)
    app.title('my application')
    app.mainloop()

Denna kos skapar ett widgetobjekt med namnet app och startar upp metoden mainloop(). Metoden mainloop är den loop som söter hantering av grafiken och reaktion på användarens inmatningar. Den är aktiv så länge objektet finns.

Att lägga till objekt i widgeten

Du lägger till objekt widgeten genom att först skapa ett nytt objekt som tillhör widgeten och sedan placera detta med metoden pack().

Övning 3.2
En etikett (label) med text. Byt ut innehållet i initialize(self) till:

    def initialize(self):
        self.label=Label(text="Hello World")
        self.label.pack()

Övning 3.3
Använd informationen i boken på sidan 158-163 för att testa pack-metoden och knappar.
 

Moduler och arv

Klasser och moduler

Det går utmärkt att ha flera klasser i en modul. Om du då vill komma åt dessa klasser från en annan modul importerar du modulen. Som för funktioner skriver du sedan modulnamn.Klassnamn när du vill använda klassen. Ex:

import minmodul

...

# Skapar objektet mittobjekt av klassen MinKlass från modulen minmodul
mittobjekt = minmodul.MinKlass()

...

Övning 2.25
Kopiera klasserna för de geometrikska kropparna du skapat till en modul med namnet klossar (filnamnet är alltså klossar.py).

Arv eller klasser och underklasser

En av poängerna med objektorienterad programmering är arv av egenskaper mellan klasser. Vi kan skapa en huvudklass med de variabler och metoder som objekt i underklasser skall ha gemensamt.

Vi vill att alla klossar skall ha en position och en färg. Positionen skall vara en  lista med tre element [x, y, z] och färgen en textsträng. Vi vill kunna ändra färg och också ha möjlighet att flytta klossarna genom att ange en ny position.

Huvudklassen blir då:

#Huvudklass Klossar
class Kloss :
    def __init__(self):
        self.position =[0, 0, 0]
        self.farg=""
        
    def flytta(self,position):
        self.position=position
        
    def satt_farg(self, farg):
        self.farg=farg
  

Nu har vi grunden för metoder och variabler som kan ärvas av alla varianter av klossar vi skapar. Metoderna i underklasserna går före de i huvudklassen så då det finns en metod volym() i klassen Kub så körs den om objektet är en kub. Skulle det inte finnas en metod i underklassen så körs istället den i huvudklassen.Så om man kallar på metoden flytta för en kub så körs metoden i huvudklassen Klossar.

För att göra det lite snyggt  så inför vi tomma metoder i huvudklassen för de som ska implementeras i alla underklasser, alltså volym, area och skala. Genom detta är det lätt att se vad en underklass förväntas implementera. Tomma metoder skapas genom att lägga in pass som enda del i metodkroppen. Metoden skala(k) i huvudklassen Klossar ser alltså ut så här:

    def skala(self, k):
        pass

Övning 2.26
Lägg till tomma klasser för skala, volym och area i huvudklassen

Att skapa arvet

Nu måste vi få underklasserna att ärva metoder och variabler från huvudklassen.

För att tala om att en klass är en underklass till en annan anges huvudklassen i parentes bakom namnet på underklassen. I vårt fall ändrar vi i raden där vi definierar Kub till:

class Kub(Kloss) :

Nu är Kub en underklass till Klossar och har tillgång till dess metoder.För att Kub skall få samma variabler som huvudklassen ser vi till att huvudklassens initiering körs samtidigt som underklassens. Detta sker med hjälp av funktionen super(). super(). refererar till huvudklassen ungefär som self refererar till klassen själv.

Klassen Kub får med arv och initiering av variablerna i Klossar utseendet:

class Kub(Kloss) :
    
    def __init__(self, sida):
        super().__init__()
        self.sida=sida
        
    def skala(self, k):
        self.sida=self.sida*k
           
    def volym(self):
        return self.sida*self.sida*self.sida
    
    def area(self):
        return self.sida*self.sida*6

Övning 2.27
Skriv om övriga kloss-klasser så att de ärver metoder och variablerna från Klossar.

Övning 2.28
Skapa en ny modul, klosstest, och pröva att arvet fungerar:
Skriv och kör:

import klossar

kuben=klossar.Kub(8)
print(kuben.position)
kuben.flytta([1,2,3])
print(kuben.position)
kuben.skala(2)
print(kuben.volym())

Övning 2.29
Skriv tester för några av de andra kloss-typerna samt färgen också.

Övningar klasser

Vi ska skapa några klasser för att testa hur de fungerar. Vi skapar klossar av olika slag.

• Kub
• Rätblock
• Pyramid - kvadratisk bas och symetrisk
• Cylinder
• Klot

En klass blir en ritning till var och en av klosstyperna. Vi vill förutom att skapa klossen även kunna få reda på dess volym och begränsningsarea.

Vi kan skapa alla klasserna i samma modul. Här är klassen för Kuben:

class Kub :
    
    def __init__(self, sida):
        self.sida=sida
        
    def volym(self):
        return self.sida*self.sida*self.sida
    
    def area(self):
        return self.sida*self.sida*6

Övning 2.22
Skapa klasser för de övriga klosstyperna i samma modul (fil). Tips: tänk på vilka mått som måste anges för de olika typerna och undvik åäö.

Vi kan nu använda klasserna för att skapa objekt och utföra beräkningar med dessa. Till exempel ta reda på sammanlagda volymen av en kub med sidan 8 och ett klot med radien 4. I huvudprogrammet skriver vi:

kuben=Kub(8)
klotet=Klot(4)
print(kuben.volym()+klotet.volym())

Uppgift 2.7
Bestäm sammanlagda arean av dessa tre objekt:
En pyramid med bas-sidan 5 och höjden 10
Ett rätblock med längden 8, bredden 4 och höjden 6
En cylinder med radien 5 och höjden 6

En metod som ändrar objektet

Ovanstående objekt kan inte förändras efter att de skapats. Vi kan göra de mer användbara genom att införa metoder som ändrar objektet. Till exempel ändrar dess storlek genom skalning. Följande version av klassen Ratblock kan skalas upp eller ned med metoden skala(k) där k är skalfaktorn:

class Ratblock :
    
    def __init__(self, langd, bredd, hojd):
        self.langd=langd
        self.bredd=bredd
        self.hojd=hojd
    
    def skala(self, k):
        self.langd=self.langd*k
        self.bredd=self.bredd*k
        self.hojd=self.hojd*k
    
    def volym(self):
        return self.langd*self.bredd*self.hojd
    
    def area(self):
        return self.langd*self.hojd*2+self.bredd*self.hojd*2+self.bredd*self.langd*2

Övning 2.23
Lägg till skalningsmetoder för övriga klasser.

Övning 2.24
Hur mycket ändrar sig begräsningsarea och volym på en kub med sidan 4 som skalas upp 10 ggr.

Klasser och objekt

Klassen Complex

Nedanstående visar ett exempel på klass och objekt skapade ur klassen. Klassen Complex fungerar som ett paket för komplexa tal.

import math

#Klassens definition
class Complex:
     #Konstruktor
     def __init__(self, realdel, imagdel):
         self.r = realdel
         self.i = imagdel

     def abs(self):
         return math.sqrt(self.r*self.r+self.i*self.i)
        
#Använder klassen
#Skapar objekt z av klassen Complex
z = Complex(3.0, -4.5)
print(str(z.r) + ", " + str(z.i))
print(z.abs())

Nya objekt skapas med konstruktorn __init__(self, realdel, imagdel). Varje nytt komplext tal skapas med värden på realdel och imaginärdel. Klassen innehåller även en metod abs() som returnerar absolutvärdet av det komplexa talet.

Övning 2.18
Lägg till en metod som returnerar det komplexa talet som en textsträng som vi normalt skriver komplexa tal. Ex: 3+4i och 2-5i. Kalla metoden string(self)
Testa din metod.

Övning 2.19
Lägg till en metod arg() som returnerar argumentet för det komplexa talet.
Tips: math.atan2(y,x) returnerar vinkeln, i radianer, från x-axeln korrekt runt hela varvet.
Testa din metod.

Standardvärden

Du kan lägga till standardvärden till konstruktorn för att möjliggöra en standardversion av ditt objekt. Det görs genom att skriva som exemplet nedan:

def __init__(self, realdel = 0, imagdel = 0):

 Nu ger z = Complex() det komplexa talet 0+0i och z = Complex(5) talet 5+0i.
Du kan dock inte enbart ange imaginärdelen då standardvärdena ersätts från vänster till höger för varje angivet argument.

Använda referens till objekt i metod och anonyma objekt

Följande metod lägger till det komplexa talet z till det ursprungliga objektet

     def add(self, z):
          self.r=self.r+z.r
          self.i=self.i+z.i

Övning 2.20
Lägg till metoden ovan till klassen Complex och testa genom att i huvudprogrammet till exempel skriva:

z.add(Complex(5,1))
print(z.string())

Ovanstående skapar ett anonymt objekt av klassen Complex med värdet 5+i och lägger till det till det ursprungliga objektet.

Övning 2.21
Skapa motsvarande metoder som ovanstående för subtraktion, multiplikation och division. (Kom ihåg att vid division förlänger du med konjugatet till nämnaren.)

Sökning och sortering

Sortering

Att sortera listor och andra uppsättningar data är viktigt inom många användningsområden och det finns ett stort antal algoritmer för detta.

Läs om sorteringsalgoritmer här.

Python har  en inbyggd metod för att sortera listor som är mycket effektiv:
lista.sort()

Sökning i listor

Om listan är oordnad är det enklast att söka från början till slut tills man hittar det man söker. Man behöver då i snitt söka genom hälften av listan innan man finner det sökta värdet.

Är listan sorterad kan sökningen snabbas upp betydligt genom en smart metod.

Binär sökning
I en sorterad lista kan man veta om man är före eller efter det sökta värdet. Man gör därför så att man gissar på det mittersta värdet inom det område man inte uteslutit. Se nedanstående bild som visar sökning efter talet 76:

Efter första gissningen vet man att talet är i den övre halvan.
Efter den andra vet man att talet är i den tredje fjärdedelen.
osv tills man finner det.

Uppgift 2.6
Skriv ett program som:

•  Låter användaren mata in ett valfritt antal tal (Avsluta inmatningen med tex. att användaren skriver N). Talen läggs i en lista.
•  Sorterar listan av tal.
•  Med hjälp av binär sökning letar fram ett tal som användaren matat in. (Förutsatt att det finns i listan. Annars ett meddelande om att det inte finns.)

Stackar och köer

Stack

I en stack placeras nya data överst i stacken och data hämtas också överst i stacken. Ordningen kallas ibland LIFO ("Last In Frist Out"). Stackar används ofta i matematiska rutiner och är fundamental för den interna funktionen i datorer.

Kö

I köer placeras nya data längst bak i kön och data hämtas från början av kön. Ordningen kallas ibland FIFO ("First In First Out"). Köer används då det är viktigt att bevara ordningen på datan.

Exempel som buffer

Följande övningar visar exempel på hur stack och kö fungerar som buffrar. En buffer lagrar temporärt data. De kan bland annat användas för att kunna processa data i jämn takt trots att den inkommande datan kommer in i mer ojämn takt vid internetuppkopplingar, bränning av skivor och mycket mer. Nedanstående exempel visar principen för en sådan buffer i form av en stack och en kö.

Övning 2.16

#Simulerar en stack där 0-2 nya element tillkommer varje sekund och ett
# poppas.

import random
import time

#Fyller stacken med 6 bokstäver. A underst i stacken
stack = ["A", "B", "C", "D", "E", "F"]
alfa = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
i = 6
while True :
    try : 
        print("Processar " + stack.pop())    
        print(stack)
    except IndexError :
        print("Stacken tom! Avslutar")
        break
    
    antal_nya = random.randint(0,2)
    while antal_nya > 0 :
        stack.append(alfa[i])
        i = (i + 1) % 26
        antal_nya = antal_nya - 1
    time.sleep(1)
    
print("Slut")

Övning 2.17

#Simulerar en kö (buffer) där 0-2 nya element tillkommer varje sekund och ett
# poppas.

import random
import time

#Fyller kön med 6 bokstäver. A först i kön
queue = ["A", "B", "C", "D", "E", "F"]
alfa = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
i = 6
while True :
    try : 
        print("Processar " + queue.pop(0))    
        print(queue)
    except IndexError :
        print("Buffern tom! Avslutar")
        break
    
    antal_nya = random.randint(0,2)
    while antal_nya > 0 :
        queue.append(alfa[i])
        i = (i + 1) % 26
        antal_nya = antal_nya - 1

    time.sleep(1)
    
print("Slut")