прикреплённый файл:hcir.py к странице LecturesVMSH/2011-01-19

   1 #!/usr/bin/python
   2 # coding: utf-8
   3 # vim:et:sw=4:
   4 
   5 '''
   6 На дорогах Ханоя было введено одностороннее круговое движение, поэтому теперь диск со стержня 1 можно перекладывать только на стержень 2, со стержня 2 на 3, а со стержня 3 на 1. 
   7 Напишите программу, которая решает головоломку; для данного числа дисков n печатает последовательность перекладываний в формате a b c, где a — номер перекладываемого диска, b — номер стержня с которого снимается данный диск, c — номер стержня на который надевается данный диск. 
   8 количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10
   9 '''
  10 
  11 import sys
  12 
  13 n=int(sys.argv[1])
  14 debug=len(sys.argv)>2
  15 
  16 abc=(range(n,0,-1),[],[])
  17 
  18 def other(k,l):
  19     return (0,2,1,0)[k+l]
  20 
  21 def passover(k,l):
  22     global move
  23     if abc[l] and abc[k][-1]>abc[l][-1]:
  24         print "OOPS",abc,k,l
  25     abc[l].append(abc[k].pop())
  26     if debug:
  27         print abc[0],abc[1],abc[2],k,l
  28     else:
  29         print abc[l][-1],k+1,l+1
  30 
  31 def hanoi(k,l,n):
  32     '''Неэффективный алгоритм!'''
  33     if (k,l) in ((1,0),(2,1),(0,2)):
  34         hanoi(k,other(k,l),n)
  35         hanoi(other(k,l),l,n)
  36     elif n == 1:
  37         passover(k,l)
  38     else:
  39         hanoi(k,other(k,l),n-1)
  40         passover(k,l)
  41         hanoi(other(k,l),l,n-1)
  42 
  43 hanoi(0,2,n)