Tour de Hanoi-Rétrospective / Non-récursive (édition Python)

règle

Ci-dessous [Tour de Hanoi-Wikipedia](http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1% À partir de 94)

Terminez si vous pouvez déplacer tous les disques vers la pile la plus à droite selon les règles suivantes.

  1. Se compose de 3 piles et de plusieurs disques de différentes tailles avec un trou au centre.
  2. Au début, tous les disques sont empilés dans l'ordre sur la pile la plus à gauche avec les plus petits en haut.
  3. Vous pouvez déplacer un disque sur l'une des piles une par une, mais vous ne pouvez pas placer un grand disque sur un petit disque.

Façon de penser

-Le sens de rotation de la pile de chaque disque alterne --Le code récursif est un processus qui répète le mouvement de trois disques (n, n-1, n-2) dans une certaine phase. --Le code non récursif est un processus qui répète le mouvement tout en déterminant si le disque peut être déplacé en utilisant la fonction d'alternance des directions de mouvement des disques. --Le nombre de coups est 2 ^ n --1

Code récursif

# coding: utf-8

def hanoi(disk_number, f, t, w, tower_dict):

    if disk_number > 0:
        hanoi(disk_number-1, f, w, t, tower_dict)
        tower_dict[t].insert(0, tower_dict[f].pop(0))
        print((tower_dict['left'], tower_dict['center'], tower_dict['right']))
        hanoi(disk_number-1, w, t, f, tower_dict)


if __name__ == '__main__':
    disk_number = int(input())
    tower_dict = {'left': [i for i in range(1, disk_number+1)], 'center': [], 'right': []}
    print((tower_dict['left'], tower_dict['center'], tower_dict['right']))
    hanoi(disk_number, 'left', 'right', 'center', tower_dict)

Code non récursif

def hanoi(tower_list, pile_list, disk_number):
    cnt = 0
    passed_list = [tower_list[:]]

    while True:

        for disk in range(1, disk_number+1):

            #Si le disque actuel n'est pas en haut de la pile, passez au disque suivant
            if tower_list.index(tower_list[disk-1]) != disk-1:
                continue

            idx = pile_list.index(tower_list[disk-1])

            #Virage à droite (à gauche)-> center -> right -> left ...Tournez dans l'ordre de)
            if (disk_number % 2 == 0 and disk % 2 == 1) or (disk_number % 2 == 1 and disk % 2 == 0) :

                if idx+1 >= len(pile_list):
                    idx = -1

                if pile_list[idx+1] not in tower_list or tower_list.index(pile_list[idx+1]) > disk-1:
                    tower_list[disk-1] = pile_list[idx+1]
                    passed_list.append(tower_list[:])
                    cnt += 1


            #La gauche-> right -> center -> left ...Tournez dans l'ordre de)
            else:

                if 0 >= idx:
                    idx = len(pile_list)

                if pile_list[idx-1] not in tower_list or tower_list.index(pile_list[idx-1]) > disk-1:
                    tower_list[disk-1] = pile_list[idx-1]
                    passed_list.append(tower_list[:])
                    cnt += 1

            if tower_list == ['r'] * disk_number:
                return cnt, passed_list

if __name__ == '__main__':
    disk_number = int(input())
    pile_list = ['l', 'c', 'r']
    tower_list = ['l'] * (disk_number)

    cnt, passed_list = hanoi(tower_list, pile_list, disk_number)

    print(passed_list)

Bonus (code de test non récursif)

# coding: utf-8

import unittest


class HanoiTest(unittest.TestCase):

    def setUp(self):
        self.pile_list = ['l', 'c', 'r']

    def test_first(self):
        disk_number = 3
        tower_list = ['l'] * (disk_number)
        cnt, passed_list = hanoi(tower_list, self.pile_list, disk_number)
        self.assertEqual(cnt, 2 ** disk_number - 1)
        self.assertEqual(passed_list, [
            ['l', 'l', 'l'],
            ['r', 'l', 'l'],
            ['r', 'c', 'l'],
            ['c', 'c', 'l'],
            ['c', 'c', 'r'],
            ['l', 'c', 'r'],
            ['l', 'r', 'r'],
            ['r', 'r', 'r']
        ])

    def test_second(self):
        disk_number = 4
        tower_list = ['l'] * (disk_number)
        cnt, passed_list = hanoi(tower_list, self.pile_list, disk_number)
        self.assertEqual(cnt, 2 ** disk_number - 1)
        self.assertEqual(passed_list, [
            ['l', 'l', 'l', 'l'],
            ['c', 'l', 'l', 'l'],
            ['c', 'r', 'l', 'l'],
            ['r', 'r', 'l', 'l'],
            ['r', 'r', 'c', 'l'],
            ['l', 'r', 'c', 'l'],
            ['l', 'c', 'c', 'l'],
            ['c', 'c', 'c', 'l'],
            ['c', 'c', 'c', 'r'],
            ['r', 'c', 'c', 'r'],
            ['r', 'l', 'c', 'r'],
            ['l', 'l', 'c', 'r'],
            ['l', 'l', 'r', 'r'],
            ['c', 'l', 'r', 'r'],
            ['c', 'r', 'r', 'r'],
            ['r', 'r', 'r', 'r']
        ])

    def test_third(self):
        disk_number = 5
        tower_list = ['l'] * (disk_number)
        cnt, passed_list = hanoi(tower_list, self.pile_list, disk_number)
        self.assertEqual(cnt, 2 ** disk_number - 1)
        self.assertEqual(passed_list, [
            ['l', 'l', 'l', 'l', 'l'],
            ['r', 'l', 'l', 'l', 'l'],
            ['r', 'c', 'l', 'l', 'l'],
            ['c', 'c', 'l', 'l', 'l'],
            ['c', 'c', 'r', 'l', 'l'],
            ['l', 'c', 'r', 'l', 'l'],
            ['l', 'r', 'r', 'l', 'l'],
            ['r', 'r', 'r', 'l', 'l'],
            ['r', 'r', 'r', 'c', 'l'],
            ['c', 'r', 'r', 'c', 'l'],
            ['c', 'l', 'r', 'c', 'l'],
            ['l', 'l', 'r', 'c', 'l'],
            ['l', 'l', 'c', 'c', 'l'],
            ['r', 'l', 'c', 'c', 'l'],
            ['r', 'c', 'c', 'c', 'l'],
            ['c', 'c', 'c', 'c', 'l'],
            ['c', 'c', 'c', 'c', 'r'],
            ['l', 'c', 'c', 'c', 'r'],
            ['l', 'r', 'c', 'c', 'r'],
            ['r', 'r', 'c', 'c', 'r'],
            ['r', 'r', 'l', 'c', 'r'],
            ['c', 'r', 'l', 'c', 'r'],
            ['c', 'l', 'l', 'c', 'r'],
            ['l', 'l', 'l', 'c', 'r'],
            ['l', 'l', 'l', 'r', 'r'],
            ['r', 'l', 'l', 'r', 'r'],
            ['r', 'c', 'l', 'r', 'r'],
            ['c', 'c', 'l', 'r', 'r'],
            ['c', 'c', 'r', 'r', 'r'],
            ['l', 'c', 'r', 'r', 'r'],
            ['l', 'r', 'r', 'r', 'r'],
            ['r', 'r', 'r', 'r', 'r']
        ])

référence

Tour de Hanoi-Wikipedia Capturez la tour de Hanoï Résolution de la tour de Hanoi par récursivité

Recommended Posts

Tour de Hanoi-Rétrospective / Non-récursive (édition Python)
Implémentation Python de l'arborescence de segments non récursive
Les bases de Python ①
Bases de python ①
Copie de python
Introduction de Python
[Python] Opération d'énumération
Liste des modules python
Algorithme A * (édition Python)
Première 3e édition de Python
Unification de l'environnement Python
Copie des préférences python
Principes de base du grattage Python
[python] comportement d'argmax
Utilisation des locaux Python ()
le zen de Python
Installation de Python 3.3 rc1
# 4 [python] Bases des fonctions
Connaissance de base de Python
L'édition définitive du grattage python! (Site cible: grande caméra)
Anecdotes sobres de python3
Résumé des arguments Python
Bases de python: sortie
Installation de matplotlib (Python 3.3.2)
Application de Python 3 vars
Divers traitements de Python
[Python] Utilisation correcte de la carte
Série Python 2 et série 3 (édition Anaconda)
Vers la retraite de Python2
résumé lié à l'opération de fichier python
Résumé des opérations de liste Python3
Python - Démarrage rapide de la journalisation
PyTorch C ++ VS Python (édition 2019)
Recommandation de la bibliothèque binpacking de python
Mise à jour automatique du module Python
Python - Vérifiez le type de valeurs
[Python] L'origine du nom de la fonction python
Construction de l'environnement CI ~ Édition Python ~
Analyse statique des programmes Python
À propos de divers encodages de Python 3
Installation de Python (édition Mac) (ancienne)
Jugement d'équivalence d'objet en Python
Introduction d'activités appliquant Python
python> Gestion des tableaux 2D
Installer plusieurs versions de Python
Mise à niveau de python Anaconda
Manipulation de python sur mac
python: principes de base de l'utilisation de scikit-learn ①
2.x, 3.x code de caractères des séries python
Comparaison de 4 types de frameworks Web Python
Mesure FPS simple de python
Vérifiez la version OpenSSL de python 2.6
Implémentation Python du filtre à particules
Post-traitement de python (NG)
[Python] Copie d'une liste multidimensionnelle
Accélérer le chargement des images Python
Exemple d'utilisation de pickle Python
Utilisation basique de la f-string Python