当前位置：首页 - 正文

汉诺塔问题通项公式

发布网友发布时间：2022-04-30 15:39

我来回答

共4个回答

热心网友时间：2022-06-26 13:22

通项公式：H（k）=2^k-1。

汉诺塔游戏是在一块铜板装置上，有三根杆(编号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可为任意数，该法同样适用于移动n-1个盘。因此，依据上法，可解决n -1个盘子从A杆移到B杆(第一步)或从B杆移到C杆(第三步)问题。现在，问题由移动n个盘子的操作转化为移动n-2个盘子的操作。

依据该原理，层层递推，即可将原问题转化为解决移动n -2、n -3… … 3、2，直到移动1个盘的操作，而移动一个盘的操作是可以直接完成的。

扩展资料：

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

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

也有研究者认为，不是计划能力而是抑制能力参与汉诺塔问题的解决过程。为了把更大的圆盘先放置于指定位置，必须让较小的圆盘暂时偏离其最终应该放置的位置，但被试的自然反应总是“尽快”将圆盘移动到最终的目的地，如此反而导致错误，使移动步数更多，完成时间更长。

热心网友时间：2022-06-26 13:22

汉诺塔通项公式

汉诺塔问题家传户晓，其问题背景不做详述，此处重点讲解在有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

热心网友时间：2022-06-26 13:23

付费内容限时免费查看回答亲亲，上午好呀，答案已经为您整理好了呢：汉诺塔的通项公式递推公式: H(k)=2H(k-1)+1。通项公式(有n个圆盘,全部完成需要的次数):sum=2^n-1。

汉诺塔问题的递推公式：M（n）=2M(N-1)+1=2N-1;从汉诺塔问题的解法看出来，它是将输入规模为n的问题变成了一个输入规模为2N的问题，从道理上看，它是将原来输入规模扩大了，而不是减少了，所以问题的解题时间为2n。

热心网友时间：2022-06-26 13:23

【1,2,3】这个递归编号相同的行，如果单拿出来，是AB,BC.CA,或AC.CB.BA的循环的。

【1】，【2】【1，2】【123】【3】【4】这就是编号。这是人类智能的洗数据结果。我发现地。。。图是落樱提供地。

这是直接产生移动指令的规律。不需要栈模拟。

声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。
E-MAIL:11247931@qq.com

焦点

汉诺塔问题通项公式

最新推荐

猜你喜欢

热门推荐