Jython

Listen


In Python kann man in Listen beliebige Daten speichern. Zum Beispiel Zahlen, Farben, Buchstaben, Punktkoordinatenlisten usw. In anderen Programmiersprachen verwendet man dazu oft Arrays. Im Gegensatz zu Arrays haben Listen keine feste, vordefinierte Länge, d.h. ihre Länge wird der Anzahl gespeicherter Elemente automatisch angepasst (dynamische Datenstruktur). Die Elemente einer Liste werden in eckigen Klammern zusammengefasst.

Beispiel 1: Liste mit Streckenlängen
Ausgehend von der linken unteren Ecke kann man mit Strecken, die entweder im Winkel 45° oder 90° zu einander stehen, ein Haus zeichnen. Die Streckenlängen ergeben die folgende Liste: [60, 71, 71, 60, 100], wobei die Zahl 71 die gerundete Länge der Diagonale eines Quadrats mit der Seitenlänge 50 ist. Im Programm wird die Liste mit zwei Strecken mit der Länge 0 ergänzt. So kann man die Liste der Reihe nach durchlaufen und die Turtle dreht nach jeder gezeichneten Strecke 45° nach rechts (bei 0 dreht sie zwei mal am Ort, was dem Winkel 90° entspricht). 

#Tu13a.py

from gturtle import *

makeTurtle()

house = [60, 71, 0, 71, 60, 0, 100]

for s in house:
    forward(s)
    right(45)
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)
 


Erklärungen zum Programmcode:

house = [60, 71, 0, 71, 60, 0, 100] : erzeugt eine Liste mit 7 Elementen
for s in house: Liste house mit einer for-Schleife durchgelaufen

 

Beispiel 2: Figur skalieren
Eine Figur, die mit Hilfe einer Liste gezeichnet wird, kann sehr einfach vergrössert oder verkleinert werden.

 

#Tu13b.py

from gturtle import *

makeTurtle()

house = [60, 71, 0, 71, 60, 0, 100]

for s in house:
    forward(2 * s)
    right(45)
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)
 


Erklärungen zum Programmcode:

forward(2 * s): jedes Listenelement wird verdoppelt. Analog kann mit forward(0.5 * s) eine halb so grosse Figur gezeichnet werden

 

Beispiel 3: Punktliste
Das gleiche Haus kann auch gezeichnet werden, indem man eine Liste die Koordinaten der Eckpunkte angibt und diese der Reihe nach verbindet. 

#Tu13c.py

from gturtle import *

makeTurtle()

house = [(0, 60), (50, 110), (100, 60), (100, 0), (0, 0)]

for p in house:
    moveTo(p)
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)
 


Erklärungen zum Programmcode:

house = [(0, 60), (50, 110), (100, 60), (100, 0), (0, 0)]: Punktliste. Die Zahlen in den runden Klammern geben jeweils die x- und y-Koordinate an
moveTo(p): zeichnet die Verbindungslinie von der aktuellen Turtle-Position zum Punkt p

 

Beispiel 4: Elemente hinzufügen

Die Anzahl Elemente einer Liste kann während der Programmausführung verändert werden. Es ist sogar möglich eine ganze Liste dynamisch zu erzeugen. Man definiert zuerst eine leere Liste [] und fügt danach mit der Funktion append() die einzelnen Elemente hinzu.

In unserem Beispiel wird zuerst eine leere Liste corner = [] erzeugt. Mit der linken Maustaste werden Punkte mit den Koordinaten des Mausklicks zu der Liste hinzugefügt. Mit einem rechten Mausklick werden diese Punkte zu einem Polygon verbunden und die Polygonfläche rot ausgefüllt.

 

# Tu13d.py

from gturtle import *

def onMousePressed(x, y):
    if isLeftMouseButton():
        pt = (x, y)
        setPos(pt)
        dot(8)        
        corner.append(pt)
    if isRightMouseButton():
        setFillColor("red")
        startPath()
        for p in corner:
             moveTo(p)
        fillPath()     
        
makeTurtle(mousePressed = onMousePressed)
hideTurtle()
corner=[]
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)
 


Erklärungen zum Programmcode:

corner = []: erzeugt eine leere Liste
corner.append(pt): fügt den Punkt pt zur Liste corner hinzu

 

Beispiel 5: Fläche eines Polygons mit Monte Carlo-Methode bestimmen
Die Eckpunkte des Polygons werden mit dem linken Mausklick festgelegt. Mit dem rechten Mausklick wird die Polygonfläche grau gefüllt. Danach lässt man n Zufallstropfen auf das Turtlefenster fallen. Mit der Funktion getPixelColorStr() kann man herausfinden, ob die Farbe in einem zufällig gewählten Punkt weiss oder grau ist. Die Tropfen in der grauen Fläche werden als Hits gezählt und rot gezeichnet, die übrigen grün. Da es vorkommen kann, dass ein Punkt mehrmals getroffen wird, müssen bei den Treffern auch die bereits rot gefärbte Punkte als Hits gezählt werden.

Aus dem Verhältnis der Anzahl Treffer zu Anzahl aller Punkte, die man auf das Turtlefenster fallen lässt, lässt sich die Polygonfläche berechnen. Eine höhere Genauigkeit erreicht man, wenn man die Anzahl der Zufallspunkte erhöht.

 

   

# Tu13e.py

from gturtle import *
import random

def onMousePressed(x, y):
    if isLeftMouseButton():
        pt = (x, y)
        setPos(pt)
        dot(5)        
        corner.append(pt)
    if isRightMouseButton():
        setFillColor("gray")
        startPath()
        for p in corner:
             moveTo(p)
        fillPath()
        wakeUp()        

def startRandomRain():
    nbHit = 0
    for i in range(n):            
            p = (random.randint (-300, 300), random.randint (-300, 300))
            setPos(p)
            color = getPixelColorStr() 
            if color == "white":
                setPenColor("green")                
                dot(2)
            if color == "gray" or color == "red":
                nbHit += 1
                setPenColor("red")                
                dot(2)
    setStatusText("#hits: " + str(nbHit) + " of " + str(n) 
                + " = " + str(nbHit/n * 100) + " % of windowarea") 
                               
makeTurtle(mousePressed = onMousePressed)
addStatusBar(20)
setStatusText("Left click to select corners, right click to start dropping") 
setPenColor("gray")
hideTurtle()
corner=[]
n = 100000
putSleep()
startRandomRain()
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)

Erklärungen zum Programmcode:

startRandomRain(): startet die Erzeugung von n Zufallspunkten
getPixelColorStr(): gibt die Hintergrundfarbe an der Turtleposition zurück
putSleep(), wakeUp(): wenn die Funktion startRandomRain() im Mauscallback aufgerufen wird, werden die Zufallspunkte nicht fortlaufend gezeichnet, sondern alle gleichzeitig am Schluss

 
Aufgaben Serie 13

1.

a) Zeichne das nebenstehende Parallelogramm mit Hilfe der Liste der Seitenlängen [71, 100, 0, 0, 71, 100].

b) Zeichne die gleiche Figur, indem du eine Liste der Eckpunkte erstellst und den Befehl moveTo(p) verwendest.
       
2.

Mit dem linken Mausklick werden beliebig viele Punkte gezeichnet und in einer Liste gespeichert. Klickt man mit der rechten Maustaste, so werden vom Punkt des Mausklicks aus Verbindungslinien zu allen gespeicherten Punkten gezeichnet.

 
       
3.

Zeichne mit dem linken Mausklick beliebig viele Punkte, so dass jeder neu gezeichnete Punkt mit allen übrigen Punkten verbunden wird.

Anleitung: Gehe ähnlich wie im Beispiel 4 vor: linker Mausklick erzeugt einen Punkt und speichert ihn in einer Liste corner. Die Verbindungslinien kannst du mit zwei for-Schleifen zeichnen:

for p in corner:            
    for q in corner:
        setPos(p)
        moveTo(q)
 


       
4.

Erstelle eine Liste colors mit 8 Farben. Definiere eine Funktion line(color, length), der eine farbige Linie zeichnet. Zeichnen Sie eine Spirale, so wie im Bild rechts. Nach jeder gezeichneten Strecke wird die nächste Farbe aus der Liste colors genommen. Nach dem man die letzte farbe genommen hat, beginnt man wieder mit der ersten Farbe. 

 

  

 

Zusatzstoff: Sortieralgorithmen

Sortieralgorithmen gehören zu den wichtigsten und meist verwendeten Verfahren der Informatik. Obwohl in vielen Programmiersprachen, so auch in Python, vordefinierte Sortierfunktionen existieren, gehören die Konzepte des Sortierens zum Standardwissen, denn es gibt immer wieder Situationen, in welchen man das Sortieren selbst implementieren muss.

Beispiel 6: Eine Liste mit n Elementen mit BubbleSort der Grösse nach ordnen

Die Sortierung mit BubbleSort-Algorithmus erfolgt wie folgt:

  • Man geht die Liste vom ersten bis zum vorletztem Element durch und vergleicht jedes Element mit dem nachfolgendem
  • Ist das Element grösser als sein Nachfolger, wird die Reihenfolge der beiden Elementen vertauscht
  • Das grösste Element steht danach am Ende der Liste
  • Man wiederholt den Vorgang mit den übrigen n - 1 Elementen und plaziert das zweitgrösste Element an die vorletzte Position. Dann wiederholt man dasselbe mit den restlichen n-2 Elementen, n-3 Elementen usw.
# BubleSort1.py

def bubbleSort(li):
    n = len(li)
    for i in range(n - 1, 0, -1):
        for k in range(i):
            if li[k] > li[k + 1]:
                li[k + 1],li[k] =  li[k],li[k + 1]
                 
li = [85, 34, 57, 13, 25, 39, 44, 7, 68, 30]
bubbleSort(li)
print(li)
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)

Ergebnis:
[7, 13, 25, 30, 34, 39, 44, 57, 68, 85]

Erklärungen zum Programmcode:
len(li): Anzahl Elemente der Liste li
for i in range(n - 1, 0, -1): Zuerst die ersten n-1 Elemente durchgehen, dann die ersten n-2 Element, n-3 Elementen usw.
li[k + 1], li[k] = li[k], li[k + 1]): Vertauscht die Reihenfolge der zwei Elemente der Liste li

 

Beispiel 7: Grafische Darstellung des BubbleSort-Algorithmus

n zufällig gewählte Zahlen zwischen 1 und 500 werden mit dem BubbleSort-Algorithmus sortiert. Um den Sortiervorgang grafisch darzustellen, zeichnet man für jede Zahl einen Balken, dessen Höhe in Pixel der Zufallszahl entspricht. Danach wird die Liste sortiert und die Balken nach jedem Sortierungsschritt neu dargestellt.

Die Funktion drawBar(s) zeichnet einen Balken der Länge s.
Die Funktion drawAllBars() zeichnet alle Balken.

 

  

Ausführen mit Webstart

 
# BubbleSort2.py

from gturtle import *
from random import randint

d = 10
n = 59

def createRandomBars():
    for i in range(n):
        s = randint(1, 500)
        li.append(s) 
    drawAllBars()

def drawBar(s):
    left(90)
    penDown()
    forward(s)
    back(s)
    penUp()
    right(90)
    
def drawAllBars():
    clear()
    setPos(-290, -250)
    for s in li: 
        drawBar(s)        
        forward(d)
    
def bubbleSort():
    for i in range(n-1, 0, -1):
        for k in range(0, i):
            if li[k] > li[k + 1]:
                li[k + 1],li[k] =  li[k],li[k + 1]
                drawAllBars()
                repaint()
                Turtle.sleep(10)                        

makeTurtle()
enableRepaint(False)
ht()
right(90)
setPenWidth(8)
li = []
createRandomBars()
bubbleSort()
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)

Erklärungen zum Programmcode:

enableRepaint(False): verhindert das automatische Rendern
repaint(): stellt die ganze Grafik auf dem Bildschirm dar
Turtle.sleep(10): damit man das Sortieren bessert verfolgen kann, wird das Programm nach jedem Sortierdurchgang 10 ms angehalten

 

Beispiel 8: n Farbkugeln mit BubbleSort nach Regebogen-Spektrum sortieren

Zu Beginn werden n Kugeln in zufällig gewählten Regenbogenfarben gezeichnet. Damit die Farben nach dem Regebogenspektrum sortiert werden können, müssen sie in das HSB-Format konvertiert werden. Im HSB-Format wird jede Farbe mit den folgenden drei Komponenten angegeben: H: Farbton, S: Sättigung, B: Helligkeit. Für die Sortierung braucht man nur den Farbton (hsb[0]). Dieser wird mit einem Winkel im HSB-Farbkreis definiert (0° entspricht der Farbe rot).

Ergebnis:

  

HSB-Farbraum

 

 

# BubbleSort3.py

from gturtle import *
from random import randint

d = 15
n = 41

def createRandomDots():
    for i in range(n):
        c = makeColor("rainbow", randint(10, 90) / 100)
        li.append(c)
    drawAllDots()    
        
def drawAllDots():
    setPos(-295, 0)
    for c in li:
        setPenColor(c)
        dot(d - 1)
        forward(d)    

def getHsb(c):
    hsb = Color.RGBtoHSB(c.getRed(), c.getGreen(), c.getBlue(), [0, 0, 0])
    return hsb[0]
   
def bubbleSort():
    for i in range(n - 1, 0, -1):
        for k in range(i):
            if getHsb(li[k]) > getHsb(li[k + 1]):
                li[k + 1],li[k] =  li[k],li[k + 1]                
                drawAllDots()
                repaint()
                Turtle.sleep(10)
 
makeTurtle()
clear("black")
enableRepaint(False)
right(90)
li = []
createRandomDots()
bubbleSort()
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)

Erklärungen zum Programmcode:

makeColor("rainbow", randint(10, 90) / 100): erzeugt eine zufällige Regenbogenfarbe
RGBtoHSB(): konvertiert eine RGB-Farbe zu
Turtle.sleep(10): damit man das Sortieren bessert verfolgen kann, wird das Programm nach jedem Sortierdurchgang 10 ms angehalten

 

Beispiel 9: QuickSort-Algorithmus

Der BubbleSort-Algorithmus ist einfach nachvollziehbar, ist aber nicht so effizient. In der Praxis werden deshalb effizientere Sortierverfahren verwendet, wie z.Bsp. QuickSort.

Der Programmcode ist einiges komplizierter als bei BubbleSort und wird an dieser Stelle nur als Demonstration aufgeführt, damit man die die Geschwindigkeit beider Sortierverfahren vergleichen kann. Eine Beschreibung des Algorithmus findet man beispielsweise auf Wikipedia. [https://de.wikipedia.org/wiki/Quicksort]

 

 

 

  

Ausführen mit Webstart

 
# QuickSort.py

from gturtle import *
from random import randint

d = 10
n = 59

def createRandomBars():
    for i in range(n):
        s = randint(1, 500)
        li.append(s) 
    drawAllBars(li)

def drawBar(s):
    left(90)
    penDown()
    forward(s)
    back(s)
    penUp()
    right(90)
    
def drawAllBars(li):
    clear()
    setPos(-290, -250)
    for s in li: 
        drawBar(s)        
        forward(d)
    
def quickSort(li):
   quickSortHelper(li,0,len(li)-1)

def quickSortHelper(li,first,last):
   if first<last:
       splitpoint = partition(li,first,last)
       quickSortHelper(li,first,splitpoint-1)
       quickSortHelper(li,splitpoint+1,last)

def partition(li,first,last):
   pivotvalue = li[first]
   leftmark = first+1
   rightmark = last
   done = False
   while not done:
       while leftmark <= rightmark and li[leftmark] <= pivotvalue:
           leftmark = leftmark + 1
       while li[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1
       if rightmark < leftmark:
           done = True
       else:
           temp = li[leftmark]
           li[leftmark] = li[rightmark]
           li[rightmark] = temp
   temp = li[first]
   li[first] = li[rightmark]
   li[rightmark] = temp
   drawAllBars(li)
   repaint()
   Turtle.sleep(10)     
   return rightmark     

makeTurtle()
enableRepaint(False)
ht()
right(90)
setPenWidth(8)
li = []
createRandomBars()
quickSort(li)
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)

 
Aufgaben

5.

In Python gibt es eine eingebaute Funktion sort().
li.sort() sortiert die Liste li.
Verwende im Beispiel 7 (BubbleSort2.py) die Funktion sort() anstelle des BubleSort-Algorithmus. Du kannst allerdings nur die Start- und End-Situation darstellen. Auf die fortlaufende Animation muss du verzichten.

Die wichtigsten Operationen mit Listen

 

li = [1, 2, 3, 4]

li = [1, "a", [7 , 5]]

li[i]

li[start:end]

li[start:end:step]

li[start:]

li[:end]

li.append(element)

li.insert(i, element)

li.extend(li2)

li.index(element)

li.pop(i)

pop()

li1 + li2

li1 += li2

li * 4

[0] * 4

len(li)

del li[i]

del li[start:end]

del li[:]

li.reverse() 

li.sort() 

x in li

x not in li

li[k+1], li[k] = li[k], li[k+1]

Liste mit den Zahlen 1, 2, 3, 4 definieren

Liste mit unterschiedlichen Datentypen definieren

Auf Listenelement mit Index i zugreifen

Neue Teilliste mit Elementen start bis end,  aber ohne end

Neue Teilliste mit Elementen start bis end mit Schritt step

Neue Teilliste mit allen Elementen von start an

Neue Teilliste von ersten Element bis end, aber ohne end

Anfügen ans Ende

Einfügen an Stelle i (Element i rutscht nach rechts)

Elemente aus li2 anfügen (Konkatenation)

Sucht das erste Vorkommen und gibt dessen Index zurück

Entfernt das Element mit Index i und gibt es zuück

Entfernt das letzte Element und gibt es zurück

Gibt die Konkatenation von li1 und li2 in neuer Liste zurück

Ersetzt li1 durch die Konkatenation von li1 und li2

Neue Liste mit Elementen von li viermal wiederholt

Neue Liste mit der Länge 4 (jedes Element Zahl 0)

Gibt die Anzahl Listenelemente zurück

Entfernt das Element mit Index i

Entfernt alle Elemente von start bis end, aber ohne end

Entfernt alle Elemente, es bleibt eine leere Liste

Kehrt die Liste um (letztes Element wird das erste)

Sortiert die Liste (Vergleich mit Standardverfahren)

Gibt True zurück, falls x in der Liste enthalten ist

Gibt True zurück, falls x nicht in der Liste enthalten ist

Vertauscht die Reihenfolge zwei nacheinanderfolgenden Elemente