Differences

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

--- lehrkraefte:snr:informatik:python:rekursion [2021/11/17 13:06] – [Rekursion] Olaf Schnürer
+++ lehrkraefte:snr:informatik:python:rekursion [2021/12/03 13:59] (current) – [Link zur Kursseite] Olaf Schnürer
@@ Line 1: / Line 1: @@
+====== Rekursion ======
+to be written
+  * Fakultät rekursiv (schon bei Funktionen)
+  * divide et impera / divide and conquer / teile und herrsche
+[[https://de.wikipedia.org/wiki/Rekursion#Rekursive_Grafiken|Wikipedia Rekursion]]
+Sierpinski rekursiv ist schon gut, eventuell turtle Grafik, Bilder von Wikipedia?
+Hanoi?
+<WRAP round todo>
+[[https://de.wikipedia.org/wiki/Cantor-Menge|Cantor-Menge]] im Textmodus:
+<code python>
+def cantor(x):
+    if x == 0:
+        return "*"
+    else:
+        s = cantor(x - 1)
+        return s + (3**(x-1)) * "-" + s
+for i in range(5):
+    print(cantor(i))
+</code>
+</WRAP>
+<WRAP round todo>
+<code python>
+from gpanel import *
+def zeichne(x, y, l, xr, yr, rekursionstiefe):
+    if rekursionstiefe == 0:
+        line(x, y, x + l * xr, y + l * yr)
+    else:
+        xl = -yr
+        yl = xr
+        zeichne(x, y, l/3, xr, yr, rekursionstiefe - 1)
+        zeichne(x + 2*l/3 * xr, y + 2*l/3 * yr, l/3, xr, yr, rekursionstiefe - 1)
+        zeichne(x + l/3 * xr, y + l/3 * yr, l/3, xl, yl, rekursionstiefe - 1)
+        zeichne(x + l/3 * (xr + xl), y + l/3 * (yr + yl), l/3, xr, yr, rekursionstiefe - 1)
+        zeichne(x + l/3 * (2 * xr + xl), y + l/3 * (2 * yr + yl), l/3, -xl, -yl, rekursionstiefe - 1)
+makeGPanel(Size(1000, 1000))
+window(-10, 1010, -10, 1010)
+title("Key 'Esc': escape")
+zeichne (0,0, 1000, 1, 0, 6)
+</code>
+</WRAP>
+<WRAP round todo>
+Das folgende Programm findet alle magischen 3x3-Quadrate durch stupides Ausprobieren.
+Die am Ende ausgegebene Zahl ist die Fakultät welcher Zahl?
+Wenn man die Variable n auf den Wert 4 endet, braucht das Programm sehr lange - grob überschlagen auf meinem Rechner 3 Jahre!
+Wer kann das Programm verbessern?
+<code python>
+# Erzeuge magisches Quadrat
+import time
+n = 3
+def magisch():
+    for x in range(0,n):
+        zeilensumme = 0
+        spaltensumme = 0
+        for y in range(0,n):
+            spaltensumme = spaltensumme + a[x][y]
+            zeilensumme = zeilensumme + a[y][x]
+        if zeilensumme != summe or spaltensumme != summe:
+            return False
+    erste_diagonalsumme = 0
+    zweite_diagonalsumme = 0
+    for x in range(0,n):
+        erste_diagonalsumme = erste_diagonalsumme + a[x][x]
+        zweite_diagonalsumme = zweite_diagonalsumme + a[x][n - 1 - x]
+    if erste_diagonalsumme != summe or zweite_diagonalsumme != summe:
+        return False
+    return True
+def trage_ein(e):
+    global anzahl
+    for x in range(0, n):
+        for y in range(0, n):
+            if a[x][y] == 0:
+                a[x][y] = e
+                if e > 1:
+                    trage_ein(e - 1)
+                else:
+                    anzahl = anzahl + 1
+                    if anzahl % 100000 == 0:
+                        print(anzahl)
+                        print(time.clock() - startzeit)
+                    if magisch():
+                        print(a)
+                a[x][y] = 0
+a = [[0 for y in range(0,n)] for x in range(0,n)]
+anzahl = 0
+summe = n * (n * n + 1) // 2
+startzeit = time.clock()
+trage_ein(n * n)
+print(anzahl)
+print(time.clock() - startzeit)
+</code>
+</WRAP>
+===== Link zur Kursseite =====
+[[lehrkraefte:snr:informatik:glf21|Zur Kursseite]]