汉诺塔问题用什么方法解决？汉诺塔问题的通项公式是什么

本文目录

• 汉诺塔问题用什么方法解决
• 汉诺塔问题的通项公式是什么
• 七层的汉诺塔游戏最少几步完成
• 一文带你吃透汉诺塔和其变形题
• 汉诺塔中盘的移动次数与个数的问题是什么
• 4层汉诺塔15步解法
• 28 汉诺塔（Hanoi）问题一个典型的（）问-|||-题-|||-A.查找-|||-B
• 分治算法——汉诺塔问题
• 关于汉诺塔的一个问题

汉诺塔问题用什么方法解决

汉诺塔问题的求解是需要借助于递归方法来实现的。

1、就是我们不管前面有多少个盘子，就是需要将A上面除了最大的盘子之外的所有n-1个盘子借助C移动到B。

2、然后移动A柱子上最大的盘子到C柱子（A-》C），这时候，就无需再考虑最大盘子的移动了，就是剩下的n-1个盘子，怎么把他们从B移动到C上面。

3、我们需要借助的柱子变成了A，因为A上面没有盘子了，问题变成了B柱子借助A柱子，将n-1个盘子移动到C柱子。

计划能力决定圆盘移动顺序

关于汉诺塔问题解决的一个最主要的观点认为，完成汉诺塔任务时要对圆盘的移动顺序进行预先计划和回顾性计划活动。

当问题呈现后，在开始第一步的移动之前，大多数被试都会根据设定好的目标状态，对圆盘的移动顺序进行预先计划。以决定圆盘的移动顺序，但是这种计划能力的作用可能会受到问题难度的影响。

汉诺塔问题的通项公式是什么

汉诺塔通项公式
汉诺塔问题家传户晓，其问题背景不做详述，此处重点讲解在有3根柱子的情况下，汉诺塔问题求解的通项公式的推导。
问题背景：有A，B和C三根柱子，开始时n个大小互异的圆盘从小到大叠放在A柱上，现要将所有圆盘从A移到C，在移动过程中始终保持小盘在大盘之上。求移动盘子次数的最小值。
变量设置：n为圆盘个数，H（k）为n=k时移动盘子次数的最小值。
递推公式： H（k）=2H（k-1）+1。
通项公式：H（k）=2^k-1。
证明：
（1）证明递推公式：首先被移动到C盘的必定是最大的盘子，否则必定违反“在移动过程中始终保持小盘在大盘之上”的规定。既然要将最大盘移动到C，此时最大盘之上必定没有任何盘子，亦即它独自在一根柱子上，要做到这点最优做法当然是先把较小的n-1个盘子由A移动到B，剩下最大盘独自在A。将n-1个盘由A移动到B花费的最少次数为H（n-1）。此时再将最大盘由A移动到C，此时移动总次数为H（n-1）+1。接着把剩下的n-1个盘由B移动到C，花费的最少次数当然也是H（n-1）。于是得到总移动次数2H（n-1）+1.证得H（k）=2H（k-1）+1。
（2）推导通项公式。由H（k）=2H（k-1）+1得H(k)+1=2(H(k-1)+1)，于是{H(k)+1}是首项为H(1)=1，公比为2的等比数列，求得H(k)+1 = 2^k，所以H(k) = 2^k-1

七层的汉诺塔游戏最少几步完成

七层的汉诺塔游戏最少需要127步。

其实算法非常简单，当盘子的个数为n时，移动的次数应等于2^n – 1。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。

首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；

若n为奇数，按顺时针方向依次摆放 A C B。

⑴按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。

⑵接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较大的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。

⑶反复进行⑴⑵操作，最后就能按规定完成汉诺塔的移动。

所以结果非常简单，就是按照移动规则向一个方向移动金片：如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C。汉诺塔问题也是程序设计中的经典递归问题。

扩展资料

汉诺塔是一个关于世界末日的古老的传说，在世界中心贝拿勒斯（在印度北部）的圣庙里，安放着一个汉诺塔，有64块金片。梵天在创造世界的时留下的。由值班的僧侣法则日夜不停地搬运。当搬运完毕时，也就是世界的末日。

汉诺塔是源于印度一个古老传说的益智游戏。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。

大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。随着盘数的增加，需要移动的次数也会越来越多，问题就变得越来越复杂，一个不小心就可能出错。

汉诺塔还有个最关键的问题就是第一步的第一小步是将顶层圆盘挪至辅助柱还是还是目标柱的问题。说它关键，是因为一步错，步步错。第一步走错了，后面再怎么走，也不会走对。

经过推理与分析，找到了问题的答案：若塔层数为奇数，顶层圆盘应首先放在目标柱；若是偶数，则放在辅助柱。

一文带你吃透汉诺塔和其变形题

汉诺塔 （港台： 河内塔 ）（Tower of Hanoi）是根据一个传说形成的数学问题：

有三根杆子A，B，C。A杆上有 N 个 (N》1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

可以将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。

我们从只有一个盘子的时候开始研究。很简单，直接把红色的盘子移到B上就可以了。

步骤：

此时两个盘子都在B上，并且红色盘子在黄色盘子上面

步骤：

根据上面的规律可以知道：

n盘子从A移动到B = 先把 n - 1 个盘子从A移动到C + 把最底下的盘子移动到B + 最后把 n - 1个盘子从C移动到B上

即 ： 公式 H ( n ) = H ( n - 1 ) + 1 + H ( n - 1 )

现在思路清楚了，我们来讲它的两种解法：

假如有2N个盘子，盘子种类有N种，并且每种盘子有两个（这两个大小和颜色完全相同）

新2n盘子从A移动到B = 2 * 之前n个盘子移动次数

因此，依然有两种解法：

假如A和B直接不能直接移动，那么怎么解决？

步骤：

移动n个盘子需要的次数 = 通过C移动n-1个盘子到B的次数 + 把最底部移动到C上的次数 + 通过C再次移动n-1个盘子到A的次数 + 把最底部盘子移动到B上次数 + 通过C把n-1个盘子移动回B的次数

因此，依然有两种解法：

汉诺塔中盘的移动次数与个数的问题是什么

如果有n个盘的话，那么移动次数为 2的n次方-1\x0d\x0a具体证明如下\x0d\x0a对于一个单独的塔，可以进行以下操作：\x0d\x0a1：将最下方的塔的上方的所有塔移动到过渡柱子\x0d\x0a2：将底塔移动到目标柱子\x0d\x0a3：将过渡柱子上的其他塔移动到目标柱子\x0d\x0a可以归纳出第一步与第三步的步数是一样的，设为a\x0d\x0a则总步数为2a+1\x0d\x0a可以得到数列\x0d\x0aAn=2A(n-1)+1\x0d\x0a最后可算得An是\x0d\x0a2的n次方-1

4层汉诺塔15步解法

算法步骤

三阶汉诺塔问题解题步骤

共需7步。

四阶汉诺塔问题解题步骤

共需15步

五阶汉诺塔问题解题步骤

算法采用了分治的思想，利用递归的方式，完成n层汉诺塔的移动。

汉诺塔问题的非递归算法

汉诺塔问题也可以借助非递归算法来解决，有许多种非递归算法可以解决汉诺塔问题，博主认为最常见的是利用递归二叉树，下面列举两种非递归算法。

1.利用二叉递归树

文献指出：汉诺塔问题的递归算法代码与二叉树的中序遍历算法代码十分相似，故采用了二叉树的中序遍历，发现汉诺塔问题的算法步骤正好可以画成一棵完全二叉树，其中序遍历过程就是汉诺塔问题的算法步骤。

函数move(N-1,s,e,t)  N:盘子数  ，s:起始桩   e:目标桩   t:过渡桩

28 汉诺塔（Hanoi）问题一个典型的（）问-|||-题-|||-A.查找-|||-B

递归问题。
相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘。游戏的目标:把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
分析:对于这样一个问题，任何人都不可能直接写出移动盘子的每一步，但我们可以利用下面的方法来解决。设移动盘子数为n，为了将这n个盘子从A杆移动到C杆，可以做以下三步:
(1)以C杆为中介，从A杆将1至n-1号盘移至B杆;
(2)将A杆中剩下的第n号盘移至C杆;
(3)以A杆为中介;从B杆将1至n-1号盘移至C杆。
这样问题解决了，但实际操作中，只有第二步可直接完成，而第一、三步又成为移动的新问题。以上操作的实质是把移动n个盘子的问题转化为移动n-1个盘，那一、三步如何解决?事实上，上述方法设盘子数为n, n可为任意数，该法同样适用于移动n-1个盘。因此，依据上法，可解决n -1个盘子从A杆移到B杆(第一步)或从B杆移到C杆(第三步)问题。现在，问题由移动n个盘子的操作转化为移动n-2个盘子的操作。依据该原理，层层递推，即可将原问题转化为解决移动n -2、n -3… … 3、2，直到移动1个盘的操作，而移动一个盘的操作是可以直接完成的。至此，我们的任务算作是真正完成了。而这种由繁化简，用简单的问题和已知的操作运算来解决复杂问题的方法，就是递归法。在计算机设计语言中，用递归法编写的程序就是递归程序。

分治算法——汉诺塔问题

一、分治算法概念
      “分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

        这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换) 。

        任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。

二、分治法的设计思想

        将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

三、分治策略

        对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

四、分治法实现步骤

①分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；②解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；③合并：将各个子问题的解合并为原问题的解。

它的一般的算法设计模式如下： 　　                                                                                          Divide-and-Conquer(P) 　　                                                                                                         1. if |P|≤n0 　　                                                                                                                              2. then return(ADHOC(P)) 　　                                                                                                    3. 将P分解为较小的子问题 P1 ,P2 ,…,Pk                                                                                     4. for i←1 to k 　　                                                                                                                       5. do yi ← Divide-and-Conquer(Pi)  递归解决Pi 　　                                                                   6. T ← MERGE(y1,y2,…,yk)  合并子问题 　　                                                                             7. return(T)

五、可使用分治法求解的一些经典问题 　　                                                                            （1）二分搜索 

 （2）大整数乘法

（3）Strassen矩阵乘法

（4）棋盘覆盖 

 （5）合并排序

（6）快速排序

（7）线性时间选择

 （8）最接近点对问题

 （9）循环赛日程表

（10）汉诺塔

关于汉诺塔的一个问题

汉诺塔算法介绍：
把三根柱子按顺序排成“品”字型，把所有圆盘按从大到小的顺序放于柱子A上，根据圆盘数量来确定柱子排放的顺序：n若为偶数的话，顺时针方向依次摆放为：A**；而n若为奇数的话，就按顺时针方向依次摆放为：ACB。
这样经过反复多次的测试，最后就可以按照规定完成汉诺塔的移动。因此很简单的，结果就是按照移动规则向一个方向移动金片：如3阶汉诺塔的移动：A→C，A→B，C→B，A→C，B→A，B→C，A→C。