c++实现多层汉诺塔问题（信息素养大赛复赛）_汉诺塔c++游戏设计

问题描述

相信大大家应该做过最经典的汉诺塔题目，那什么是多层汉诺塔呢？

【题目描述】 汉诺塔是一个有意思的游戏，每个柱子上套上多个中心有洞的圆盘，每次只能移动一个圆盘，并且每个圆盘不能放在比它面积小的圆盘的上面。现在有三套圆盘并叠加放在一个柱子上了，请移动圆盘，使每个柱子上的圆盘都按照相同的顺序从大到小的摆放好，也就是把三份盘子平均分开。请问对于 n 个不同数量的圆盘（也就是共有 3*n 个盘子），分别在每个柱子上分好 n 个盘子，最少需 要移动多少步？示意图如下图。

【输入格式】 输入共 1 行，包括一个正整数 n

【输出格式】输出共 1 行，一个整数，表示需要移动圆盘的最少的步骤数。

【样例输入】 1

【样例输出】 2

下面是n=3时的示意图：

解题思路

首先我们要知道经典的汉诺塔是怎么解决的，我们就把最经典的称为一阶n层汉诺塔吧，把题目上要做的称为3阶n层汉诺塔（3阶为一层三个盘子，同理一阶为一层一个盘子）。

一阶n层汉诺塔

我们对一阶汉诺塔的思路就是

（1）当n == 1时，直接把盘子从A柱移动到C柱。（n为层数）

（2）当n > 1时，1.将n - 1个盘子从A---->B

                            2.将第n个盘子从A---->C

                            3.将n - 1个盘子从B---->C

我们用一个图片来解释就是：

A----->B

A------>C

B---->C

步骤（2