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.
- Se compose de 3 piles et de plusieurs disques de différentes tailles avec un trou au centre.
- Au début, tous les disques sont empilés dans l'ordre sur la pile la plus à gauche avec les plus petits en haut.
- 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.
-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
# 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)
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)
# 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']
])
Tour de Hanoi-Wikipedia Capturez la tour de Hanoï Résolution de la tour de Hanoi par récursivité
Recommended Posts