河内塔 - 如何在每次递归时不跳过钉子

我的任务是使用递归求解任意数字的河内塔。我用 C++ 编写了代码。

Rules:

1. 无法将较大的磁盘堆叠在较小的磁盘之上。
2. 一次无法移动多个磁盘。

** 3. 一次只移动一个圆盘，不要回到起点或离开终点。

如下： 开始 --> peg1 peg2 peg3 --> END

#include <iostream>
#include <time.h>
using namespace std;
void move(int, int, int, int, int, int);
int i, j, l, n;
const int start = 1, end = 5, aux1 = 2, aux2 = 3, aux3 = 4;
int main(){
    double time = 0;
    clock_t begin, stop;
    begin = clock();
    for(n = 10; n>=1; n--){
        l = 0, i = 0, j = 0;
        move(n, start, end, aux1, aux2, aux3);
        cout << "Number of disks moved: " << n << endl;
        cout << "Number of moves made: " << l << endl;
    }
    stop = clock();
    time = (stop - begin)/1000.00;  
    cout << "Game solved in: " << time << " miliseconds";
    return 0;
}
void move(int n, int start, int end, int aux1, int aux2, int aux3){
    if(n>0){
        l++;
        if(i>=100){
            j++;
            if(l - j == i){
                move(n-1, start, aux1, aux2, aux3, end);
                cout << "Move disc " << n << " from peg " << start << " to peg " << end << endl;
                move(n-1, aux1, aux2, aux3, end, start);
            }
        }
        if(i<=100){
                i++;
                move(n-1, start, aux1, aux2, aux3, end);
                cout << "Move disc " << n << " from peg " << start << " to peg " << end << endl;
                move(n-1, aux1, end, aux3, aux2, start);
        }
    }
}

以 3 个磁盘为例，代码如下

Move disc 1 from peg 1 to peg 3
Move disc 2 from peg 1 to peg 2
Move disc 1 from peg 3 to peg 2
Move disc 3 from peg 1 to peg 5
Move disc 1 from peg 2 to peg 4
Move disc 2 from peg 2 to peg 5
Move disc 1 from peg 4 to peg 5
Number of disks moved: 3
Number of moves made: 7

我需要为 3 个磁盘放置算法的示例：

Move disc 1 from peg 1 to peg 2 
Move disc 1 from peg 2 to peg 3
Move disc 1 from peg 3 to peg 4
Move disc 2 from peg 1 to peg 2
Move disc 2 from peg 2 to peg 3
Move disc 1 from peg 4 to peg 3
Move disc 1 from peg 3 to peg 2
Move disc 2 from peg 3 to peg 4
Move disc 1 from peg 2 to peg 3
Move disc 1 from peg 3 to peg 4
Move disc 3 from peg 1 to peg 2
Move disc 3 from peg 2 to peg 3
Move disc 1 from peg 4 to peg 3
Move disc 1 from peg 3 to peg 2
Move disc 2 from peg 4 to peg 3
Move disc 1 from peg 2 to peg 3
Move disc 1 from peg 3 to peg 4
Move disc 2 from peg 3 to peg 2
Move disc 1 from peg 4 to peg 3
Move disc 1 from peg 3 to peg 2
Move disc 3 from peg 3 to peg 4
Move disc 3 from peg 4 to peg 5
Move disc 1 from peg 2 to peg 3
Move disc 1 from peg 3 to peg 4
Move disc 2 from peg 2 to peg 3
Move disc 1 from peg 4 to peg 3
Move disc 1 from peg 3 to peg 2
Move disc 2 from peg 3 to peg 4
Move disc 2 from peg 4 to peg 5
Move disc 1 from peg 2 to peg 3
Move disc 1 from peg 3 to peg 4
Move disc 1 from peg 4 to peg 5
Number of disks moved: 3
Number of moves made: 32

我很迷茫，我不知道如何使代码不让磁盘跳过一个钉子。它可能就在我面前，但我一辈子都无法弄清楚。

请忽略 for 循环“i”和“j”，这些循环的目的是如果结果太大，它将打印前 100 步和最后 100 步。

谢谢你！

基本上每次通话时您都需要执行以下步骤：

1. 将 n-1 堆圆盘移至第 4 个钉子（向后移动时则移至第 2 个）

2. 将第 n 个圆盘移至中间（第 3 个钉子）

3. 将 n-1 堆栈移回第 2 个钉子（即向后移动时的第 4 个钉子）

4. 将第 n 个光盘移动到目的地

5. 将 n-1 堆栈移动到目的地

所以你需要 3 次递归调用而不需要记忆。

function hanoi5(n) {
  let out = []
  move(n, 0, 4)
  console.log(out.length + " steps")
  console.log(out.join("\n"))
  function move(n, from, to) {
    if (n == 1) {
      let dir = from < to ? 1 : -1
      for (let i = from; i != to; i += dir)
        out.push("move disc 1 from peg " + (i+1) + " to peg " + (i+1+dir))
    } else if (from < to) {
      move(n - 1, from, 3)
      for (let i = from; i < 2; i++)
        out.push("move disc " + n + " from peg " + (i+1) + " to peg " + (i+2))
      move(n - 1, 3, 1)
      for (let i = 2; i < to; i++)
        out.push("move disc " + n + " from peg " + (i+1) + " to peg " + (i+2))
      move(n - 1, 1, to)
    } else {
      move(n - 1, 3, 1)
      out.push("move disc " + n + " from peg 3 to peg 2")
      move(n - 1, 1, 3)
      out.push("move disc " + n + " from peg 2 to peg 1")
      move(n - 1, 3, 1)
    }
  }
}

hanoi5(3)