algorithm - Hanoi tower recursion with a move function that moves indexed rings

Question

I've got a problem with a Hanoi tower recursion problem. I'm given a move function that takes 2 arguments :

• j (the index of a ring : 1 -> n from bottom to top) and
• a position.

I've found a way to the recursive problem without using this function but I'm stuck when I need to use it. In fact, I don't know how to change my j variable efficiently.

moveTower(n, position1, position2):
    if n > 1:
        moveTower(n-1, position1, aux)
        move(j, position2) """ That's where i'm stuck """
        moveTower(n-1, aux, position2)
    else:
        move(j, position2)

I've found some pattern for the evolution of j:

For example with 3 rings :

j = 3
j = 2
j = 3
j = 1
j = 3
j = 2
j = 3

标签： algorithmrecursiontowers-of-hanoi

Answer 1

我相信最简单的计算方法j是注意到它总是与position1和不同position2。所以你可以写一个嵌套的if/else，或者你可以将它作为第三个参数显式传递，或者如果你想要一些聪明的魔法，使用：

j = 6 - position1 - position2

这里的想法是6 = 1 + 2 + 3，所以这计算j为其中一个(1,2,3)不是 position1或position2。