Défiez la tour de Hanoi avec récurrence

Bonsoir. Merci pour votre soutien continu.

J'ai vu diverses opinions d'experts, mais C'était assez difficile. C'est probablement une question de compréhension, donc je ne peux pas m'en empêcher.

Faisons-le d'abord. Essayez de déplacer les deux disques du bord gauche vers le bord droit. Ici, les expressions à l'extrémité droite, au centre et à l'extrémité gauche sont subtiles, donc Attribuez un numéro. Bord gauche: 1, centre: 2, bord droit: 3. 図1.PNG Je l'ai écrit, Le disque s'est déplacé vers la droite et d'où Il a été déplacé ou complété.

J'ai capturé le revêtement de sol dans l'article précédent par récursif Peut-il être détourné? Nous allons jeter un coup d'oeil.

cure.py


def test(n:int=3):
    if n>1:
        return n * test(n-1)
    else:
        return 1

Quant à ce que je veux faire. ..

Je souhaite déplacer deux disques de 1 à 3
Déplacez le disque numéro 1 de 1 à 2, puis
Déplacez le disque numéro 2 de 1 à 3 et
Déplacez le disque numéro 1 de 2 à 3.

Rendre le nombre et la feuille communs comme n, Passons de x à y. Encore une fois, voici l'image.

2 feuilles(n)Disque de 1(x)À partir de 3(y)Je veux déménager
N ° 1(n)Disque de 1(x)À partir de 2(y)Après avoir déménagé à
N ° 2(n)Disque de 1(x)À partir de 3(y)Déménager à
N ° 1(n)Disque de 2(x)À partir de 3(y)Déménager à.

Par conséquent, il semble bon de commencer par le test def (n, x, y).

2 feuilles(n)Disque de 1(x)À partir de 3(y)Je veux déménager=> def test(n , x , y): 
N ° 1(n)Disque de 1(x)À partir de 2(y)Après avoir déménagé à
N ° 2(n)Disque de 1(x)À partir de 3(y)Déménager à
N ° 1(n)Disque de 2(x)À partir de 3(y)Déménager à.

Suivant. Après avoir commencé le test (2,1,3), ensuite Doit être configuré pour réussir le test (1,1,2). test(1,1,?) Comment faites-vous le dernier? Rappelez-vous que chaque axe était numéroté. Puisque 1 + 2 + 3 = 6, 6-x-y peut être utilisé pour exprimer ?.

2 feuilles(n)Disque de 1(x)À partir de 3(y)Je veux déménager=> def test(n , x , y): 
N ° 1(n)Disque de 1(x)À partir de 2(y)Après avoir déménagé à=>     test(n-1,x ,6-x-y)
N ° 2(n)Disque de 1(x)À partir de 3(y)Déménager à
N ° 1(n)Disque de 2(x)À partir de 3(y)Déménager à.

Si ce qui précède est laissé tel quel, l'état de n == 0 se produira. 0 disque? 0 disque? Il semble être un peu cassé, donc Faisons une condition avec l'instruction if. Si n> 1, alors Vous pouvez éviter la condition n == 0.

2 feuilles(n)Disque de 1(x)À partir de 3(y)Je veux déménager=> def test(n , x , y): 
N ° 1(n)Disque de 1(x)À partir de 2(y)Après avoir déménagé à=>   if n>1:
                                  test(n-1,x ,6-x-y)

N ° 2(n)Disque de 1(x)À partir de 3(y)Déménager à
N ° 1(n)Disque de 2(x)À partir de 3(y)Déménager à.

Considérant en remplaçant par le test (1,1,2), la configuration ci-dessus Je ne suis pas accro à si n> 1, alors passe. À ce stade, il est OK si vous pouvez afficher "Déplacer le 1er (n) disque de 1 (x) à 2 (y)" en utilisant print.

2 feuilles(n)Disque de 1(x)À partir de 3(y)Je veux déménager=> def test(n , x , y): 
N ° 1(n)Disque de 1(x)À partir de 2(y)Après avoir déménagé à=>   if n>1:
                                    test(n-1,x ,6-x-y)
                                  print(f"{n}À{x}=>{y}Quoi")
N ° 2(n)Disque de 1(x)À partir de 3(y)Déménager à
N ° 1(n)Disque de 2(x)À partir de 3(y)Déménager à.

C'est un peu difficile à expliquer, test (1,1,2) est égal à print (f "{1} to {1} => {2}"). Après l'avoir quitté, imprimez (f "{2} to {1} => {3}") au test (2,1,3) Vous serez connecté automatiquement. Qu'en est-il du dernier "Déplacer le 1er (n) disque de 2 (x) à 3 (y)"? Je l'ai essayé comme ça.

test.py


def test(n,x,y):
    if n>1:
        test(n-1,x,6-x-y)
    print(f"{n}À{x}=>{y}Quoi")
    if n>1:
        test(n-1,6-x-y,y)

Eh bien, je pense à l'expliquer (rires).

Recommended Posts

Défiez la tour de Hanoi avec récurrence
Défiez la tour de Hanoi avec recurs + stack
[Pour les débutants] Fonction récursive (Facile à comprendre la tour de Hanoi!)
[Introduction à cx_Oracle] Présentation de cx_Oracle
Combinaison de récursif et de générateur
Allocation de ressources aux tests
Je voulais contester la classification du CIFAR-10 en utilisant l'entraîneur de Chainer