Differences

This shows you the differences between two versions of the page.

--- lehrkraefte:blc:informatik:ffprg1-2018:ffprg1-2018 [2018/06/12 12:42] – [Dienstag 5. 6. 2018] Ivo Blöchliger
+++ lehrkraefte:blc:informatik:ffprg1-2018:ffprg1-2018 [2018/06/26 15:51] (current) – Ivo Blöchliger
@@ Line 1: / Line 1: @@
+====== Freifach Einführung ins Programmieren ======
+Direkt-Link: **https://fginfo.ksbg.ch/ffprog**
+  * Jeweils Dienstags, 16:25 - 17:58 im H21.
+  * Nach Möglichkeit soll ein eigener Laptop mitgebracht werden.
+  * Wir programmieren mit TigerJython.
+===== Programmier-Projekt =====
+Wer programmiert die schlauste Schlange? {{ :lehrkraefte:blc:informatik:ffprg1-2018:screenshot.png|}}
+Version 0.1 (vom 8.3.2017): {{ :lehrkraefte:blc:informatik:ffprg1-2018:tjsnake.zip |}}. Tester sind willkommen.
+=== Anleitung ===
+  * Archiv entpacken (wirklich entpacken, nur weil Windows die Dateien im Archiv anzeigt, sind diese deswegen noch nicht entpackt).
+  * game.py in Tigerjython starten.
+  * Für eigene Strategie ivo_beispiel_strategy.py kopieren und wie folgt benennen: name_xyz_strategie.py, nur Kleinbuchstaben a-z und _ (underscore). Die Datei muss mit dem eigenen Namen beginnen und mit strategie.py aufhören.
+  * In game.py:
+    * Die eigene Strategie importen (ganz oben im Code)
+    * Eigene Strategie ganz unten in game.py eintragen.
+  * Code studieren, Fragen stellen.
+=== Dokumentation ===
+Entweder direkt Kommentare im Code oder [[https://fginfo.ksbg.ch/~ivo/tjsnake/annotated.html|online]].
+===== TigerJython =====
+  * Lehrgang: http://www.tigerjython.ch
+  * Download der Programmierumgebung: [[http://www.tigerjython.ch/index.php?inhalt_links=navigation.inc.php&inhalt_mitte=lernumgebung/einrichtung.inc.php|online]] oder [[https://fginfo.ksbg.ch/~ivo/ti1gerjython/|schulintern]].
+===== Programm =====
+==== Dienstag 19. 6. 2018 ====
+=== Vorschlag 1 ===
+Einblick in die "dynamische Programmierung", was nichts direkt mit Computer-Programmierung, sondern mit einer Lösungstrategie für rekursive Probleme zu tun hat.
+Problem: Bestimme die durchschnittliche Anzahl Versuche beim Zahlenratespiel, a) bei gegebener Strategie, b) bei gleichzeitiger Bestimmung der optimalen Strategie.
+=== Vorschlag 2 ===
+TicTacToe:
+  * Gegeben ein 3x3-Array mit Einträgen 0, 1 oder 2 (leer, x, o).
+<code python tictactoe.py>
+from gpanel import *
+# leeres Feld
+dim = 10 # Anzahl Felder
+winlen = 5 # Anzahl fuer Gewinn
+feld = [[0 for y in range(dim)] for x in range(dim)]
+player = 1
+filled = 0
+winner = 0
+# Startpunkt x,y
+# Vektor vx,vy
+def testLine(x,y,vx,vy,feld):
+    global winlen,dim
+    what = feld[x][y]
+    count = 1 if what>0 else 0
+    while True:
+        x+=vx
+        y+=vy
+        if x<0 or y<0 or x>=dim or y>=dim:
+            break
+        if feld[x][y]==what:
+            count+=1
+        else:
+            what = feld[x][y]
+            count=1 if what>0 else 0
+        if feld[x][y]==0:
+            count = 0
+        if count==winlen:
+            return what
+    return 0
+def win(feld):
+    for x in range(dim):
+        combos = [[x,0,0,1],\
+                    [0,x,1,0],\
+                    [0,x,1,1],\
+                    [x,0,1,1],\
+                    [x,dim-1,1,-1],\
+                    [0,x,1,-1]]
+        for combo in combos:
+            winner = testLine(combo[0], combo[1],
+                          combo[2], combo[3],feld)
+            if winner>0:
+                return winner
+    return 0
+def ausgabe(feld):
+    clear()  # Fenster loeschen
+    dim = len(feld)
+    for i in range(1,dim): # Raster
+        line(0,i,dim,i)
+        line(i,0,i,dim)
+    for x in range(dim):
+        for y in range(dim):
+            if (feld[x][y]==1):
+                line(x+0.1, y+0.1, x+0.9,y+0.9)
+                line(x+0.1, y+0.9, x+0.9,y+0.1)
+            elif (feld[x][y]==2):
+                move(x+0.5, y+0.5)
+                circle(0.4)
+def onMousePressed(x, y):
+    global feld
+    global player
+    global filled
+    global winner
+    global dim
+    x = int(x)
+    y = int(y)
+    if winner>0 or filled == dim*dim:
+        feld = [[0 for y in range(dim)] for x in range(dim)]
+        player = 1
+        filled = 0
+        winner = 0
+    elif feld[x][y]==0:
+        filled+=1
+        feld[x][y] = player
+        player = 3-player
+    ausgabe(feld)
+    winner = win(feld)
+    if (winner>0):
+        print("Spieler %d hat gewonnen!" % winner)
+    elif (filled == dim*dim):
+        print("Unentschieden...")
+makeGPanel(0,dim-0.001, 0,dim-0.001,mousePressed = onMousePressed)
+lineWidth(5)
+ausgabe(feld)
+</code>
+  * Gegeben ein 3x3-Array wie oben. Stellen Sie fest, ob schon jemand gewonnen hat.
+  * Programmieren Sie ein Spiel für 2 menschliche Spieler, die abwechslungsweise die Koordinaten eingeben. Die Eingabe soll überprüft werden.
+  * Programmieren Sie ein Strategie, die gegen einen menschlichen Spieler spielt.
+==== Dienstag 12. 6. 2018 ====
+Zahlenraten:
+Eingabe einer Zahl: ([[http://www.tigerjython.ch/index.php?inhalt_links=navigation.inc.php&inhalt_mitte=turtle/turtledoc.html|siehe auch]](
+<code python>
+  zahl = inputInt("Bitte eine Zahl")
+</code>
+Generierung einer Zufallszahl:
+<code python>
+from random import randint
+zufall = randint(0,100) # Zahlen von 0 bis und **mit** 100
+</code>
+<hidden Lösungsvorschlag>
+<code python zahlenraten.rb>
+from random import randint
+debug = True
+mini = 0
+maxi = 100
+zahl = randint(mini, maxi)
+if debug:
+    print(zahl)
+versuche = 1
+while True:
+    msg = "Anzahl Versuche %d\nBereich: %d bis %d" % (versuche, mini, maxi)
+    tip = inputInt(msg)
+    if zahl < tip:
+        maxi = tip
+    elif zahl > tip:
+        mini = tip
+    else:
+        msgDlg("Super! %d Versuche" % (versuche))
+        break
+    versuche+=1
+</code>
+==== Snake ====
+Implementation Bestimmung des kürzesten Wegs. Statische Variante.
+Vorgehen:
+  * Doppeltes Array mit -1 initialisieren für Distanzen (für jedes feld[x][y]). -1 heisst dann unerreichbares Feld
+  * Todo-Liste: Array mit Koordinatenpaaren.
+  * Apfel-Feld mit 0 initialisieren, Apfel-Koordinaten in Todo-Liste speichern:
+  * Solange Todo-Liste nicht leer ist:
+    * Koordinatenpaar vorne von Todo-Liste entfernen -> p.
+    * Nachbarn von p "abklappern", nötigenfalls Distanzen eintragen, nötigenfalls Nachbar hinten an TODO-Liste anhängen.
+Richtungsauswahl:
+  * Wenn ein Nachbarfeld vom Schlangenkopf mit Distanz >= 0 existiert, zum Feld mit kleinstmöglicher Distanz gehen.
+  * Sonst sich eine Überlebensstrategie ausdenken.
+Variante: Vom Schlangenkopf aus die Distanzen bestimmen. Der kürzeste Weg zum Apfel muss dann allerdings von dort rückwärts gesucht werden. Dafür können dann Felder miteinbezogen werden, die wieder verschwinden.
+==== Dienstag 5. 6. 2018 ====
+Ausfall der Stunden
+==== Dienstag 29. 5. 2018 ====
+Ziele:
+  * Strategie mit Skalarprodukt von der letzten Stunde verstehen.
+  * Zusatzfunktion erstellen, die die Möglichkeit einer Kopf-an-Kopf-Kollision erkennt und diese Richtung(en) vermeidet.
+  * Weitere Verbesserungen, wie z.B. kürzeste Wege zum Apfel berechnen.
+<code python>
+    def kopfankopfok(self, a,b):
+        x,y = self.params.x, self.params.y
+        for schlange in self.params.heads:
+            # schlange ist hier ein Array mit 2 Einträgen
+            if abs(x-schlange[0])+abs(y-schlange[1])>0: # nicht eigene
+                if abs(a-schlange[0])+abs(b-schlange[1])==1: #dist 1
+                    return False  # Achtung Gefahr
+        return True # Keine Gefahr
+</code>
+==== Dienstag 22. 5. 2018 ====
+Ziel: Beispielstrategie für Snake kopieren und verbessern, dass die Äpfel direkt gefressen werden, zumindest, wenn sich der Schlangenkopf auf der gleichen $x$ oder $y$-Koordinate wie der Apfel befindet.
+Variante: Sei $P$ die Position der Schlange, $A$ die position des Kopfs und $\vec{v}_0$ bis $\vec{v}_3$ die 4 Richtungsvektoren. Das Skalarprodukt zwischen dem Vektor $\vec{PA}$ und einem Richtungsvektor ist dann positiv, wenn sich die Schlange so dem Apfel nähert.
+Es gilt $\vec{u} \cdot \vec{v} = |\vec{u}| \cdot |\vec{v}| \cdot \cos(\alpha)$ mit $\alpha = \angle(\vec{u}, \vec{v})$ aber auch $\vec{u} \cdot \vec{v} = u_x \cdot v_x + u_y\cdot v_y$. Das lässt sich auch auf 3 und mehr Dimensionen verallgemeinern.
+<code python>
+        # Aktuelle Position ermitteln
+        x,y = self.params.x, self.params.y
+        # print("(x,y)=(%d,%d)  d=%d" % (x,y,d))
+        # Koordinaten vom Apfel
+        apfx = self.params.apple[0]
+        apfy = self.params.apple[1]
+        # Richtungsvektoren durchlaufen
+        for i in range(4):
+            # Prüfen, ob nicht Gegenrichtung von d, egal, ist eh besetzt
+            # Komponenten vom Richtungsvektor
+            vx = Board.VECS[i][0]
+            vy = Board.VECS[i][1]
+            # Skalarprodukt berechnen, wenn positiv und moeglich, dann machen.
+            s = vx*(apfx-x)+vy*(apfy-y)
+            # Neue Position
+            a,b = Board.move(x,y,i)
+            if s>0 and (self.params.feld[a][b]==Board.EMPTY or self.params.feld[a][b]==Board.APPLE):
+                return i
+</code>
+==== Dienstag 8. 5. 2018 ====
+Als Vorbereitung auf das Snake-Spiel: Wegfindung in einem Labyrinth:
+<code python wegfinden.py>
+from gpanel import *
+import random
+import time
+width = 40
+vecs = [[1,0],[0,1],[-1,0],[0,-1]]
+makeGPanel(0, width, 0, width)
+# Array mit Distanzen fuer alle Punkte, gefuellt mit -1
+dist = [[-1 for y in range(width)] for x in range(width)]
+for i in range(800):
+    x=random.randint(1,width-1)
+    y=random.randint(1,width-1)
+    fillRectangle(x,y,x+1,y+1)
+todo=[(0,0)]
+dist[0][0] = 0
+waitTime = 0.002
+maxDist = 0
+setColor("red")
+while len(todo)>0:
+    #waitTime*=0.99
+    #print(todo)
+    pt = todo.pop(0) #vorne entfernen
+    aktuelle_d = dist[pt[0]][pt[1]]
+    if aktuelle_d>maxDist:
+        maxDist = aktuelle_d
+    setColor("blue")
+    move(pt[0]+0.5, pt[1]+0.5)
+    fillRectangle(0.5,0.5)
+    time.sleep(waitTime)
+    for d in range(4):
+        p = (pt[0]+vecs[d][0], pt[1]+vecs[d][1])
+        if (p[0]>=0 and p[0]<width and p[1]>=0 and p[1]<width):
+            #print(p, getPixelColor(p[0]+0.5, p[1]+0.5))
+            if getPixelColor(p[0]+0.5, p[1]+0.5)==makeColor("white"):
+                setColor("red")
+                move(p[0]+0.5, p[1]+0.5)
+                fillRectangle(0.5,0.5)
+                todo.append(p)  # Hinten anfuegen
+                dist[p[0]][p[1]] = aktuelle_d + 1
+                time.sleep(waitTime)
+print(maxDist)
+for x in range(width):
+    for y in range(width):
+        move(x+0.5,y+0.5)
+        if dist[x][y]>=0:
+            setColor(dist[x][y]/maxDist*255,255-dist[x][y]/maxDist*255,0)
+            fillRectangle(0.5,0.5)
+        else:
+            setColor("black")
+            fillRectangle(1,1)
+</code>
+==== Dienstag 8. 5. 2018 ====
+Primzahlen auf eine Spirale darstellen.
+Die Spirale soll "quadratisch" aussehen, d.h. man bewegt sich nur in die Achsenrichtungen um ganze Pixel (Bildpunkte) fort.
+Man startet in der Mitte und geht dann reihum und zählt die Schritte (in Pixeln). Immer wenn die Schrittnummer prim ist, wird der entsprechende Pixel markiert.
+{{:lehrkraefte:blc:informatik:ffprg1-2018:spirale.png|}} {{:lehrkraefte:blc:informatik:ffprg1-2018:spirale-mit.png|}}
+=== Implementation ===
+Die vier Richtungsvektoren werden in ein zweidimensionales Array gespeichert (Arrays sollten im Plural bezeichnet werden):
+<code python>
+vecs=[[1,0],[0,1],[-1,0],[0,-1]];  # Vier Richtungen, im trigonometrischen Umlaufsinn
+</code>
+Die aktuelle Richtung wird als Zahl zwischen 0 und 3 dargestellt. Eine Drehung um 90 Grad heisst also 1 addieren oder subtrahieren und nötigenfalls wieder auf den Bereicht 0 bis 3 anpassen. Dafür eignet sich die Modulo-Operation:
+<code python>
+dir = 0
+#
+#...
+#
+dir = (dir+1)%4  # Drehung um +90 Grad
+dir = (dir+3)%4  # Drehung im -90 Grad
+dir = (dir+2)%4  # Drehung um 180 Grad
+</code>
+Die aktuelle Position wird mit zwei Variablen gespeichert. Die Position kann dann in eine Richtung verschoben werden:
+<code python>
+x = 10
+y = 32
+# Verschiebung in Richtung dir (Zahl von 0 bis 3)
+x = x+vecs[dir][0]
+y = y+vecs[dir][1]
+</code>
+<hidden Lösungsvorschlag>
+<code python spirale.py>
+from gpanel import *
+x = 100
+y = 100
+dir = 0
+zahl = 1
+vecs = [[1,0],[0,1],[-1,0],[0,-1]]
+makeGPanel(0, 200, 0, 200)
+def isPrime(z):
+    for i in range(2,int(z**0.5)+1):
+        if z%i==0:
+            return False
+    return True
+for l in range(1,200):
+    for i in range(2):
+        for s in range(l):
+            if isPrime(zahl):
+                point(x,y)
+            x+=vecs[dir][0]
+            y+=vecs[dir][1]
+            zahl+=1
+        dir=(dir+1)%4
+</code>
+</hidden>
+=== Und mehr ===
+Implementieren Sie z.B. so was: http://www.naturalnumbers.org/sparticle.html
+==== Dienstag 24. 4. 2018 ====
+Sieb des Eratosthenes.
+Idee: Erst wird jede 2. Zahl weggestrichen (ausser die 2), dann jede dritte, jede fünfte, jede siebte, etc. Übrig bleiben die Primzahlen.
+Implementation: Array, bzw. Liste von n Wahrheitswerten (True oder False):
+<code python eratosthenes.py>
+import time
+start = time.time()
+n = 10000
+prim = [i>1 for i in range(n+1)]
+zwischen = time.time()-start
+p = 2
+while p*p<=n:
+    # Vielfache von p wegstreichen:
+    x = p*p
+    while (x<=n):
+        prim[x]=False
+        x+=p  # Kurzform fuer i=i+p
+    # Naechste Primzahl bestimmen
+    p+=1
+    while prim[p]==False:  # Schoener: while not prim[p]
+        p+=1
+berechnung = time.time()-start - zwischen
+# Ausgabe:
+for i in range(n+1):
+    if prim[i]:
+        print(i)
+print("Initialisierung ",zwischen)
+print("Berechnung ",berechnung)
+print("Total ", time.time()-start)</code>
+Mehr zu Listen und Arrays: [[http://www.tigerjython.ch/index.php?inhalt_links=navigation.inc.php&inhalt_mitte=grafik/listen.inc.php]]
+==== Dienstag 3. 4. 2018 ====
+Primzahlen auflisten:
+<code python>
+import math
+import time
+start = time.time()
+for i in range(2,500):
+    prime = True
+    for t in range(2,int(math.sqrt(i))+1):
+        if i % t==0:
+            prime = False
+            break
+    if prime:
+        print i,
+    if i%50==0:
+        print
+print
+print(time.time()-start)
+</code>
+Optimierung: Ersetzen Sie range durch xrange. Hintergrund: range erzeugt ein ganzes Array (Feld) von entsprechend vielen Werten im Speicher. xrange ist ein Iterator und erzeugt ein Wert nach dem anderen (konstanter, kleiner Speicherbedarf). Python 3 hat kein xrange, dort funktioniert range wie xrange.
+==== Dienstag 27. 3. 2018 ====
+**Lernziele:**
+  * [[http://www.tigerjython.ch/index.php?inhalt_links=navigation.inc.php&inhalt_mitte=grafik/koordinaten.inc.php|Einführung $xy$-Grafik]]
+  * [[http://www.tigerjython.ch/index.php?inhalt_links=navigation.inc.php&inhalt_mitte=grafik/forInRange.inc.php|For-Schleifen]]
+=== Mögliche Zusatzaufgaben ===
+  * Zeichnen Sie $n$ Kreise, die alle durch einen gegebenen Punkt gehen und deren Zentren gleichmässig auf einem gegebenen Kreis verteilt sind. Die Hüllkurve, die man erhält ist eine der Kardioide verwandte Form (bzw. genau jene, wenn der gegebene Punkt auf dem gegebenen Kreis liegt).
+  * Schreiben Sie ein Programm, das nacheinander Primzahlen ausgibt. Hinweis: ''a % b'' berechnet der Rest der Division von ''a'' durch ''b'' und wird **a modulo b** gelesen. Beispiele: 18 % 5 ergibt 3, 49 % 7 ergibt 0.
+==== Dienstag 5. 3. 2018 ====
+  * Freifach freiwillig bereits ab 15:35 (um den ersten Dienstag nachzuholen). Das Zimmer wird offen sein, ich werde aber wohl noch ca. 30 min für eine Sitzung weg sein...
+**Lektionsziele**
+  * [[http://www.tigerjython.ch/index.php?inhalt_links=navigation.inc.php&inhalt_mitte=turtle/selektion.inc.php|Selektion (Verzweigungen)]]
+  * [[http://www.tigerjython.ch/index.php?inhalt_links=navigation.inc.php&inhalt_mitte=turtle/schleifen.inc.php|While-Schleifen]]
+==== Dienstag 27. 2. 2018 ====
+  * Freifach freiwillig bereits ab 15:35 (um den ersten Dienstag nachzuholen).
+**Lektionsziele** (mit "obligatorischen" Aufgaben, die aber auch sinngemäss abgwandelt werden können):
+  * {{http://www.tigerjython.ch/index.php?inhalt_links=navigation.inc.php&inhalt_mitte=turtle/wiederholung.inc.php|Wiederholung}} (A4)
+  * {{http://www.tigerjython.ch/index.php?inhalt_links=navigation.inc.php&inhalt_mitte=turtle/funktionen.inc.php|Funktionen}} (A2 oder A3)
+  * {{http://www.tigerjython.ch/index.php?inhalt_links=navigation.inc.php&inhalt_mitte=turtle/parameter.inc.php|Parameter}} (A2)
+  * {{http://www.tigerjython.ch/index.php?inhalt_links=navigation.inc.php&inhalt_mitte=turtle/variablen.inc.php|Variablen}} (A4).
+=== Dateien mit Funktionen einbinden ===
+<code python importtest.py>
+def hello():
+    print("Hello world")
+if __name__=="__main__":
+    print("Nur wenn diese Datei ausgefuehrt wird")
+</code>
+<code python othertest.py>
+import importtest
+importtest.hello()
+</code>
+<code python yetanother.py>
+import hello from importtest
+hello()
+</code>