汉诺塔怎么玩（汉诺塔）

汉诺塔是计算机学教科书中常用的游戏               ，用来说明递归的魔力               。该游戏有3个柱子和一组不同大小的圆盘 
 
  
 
  
 
  
 
  
 
  
 
  
 
  
，柱子从圆盘的中心穿过 
 
  
 
  
 
  
 
  
 
  
 
  
 
  
。

题目描述

设abc是三个塔座













，开始时
  
  
  
  
  
  
  
 ，在塔座a 上有一叠共n个圆盘 
  
  
  
  
  
  
 ，这些圆盘自下而上 


 


 


 


 


 


 


 
，由大到小地叠放在一起
 
 
 
 
 
 
 
，各圆盘从小到大编号为1,2,3,...,n













。

现要求将塔座a 上的一叠圆盘移到塔座 b 上  
   
   
   
   
   
   
  ，并仍按同样顺序叠置
  
  
  
  
  
  
  
 。在移动圆盘是应遵守以下移动规则：

每次只能移动一个圆盘；

任何时刻都不允许将较大的圆盘压在较小的圆盘之上；

在满足移动规则1和2的前提下 

 

 

 

 

 

 

 
，可以将圆盘移至a,b,c中任一塔座上 
  
  
  
  
  
  
 。

要求打印出出若干行

 

 

 

 

 

 

 
，每行表示盘子的一次移动

如：1 a->c 表示将 a 号圆盘从 塔座移到 c 塔座

输入

一行：n表示表示初始时 a塔有 c 个圆盘

输出

未知行数

每行表示一次移动：

格式：圆盘编号 塔的编号->塔的编号

如：1 a->c 表示将 号圆盘从 a 塔座移到 c 塔座

样例输入 2 样例输出 1 A->C 2 A->B 1 C->B

游戏开始时               ，所有圆盘叠放在左侧第一个柱子上 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
，如下图所示：

游戏的目标是将所有的圆盘从第一个柱子移动到第三个柱子














，同时遵守以下规则：

① 除了被移动时                      ，所有圆盘都必须放在柱子上 


 


 


 


 


 


 


 
。

② 一次只能移动一个圆盘
 
 
 
 
 
 
 
。

③ 圆盘不能放置在比它小的圆盘上面  
   
   
   
   
   
   
  。

现在来看一看游戏的一些玩法示例 

 

 

 

 

 

 

 
。最简单的情况是当只有一个圆盘时：在这种情况下 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
，只要将圆盘从第一个柱子移动到第三个柱子就可以一次性完成游戏

 

 

 

 

 

 

 
。

如果有两个圆盘





















，则需要通过 3 个步骤解决这个游戏：

① 将圆盘从第一个柱子移动到第二个柱子（它必须是最上面的一个)               。

② 将圆盘从第一个柱子移动到第三个柱子 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
。

③ 将圆盘从第二个柱子移动到第三个柱子














。

请注意               ，虽然游戏的目的是将圆盘从第一个柱子移动到第三个柱子 
 
  
 
  
 
  
 
  
 
  
 
  
 
  
，但是有必要使用第二个柱子作为一些圆盘的临时安放位置                      。解决方案的复杂性随着要移动的圆盘数量的增加而迅速增加 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
。

移动 3 个圆盘需要 7 步移动













，如下图所示：

这个游戏有一个迷人的传说





















。根据这个传说
  
  
  
  
  
  
  
 ，河内寺庙里有一群僧侣 
  
  
  
  
  
  
 ，他们有 3 个柱子和 64 个圆盘               。这些圆盘最初堆放在第一个柱子上 


 


 


 


 


 


 


 
，而僧侣们则需要将它们移动到第三个柱子上 
 
  
 
  
 
  
 
  
 
  
 
  
 
  
。当僧侣们完成任务时
 
 
 
 
 
 
 
，世界将会消亡













。

现在回到这个问题本身  
   
   
   
   
   
   
  ，来考虑当圆盘的数量不做限制时 

 

 

 

 

 

 

 
，一般情况下的解决方案
  
  
  
  
  
  
  
 。

这个问题可以被描述为：将 n 个圆盘从第一个柱子移动到第三个柱子

 

 

 

 

 

 

 
，使用第二个柱子作为临时柱子 
  
  
  
  
  
  
 。

要理解如何使用循环解决这个问题是非常困难的               ，但令人高兴的是 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
，设想一个递归解决方案并不困难：如果可以（递归地）将 n-1 个圆盘从第一个柱子移动到第二个柱子














，而使用第三个柱子作为临时挂钩                      ，那么最大的圆盘将独自放在第一个柱子上 


 


 


 


 


 


 


 
。然后就可以一次性把最大圆盘从第一个柱子移动到第三个柱子
 
 
 
 
 
 
 
。接下来 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
，可以（递归地）将 n-1 个圆盘从第二个柱子移动到第三个柱子





















，这次使用第一个柱子作为临时柱子  
   
   
   
   
   
   
  。

so:

#include <bits/stdc++.h> using namespace std; void f(int n,char x,char y,char z) { if(n==0) return; f(n-1,x,z,y); cout <<n << << x << "->" << z << endl; f(n-1,y,x,z); } int main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); int n; cin >> n; f(n,A,C,B); return 0; }