pythonはハノータアルゴリズムを実現します。


タイトル:
ハノータは最適解を与えます。ハノータの定義が分からないなら、データ構造の教材を見てください。
一番基本的な以外に、一つの配列を与えられました。arr=[2,3,1,2,3]という意味です。これは5つの円盤があるハノータという意味です。数字はこの円盤の位置を表します。1は左側の柱、2は中間、3は右を表します。このシーケンスはハノータ移動の第数ステップを表し、このステップが間違っている場合は-1に戻り、エラーとは、このステップが最も簡単にハノータシーケンスを得るための操作ステップではないことを意味する。
分析:
1、アルゴリズムはもちろん再帰的に解きました。つまり、n個のハノータの皿をn-1個の皿に分解して移動することと、一つの下の皿の移動することで、問題は一連の再帰となり、その後徐々に解決できます。
もちろんです。ハノータには進級問題があります。ここでは議論しないで、あとで補充してください。
2、この手順の循環は一番右から始まります。一番大きな円盤を調べます。配列のインデックス値が大きいほど円盤の半径が大きくなります。
このようにして、最大の円盤の値が3であれば、もう動いていると説明します。1であれば、底の円盤をまだ動かし始めていないと説明しています。2であれば、円盤が真ん中に移動したと説明しています。
コード:

#!usr/bin/python2.7
# -*- coding=utf8 -*-
# @Time : 18-1-3   9:52
# @Author : Cecil Charlie


class Hanoi(object):
 """
      ,      ,                          。
 """
 def __init__(self):
 self.place = ["left", "middle", "right"]
 self.num = 0 #           

 def hanoi(self, n):
 """
      n,         ,                   
 :param n:    
 :return:     
 """
 self.num = 0
 if n > 0:
  self.__move(n, "left", "middle", "right")

 def __move(self, n, start, mid, end):
 if n == 1:
  print "move from " + start + " to " + end
  self.num += 1
 else:
  self.__move(n-1, start, end, mid)
  self.__move(1, start, mid, end)
  self.__move(n-1, mid, start, end)

 def step(self, arr):
 """
      arr   ,             。                    3  ,   ,          ;
       ,         ,          ,      ,      。
 :param arr:                    ,    1,2,3。1   ,2   ,3   ,     ,          。
 :return:          
 """
 if arr is None:
  return -1
 for i in xrange(len(arr) - 1):
  if arr[i] != 1 and arr[i] != 2 and arr[i] != 3:
  return -1
 return self.__process(arr, len(arr)-1, 1, 2, 3)

 def __process(self, arr, i, start, mid, end):
 """
        arr     
 :param arr:            
 :param i:   arr      ,     len(arr)-1
 :return:     ,     arr           ,    -1。
 """
 if i == -1:
  return 0
 if arr[i] != start and arr[i] != end:
  return -1
 if arr[i] == start:
  return self.__process(arr, i-1, start, end, mid) #         ,        
 else: #          。
  count = self.__process(arr, i-1, mid, start, end)
  if count == -1:
  return -1
  return (i * 2) + count

h = Hanoi()
h.hanoi(4)
print h.num
print h.step([3,3,2,1])
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。