河内塔 - 算法和 Java 实现

河内塔是一个在编程世界的经典问题. 问题设置由三根棒子和n磁盘组成。

磁盘可以从一个插头移动到另一个. n 磁盘有不同的尺寸。

最初,所有磁盘都堆积在第一个塔上,磁盘总是堆积在比自己更大的磁盘上。

河内塔默认设置

$海南大楼设置\n$

这个游戏是由法国数学家埃杜华·卢卡斯(Édouard Lucas)在19世纪发明的,它与一个印度教寺庙的传说有关,据说这个拼图被用来提高年轻神父的精神纪律。

问题声明

1Move all the disks stacked on the first tower over to the last tower using a helper tower in the middle. While moving the disks, certain rules must be followed. These are : 
2
31. Only one disk can be moved.
4
52. A larger disk can not be placed on a smaller disk.

因此,您需要将所有磁盘从第一个塔移动到最后一个塔,您只能一次移动一个磁盘,而绝不能将一个较小的磁盘放置在一个较大的磁盘上。

要做到这一点,你有一个额外的塔,它被称为助手 / 辅助塔。

由于您一次只能移动一个磁盘,所以您移动的磁盘必须位于其塔顶。

河内塔问题的理论解决方案

让我们把塔称为A,B,C,磁盘称为1,2,3.

!(空间/2020/08/屏幕截图2020-08-27-at-5.15.00-PM.png)

我们使用简单的回归来解决这个问题. 要把三个磁盘传到最后的塔上,你需要:

将磁盘号码 1 和 2 带到塔 B.
将磁盘号码 3 移动到塔 C.
将磁盘号码 1 和 2 带到塔 B

当然,由于局限性,你不能这样做,但是,我们可以使用它来创建一个重复执行功能。

TOH 1

在我们写的函数中,我们将打印磁盘的运动。

如何在Java实现河内塔的解决方案

让我们先来了解代码的两个主要部分,来解决河内塔的问题。

1、基础案例

我们的代码中的基本情况是,我们只有一个磁盘,即n = 1。

1if (n == 1)
2        {
3            System.out.println("Take disk 1 from rod " +  from_rod + " to rod " + to_rod);
4            return;
5        }

二、回应呼叫

解决河内塔的回归呼吁如下:

1towerOfHanoi(n-1, from_rod, helper_rod, to_rod);
2        System.out.println("Take disk " + n + " from rod " +  from_rod + " to rod " + to_rod);
3        towerOfHanoi(n-1, helper_rod, to_rod, from_rod);
4    }

它们等同于:

将顶部 n-1 磁盘移动到辅助磁盘
将 1 磁盘从源磁盘移动到目的地磁盘
从辅助磁盘移动到目的地磁盘

河内塔的完整Java实现

 1package com.JournalDev;
 2public class Main {
 3    static void towerOfHanoi(int n, char from_rod, char to_rod, char helper_rod)
 4    {
 5        if (n == 1)
 6        {
 7            System.out.println("Take disk 1 from rod " +  from_rod + " to rod " + to_rod);
 8            return;
 9        }
10        towerOfHanoi(n-1, from_rod, helper_rod, to_rod);
11        System.out.println("Take disk " + n + " from rod " +  from_rod + " to rod " + to_rod);
12        towerOfHanoi(n-1, helper_rod, to_rod, from_rod);
13    }
14
15    public static void main(String args[])
16    {
17        int n = 5;
18        towerOfHanoi(n,'A','C', 'B');
19    }
20
21}

代码的输出是:

1Take disk 1 from rod A to rod C
2Take disk 2 from rod A to rod B
3Take disk 1 from rod C to rod B
4Take disk 3 from rod A to rod C
5Take disk 1 from rod B to rod A
6Take disk 2 from rod B to rod C
7Take disk 1 from rod A to rod C

Tower of Hanoi Output

我们可以使用下面的图像来理解这个过程,您可以运行任何数量的磁盘的代码。

n = 5 的输出是:

 1Take disk 1 from rod A to rod C
 2Take disk 2 from rod A to rod B
 3Take disk 1 from rod C to rod B
 4Take disk 3 from rod A to rod C
 5Take disk 1 from rod B to rod A
 6Take disk 2 from rod B to rod C
 7Take disk 1 from rod A to rod C
 8Take disk 4 from rod A to rod B
 9Take disk 1 from rod C to rod B
10Take disk 2 from rod C to rod A
11Take disk 1 from rod B to rod A
12Take disk 3 from rod C to rod B
13Take disk 1 from rod A to rod C
14Take disk 2 from rod A to rod B
15Take disk 1 from rod C to rod B
16Take disk 5 from rod A to rod C
17Take disk 1 from rod B to rod A
18Take disk 2 from rod B to rod C
19Take disk 1 from rod A to rod C
20Take disk 3 from rod B to rod A
21Take disk 1 from rod C to rod B
22Take disk 2 from rod C to rod A
23Take disk 1 from rod B to rod A
24Take disk 4 from rod B to rod C
25Take disk 1 from rod A to rod C
26Take disk 2 from rod A to rod B
27Take disk 1 from rod C to rod B
28Take disk 3 from rod A to rod C
29Take disk 1 from rod B to rod A
30Take disk 2 from rod B to rod C
31Take disk 1 from rod A to rod C

TOH for n=5

计算 n 磁盘的步骤数的公式是:

1(2^n)-1

结论

这就是你如何使用回归来解决河内塔,希望你与我们一起学习有趣!