[PYTHON] Défiez la tour de Hanoi avec recurs + stack
Bonsoir à tous (* ^ - ^ *)
L'autre jour, j'ai étudié la récidive dans l'article "Défier la tour de Hanoi avec récurrence". https://qiita.com/AKpirion/items/c0f7905c6227e086644e
- N'est-il pas possible de créer des hyperliens? ??
Donc, j'ai immédiatement écrit la description suivante que @shiracamus m'a racontée. Considérez si cela peut être réalisé en ajoutant une pile.
hanoi_reference.py
def move(n, a, b, c):
"""Déplacer n disques de a vers b comme abri temporaire vers c"""
if n > 1:
move(n - 1, a, c, b) #Enregistrer dans b avec c comme abri temporaire, sauf pour le bas d'un
print(f" {n}Aucun disque{a}De{c}Déménager à") #Déplacer le bas de a à c
if n > 1:
move(n - 1, b, a, c) #Déplacer vers c avec a comme abri temporaire, sauf pour le fond qui a été enregistré dans b
def hanoi(n):
print(f"{n}Étapes pour déplacer un disque de A à C")
move(n, 'A', 'B', 'C')
if __name__ == '__main__':
hanoi(2)
hanoi(3)
Cette fois, nous allons déplacer les deux disques comme dans l'article précédent.
La description récursive revient toujours à l'impression (f "déplacer le disque # {n} de {a} vers {c}").
Si tel est le cas, chaque valeur de {a} et {c} est classée par l'instruction if.
Je pensais que si vous mélangez push et pop, vous pouvez réaliser la tour de Hanoi avec un stack.
Tout d'abord, j'ai préparé des piles dédiées aux positions A, B et C, respectivement.
hanoi_r1.py
class top:
def __init__(self,capacity:int = 2):
self.Astr = [2,1]
self.Bstr = [None] * capacity
self.Cstr = [None] * capacity
self.capa = capacity
self.Aptr = 0
self.Bptr = 0
self.Cptr = 0
Je ne pense pas qu'un supplément soit nécessaire. Ensuite, il y a push, mais fondamentalement, il ne devient jamais plein, donc La description peut être simple.
hanoi_r1.py
def Apush(self,value):
self.Astr[self.Aptr] = value
self.Aptr += 1
def Bpush(self,value):
self.Bstr[self.Bptr] = value
self.Bptr += 1
def Cpush(self,value):
self.Cstr[self.Cptr] = value
self.Cptr += 1
Puisque la pop n'a pas à s'inquiéter du vide La description est simple.
hanoi_r1.py
def Apop(self):
self.Aptr -= 1
return self.Astr[self.Aptr]
def Bpop(self):
self.Bptr -= 1
return self.Bstr[self.Bptr]
def Cpop(self):
self.Cptr -= 1
return self.Cstr[self.Cptr]
Pas de problème, non? Le reste, c'est bouger.
hanoi_r1.py
def move(self,n,a,b,c):
if n>1:
top.move(self,n-1,a,c,b)
print(f"{n}À{a}De{c}Quoi")
if a == "A" and c == "B":
top.Bpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "A" and c == "C":
top.Cpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "B" and c == "C":
top.Cpush(self,top.Bpop(self))
top.Bpush(self,None)
top.Bpop(self)
top.view(self)
if n>1:
top.move(self,n-1,b,a,c)
Comme je l'ai écrit au début, assurez-vous d'imprimer (f "déplacer le disque # {n} de {a} vers {c}") Puisqu'il va descendre, j'utilise if après cela pour classer les conditions. Avec trois disques, il semble qu'il y aura plus de boîtiers (rires) Je me demande s'il existe un bon moyen. .. (´Д ｀) y━─┛ ~~
Pour compléter un peu plus l'intérieur de l'instruction if, Puisque push / pop ne gère que le comportement du pointeur ptr, Assurez-vous de remplacer la valeur du corps de la pile A / B / C par None ou cela ne fonctionnera pas. Alors je ne pousse aucun, Le ptr sera incrémenté de 1, puis reviendra.
hanoi_r1.py
class top:
def __init__(self,capacity:int = 2):
self.Astr = [2,1]
self.Bstr = [None] * capacity
self.Cstr = [None] * capacity
self.capa = capacity
self.Aptr = 0
self.Bptr = 0
self.Cptr = 0
def Apush(self,value):
self.Astr[self.Aptr] = value
self.Aptr += 1
def Bpush(self,value):
self.Bstr[self.Bptr] = value
self.Bptr += 1
def Cpush(self,value):
self.Cstr[self.Cptr] = value
self.Cptr += 1
def Apop(self):
self.Aptr -= 1
return self.Astr[self.Aptr]
def Bpop(self):
self.Bptr -= 1
return self.Bstr[self.Bptr]
def Cpop(self):
self.Cptr -= 1
return self.Cstr[self.Cptr]
def view(self):
print(f"A = {self.Astr}")
print(f"B = {self.Bstr}")
print(f"C = {self.Cstr}")
def move(self,n,a,b,c):
if n>1:
top.move(self,n-1,a,c,b)
print(f"{n}À{a}De{c}Quoi")
if a == "A" and c == "B":
top.Bpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "A" and c == "C":
top.Cpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "B" and c == "C":
top.Cpush(self,top.Bpop(self))
top.Bpush(self,None)
top.Bpop(self)
top.view(self)
if n>1:
top.move(self,n-1,b,a,c)
test = top()
if __name__ =="__main__":
print("default setting")
print("A = [2,1]")
print("B = [None,None]")
print("C = [None,None]")
test.move(2,"A","B","C")
Le résultat de l'exécution est ici.
default setting
A = [2,1]
B = [None,None]
C = [None,None]
1 de A à B
A = [2, None]
B = [1, None]
C = [None, None]
2 de A à C
A = [None, None]
B = [1, None]
C = [2, None]
1 de B à C
A = [None, None]
B = [None, None]
C = [2, 1]
N = 2 Non fixe, mais une configuration qui peut suivre même si elle est librement modifiée Je vais y réfléchir à nouveau. Probablement, même si le nombre de feuilles augmente, l'endroit où se déplacer n'augmente pas, donc Je sens que je peux faire quelque chose à ce sujet. Faisons-le un jour. .. (￣з￣)
--10/03 18:53
La compétition sportive des enfants était terminée et il s'est couché tôt. J'ai du temps. Je vais le mettre à jour.
Le contenu de la mise à jour est de considérer une configuration capable de convertir le nombre de disques en N. Comme je l'ai mentionné brièvement la dernière fois, augmenter le nombre de disques ne signifie pas que le nombre de points mobiles augmentera. Par conséquent, il est OK si tous les modèles de mouvement sont répertoriés dans l'instruction if.
A => B A => C B => C B => A C => A C => B
Si vous pouvez diviser l'affaire, ce n'est pas intelligent Le problème peut être résolu.
hanoi_stack_r1.py
if a == "A" and c == "B":
top.Bpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "A" and c == "C":
top.Cpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "B" and c == "C":
top.Cpush(self,top.Bpop(self))
top.Bpush(self,None)
top.Bpop(self)
top.view(self)
if a == "B" and c == "A":
top.Apush(self,top.Bpop(self))
top.Bpush(self,None)
top.Bpop(self)
top.view(self)
if a == "C" and c == "B":
top.Bpush(self,top.Cpop(self))
top.Cpush(self,None)
top.Cpop(self)
top.view(self)
if a == "C" and c == "A":
top.Apush(self,top.Cpop(self))
top.Cpush(self,None)
top.Cpop(self)
top.view(self)
C'est bon. Ensuite, définissez le nombre de disques à préparer N, variable.
hanoi_stack_r1.py
class top:
def __init__(self,capacity):
self.Astr = [] * capacity #Aucun n'est également des données, alors laissez-le vide ici
self.Bstr = [None] * capacity
self.Cstr = [None] * capacity
self.capa = capacity
self.Aptr = 0
self.Bptr = 0
self.Cptr = 0
for i in range(capacity): #Si vous mettez 4, 0=> 1 => 2 =>3 et changer
self.Astr.append(capacity-i) #Capacité du nombre de disques-Si je, 4=> 3 => 2 =>1 peut être attribué à Astr
top.view(self)
if __name__ =="__main__":
num = int(input("enter: ")) #Définissez le nombre de disques à utiliser
test = top(num) # def__init__Capacité de remplacement, la valeur initiale de, en nombre
test.move(num,"A","B","C") #num est effectivement égal à la profondeur de la pile
N'est-il pas normal de n'avoir aucun en premier lieu? !! (Lol) Je l'ai essayé avec 5 feuilles.
enter: 5
A = [5, 4, 3, 2, 1]
B = [None, None, None, None, None]
C = [None, None, None, None, None]
1 de A à C
A = [5, 4, 3, 2, None]
B = [None, None, None, None, None]
C = [1, None, None, None, None]
2 de A à B
A = [5, 4, 3, None, None]
B = [2, None, None, None, None]
C = [1, None, None, None, None]
1 de C à B
A = [5, 4, 3, None, None]
B = [2, 1, None, None, None]
C = [None, None, None, None, None]
3 de A à C
A = [5, 4, None, None, None]
B = [2, 1, None, None, None]
C = [3, None, None, None, None]
1 de B à A
A = [5, 4, 1, None, None]
B = [2, None, None, None, None]
C = [3, None, None, None, None]
2 de B à C
A = [5, 4, 1, None, None]
B = [None, None, None, None, None]
C = [3, 2, None, None, None]
1 de A à C
A = [5, 4, None, None, None]
B = [None, None, None, None, None]
C = [3, 2, 1, None, None]
4 de A à B
A = [5, None, None, None, None]
B = [4, None, None, None, None]
C = [3, 2, 1, None, None]
1 de C à B
A = [5, None, None, None, None]
B = [4, 1, None, None, None]
C = [3, 2, None, None, None]
2 de C à A
A = [5, 2, None, None, None]
B = [4, 1, None, None, None]
C = [3, None, None, None, None]
1 de B à A
A = [5, 2, 1, None, None]
B = [4, None, None, None, None]
C = [3, None, None, None, None]
3 de C à B
A = [5, 2, 1, None, None]
B = [4, 3, None, None, None]
C = [None, None, None, None, None]
1 de A à C
A = [5, 2, None, None, None]
B = [4, 3, None, None, None]
C = [1, None, None, None, None]
2 de A à B
A = [5, None, None, None, None]
B = [4, 3, 2, None, None]
C = [1, None, None, None, None]
1 de C à B
A = [5, None, None, None, None]
B = [4, 3, 2, 1, None]
C = [None, None, None, None, None]
5 de A à C
A = [None, None, None, None, None]
B = [4, 3, 2, 1, None]
C = [5, None, None, None, None]
1 de B à A
A = [1, None, None, None, None]
B = [4, 3, 2, None, None]
C = [5, None, None, None, None]
2 de B à C
A = [1, None, None, None, None]
B = [4, 3, None, None, None]
C = [5, 2, None, None, None]
1 de A à C
A = [None, None, None, None, None]
B = [4, 3, None, None, None]
C = [5, 2, 1, None, None]
3 de B à A
A = [3, None, None, None, None]
B = [4, None, None, None, None]
C = [5, 2, 1, None, None]
1 de C à B
A = [3, None, None, None, None]
B = [4, 1, None, None, None]
C = [5, 2, None, None, None]
2 de C à A
A = [3, 2, None, None, None]
B = [4, 1, None, None, None]
C = [5, None, None, None, None]
1 de B à A
A = [3, 2, 1, None, None]
B = [4, None, None, None, None]
C = [5, None, None, None, None]
4 de B à C
A = [3, 2, 1, None, None]
B = [None, None, None, None, None]
C = [5, 4, None, None, None]
1 de A à C
A = [3, 2, None, None, None]
B = [None, None, None, None, None]
C = [5, 4, 1, None, None]
2 de A à B
A = [3, None, None, None, None]
B = [2, None, None, None, None]
C = [5, 4, 1, None, None]
1 de C à B
A = [3, None, None, None, None]
B = [2, 1, None, None, None]
C = [5, 4, None, None, None]
3 de A à C
A = [None, None, None, None, None]
B = [2, 1, None, None, None]
C = [5, 4, 3, None, None]
1 de B à A
A = [1, None, None, None, None]
B = [2, None, None, None, None]
C = [5, 4, 3, None, None]
2 de B à C
A = [1, None, None, None, None]
B = [None, None, None, None, None]
C = [5, 4, 3, 2, None]
1 de A à C
A = [None, None, None, None, None]
B = [None, None, None, None, None]
C = [5, 4, 3, 2, 1]
Veuillez vérifier si quelqu'un a un problème (rires) Maintenant, voici l'indice donné par @shiracamus Je vais essayer de faire une description de type pyhton qui peut être simplifiée. J'ai lu le code de @ shiracamus, Après l'avoir lu, j'ai ri. Python peut le faire (rires). Ah ~ embarrassant (* noωno) J'écris un article pour étudier En ce moment, je m'en fiche (rires) Pour le moment, j'ai essayé de l'exécuter en premier.
test.py
tower = {"A": [*range(3, 0, -1)], "B": [], "C": []}
print(tower)
{'A': [3, 2, 1], 'B': [], 'C': []}
Qu'est-ce que c'est?! Magic ?? Au fait, si vous supprimez le * devant la plage. ..
{'A': [range(3, 0, -1)], 'B': [], 'C': []}
J'ai été surpris. Je vois, si vous ajoutez un "*" magique, Il se transforme en tableau (..) φ memo memo
Comme mentionné ci-dessus, None est également un type de données, donc Aller à vide sans utiliser Aucun, c'est la même chose.
Vient ensuite l'introduction de append () et pop (). append () se comporte comme push. De plus, la pop est comme l'idée de la pop. De plus, il est pratique de récupérer les données pour pop. Il est sur le point d'effacer les données.
.. .. .. attends une minute. Cela signifie-t-il que le contrôle géré par le pointeur n'est plus nécessaire?! Optimisons-le immédiatement, la description de def __ init __.
test.py
def __init__(self,capacity):
###############################
self.Astr = [] * capacity #=> tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}Remplacer par
self.Bstr = [None] * capacity
self.Cstr = [None] * capacity
self.capa = capacity
###############################
self.Aptr = 0 #=> append,Pas besoin de variables de gestion de pointeur car l'opération de pile est réalisée par pop.
self.Bptr = 0
self.Cptr = 0
##############################
for i in range(capacity): #=> "A": [*range(n, 0, -1)],Inutile car il est remplacé par
self.Astr.append(capacity-i)
top.view(self)
##############################
# || #
# \/ #
def __init__(self,n):
self.tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}
J'ai ri w. Ensuite, si append et pop sont les mouvements de la pile, La description suivante qui gère l'opération du pointeur au moment du push and pop n'est pas inutile?
test.py
#Tout inutile!!!!#####################
def Apush(self,value):
self.Astr[self.Aptr] = value
self.Aptr += 1
def Bpush(self,value):
self.Bstr[self.Bptr] = value
self.Bptr += 1
def Cpush(self,value):
self.Cstr[self.Cptr] = value
self.Cptr += 1
def Apop(self):
self.Aptr -= 1
return self.Astr[self.Aptr]
def Bpop(self):
self.Bptr -= 1
return self.Bstr[self.Bptr]
def Cpop(self):
self.Cptr -= 1
return self.Cstr[self.Cptr]
################################
La tour est définie comme la valeur initiale, Déplaçons-le immédiatement en utilisant append et pop. En conclusion, c'est ce qui s'est passé.
test.py
class hanoi:
def __init__(self,n):
self.tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}
def move(self,n,a,b,c):
if n>1:
hanoi.move(self,n-1,a,c,b)
print(f"{n}À{a}De{c}Quoi")
self.tower[c].append(self.tower[a].pop())
if n>1:
hanoi.move(self,n-1,b,a,c)
Ma compréhension est que self est utilisé lors du passage de variables entre des définitions en classe. Donc, si vous déclarez self.tower, vous pouvez taper def move (self,) et self. Une compréhension que vous pouvez mettre self.tower en mouvement.
Quant à hanoi.move, c'est une image qui appelle def move dans la classe hanoi. hanoi.move () J'ai été surpris. Vous devrez peut-être vous étudier un peu plus.
J'irai ensuite. Les fonctions suivantes sont définies pour représenter l'état de chaque boîte.
test.py
def view(self):
print(f"A = {self.Astr}")
print(f"B = {self.Bstr}")
print(f"C = {self.Cstr}")
Maintenant que Astr / Bstr / Cstr n'est plus nécessaire, Doit être représenté d'une autre manière. Je ne suis pas assez génial pour comprendre avec juste le code que j'ai reçu Je l'ai cherché. Il y avait une explication facile à comprendre ci-dessous.
https://note.nkmk.me/python-dict-keys-values-items/
Selon cela, le nom de la boîte et le contenu de la boîte peuvent être exprimés en tournant l'instruction for. C'était une chose.
test.py
def view(self):
for name,value in self.tower.items()
print(f"{name} = {value}")
Je vois. Incorporons-le immédiatement.
test.py
class hanoi:
def __init__(self,n):
self.tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}
def view(self):
for name,value in self.tower.items():
print(f"{name} = {value}")
def move(self,n,a,b,c):
if n>1:
hanoi.move(self,n-1,a,c,b)
print(f"{n}À{a}De{c}Quoi")
self.tower[c].append(self.tower[a].pop())
hanoi.view(self)
if n>1:
hanoi.move(self,n-1,b,a,c)
C'est assez simple de mourir. L'image entière est comme ça.
hanoi_stack_r2.py
class hanoi:
def __init__(self,n):
self.tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}
def view(self):
for name,value in self.tower.items():
print(f"{name} = {value}")
def move(self,n,a,b,c):
if n>1:
hanoi.move(self,n-1,a,c,b)
print(f"{n}À{a}De{c}Quoi")
self.tower[c].append(self.tower[a].pop())
hanoi.view(self)
if n>1:
hanoi.move(self,n-1,b,a,c)
if __name__ =="__main__":
num = int(input("enter: "))
test = hanoi(num)
test.move(num,"A","B","C")
Merci à @shiracamus pour l'opportunité d'étudier m (_ _) m
Recommended Posts