河内塔问题

河内塔是一个难题的问题。我们有三个看台和n个光盘。最初，将光盘放置在第一支架中。我们必须将光盘放入第三个或目标支架，第二个或辅助支架可以用作帮助支架。

• 但是要遵循一些规则。

•  每个动作我们只能传送一张光盘。

• 只能从架子上取出最上面的光盘。

• 较大的光盘不会放在较小的光盘的顶部。

此问题可以通过递归轻松解决。首先，使用递归，将前(n-1)个光盘从源放置到辅助支架，然后将最后一个光盘从源放置到目标，然后再次将(n-1)光盘从辅助支架放置到目的支架。

输入输出

Input:
Number of discs: 3
Output:
1. Move disk 1 from A to C
2. Move disk 2 from A to B
3. Move disk 1 from C to B
4. Move disk 3 from A to C
5. Move disk 1 from B to A
6. Move disk 2 from B to C
7. Move disk 1 from A to C

算法

toh(n, s, a, d)

输入：光盘数量，来源，辅助，目的地。

输出：将光盘从源移动到目标的步骤，并保持正确的规则。

Begin
   if n = 1, then
      display move disc from s to d
   toh(n-1, s, d, a)

   display move disc from s to d
   toh(n-1, a, s, d)
End

示例

#include<iostream>
using namespace std;

void TOH(int n, char s, char a, char d) {
   static int count = 0;          //store number of counts
   if(n == 1) {
      count++;
      cout << count<< ". Move disk " << n << " from "<<s <<" to "<<d<<endl;
      return;      //base case, when only one disk
   }

   TOH(n-1, s, d, a);               //recursive call the function
   count++;
   cout << count<< ". Move disk " << n << " from "<<s <<" to"<<d<<endl;
   TOH(n-1, a, s, d);
}

int main() {
   int n;
   cout << "Enter the number of disks: ";
   cin >> n;
   TOH(n, 'A','B','C');
}

输出结果

Enter the number of disks: 3
1. Move disk 1 from A to C
2. Move disk 2 from A to B
3. Move disk 1 from C to B
4. Move disk 3 from A to C
5. Move disk 1 from B to A
6. Move disk 2 from B to C
7. Move disk 1 from A to C