河内塔 - 如何在每次递归时不跳过挂钩

Question

我的任务是使用递归解决任意数字的汉诺塔问题。我用 C++ 编写代码。

规则：

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

** 3.一次只能移动一个圆盘，不要回到起点或走出终点。 <- 这就是我目前正在努力解决的问题。 **

以下：开始 --> peg1 <--> peg2 <--> peg3 --> 结束

#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 步。

谢谢！

Answer 1

基本上每次调用都需要执行以下步骤：

将 n-1 叠棋子移动到第 4 个柱子（或向后移动时第 2 个）
将第n个盘子移到中间（第3个柱子）
将 n-1 堆移回第 2 个钉子（即向后移动时第 4 个）
将第n张光盘移动到目的地
将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)

河内塔 - 如何在每次递归时不跳过挂钩

tower of hanoi - How to not skip over a peg every recursion

c++

algorithm

recursion

towers-of-hanoi