Die Stelle, an der Sie das Quadrat $ n \ times n $ einmal in ["Wie man flauschig zählt"] passiert haben (http://www.miraikan.jst.go.jp/sp/medialab/11.html) Das Problem, die Kombinationen von Routen zu zählen, die sich von links oben nach rechts unten bewegen, um nicht durchzugehen. Ich habe den grundlegendsten Prozess dieses selbstvermeidenden Spaziergangs erstellt, dh den Prozess des Zählens aller Kombinationen im Ausdruck einer Schwester mit Python.
Ich habe es jedoch gerade erstellt, und wie Sie im Video sehen können, nimmt die Anzahl der Kombinationen mit zunehmender Anzahl der Quadrate zu, sodass dieses Skript für eine angemessene Verwendung überhaupt nicht praktikabel ist (Graphillion). Verwenden Sie //github.com/takemaru/graphillion/wiki) usw.).
def saw(n, path):
if -1 in path[-1] \
or n in path[-1] \
or path[-1] in path[:-2] : return 0
if path[-1]==(n-1,n-1) : return 1
return saw(n,path+[(path[-1][0]+1, path[-1][1]+0)]) \
+ saw(n,path+[(path[-1][0]-1, path[-1][1]+0)]) \
+ saw(n,path+[(path[-1][0]+0, path[-1][1]+1)]) \
+ saw(n,path+[(path[-1][0]+0, path[-1][1]-1)])
n = 5
print(saw(n,[(0,0)]))
8512
Die Funktion "Säge" (selbstvermeidendes Gehen) erhält die Anzahl der vertikalen oder horizontalen Knoten (* Anzahl der Quadrate + 1 ) und die Koordinaten des Startpunkts. Die Startpunktkoordinaten werden in Form einer " Liste einschließlich Tapples von Startpunktkoordinaten *" angegeben.
Der Inhalt der Sägefunktion ist
Infolgedessen wird "saw" rekursiv wiedergegeben, während die Koordinaten mit den letzten um eins vertikal und horizontal verschobenen Koordinaten addiert werden, und die zurückgegebenen numerischen Werte werden summiert. Mit anderen Worten wird die Gesamtzahl der Routen berechnet, die das Ziel erreicht und "1" zurückgegeben haben.
Recommended Posts