河内塔算法： Python, C++ 代码

由： 陈莎拉 陈莎拉
Hours 更新

汉诺塔是什么？

汉诺塔是一道数学难题，由三根杆和多个叠放在一起的圆盘组成。它也被称为梵天塔或卢卡斯塔，因为法国数学家爱德华·卢卡斯早在 1883 年就发明了它。这个难题基于在三根杆之间移动金盘的传说。

这个拼图有三根杆和数量不定的堆叠圆盘。这些杆设计成循环塔。因此，直径较大的圆盘堆叠在底部，较小的圆盘堆叠在顶部。

最初，我们得到三根木桩或杆。其中一根（A，如示例中所示）上堆叠了所有圆盘。我们的目标是遵循一些特定规则，将一整叠圆盘从一根杆（A）移到另一根杆（C）。

这是谜题的初始设置-

汉诺塔问题
汉诺塔问题

这是最终目标-

汉诺塔

汉诺塔规则

以下是汉诺塔的一些基本规则：

  • 此谜题的初始状态是，所有圆盘将堆叠在第一根杆中。
  • 最终状态是，第一根杆上的所有圆盘将堆叠在第二根杆或第三根杆上。
  • 我们可以随时将磁盘从一根杆移动至另一根杆。
  • 我们只能移动杆上最上面的圆盘。
  • 一个磁盘不能放置在另一个较小的磁盘上。

最初的传说是关于移动 64 个盘子的。根据规则，牧师每次只能移动一个盘子。根据传说，有一个预言说，如果他们能完成这一行为，世界就会灭亡。在时间复杂度部分，我们将展示一个由 n 个盘子组成的汉诺塔设置需要 2^n – 1 步。

因此，如果牧师需要 1 秒钟来移动圆盘，那么他们解决这个难题所需的总时间将是 2^64 - 1 秒，即 584,942,417,356 年、26 天、7 小时、15 秒。

汉诺塔算法

解决汉诺塔问题的一个通用方法是递归算法。首先，我们需要确定两个杆或桩作为源和目标，而备用桩将是辅助物或助手。

以下是解决汉诺塔难题的步骤：

  • 将最上面的 n-1 个盘子从源桩移到辅助桩。
  • 然后，将第 n 个盘子从源桩移到目标桩。
  • 最后，将剩下的 n-1 个盘子从辅助桩移到目标桩。

备注：如果我们有一个磁盘，我们可以直接将其从源移动到目标。

如何解决汉诺塔难题

让我们说明三个圆盘的算法，并将 A 桩视为源，B 桩视为辅助桩，C 桩视为目标桩

步骤1） 最初，所有圆盘都堆放在 A 柱上。

解答汉诺塔谜题

在这个阶段：

来源=Peg A
目的地 = Peg C
助手 = Peg B

现在，我们需要将最上面的 n-1 个盘子从源盘子移到辅助盘子。

请注意： 虽然我们一次只能移动一个磁盘，但它将我们的问题从 3 个磁盘的问题分解为 2 个磁盘的问题，这是一个递归调用。

步骤2） 当我们从挂钩 A 进行递归调用且目的地是挂钩 B 时，我们将使用挂钩 C 作为辅助。

请注意，对于同样的两个圆盘的汉诺塔问题，我们再次处于第一阶段。

现在我们需要将 n-1 或一个盘子从源移动到辅助盘子，将最小的盘子从 A 桩移动到 C 桩。

解答汉诺塔谜题

在这个阶段：

来源=挂钩A
目的地 = 挂钩 B
助手 = 钉 C

步骤3） 然后，根据我们的算法，第 n 个或第 2 个磁盘需求应该转移到目的地或挂钩 B。

解答汉诺塔谜题

在这个阶段：

来源=挂钩A
目的地 = 挂钩 B
助手 = 钉 C

步骤4） 现在，我们将根据算法的第三阶段，将 n-1 个盘子或盘子一从辅助盘子或桩 C 移动到目标盘子或桩 B。

解答汉诺塔谜题

在这个阶段：

来源=挂钩A
目的地 = 挂钩 B
助手 = 钉 C

相关文章

步骤5） 当完成递归调用之后，我们会回到之前算法第一阶段的设置。

步骤6） 现在，在第二阶段，我们将源移动到目的地，即将磁盘 3 从钉 A 移动到钉 C。

在这个阶段：

来源=挂钩A
目的地 = 挂钩 C
助手 = 钉 B

步骤7） 现在我们可以看到

解答汉诺塔谜题

d 是将剩余的盘子从辅助位置（桩 B）移动到目标位置（桩 C）。在这种情况下，我们将使用初始源或桩 A 作为辅助位置。

步骤8） 由于我们不能同时移动两个盘子，我们将对盘子 1 进行递归调用。根据上一步和我们的 算法，此步骤的目的地是钉 A。

解答汉诺塔谜题

在这个阶段：

来源=挂钩B
目的地 = 挂钩 A
助手 = 钉 C

步骤9） 现在我们的递归调用已经完成。然后我们将磁盘 2 从其源移动到其目标。

解答汉诺塔谜题

在这个阶段：

来源=挂钩B
目的地 = 挂钩 C
助手 = 钉 A

步骤10） 然后我们将剩下的 n-1 或磁盘 1 从辅助磁盘移动到目标磁盘。

解答汉诺塔谜题

在这个阶段：

来源=挂钩A
目的地 = 挂钩 C
助手 = 钉 B

汉诺塔的伪代码

START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
  		IF disk == 1, THEN
      			move disk from source to dest             
   		ELSE
     			Tower_Of_Hanoi (disk - 1, source, helper, dest)     
      			move disk from source to dest          
      			Tower_Of_Hanoi (disk - 1, helper, dest, source)     
   		END IF   
END Procedure

程序代码 C++

#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
  if (num == 1) {
    cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
    return;
  }
  tower_of_hanoi(num - 1, source, helper, dest);
  cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
  tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
  int num;
  cin >> num;
  printf("The sequence of moves :\n");
  tower_of_hanoi(num, "I", "III", "II");
  return 0;
}

输出

3
The sequence of moves :
Move disk 1 from tower I to tower III
Move disk 2 from tower I to tower II
Move disk 1 from tower III to tower II
Move disk 3 from tower I to tower III
Move disk 1 from tower II to tower I
Move disk 2 from tower II to tower III
Move disk 1 from tower I to tower III

程序代码 Python

def tower_of_hanoi(n, source, destination, helper):
	if n==1:
		print ("Move disk 1 from peg", source," to peg", destination)
		return
	tower_of_hanoi(n-1, source, helper, destination)
	print ("Move disk",n," from peg", source," to peg", destination)
	tower_of_hanoi(n-1, helper, destination, source)		
# n = number of disks
n = 3
tower_of_hanoi(n,' A','B','C')

输出：

Move disk 1 from peg A to peg B
Move disk 2 from peg A to peg C
Move disk 1 from peg B to peg C
Move disk 3 from peg A to peg B
Move disk 1 from peg C to peg A
Move disk 2 from peg C to peg B
Move disk 1 from peg A to peg B

汉诺塔的复杂性

以下是汉诺塔的时间和空间复杂度：

1）时间复杂度：

如果我们回顾一下我们的算法，我们可以看到我们引入了两次对 (n-1) 个盘子的递归调用。对 (n-1) 个盘子的递归调用可以分解为其他 ((n-1)-1) 等等，直到我们只移动一个盘子。

对于三个磁盘-

  • 磁盘 3 对磁盘 XNUMX 调用两次递归函数。
  • 磁盘 2 对磁盘 XNUMX 调用两次递归函数。
  • 圆盘 1 可以在恒定时间内移动，并且需要时间来求解三个圆盘。

= 2*(解决两个盘子的时间) + 移动盘子 3 的常数时间

= 2*(2*求解一个圆盘的时间 + 移动圆盘 2 的常数时间) + 移动圆盘 3 的常数时间

= (2*2) (移动磁盘 1 的恒定时间) + 2*移动磁盘 2 的恒定时间 + 移动磁盘 3 的恒定时间

对于 n 个磁盘，可以写成 -

(2正1 * 移动磁盘 1 + 2 的常数时间正2 * 移动磁盘 2 + ...的恒定时间。

这个几何级数将导致 O(2正1），或 （2）n), 它是指数的。

2）空间复杂度

汉诺塔的空间复杂度是 0(n)。这是因为我们需要存储盘子的顺序。当我们使用递归时，它使用堆栈。堆栈的最大大小可以是“n”。这就是空间复杂度变成 O(n) 的原因。

你可能会喜欢：