河内之塔

编程入门 行业动态 更新时间:2024-10-23 04:46:00
本文介绍了河内之塔-用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 不是 .如果没有这样的磁盘,则返回,因为所有大小为< = 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
  • 更多推荐

    河内之塔

    本文发布于:2023-11-30 03:11:59,感谢您对本站的认可!
    本文链接:https://www.elefans.com/category/jswz/34/1648531.html
    版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
    本文标签:河内

    发布评论

    评论列表 (有 0 条评论)
    草根站长

    >www.elefans.com

    编程频道|电子爱好者 - 技术资讯及电子产品介绍!