1. 1. introduction

Les fonctions récursives peuvent être le premier obstacle à la programmation. Maîtrisons la fonction récursive tout en résolvant la tour de Hanoi avec Python.

Les fonctions récursives, comme Matryoshka, ont une structure de programme imbriquée. Bien sûr, veuillez lire l'explication suivante en imaginant Matriochka. マトリョーシカ.jpg

2. Tour de Hanoi

Voir ci-dessous pour la tour de Hanoi. Tour de Hanoï ハノイの塔.jpg

En bref, il y a trois bâtons qui peuvent être percés par une planche. Il y a plusieurs planches sur la gauche. La taille de la planche est la plus grande en bas et devient plus petite vers le haut. Je veux déplacer les planches une par une et enfin déplacer toutes les planches de la gauche vers la barre du milieu. Cependant, une grande assiette ne peut pas être placée sur une petite assiette.

Dans l'apprentissage de la programmation, c'est un problème à résoudre à l'aide d'une fonction récursive.

3. 3. Façon de penser

L'un est super facile. Déplacez-vous de la gauche vers le centre et vous avez terminé. Le point est le cas de deux feuilles. Du coup, ne déplacez pas le petit plateau de la barre de gauche vers le centre. (1) Tout d'abord, la petite plaque est une fois transférée sur la tige de travail du côté droit. (2) Ensuite, déplacez le grand plateau gauche à gauche vers le centre. (3) Après cela, déplacez le petit plateau de la droite vers le centre, et c'est OK.

En d'autres termes, n planches (2 planches dans ce cas), afin de tout déplacer de la gauche vers le centre, (1) n-1 planches (1 planche dans ce cas) en excluant la plus grande planche du bas , Il est nécessaire de passer une fois de gauche à droite sur la tige de travail. (2) Ensuite, après avoir déplacé la plus grande plaque du bas de la gauche vers le centre, (3) toutes les n-1 plaques (une dans ce cas) sur la tige de travail droite, Si vous le déplacez vers le centre, tout va bien.

Dans la description suivante, les points (1) à (3) ci-dessus seront décrits à plusieurs reprises. (1) à (3) qui apparaissent dans l'explication suivante ont fondamentalement la même signification que (1) à (3) ci-dessus. Cependant, "où aller où" change selon le cas dans "gauche, milieu, droite".

4. Solution récursive

Voici le programme de solution pour la tour de Hanoi. Je l'exécuterai plus tard, mais lors de son utilisation, remplacez le nombre de cartes par N.

start=list(range(N,0,-1));end=[];tmp=[];i=0  #1
def print_hanoi(): #2
    print(start,end,tmp)
def hanoi(n,start,end,tmp): #3
    if n<=0:        return  #4
    hanoi(n-1,start,tmp,end)  #5
    end.append(start.pop())   #6
    print_hanoi()              #7
    global i; i+=1             #8
    print('Ce qui précède est',i,'État après la deuxième opération')   #9
    hanoi(n-1,tmp,end,start)   #10
print_hanoi()                  #11
print('Ce qui précède est l'état initial')       #12
hanoi(N,start,end,tmp)         #13

Je vais vous expliquer brièvement. Les numéros correspondent aux parties marquées d'un # dans le programme.

1. start est une liste qui représente le tableau qui est bloqué dans la barre de gauche en premier. Dans l'état initial, le bas est le plus grand, la liste est plus petite de 1 et la dernière est de 1.

end est une liste montrant la carte coincée dans le bâton central que vous souhaitez enfin transférer la carte. Au début, rien n'est bloqué, donc une liste vide.

tmp est une liste montrant la planche coincée dans le bâton pour le travail à droite. C'est aussi une liste vide car rien n'est bloqué au début.

i est défini pour indiquer le nombre d'opérations.

Représente un état. Les planches collées dans les bâtons "gauche, milieu, droit" dans l'ordre sont affichées dans une liste.
1. C'est la fonction qui résout la tour de Hanoi. Cependant, comme il utilise une fonction récursive, il est imbriqué comme Matryoshka. Veuillez prêter attention à l'argument. Le premier n est le nombre de planches. Le suivant est le début et je veux le déplacer à la fin suivante. Le dernier est tmp.
Il s'agit de la condition de terminaison de base. Lorsque le nombre de cartes à déplacer devient 0, le processus se termine. Si vous oubliez la condition de terminaison de base, vous vous retrouverez dans une boucle infinie, alors soyez prudent.

La fonction de 5.3 est utilisée de manière récursive. Cependant, la fonction de 3 est définie pour déplacer toutes les n feuilles du premier argument du début du deuxième argument à la fin du troisième argument. (Le quatrième argument est tmp pour le travail.)

Ici, ** (1) Toutes les n-1 feuilles restantes (premier argument) sauf les n du bas sont temporairement déplacées de start (deuxième argument) à tmp (troisième argument). ** (Le quatrième argument est la fin de l'argument restant.)

** En faisant cela, n-1 feuilles du haut se déplacent vers tmp, vous pouvez donc déplacer n en bas. ** **

Depuis que j'ai déplacé n-1 feuilles du haut vers tmp en 6.5, seul le n du bas reste sur la barre de démarrage gauche. (2) Retirez le plateau du bas et déplacez-le vers start.pop () et la barre de fin du milieu ʻend.append () `(ajouter à la liste).

Imprimez l'état ici.
Comptez le nombre de fois.
Imprimez le nombre d'opérations après l'opération pour une meilleure compréhension.

dix. ** Le plus grand tableau sur 6 a déménagé au centre. (3) Transférez toutes les plaques n-1 de la tige de travail droite sur la plus grande plaque. Si vous regardez les arguments, vous pouvez voir ce que vous faites. ** **

Imprimez ici l'état initial.
Imprimez des commentaires pour une compréhension facile.
Exécution réelle. N est donné lors de son utilisation.

5. Essayons réellement

1. Tout d'abord, lorsqu'il n'y a qu'un seul tableau. Je ne pense pas que ce soit nécessaire de le faire, mais faites attention à tout. N est spécifié au début du programme.

N=1;start=list(range(N,0,-1));end=[];tmp=[];i=0  #1
def print_hanoi(): #2
    print(start,end,tmp)
def hanoi(n,start,end,tmp): #3
    if n<=0:        return  #4
    hanoi(n-1,start,tmp,end)  #5
    end.append(start.pop())   #6
    print_hanoi()              #7
    global i; i+=1             #8
    print('Ce qui précède est',i,'État après la deuxième opération')   #9
    hanoi(n-1,tmp,end,start)   #10
print_hanoi()                  #11
print('Ce qui précède est l'état initial')       #12
hanoi(N,start,end,tmp)         #13

Le résultat est le suivant. Déplacez-vous de la gauche vers le centre et vous avez terminé.

Ici, seule la partie (2) décrite dans «l'idée» de 3 est exécutée. Comme vous pouvez le voir en regardant # 5 correspondant à (1) et # 10 correspondant à (2), n-1 devient 0 et rien n'est exécuté en # 4.

[1] [] []
Ce qui précède est l'état initial
[] [1] []
Ce qui précède est l'état après la première opération

Viennent ensuite deux cas. Contrairement à un cas, le bon bâton de travail est utilisé pour le deuxième cas et les suivants.

N=2;start=list(range(N,0,-1));end=[];tmp=[];i=0  #1
def print_hanoi(): #2
    print(start,end,tmp)
def hanoi(n,start,end,tmp): #3
    if n<=0:        return  #4
    hanoi(n-1,start,tmp,end)  #5
    end.append(start.pop())   #6
    print_hanoi()              #7
    global i; i+=1             #8
    print('Ce qui précède est',i,'État après la deuxième opération')   #9
    hanoi(n-1,tmp,end,start)   #10
print_hanoi()                  #11
print('Ce qui précède est l'état initial')       #12
hanoi(N,start,end,tmp)         #13

Le résultat est le suivant. Les chiffres représentent la taille du plateau. Les nombres de la liste sont sortis dans l'ordre de celui ci-dessous. En d'autres termes, il est nécessaire pour les règles de la tour de Hanoi que les numéros de la liste soient classés par ordre décroissant. Dans deux cas, (1) ** Commencez par déplacer la petite plaque de gauche à droite sur la tige de travail. ** (Première opération) (2) Et ** Ce faisant, la grande planche de gauche peut être déplacée vers le centre. ** (Deuxième opération) (3) ** Enfin, déplacez la petite assiette à droite sur la grande assiette au milieu, et c'est OK. ** (3e opération)

[2, 1] [] []
Ce qui précède est l'état initial
[2] [] [1]
Ce qui précède est l'état après la première opération
[] [2] [1]
Ce qui précède est l'état après la deuxième opération
[] [2, 1] []
Ce qui précède est l'état après la troisième opération

Le programme est omis après 3,3 feuilles. Ce n'est pas grave si vous modifiez le nombre de feuilles à attribuer à N. Le résultat est le suivant.

[3, 2, 1] [] []
Ce qui précède est l'état initial
[3, 2] [1] []
Ce qui précède est l'état après la première opération
[3] [1] [2]
Ce qui précède est l'état après la deuxième opération
[3] [] [2, 1]
Ce qui précède est l'état après la troisième opération
[] [3] [2, 1]
Ce qui précède est l'état après la 4ème opération
[1] [3] [2]
Ce qui précède est l'état après la 5ème opération
[1] [3, 2] []
Ce qui précède est l'état après la 6ème opération
[] [3, 2, 1] []
Ce qui précède est l'état après la 7e opération

(1) ** Dans les première à troisième opérations, deux feuilles (c'est-à-dire n-1 feuilles) sont transférées sur la tige de travail droite. Les premier à troisième temps incluent (1) à (3) dans le cas de deux feuilles. ** Bien sûr, les détails de «où aller où» sont au cas par cas.

(2) Ensuite, lors de la ** 4ème opération, la troisième feuille la plus grande (c'est-à-dire la nième feuille) est déplacée de la gauche vers le centre. ** **

(3) Après cela, dans les opérations de ** 5e à 7e, déplacez les 2 feuilles (c'est-à-dire n-1 feuilles) de l'ouvrage de droite sur la plus grande plaque du milieu et terminez. Les 5e à 7e fois comprennent également (1) à (3) dans le cas de deux feuilles. ** Bien sûr, les détails de «où aller où» sont au cas par cas.

Ce à quoi je voudrais que vous soyez prudent ici, c'est la méthode de transfert des deux pièces sur le bon bâton de travail dans (1). ** Dans le cas du déplacement des deux pièces réalisées en 2 de la gauche vers le centre, le côté droit est devenu l'œuvre. Cependant, dans le cas du déplacement de deux feuilles de gauche à droite avec trois feuilles (1), le centre est naturellement destiné au travail. Par conséquent, la plus petite planche sera déplacée vers le centre lors de la première opération. ** **

** Il en va de même lors du déplacement de deux feuilles de la droite vers le centre en (3). Ici, la gauche est le travail, donc dans la cinquième opération, la plus petite plaque est déplacée de droite à gauche. ** **

Terminons avec 4 cas à la fin.

[4, 3, 2, 1] [] []
Ce qui précède est l'état initial
[4, 3, 2] [] [1]
Ce qui précède est l'état après la première opération
[4, 3] [2] [1]
Ce qui précède est l'état après la deuxième opération
[4, 3] [2, 1] []
Ce qui précède est l'état après la troisième opération
[4] [2, 1] [3]
Ce qui précède est l'état après la 4ème opération
[4, 1] [2] [3]
Ce qui précède est l'état après la 5ème opération
[4, 1] [] [3, 2]
Ce qui précède est l'état après la 6ème opération
[4] [] [3, 2, 1]
Ce qui précède est l'état après la 7e opération
[] [4] [3, 2, 1]
Ce qui précède est l'état après la 8e opération
[] [4, 1] [3, 2]
Ce qui précède est l'état après la 9ème opération
[2] [4, 1] [3]
Ce qui précède est l'état après la 10e opération
[2, 1] [4] [3]
Ce qui précède est l'état après la 11e opération
[2, 1] [4, 3] []
Ce qui précède est l'état après la 12e opération
[2] [4, 3] [1]
Ce qui précède est l'état après la 13e opération
[] [4, 3, 2] [1]
Ce qui précède est l'état après la 14e opération
[] [4, 3, 2, 1] []
Ce qui précède est l'état après la 15e opération

(1) ** Dans les opérations du 1er au 7e, 3 feuilles (soit n-1 feuilles) sont transférées sur la tige pour le bon travail. Les première à septième fois comprennent (1) à (3) dans le cas de trois feuilles. Ensuite, (1) dans le cas de 3 feuilles comprend (1) à (3) dans le cas de 2 feuilles, et (1) dans le cas de 2 feuilles est également inclus dans (3) dans le cas de 3 feuilles. ) À (3) sont inclus. ** **

(2) Ensuite, lors de la ** 8ème opération, la quatrième feuille la plus grande (c'est-à-dire la nième feuille) est déplacée de la gauche vers le centre. ** **

(3) ** Après cela, dans la 9e à la 15e opérations, déplacez les 3 feuilles (c'est-à-dire n-1 feuilles) du bon travail sur la plus grande plaque du milieu, et vous avez terminé. Les 9e à 15e fois incluent (1) à (3) dans le cas de trois feuilles. Ensuite, (1) dans le cas de 3 feuilles comprend (1) à (3) dans le cas de 2 feuilles, et (1) dans le cas de 2 feuilles est également inclus dans (3) dans le cas de 3 feuilles. ) À (3) sont inclus. ** **

Cette fois ainsi que dans le cas de 3 feuilles, l'utilisation du travail changera.

6. Résumé

Le rôle des travaux dans la tour de Hanoi change en fonction du nombre de planches. Cependant, je voudrais que vous prêtiez attention aux parties (1), (2) et (3) décrites dans les 2e, 3e et 4e feuilles de 5. (1) ** Tout d'abord, déplacez n-1 feuilles du haut pour le travail de gauche à droite, ** (2) ** Ce faisant, le grand plateau inférieur peut être déplacé de la gauche vers le centre, ** (3) ** Enfin, si vous déplacez n-1 feuilles du haut vers le centre du travail à droite, c'est OK. ** **

En parlant du programme de 4, (1) correspond à 5, (2) correspond à 6 et (3) correspond à 10. Cette opération est répétée, comme Matriochka, dans la fonction récursive utilisée pour résoudre la tour de Hanoi. (Pour être précis, les parties récursives pures sont (1) et (3).)

7. Site de référence

Les sites suivants sont écrits en C ++, mais ce sont des sites très utiles. L'auteur est celui que je respecte personnellement.

Quel genre de monde va s'étendre lorsque vous apprenez les fonctions récursives

[Pour les débutants] Fonction récursive (Facile à comprendre la tour de Hanoi!)