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