河内塔-如何不跳过每个递归钉 [英] tower of hanoi - How to not skip over a peg every recursion

问题描述

我的任务是使用递归来解决河内塔的任何数目。我用C ++写了代码。

My assignment is to solve the Towers of Hanoi for any number using recursion. I wrote my code in C++.

规则：

1. 不能在一个较小的磁盘上堆叠一个较大的磁盘。


2. 一次不能移动多个磁盘。

**
3.一次仅将磁盘移动一个钉，而无需回到起点或终点。 <-这是我目前正在努力的目标。
**

** 3. Only move a disk one peg at a time without going back to the start or going out of the end. <- This is what i'm currently struggling with. **

以下内容：START-> peg1<-> peg2<-> peg3-> END

Following: START --> 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个磁盘的示例代码放置

Example for 3 Disks, the code puts

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个磁盘放置算法的示例：

Example of what I need the algorithm to put for 3 Disks:

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

我是如此迷失，我不知道如何使代码不让磁盘跳过钉住。

I am so lost, I have no idea how to make the code not let the disk skip a peg. It's probably staring me right in the face but i cannot for the life of me figure it out.

请忽略for循环 i和 j，这些是我的一生。这样，如果结果太大，它将打印出前100步，最后100步。

Please ignore the for loops 'i' and 'j', those were made so that if the results get too big, it will print the first 100 moves and the last 100 moves.

谢谢！

推荐答案

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

Basically on each call you need to do the following steps:

1. 将n-1个光盘移动到第4个钉子（或向后移动到第2个钉子）

1. Move the n-1 stack of discs to the 4th peg (or 2nd when going backwards)

将第n个光盘移动到中间（第3个钉子） ）

Move the nth disc to the middle (3rd peg)

将n-1堆栈移回第二个钉子（即向后移动到第四个钉子）

Move the n-1 stack back to the 2nd peg (i.e. 4th when going backwards)

将第n张光盘移动到目标位置

Move the nth disc to its destination

将n-1堆栈移动到目标位置

Move the n-1 stack to the destination

因此，您需要3次没有记忆的递归调用。

So you need 3 recursive calls without memoization.

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)

这篇关于河内塔-如何不跳过每个递归钉的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！