Rekursion

Cantor-Menge im Textmodus:

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))

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)    

Das folgende Programm findet alle magischen 3×3-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?

# 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)