河内之塔-用Python解决中途算法 [英] Tower Of Hanoi - Solving Halfway Algorithm in Python
问题描述
可以半途解决河内塔吗?我已经进行了广泛的研究，以寻找可以中途解决用户配置问题的代码，但是我还没有找到.这是一项作业，我要求代码从用户停止求解的位置开始接管，并继续为用户解决该问题，而无需将难题重置为平方.
Is it possible to solve tower of hanoi halfway? I've done extensive research to look for codes that solves the user's configuration halfway but I've yet to find one. This is for an assignment and I require the code to take over from where the user has stopped solving and continue solving it for the user, without resetting the puzzle to square one.
我知道有一些递归算法很容易找到，但这不是我要寻找的.我正在寻找可以从用户解决的地方接手的算法，然后从那里继续解决.有什么想法吗?
I understand that there are recursion algorithms out there readily available but that is not what I'm searching for. I'm searching for algorithms that can take over from where the user has solved until, and then continue solving from there. Any ideas?
到目前为止，我想出了一种算法，该算法将优化算法(通过递归完成)存储到数组中，然后检查用户输入是否等于数组中的任何输入，然后继续从那里解决.但是，问题出在优化算法数组中找不到用户的配置时.
So far, I've come up with an algorithm that stores the optimized algorithms( which is being done by recursion) into an array, and then checks if the user's input is equal to any found in the array, and then continue solving from there. However, the problem lies when the user's configuration is not found in the optimized algorithm array.
以下是我到目前为止的代码(我已经排除了stack.py代码):
The following are my codes so far ( I've excluded the stack.py codes):
def solveHalfway(n, start, end, middle, count):
gameInstance.stackA = [3,2]
gameInstance.stackB = []
gameInstance.stackC = [1]
loopCounter = 0 # initialise loopCounter as 0
moveCounter = 0 # initialise the move index the user is stuck at
indicator = 0 # to indicate whether the user's config equals the solution's config
while loopCounter < arrayOfStacks.size(): # while loopCounter size has not reached the end of arrayOfStacks
if loopCounter != 0 and loopCounter % 3 == 0: # if 3 stacks have been dequeued
moveCounter += 1
if gameInstance.getUserConfig() == tempStack.data: #check whether user's config is equal to the solution's config
indicator += 1
print "User is stuck at move: ", moveCounter #this will be the current move the user is at
while arrayOfStacks.size() != 0: # while not the end of arrayOfStacks
correctMovesStack.push(arrayOfStacks.dequeue()) # add the moves to correctMovesStack
if correctMovesStack.size() == 3: # if 3 stacks have been dequeued
print "Step:", moveCounter , correctMovesStack.data # display the step number plus the correct move to take
moveCounter+=1 # increase move by 1
while correctMovesStack.size() != 0: # if correct moves stack isn't empty
correctMovesStack.pop() # empty the stack
return
else:
while tempStack.size() != 0: # check if tempStack is empty
tempStack.pop() # empty tempStack so that it can be used for the next loop
tempStack.push(arrayOfStacks.dequeue()) #dequeue from arrayOfStacks for a total of 3 times and push it to tempStack
else:
tempStack.push(arrayOfStacks.dequeue()) #dequeue from arrayOfStacks for a total of 3 times and push it to tempStack
loopCounter +=1 # increase loop counter by 1
if indicator == 0:
moveWith3Towers(noOfDisks, stackA, stackC, stackB, count)
print indicator
推荐答案
要从任意位置求解河内塔，您可以使用类似于从标准起始位置开始工作的标准解决方案的递归程序.
To solve the Towers of Hanoi from an arbitrary position, you can use a recursive procedure similar to the standard solution that works from the standard start position.
它必须更一般一些.
编写一个递归过程 moveDisks(maxSize，targetPeg)，将所有大小为< = maxSize 的磁盘移动到钉 targetPeg ，像这样:
Write a recursive procedure moveDisks(maxSize,targetPeg) that moves all the disks with size <= maxSize to the peg targetPeg, like this:
-
查找最大磁盘 m ，以使 m.size< = maxSize 和 m 不是 targetPeg 上的em>.如果没有这样的磁盘，则返回，因为所有大小为< = maxSize 的磁盘都已放置在正确的位置.
Find the largest disk m such that m.size <= maxSize and m is not on targetPeg. If there is no such disk, then return, because all the disks with size <= maxSize are already in the right place.
让 sourcePeg 为当前 m 的钉子，让 otherPeg 为非的钉子> sourcePeg 或 targetPeg .
Let sourcePeg be the peg where m is currently, and let otherPeg be the the peg that isn't sourcePeg or targetPeg.
递归调用 moveDisks(m.size-1，otherPeg)以获取较小的磁盘.
Call moveDisks(m.size-1, otherPeg) recursively to get the smaller disks out of the way.
将 m 从 sourcePeg 移至 targetPeg .
递归调用 moveDisks(m.size-1，targetPeg)，将较小的磁盘放在它们所属的位置.
Call moveDisks(m.size-1, targetPeg) recursively to put the smaller disks where they belong.
在python中，我会这样写.请注意，我对游戏状态使用了不同的表示形式，该表示形式更适合此算法，并且不允许出现任何非法位置:
In python, I would write it like this. Note that I used a different representation for the game state that works better for this algorithm and doesn't allow any illegal positions:
#
# Solve Towers of Hanoi from arbitrary position
#
# diskPostions -- the current peg for each disk (0, 1, or 2) in decreasing
# order of size. This will be modified
# largestToMove -- move this one and all smaller disks
# targetPeg -- target peg for disks to move
#
def moveDisks(diskPositions, largestToMove, targetPeg):
for badDisk in range(largestToMove, len(diskPositions)):
currentPeg = diskPositions[badDisk]
if currentPeg != targetPeg:
#found the largest disk on the wrong peg
#sum of the peg numbers is 3, so to find the other one...
otherPeg = 3 - targetPeg - currentPeg
#before we can move badDisk, we have get the smaller ones out of the way
moveDisks(diskPositions, badDisk+1, otherPeg)
print "Move ", badDisk, " from ", currentPeg, " to ", targetPeg
diskPositions[badDisk]=targetPeg
#now we can put the smaller ones in the right place
moveDisks(diskPositions, badDisk+1, targetPeg)
break;
测试:
> moveDisks([2,1,0,2], 0, 2)
Move 3 from 2 to 0
Move 1 from 1 to 2
Move 3 from 0 to 1
Move 2 from 0 to 2
Move 3 from 1 to 2
这篇关于河内之塔-用Python解决中途算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
