====== Programmieren III: Listen, for-Schleifen ======

===== Listen =====

{{ :gf_informatik:2023_listen.pdf |}}

Bisher haben wir in Variablen einzelne Werte gespeichert. Kann man auch *mehrere Werte* in einer Variablen speichern? Ja! Mit Listen!

Eine Liste wird erstellt, indem die Elemente in `[` eckigen Klammern `]` (_en_: brackets) eingeschlossen werden:

<bottom-editor autorun>
alphabet = ['a','b','c','d','e']
</bottom-editor>

Die Liste im Beispiel oben hat die fünf **Elemente** `'a'`, `'b'`, `'c'`, `'d'` und `'e'`. Jedes dieser Elemente hat einen bestimmten **Index**, seine **Position** in der Liste:

^ Position / Index ^  `0` ^  `1` ^  `2` ^  `3` ^  `4` ^
|Element| `'a'` | `'b'` | `'c'` | `'d'` | `'e'` |

Beachte, dass das erste Element den **Index 0** hat((Warum beginnt die Nummerierung bei 0? [[wp>Zero-based_numbering]] und [[https://www.cs.utexas.edu/~EWD/transcriptions/EWD08xx/EWD831.html|Edsger W. Dijkstra]] geben ein paar Anhaltspunkte.))!

==== Selektion und Modifikation ====

Über den Index kann man auf ein **Element zugreifen**, das Element wird _ausgewählt_ oder **selektiert**. Dazu schreibt man zuerst den Namen der Liste und dann den Index in eckigen Klammern:

<bottom-editor autorun>
print(alphabet[2]) # gibt 'c' aus

alphabet[3] = 'z'  # ändert Element an Position 3 (also 'd') zu 'z'
print(alphabet)    # Ausgabe: ['a','b','c','z','e']
</bottom-editor>

Einer Liste kann man Elemente **hinzufügen** und **entfernen**
<bottom-editor autorun>
alphabet.append('f')   # Fügt Element hinten an, Liste nachher: ['a','b','c','z','e','f']
alphabet.insert(1,'q') # Fügt Element 'q' an Position 1 ein, Liste nachher: ['a','q','b','c','z','e','f']
alphabet.pop(3)        # Entfernt Element an Position 3, Liste nachher: ['a','q','b','z','e','f']
alphabet.pop()         # Entfernt letztes Element, Liste nachher: ['a','q','b','z','e']
print(alphabet)
</bottom-editor>

Die Länge einer Liste bestimmt man wie folgt:
<bottom-editor autorun>
l = len(alphabet) # Anzahl Elemente in Liste
print(l)
</bottom-editor>

==== Iteration ====

Oft möchte man durch alle Elemente einer Liste **durchgehen** und etwas mit diesen machen, z.B. sie in die Konsole printen:
<bottom-editor>
alphabet = ['a','b','c','d','e']
i = 0                     # Startindex, 0, weil wir zuerst das vorderste Element (hier 'a') auslesen möchten
while i < len(alphabet):  # Bedingung while-Schleife
    print(alphabet[i])    # lese Element aus Liste aus, alphabet[i], und printe dieses
    i = i + 1             # erhöhe Index
</bottom-editor>

In der Bedingung `i < len(alphabet)` ermitteln wir mit len(alphabet) die Länge der Liste. Wichtig ist auch, dass der Index `i` *kleiner* (und nicht kleiner gleich) ist als diese Länge, da sonst versucht wird, auf Element zuzugreifen, welches nicht existiert.

Noch etwas eleganter geht dasselbe mit einer `for`-Schleife (mehr dazu im nächsten Kapitel). Dabei wird die Schleifen-Variable (im Beispiel `e`) in jedem Durchgang der Schleife auf das nächste Element der Liste gesetzt.
<bottom-editor>
alphabet = ['a','b','c','d','e']
for e in alphabet:
    print(e)
</bottom-editor>

Mit folgendem Code überprüft man, ob ein Element in einer Liste steht:
<bottom-editor>
if 'b' in ['a','c','e','g']:
    print('kommt in Liste vor')
else:
    print('kommt nicht in Liste vor')
</bottom-editor>

==== Aufgaben H ====

=== Aufgabe H1 ===

<bottom-exercise id="h1">
<div slot="prompt">
Betrachte die Liste <code>alphabet = ["B","C","X","D","Z","F","G","I","J"]</code>. Korrigiere die Liste, indem du mit den entsprechenden Funktionen:
<ul>
   <li>am Anfang ein "A" einfügst
   <li>das "X" entfernst
   <li>dem Element mit Wert "Z" den korrekten Wert "E" zuweist
   <li>am richtigen Ort ein "H" einfügst
   <li>am Ende ein "K" anhängst
</ul>
</div>
<template data-type="starter">
alphabet = ["B","C","X","D","Z","F","G","I","J"]
</template>
<template data-type="test">
assert alphabet == ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"]
</template>
<template data-type="solution">
alphabet = ["B","C","X","D","Z","F","G","I","J"]

alphabet.insert(0,"A")
alphabet.pop(3) # oder: alphabet.remove("X")
alphabet[4] = "E"
alphabet.insert(7,"H")
alphabet.append("K")

print(alphabet)
</template>
</bottom-exercise>

=== Aufgabe H2 ===

<bottom-exercise id="h2">
<div slot="prompt">

Betrachte die Liste:

<code>
likeable_football_clubs = ["bvb", "liverpool", "st. gallen", "bayern", "freiburg", "breitenrain"]
</code>

<ol>
   <li>Gehe mit einer Schleife der Reihe nach durch alle Elemente der Liste durch und gebe sie aus.
   <li>Die Bayern haben nichts in dieser Liste verloren. Bitte entferne sie, danke! Füge weiter deinen Lieblingsklub hinzu.
</ol>
</div>
<template data-type="starter">
likeable_football_clubs = ["bvb", "liverpool", "st. gallen", "bayern", "freiburg", "breitenrain"]
</template>
<template data-type="test">
assert {"bvb", "liverpool", "st. gallen", "bayern", "freiburg", "breitenrain"}.issubset(set(output_lines()))
assert "bayern" not in likeable_football_clubs
assert len(likeable_football_clubs) > 5
</template>
<template data-type="solution">
likeable_football_clubs = ["bvb", "liverpool", "st. gallen", "bayern", "freiburg", "breitenrain"]

# 1) Ausgeben
i = 0
while i < len(likeable_football_clubs):
    print(likeable_football_clubs[i])
    i = i + 1

# 2) Bayern entfernen, YB einfügen
likeable_football_clubs.pop(3)
likeable_football_clubs.append("YB")
print(likeable_football_clubs)</template>
</bottom-exercise>

=== Aufgabe H3 ===

<bottom-exercise id="h3">
<div slot="prompt">
Betrachte die Liste <code>[68, 71, 53, 34, 66, 55, 80, 93, 24, 49, 68, 73, 9, 8, 93, 22, 44, 11, 82]</code>

<ol>
   <li>Berechne die Summe aller Elemente in der Liste in einer <code>for</code>-Schleife.
   <li>Berechne die Summe aller Elemente in der Liste in einer <code>while</code>-Schleife.
   <li>Berechne die Summe aller Elemente mit geradem Index (also mit Index 0, 2,...) in der Liste.
</ol>

</div>
<template data-type="starter">
numbers = [68, 71, 53, 34, 66, 55, 80, 93, 24, 49, 68, 73, 9, 8, 93, 22, 44, 11, 82]
</template>
<template data-type="test">
assert "1003" in output_lines()
assert "587" in output_lines()
</template>
<template data-type="solution">
numbers = [68, 71, 53, 34, 66, 55, 80, 93, 24, 49, 68, 73, 9, 8, 93, 22, 44, 11, 82]

summe = 0
for elem in numbers:
    summe = summe + elem
print(summe)

summe2 = 0
i = 0
while i < len(numbers):
    summe2 = summe2 + numbers[i]
    i = i + 1
print(summe2)

summe3 = 0
i = 0
while i < len(numbers):
    summe3 = summe3 + numbers[i]
    i = i + 2
print(summe3)
</template>
</bottom-exercise>

=== Aufgabe H4 ===

<bottom-exercise id="h4">
<div slot="prompt">
Implementiere einige Funktionen, welche einem helfen sollen, Listen zu analysieren:
<ul>
   <li>Funktion <code>liste_anzahl(liste,x)</code>: Nimmt eine Liste <code>liste</code> und eine Zahl oder einen String <code>x</code> entgegen. Die Funktion bestimmt dann, wie oft das Element <code>x</code> in <code>liste</code> vorkommt und gibt diese Anzahl zurück.
   <li>Funktion <code>liste_max(liste)</code>: Bestimmt das grösste Element einer Liste und gibt dieses zurück.
   <li>Funktion <code>liste_min(liste)</code>: Ähnlich wie <code>liste_max(liste)</code>, gibt aber das kleinste Element zurück.
</ul>
<p>Für die Liste <code>numbers = [3,1,5,4,9,4,8,3,1,2,4,9]</code> und die Aufrufe 
<code>print(liste_anzahl(numbers, 3))</code>, <code>print(liste_max(numbers))</code> und <code>print(liste_min(numbers))</code>
ist der Output <code>2</code>, <code>9</code> und <code>1</code>.
</div>
<template data-type="starter">
numbers = [3,1,5,4,9,4,8,3,1,2,4,9]
</template>
<template data-type="test">
assert liste_anzahl([3,1,5,4,9,4,8,3,1,2,4,9], 3) == 2
assert liste_max([3,1,5,4,9,4,8,3,1,2,4,9]) == 9
assert liste_min(numbers) == 1
</template>
<template data-type="solution">
def liste_anzahl(liste, x):
    count = 0
    for elem in liste:
        if elem == x:
            count = count + 1
    return count

def liste_max(liste):
    maximum = liste[0]  # Achtung, funktioniert nicht für leere Listen!
    for elem in liste:
        if elem > maximum:
            maximum = elem
    return maximum

def liste_min(liste):
    minimum = liste[0]
    for elem in liste:
        if elem < minimum:
            minimum = elem
    return minimum

numbers = [3,1,5,4,9,4,8,3,1,2,4,9]
suche = 3
print(f'{suche} kommt {liste_anzahl(numbers, suche)} Mal in der Liste vor.')
print(f'{liste_max(numbers)} ist das Maximum der Liste.')
print(f'{liste_min(numbers)} ist das Minimum der Liste.')
</template>
</bottom-exercise>

=== Aufgabe H5 ===

<bottom-exercise id="h5">
<div slot="prompt">
Definiere eine Funktion <code>mittelwert(numbers)</code>, welcher eine Liste mit Zahlen übergeben wird. Von diesen Zahlen wird dann der Mittelwert berechnet und zurückgegeben. Übergibt man zum Beispiel eine Liste mit Schulnoten, so erhält man den Notendurchschnitt zurück. Zeige den Durchschnittswert dann in einem formatierten String an, z.B. "Der Mittelwert ist 4.46".
</div>
<template data-type="starter">
def mittelwert(numbers):
    """Gibt den Mittelwert von numbers zurück."""
    # TODO: Code hier
</template>
<template data-type="test">
assert mittelwert([3.8, 4.2, 5.7, 4.8]) == 4.625
assert mittelwert([4, 4, 4, 6]) == 4.5
</template>
<template data-type="solution">
def mittelwert(numbers):
    """Gibt den Mittelwert von numbers zurück."""
    summe = 0
    for elem in numbers:
        summe = summe + elem
    return summe / len(numbers)

print(f'Der Mittelwert ist {mittelwert([3.8, 4.2, 5.7, 4.8])}')
</template>
</bottom-exercise>

=== Aufgabe H6 (optional) ===


<bottom-exercise id="h6">
<div slot="prompt">
Programmiere eine Funktion <code>liste_haeufigste(liste)</code>: Gibt eine Liste zurück, die alle Elemente enthält, die am häufigsten vorkommen. Neben dieser Liste wird auch eine Zahl ausgegeben, die angibt, wie oft diese Elemente in der Liste vorkommen.
</div>
<template data-type="starter">
def liste_haeufigste(liste):
    """Gibt den häufigsten Wert der Liste zurück, und seine Häufigkeit."""
    # TODO: Code hier
</template>
<template data-type="test">
assert liste_haeufigste([3,1,5,4,9,4,8,3,1,2,4,9]) == ([4], 3)
assert set(liste_haeufigste([3,1,5,4,9,4,8,3,1,2,4,9,9])[0]) == {4, 9}
</template>
<template data-type="solution">
def liste_anzahl(liste, x):
    count = 0
    for elem in liste:
        if elem == x:
            count = count + 1
    return count

def liste_haeufigste(liste):
    max_anzahl = 0    # die Häufigkeit des bisherigen Siegers
    sieger = []       # die bisherigen Sieger
    for element in liste:
        anzahl = liste_anzahl(liste, element)
        if anzahl > max_anzahl:
            # Neuer Sieger
            max_anzahl = anzahl
            sieger = [element]
        elif anzahl == max_anzahl and element not in sieger:
            # Gleich häufig wie bisheriger Sieger
            sieger.append(element)
    return sieger, max_anzahl

numbers = [3,1,5,4,9,4,8,3,1,2,4,9]
print(liste_haeufigste(numbers))
</template>
</bottom-exercise>


===== For-Schleife =====
<nodisp 2>
++++TODO hof|
  * Einstieg mit direkter for-Schleife.
  * Einführung indirekte for-Schleife, z.B. `for index in [1, 6, 7]: print(liste[index])`
  * Erst dann Einführung von `range`.
++++
</nodisp>

==== Theorie ====

Wir haben bereits die *while*-Schleife kennengelernt, aber auch, dass wir die Elemente einer Liste mit `for` viel eleganter besuchen können. Die `for`-Schleife kann zusammen mit der `range` Funktion auch sonst äusserst praktisch sein. `range(n)` erzeugt eine Liste der Zahlen von $0$ bis $n-1$.


Man kann damit einen Codeblock mehrfach hintereinander ausführen lassen.
Zum Beispiel kann man mit dem folgenden Code ein Turtle ein Quadrat ablaufen lassen:

<code py>
repeat 4:
    fritz.forward(150)
    fritz.right(90)
</code>

Genau das Gleiche kann man auch mit einer *for*-Schleife erreichen:

<code python>
for i in range(4):
    fritz.forward(150)
    fritz.right(90)
</code>

Doch es gibt einen grossen Unterschied:
In der for-Schleife hat man eine Variable (hier `i`), die in jedem Durchlauf einen anderen Wert hat:
Im ersten Durchlauf den Wert 0, im nächsten 1, dann 2 und im letzten 3.

** Quiz:**

* Was ist der Output des folgenden Codeblocks?

<bottom-editor>
for i in range(4):
    print(i)
</bottom-editor>

* Was ist der Output des folgenden Codeblocks?

<bottom-editor>
for k in range(4):
    print(5 + k*10)
</bottom-editor>

**Beispiel:**

Mit einer for-Schleife können wir unsere Turtle jetzt interessantere Wege ablaufen lassen. Betrachte zum Beispiel folgenden Code:

<code python>
from turtle import *
fritz = Turtle()

for j in range(30):
    fritz.forward(j*10)
    fritz.left(90)
</code>

* Überlege dir zuerst, wie die Figur aussieht. Stelle eine Vermutung auf.
* Implementiere nun den Code (Selbst tippen, nicht copy-paste!) und überprüfe deine Vermutung. Hattest du recht?
* Modifiziere nun deinen Code so, dass der Abstand zwischen den Linien (a) enger oder (b) grösser wird.

<bottom-editor id="spiral" layout="canvas" showswitcher>

</bottom-editor>

=== Startwert ===

Statt immer bei null zu starten, kann der Startwert auch angegeben werden:
<bottom-editor>
for m in range(10,20):
    print(m)</bottom-editor>

Mit zwei Parametern interpretiert `range` den ersten als Start- und den zweiten als (exklusiven) Endwert.

=== Schrittweite ===
In den bisherigen for-Schleifen wurde der Parameter in jedem Durchlauf um 1 erhöht. Möchten wir, dass grössere Schritte gemacht werden, können wir _drei_ Parameter verwenden:
<bottom-editor>
for m in range(0,101,10):
    print(m)
</bottom-editor>

Der Parameter `m` hat im ersten Durchlauf den Wert `0`. In jedem weiteren Durchlauf wird er um `10` erhöht, solange er kleiner ist als der Endwert `101`. Ersetzen wir die Zahl `101` durch `110`, so ist das Resultat genau das gleiche. Erst mit `111` ist die grösste ausgegebene Zahl `110`.
#### Indirekte for-Schleife
`range()` ist zusammen mit `len()` äusserst praktisch, um alle gültigen Positionen (Indices) einer Liste aufzuzählen:

<bottom-editor>
numbers = [2, 5, 42, 17]

for index in range(len(numbers)):
    element = numbers[index]
    print(index, ":", element)
</bottom-editor>

==== Aufgaben I ====

*Tipp:* Für die Aufgaben kann es jeweils eine Weile dauern, bis der Turtle den Weg abgelaufen ist. Verwende die `hideturtle`-Funktion vor der for-Schleife, um gleich das Resultat anzuzeigen.

=== Aufgabe I1 ===

Du hast hoffentlich herausgefunden, wie man in einer quadratischen Spirale die Abstände zwischen den Linien kleiner und grösser machen kann. Zeichne nun in eine Figur zwei solche Spiralen ähnlich wie im Bild. Zeichne dazu mit einer for-Schleife die eine. Versetze dann die Position deiner Turtle mit `teleport` und zeichne die zweite Spirale mit einer neuen for-Schleife.

{{ :gf_informatik_1m_20_21:spiralen_duo.png?250 |}}

<bottom-exercise id="i1" layout="canvas" showswitcher>
<template data-type="starter">
from turtle import *
</template>
<template data-type="solution">
from turtle import *

t = Turtle()
t.speed(0)

t.teleport(-75, 50)
for side in range(32):
    t.forward(side * 4)
    t.left(90)

t.teleport(75, 50)
for side in range(64):
    t.forward(side * 2)
    t.left(90)
</template>
</bottom-exercise>
=== Aufgabe I2 ===

Verwende eine *for-Schleife* und die `circle`-Funktion um eine Spirale zu erzeugen, ähnlich wie diejenige im Bild. 

{{ :gf_informatik_1m_20_21:spirale.png?200 |}}

<bottom-exercise id="i2" layout="canvas" showswitcher>
<template data-type="starter">
from turtle import *
</template>
<template data-type="solution">
from turtle import *

t = Turtle()
t.speed(0)

for radius in range(16):
    t.circle(radius * 5, 180)
</template>
</bottom-exercise>
=== Aufgabe I3 (optional) ===

Zeichne folgende Figur:

{{ :gf_informatik_1m_20_21:spirale_rechteckig.png?250 |}}

<bottom-exercise id="i3" layout="canvas" showswitcher>
<template data-type="starter">
from turtle import *
</template>
<template data-type="solution">
from turtle import *

t = Turtle()
t.speed(0)

for side in range(28):
    t.forward(side * 8)
    t.left(90)
    t.forward(side * 4)
    t.left(90)
</template>
</bottom-exercise>
=== Aufgabe I4 ===

<bottom-exercise id="i4">
<div part="prompt">
Wandle in <code>while</code>-Schleife um:
<pre>
for i in range(4,12):
    print(i)
</pre>
</div>
<template data-type="solution">
i = 4
while i < 12:
    print(i)
    i = i + 1
</template>
</bottom-exercise>

=== Aufgabe I5 ===

<bottom-exercise id="i5">
<div part="prompt">
Wandle in möglichst kurze <code>for</code>-Schleife (max. 2 Zeilen) um:
<pre>
i = 10
while i < 29:
    print(i)
    i = i + 3
</pre>
</div>
<template data-type="solution">
for i in range(10, 29, 3):
    print(i)
</template>
</bottom-exercise>

=== Aufgabe I6 ===

<bottom-exercise id="i6">
<div part="prompt">
<p>Finde den Index (die Position) von <code>"Bebraham"</code> in der folgenden Liste. Nutze eine <code>for ... in range</code> Schleife, bei der die <code>range</code> über die Länge der Liste geht.

<pre>['Cebraham', 'Debraham', 'Bebraham', 'Abraham']</pre>

<p><b>Zusatzaufgabe:</b> Schreibe eine Funktion <code>suchen(l, query)</code> die in einer beliebigen Liste <code>l</code> nach dem Element <code>query</code> sucht und dessen Index zurückgibt!
</div>
<template data-type="starter">
names = ['Cebraham', 'Debraham', 'Bebraham', 'Abraham']
</template>
<template data-type="test">
assert "2" in output_lines()
assert suchen(['Cebraham', 'Debraham', 'Bebraham', 'Abraham'], 'Bebraham') == 2
assert suchen("Abrakadabra", "k") == 4
</template>
<template data-type="solution">
names = ['Cebraham', 'Debraham', 'Bebraham', 'Abraham']
for index in range(len(names)):
    if names[index] == 'Bebraham':
        print(index)

# Als Funktion:
def suchen(l, query):
    for index in range(len(l)):
        if l[index] == query:
            return index

print(suchen(names, "Bebraham"))
</template>
</bottom-exercise>


=== Aufgabe I7 ===
<bottom-exercise id="i7">
<div part="prompt">
<p><b>Teil 1</b>: Schreibe eine Funktion <code>reihensumme()</code>, die die Summe aller Zahlen der Siebnerreihe zurückgibt, also <code>7 + 14 + 21 + &hellip; + 63 + 70 = 385</code>.
<p>Verwende dazu eine <code>for zahl in range(...)</code> Schleife.
 
<p><b>Teil 2</b>: Ändere die Funktion so, dass der Teiler über ein Funktionsargument gewählt werden kann.
Der Aufruf <code>reihensumme(5)</code> soll beispielsweise die Summe der Fünferreihe von 5 bis 50 berechnen und 275 zurückgeben. 
Der Aufruf ohne Argument soll weiterhin die Siebnerreihe addieren.
</div>
<template data-type="starter">
def reihensumme():
    """Gibt die Summe der Siebnerreihe zurück."""
</template>
<template data-type="test">
assert reihensumme() == 385, "Teil 1: Reihensumme soll 385 zurückgeben"
assert reihensumme(5) == 275, "Teil 2: reihensumme(5) soll 275 zurückgeben"
</template>
<template data-type="solution">
def reihensumme(n=7):
    """Berechnet die Summe der n-er-Reihe."""
    summe = 0
    for zahl in range(n, 11*n, n):  # Das Ende-Argument von range ist exklusiv, also reicht 10*n nicht!
        summe = summe + zahl
    return summe

print(reihensumme())
print(reihensumme(5))
</template>
</bottom-exercise>


=== Aufgabe I8 ===
<bottom-exercise id="i8">
<div part="prompt">
<p>Schreibe eine Funktion <code>umdrehen(liste)</code>, die eine neue Liste erstellt und die Elemente von <code>liste</code> in umgekehrter Reihenfolge darin abspeichert und die umgekehrte Liste zurückgibt. Die eingebauten Funktionen <code>reverse</code> und <code>reversed</code> dürfen nicht benützt werden - verwende stattdessen eine negative Schrittweite für <code>range</code>.
</div>
<template data-type="starter">
def umdrehen(liste):
    """Gibt eine neue Liste mit den gleichen Elementen, aber in umgekehrter Reihenfolge zurück."""
</template>
<template data-type="test">
assert umdrehen(['Cebraham', 'Debraham', 'Bebraham', 'Abraham']) == ['Abraham', 'Bebraham', 'Debraham', 'Cebraham']
</template>
<template data-type="solution">
def umdrehen(liste):
    result = []
    # range erzeugt eine Zahlenfolge n, n-1, ... 3, 2, 1, 0:
    #       Beginne mit dem letzten Index (len(liste) - 1)
    #       Der letzte Index ist 0, das exklusive Ende damit -1
    #       Die Schrittweite ist -1 (wir zählen ja rückwärts)
    for index in range(len(liste) - 1, -1, -1):
        result.append(liste[index])
    return result

names = ['Cebraham', 'Debraham', 'Bebraham', 'Abraham']
print(umdrehen(names))</code>
</template>
</bottom-exercise>