Differences

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

--- lehrkraefte:blc:informatik:ffprg1-2020:funktionen [2020/02/22 11:01] – [Permutationen erzeugen] Ivo Blöchliger
+++ lehrkraefte:blc:informatik:ffprg1-2020:funktionen [2022/06/23 10:58] (current) – [Sudoku parsen] Ivo Blöchliger
@@ Line 1: / Line 1: @@
+====== Funktionen ======
+Der Zweck von Funktionen ist, kompliziertere Abläufe, die mehrmals im Programm gebraucht werden in eine Einheit zu verpacken.
+Damit kann ein Programm übersichtlicher gestaltet werden.
+Auch kann damit die Korrektheit jeder einzelnen Funktion leichter überprüft werden.
+===== Theorie =====
+Unterprogramme geben keine Werte zurück, z.B.
+<code python>
+def hello(wer):  # Definition des Unterprogramms, führt noch nichts aus!
+    print("Hallo "+wer+"!")
+# Erst hier, wird das Unterprogramm zweimal aufgerufen
+hello("Python")  # Gibt "Hallo Python!" aus (ohne Anführungszeichen)
+hello("C++")
+</code>
+Funktionen haben einen Rückgabewert, berechnen also etwas:
+<code python>
+def quadrieren(x):
+    return x*x
+print("%d hoch zwei ist %d" % (7, quadrieren(7)))
+</code>
+Beachten Sie, dass das "return" die Funktion sofort beendet.
+===== Sichtbarkeit der Variablen =====
+Alle Variablen in einer Funktion sind nur dort sichtbar und haben nichts mit Variablen zu tun, die auch ausserhalb der Funktion existieren. Alle Werte müssen als Parameter übergeben werden.
+<code python>
+# Direkt return a+b wäre natürlich effizienter und würde die Lesbarkeit erhöhen.
+def summe(a,b):
+    a=a+b
+    return a
+def produkt(a,b):
+    a = a*b
+    return a
+def kompliziert(a,b):
+   a = summe(a,b)
+   b = produkt(a,b)
+   return b-a
+a = 5
+b = 7
+c = kompliziert(a,b)
+# Die Werte von a,b sind nicht verändert worden!
+print("a=%d, b=%d, c=%d" % (a,b,c))
+</code>
+Hinweis: Es gibt die Möglichkeit, in Funktionen auf globale Variablen zuzugreifen. Das sollte aber nach Möglichkeit vermieden werden. Wenn so etwas nötig ist, sollte wohl eine Klasse programmiert werden.
+===== Beispiel: Buchstaben verwürfeln =====
+Sie knneen shcier die Tastache, dsas man Txet acuh gut lseen knan, wnen die Bucahtsben innreahlb der Woetrer vrecaustht wreden, voraesgeustzt, der esrte und ltezte Bcutshabe bielbt gliech. Zeil ist es, dieess Progrmam zu shbreicen und die eeiznlnen Aufagben in Fuotkinnen zu vaeprcken.
+Für diese Aufgabe sind folgende Dinge zu erledigen:
+  * Text in Wörter aufzuteilen
+    * Erkennen, welche Buchstaben zu einem Wort gehören und welche nicht.
+  * Ein Wort verwürfeln
+    * Zwei Buchstaben in einem Wort vertauschen
+  * Den neuen Text zusammensetzen.
+<hidden Lösungsvorschlag>
+<code python buchstabenvertauschen.py>
+import random
+def buchstabenTauschen(wort, i, j):
+    # Sicherstellen, dass i<j
+    if (i>j):
+        i,j = j,i
+    return wort[:i]+wort[j]+wort[(i+1):j]+wort[i]+wort[(j+1):]
+def buchstabenWuerfeln(wort):
+    if len(wort)<4:
+        return wort
+    i = random.randint(1,len(wort)-2)  # Zufällige Position von zweitem bis zweit-letztem Buchstaben
+    j = random.randint(1,len(wort)-3)  # Aus den n-3 verbleibenden Positionen eine auswählen
+    if (j==i):  # Zufällig die gleiche Position erwischt? Also j um eins erhöhen.
+        j+=1
+    return buchstabenTauschen(wort, i, j)
+def wortWuerfeln(wort):
+    wort = buchstabenWuerfeln(wort)
+    if (len(wort)>8):
+        wort = buchstabenWuerfeln(wort)
+    return wort
+def wortTeil(b):
+    return (b>='a' and b<='z') or (b>='A' and b<='Z')
+def textWuerfeln(text):
+    wort = ""
+    resultat = ""
+    p = 0
+    while (p<len(text)):
+        if wortTeil(text[p]):
+            wort += text[p]
+        else:
+            if len(wort)>0:
+                resultat += wortWuerfeln(wort)
+            resultat += text[p]
+            wort = ""
+        p+=1
+    if len(wort)>0:
+        resultat += wortWuerfeln(wort)
+    return resultat
+mytext = "Sie kennen sicher die Tatsache, dass man Text auch gut lesen kann, wenn die Buchstaben innerhalb der Woerter vertauscht werden, vorausgesetzt, der erste und letzte Buchstabe bleibt gleich. Ziel ist es, dieses Programm zu schreiben und die einzelnen Aufgaben in Funktionen zu verpacken."
+print(textWuerfeln(mytext))
+</code>
+</hidden>
+====== Aufgaben ======
+===== Summe über ein Array =====
+Programmieren Sie eine Funktion summe(a), die die Summe über die Elemente eines Arrays berechnet.
+Testen Sie mit dem Array, bestehend aus den Zahlen von 1 bis 100.
+<hidden Lösungsvorschlag>
+<code python summe.py>
+def summe(a):
+    s = 0
+    for element in a:
+        s+=element
+    return s
+a = list(range(1,11))
+print(a)
+print(summe(a))
+</code>
+</hidden>
+===== Tic-Tac-Toe schön ausgeben =====
+Hinweis: Diese Aufgabe gibt auch als [[lehrkraefte:blc:informatik:ffprg1-2020:funktionen-mit-klassen#tic_tac_toe|Aufgabe mit Klassen, inklusive Ausbaumöglichkeiten]].
+Ein Tic-Tac-Toe Feld kann mit einem 3x3-Array dargestellt werden. Wir verwenden 0,1,2 als Einträge (leer, Kreis, Kreuz).
+Hier ein Beispiel:
+<code python>
+feld = [[0,1,1], [2,1,2], [0,2,2]]
+</code>
+Wobei feld[2][0] die rechte obere Ecke sein soll. Die Unter-Arrays stellen Spalten dar!
+Schreiben Sie eine Funktion, die ein 3x3-Feld als Parameter bekommt, und einen String (inklusive Zeilenumbrüche "\n") als return-Wert generiert.
+Die Ausgabe soll (für obiges Array) wie folgt aussehen:
+<code txt>
+   | X |
+---+---+---
+ O | O | X
+---+---+---
+ O | X | X
+</code>
+Hinweis: Verwenden Sie ein Array, um die möglichen Symbole festzulegen. Der Eintrag im Spielfeld-Array liefert dann den Index vom Symbol.
+<hidden Lösungsvorschlag>
+<code python tictactoe.py>
+feld = [[0,1,1], [2,1,2], [0,2,2]]
+def ascii(f):
+    symbols = [" ", "O", "X"]
+    res = ""
+    for y in range(3):
+        for x in range(3):
+            res += " "+symbols[feld[x][y]]+" "
+            if (x<2):
+                res += "|"
+        res += "\n"
+        if (y<2):
+            res += "---+---+---\n"
+    return res
+print(ascii(feld))
+</code>
+</hidden>
+===== Sudoku parsen =====
+Hinweis: Diese Aufgabe gibt auch mit einer [[lehrkraefte:blc:informatik:ffprg1-2020:funktionen-mit-klassen#sudoku|Klasse und Ausbaumöglichkeiten]].
+Gegeben ist ein String, der ein Sudoku darstellt. Die Regeln sind wie folgt:
+  * Eine Ziffer von 1 bis 9 stellt ein gegebenes Feld dar.
+  * Eine Ziffer 0 oder ein . stellt ein leeres Feld dar.
+  * Alle anderen Zeichen werden komplett ignoriert, so dass 81 Zeichen übrigbleiben. Diese stellen die Einträge zeilenweise von links nach rechts dar.
+Ihre Aufgabe ist es daraus ein 9x9 - Array mit **Zahlen** (nicht Strings) von 0-9 zu erzeugen, wobei der Eintrag 0 für ein leeres Feld steht. Die Unter-Arrays stellen Spalten dar!
+Beispiel-Eingaben:
+<code python>
+sudoku1 = "003020600900305001001806400008102900700000008006708200002609500800203009005010300"
+sudoku2 = "200080300\n060070084\n030500209\n000105408\n\n000000000\n402706000\n301007040\n720040060\n004010003"
+sudoku3 = "......9.7\r\n...42.18.\r\n...7.5.26\r\n1..9.4...\r\n.5.....4.\r\n...5.7..9\r\n92.1.8...\r\n.34.59...\r\n5.7......"
+</code>
+Ausgaben:
+<code text>
+[[0, 9, 0, 0, 7, 0, 0, 8, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [3, 0, 1, 8, 0, 6, 2, 0, 5], [0, 3, 8, 1, 0, 7, 6, 2, 0], [2, 0, 0, 0, 0, 0, 0, 0, 1], [0, 5, 6, 2, 0, 8, 9, 3, 0], [6, 0, 4, 9, 0, 2, 5, 0, 3], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 8, 0, 0, 9, 0]]
+[[2, 0, 0, 0, 0, 4, 3, 7, 0], [0, 6, 3, 0, 0, 0, 0, 2, 0], [0, 0, 0, 0, 0, 2, 1, 0, 4], [0, 0, 5, 1, 0, 7, 0, 0, 0], [8, 7, 0, 0, 0, 0, 0, 4, 1], [0, 0, 0, 5, 0, 6, 7, 0, 0], [3, 0, 2, 4, 0, 0, 0, 0, 0], [0, 8, 0, 0, 0, 0, 4, 6, 0], [0, 4, 9, 8, 0, 0, 0, 0, 3]]
+[[0, 0, 0, 1, 0, 0, 9, 0, 5], [0, 0, 0, 0, 5, 0, 2, 3, 0], [0, 0, 0, 0, 0, 0, 0, 4, 7], [0, 4, 7, 9, 0, 5, 1, 0, 0], [0, 2, 0, 0, 0, 0, 0, 5, 0], [0, 0, 5, 4, 0, 7, 8, 9, 0], [9, 1, 0, 0, 0, 0, 0, 0, 0], [0, 8, 2, 0, 4, 0, 0, 0, 0], [7, 0, 6, 0, 0, 9, 0, 0, 0]]
+</code>
+<hidden Lösungsvorschlag>
+<code python sudokuparser.py>
+sudoku1 = "003020600900305001001806400008102900700000008006708200002609500800203009005010300"
+sudoku2 = "200080300\n060070084\n030500209\n000105408\n\n000000000\n402706000\n301007040\n720040060\n004010003"
+sudoku3 = "......9.7\r\n...42.18.\r\n...7.5.26\r\n1..9.4...\r\n.5.....4.\r\n...5.7..9\r\n92.1.8...\r\n.34.59...\r\n5.7......"
+def parse(s):
+    res = [[0 for y in range(9)] for x in range(9)]
+    x=0
+    y=0
+    for c in s:
+        if (c>="0" and c<="9") or (c=="."):
+            if c==".":
+                c="0"
+            res[x][y] = int(c)
+            x+=1
+            if (x==9):
+                x=0;
+                y+=1
+    return res
+print(parse(sudoku1))
+print(parse(sudoku2))
+print(parse(sudoku3))
+</code>
+</hidden>
+===== Sudoku schön ausgeben =====
+Gegeben ist ein 9x9-Array (siehe vorhergenden Aufgabe), wobei die Unter-Arrays Spalten sind. Die Eintäge sind 0 bis 9 (0 heisst leer). Schreiben Sie eine Funktion, die ein schönes Sudoku in ASCII-Art als String produziert:
+<code txt>
+#===========#===========#===========#
+#   |   | 3 #   | 2 |   # 6 |   |   #
+#---+---+---#---+---+---#---+---+---#
+# 9 |   |   # 3 |   | 5 #   |   | 1 #
+#---+---+---#---+---+---#---+---+---#
+#   |   | 1 # 8 |   | 6 # 4 |   |   #
+#===========#===========#===========#
+#   |   | 8 # 1 |   | 2 # 9 |   |   #
+#---+---+---#---+---+---#---+---+---#
+# 7 |   |   #   |   |   #   |   | 8 #
+#---+---+---#---+---+---#---+---+---#
+#   |   | 6 # 7 |   | 8 # 2 |   |   #
+#===========#===========#===========#
+#   |   | 2 # 6 |   | 9 # 5 |   |   #
+#---+---+---#---+---+---#---+---+---#
+# 8 |   |   # 2 |   | 3 #   |   | 9 #
+#---+---+---#---+---+---#---+---+---#
+#   |   | 5 #   | 1 |   # 3 |   |   #
+#===========#===========#===========#
+</code>
+<hidden Lösungsvorschlag>
+<code python asciisudoku.py>
+sudoku1 = "003020600900305001001806400008102900700000008006708200002609500800203009005010300"
+sudoku2 = "200080300\n060070084\n030500209\n000105408\n\n000000000\n402706000\n301007040\n720040060\n004010003"
+sudoku3 = "......9.7\r\n...42.18.\r\n...7.5.26\r\n1..9.4...\r\n.5.....4.\r\n...5.7..9\r\n92.1.8...\r\n.34.59...\r\n5.7......"
+def parse(s):
+    res = [[0 for y in range(9)] for x in range(9)]
+    x=0
+    y=0
+    for c in s:
+        if (c>="0" and c<="9") or (c=="."):
+            if c==".":
+                c="0"
+            res[x][y] = int(c)
+            x+=1
+            if (x==9):
+                x=0;
+                y+=1
+    return res
+def ascii(f):
+    hbar1 = ("#==="+"===="*2)*3+"#\n"
+    hbar2 = ("#---"+"+---"*2)*3+"#\n"
+    symbols = [str(i) for i in range(10)]
+    symbols[0] = " "
+    separators = ["|", "|", "#"]
+    res = hbar1
+    for y in range(9):
+        res += "#"
+        for x in range(9):
+            res += " "+symbols[f[x][y]]+" "+separators[x%3]
+        res+="\n"
+        if y%3==2:
+            res += hbar1
+        else:
+            res += hbar2
+    return res
+print(ascii(parse(sudoku1)))
+print(ascii(parse(sudoku2)))
+print(ascii(parse(sudoku3)))
+</code>
+</hidden>
+===== Challenge: Permutationen erzeugen =====
+Schreiben Sie eine Funktion permuationen(n), die alle Permutationen (Vertauschungen) der Zahlen 0 bis $n-1$ in einem Array generiert.
+Z.B. ist die Ausgabe von permutationen(4) folgende:
+<code txt>
+[[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], [0, 3, 2, 1], [1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0], [2, 0, 1, 3], [2, 0, 3, 1], [2, 1, 0, 3], [2, 1, 3, 0], [2, 3, 0, 1], [2, 3, 1, 0], [3, 0, 1, 2], [3, 0, 2, 1], [3, 1, 0, 2], [3, 1, 2, 0], [3, 2, 0, 1], [3, 2, 1, 0]]
+</code>
+<hidden Lösungsvorschläge>
+Element als erstes auswählen, dahinter alle möglichen Vertauschungen der restlichen Elemente anhängen.
+<code python permutationen.py>
+# Vertausche alle Element im Array a
+def vertausche(a):
+    if len(a)==1:
+        return [a]
+    res = []
+    for i in range(len(a)):
+        # Alle Vertauschungen ohne das Element i
+        temp = vertausche(a[:i]+a[(i+1):])
+        for p in temp:
+            # Das Element i vorne anfuegen
+            res.append([a[i]]+p)
+    return res
+def permutationen(n):
+    return vertausche(list(range(n)))
+print(permutationen(3))
+</code>
+Mit map und lambda-Funktionen:
+<code python permutationen_map_lambda.py>
+def permutationen(n):
+    if n==1:
+        return [[0]]
+    res = []
+    for first in range(n):
+        res += map(lambda x : [first]+map(lambda e: (e+1 if e>=first else e), x), permutationen(n-1))
+    return res
+print(permutationen(4))
+</code>
+Umwandlung des Index der lexikografischen Ordnung der Permutation:
+<code python permutation_number.py>
+def factorial(n):
+    r = 1
+    for i in range(2,n+1):
+        r*=i
+    return r
+# Berechnet die n-te Permutation vom Array a (nummeriert von 0 bis n!-1)
+def num2perm(num, a):
+    if len(a)==1:
+        return a
+    total = factorial(len(a)-1)
+    first = num//total  # Erste Stelle
+    rest = num % total  # Nummer der restlichen Permutation
+    return [a[first]] + num2perm(rest, a[:first]+a[(first+1):])
+def permutationen(n):
+    a = list(range(n))
+    return [num2perm(j,a) for j in range(factorial(n))]
+print(permutationen(4))
+</code>
+</hidden>