L'endroit où vous avez passé le $ n \ times n $ square une fois dans "How to count fluffy" Le problème du comptage des combinaisons d'itinéraires qui se déplacent du haut à gauche vers le bas à droite pour ne pas passer. J'ai créé le processus le plus basique de cette marche auto-évitée, c'est-à-dire le processus de comptage de toutes les combinaisons dans l'expression d'une sœur avec python.
Cependant, je viens de le créer, et comme vous pouvez le voir dans la vidéo, le nombre de combinaisons augmente à mesure que le nombre de carrés augmente, donc ce script n'est pas du tout pratique (Graphillion pour une utilisation décente. Utilisez (: //github.com/takemaru/graphillion/wiki) etc.).
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
La fonction saw (marche auto-évitée) reçoit le nombre de nœuds verticaux ou horizontaux (* nombre de carrés + 1 ) et les coordonnées du point de départ. Les coordonnées du point de départ sont données sous forme de " liste comprenant les points de coordonnées du point de départ *".
Le contenu de la fonction «scie» est
0 (n-1, n-1)) ", 1En conséquence, «saw» est récursé en ajoutant les coordonnées avec les dernières coordonnées décalées de un verticalement et horizontalement, et les valeurs numériques renvoyées sont totalisées. En d'autres termes, le nombre total d'itinéraires ayant atteint la destination et renvoyé «1» est calculé.
Recommended Posts