解决河内塔问题采用啥方法

⑴ “河内塔问题”的解法

汉诺塔问题（又称河内塔问题）是根据一个传说形成的一个问题：

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

1. 每次只能移动一个圆盘；
2. 大盘不能叠在小盘上面。

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

问：如何移？最少要移动多少次？
一般取N=64。这样，最少需移动264-1次。即如果一秒钟能移动一块圆盘，仍将需5845.54亿年。目前按照宇宙大爆炸理论的推测，宇宙的年龄仅为137亿年。

在真实玩具中，一般N=8；这将需移动255次。如果N=10，需移动1023次。如果N=15，需移动32767次；这就是说，如果一个人从3岁到99岁，每天移动一块圆盘，他仅能移动15块。如果N=20，需移动1048575次，即超过了一百万次。
先看hanoi(1, one, two, three)的情况。这时直接将one柱上的一个盘子搬到three柱上。注意，这里one柱或three柱到底是A、B还是C并不重要，要记住的是函数第二个参数代表的柱上的一个盘被搬到第四个参数代表的柱上。为方便，将这个动作记为：
one =》three

再看hanoi(2, one, two, three)的情况。考虑到hanoi(1)的情况已经分析过了，可知这时实际上将产生三个动作，分别是：
one =》two
one =》three
two =》three
很显然，这实际上相当于将one柱上的两个盘直接搬到three柱上。

再看hanoi(3, one, two, three)的情况。分析
hanoi(2, one , three, two)
one =》three
hanoi(2, two, one, three)
即：先将one柱上的两个盘搬到two柱上，再将one柱上的一个盘搬到three柱上，最后再将two柱上的两个盘搬到three柱上。这不就等于将one柱上的三个盘直接搬到three柱上吗？

运用归纳法可知，对任意n，
hanoi(n-1, one , three, two)
one =》three
hanoi(n-1, two, one, three)
就是先将one柱上的n-1个盘搬到two柱上，再将one柱上的一个盘搬到three柱上，最后再将two柱上的n-1个盘搬到three柱上。这就是我们所需要的结果！
回答者：wuchenghua121 - 经理 四级 12-5 11:51
汉诺塔
汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果请自己运行计算，程序见尾部。面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。

后来，这个传说就演变为汉诺塔游戏:

1.有三根杆子A,B,C。A杆上有若干碟子
2.每次移动一块碟子,小的只能叠在大的上面
3.把所有碟子从A杆全部移到C杆上

经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片：
如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C

此外，汉诺塔问题也是程序设计中的经典递归问题。

补充：汉诺塔的算法实现（c++）
#include <fstream>
#include <iostream>
using namespace std;

ofstream fout("out.txt");

void Move(int n,char x,char y)
{
fout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl;
}

void Hannoi(int n,char a,char b,char c)
{
if(n==1)
Move(1,a,c);
else
{
Hannoi(n-1,a,c,b);
Move(n,a,c);
Hannoi(n-1,b,a,c);
}
}

int main()
{
fout<<"以下是7层汉诺塔的解法:"<<endl;
Hannoi(7,'a','b','c');
fout.close();
cout<<"输出完毕！"<<endl;
return 0;
}

C语言精简算法
/* Copyrighter by SS7E */
#include<stdio.h> /* Copyrighter by SS7E */
void hanoi(int n,char A,char B,char C) /* Copyrighter by SS7E */
{
if(n==1)
{
printf("Move disk %d from %c to %c\n",n,A,C);
}
else
{
hanoi(n-1,A,C,B); /* Copyrighter by SS7E */
printf("Move disk %d from %c to %c\n",n,A,C);
hanoi(n-1,B,A,C); /* Copyrighter by SS7E */
}
}
main() /* Copyrighter by SS7E */
{
int n;
printf("请输入数字n以解决n阶汉诺塔问题：\n");
scanf("%d",&n);
hanoi(n,'A','B','C');
}/* Copyrighter by SS7E */
回答者： Vanquisher_ - 举人 五级 12-5 13:57
parcel::::::::::
program hanoi;
functionhanoi(x:integer):longint;
begin
if x=1 then hanoi:=1;
if x=2 then hanoi:=3;
else
begin
hanoi:=2*hanoi(x-1)+1;
end;
end;

begin
read(x){第几个数 }
write(hanoi(x));
end.

思想就是：第N个就等于第n-1个乘以2+1次

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

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

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

2、抑制能力参与汉诺塔问题

为了把更大的圆盘先放置于指定位置，必须让较小的圆盘暂时偏离其最终应该放置的位置，但被试的自然反应总是“尽快”将圆盘移动到最终的目的地，如此反而导致错误，使移动步数更多，完成时间更长。

3、对圆盘位置的记忆

临床上常将汉诺塔任务用于脑损伤者执行功能的测查。由于执行功能存在多种表现形式，有必要对汉诺塔任务所属的性质进行明确的归类。在解决汉诺塔问题的过程中，对圆盘位置的记忆应该是存在的。

那么这种记忆涉及的是工作记忆还是短时记忆，有研究发现汉诺塔任务与工作记忆没有关系。但另有研究发现汉诺塔任务与空间工作记忆明显相关，只是与词语工作记忆关系不大。临床上对脑损伤者或智力落后者的研究表明，空间工作记忆缺陷导致他们的汉诺塔问题成绩明显不如正常控制组。

简介：

汉诺塔问题，是心理学实验研究常用的任务之一。该问题的主要材料包括三根高度相同的柱子和一些大小及颜色不同的圆盘，三根柱子分别为起始柱A、辅助柱B及目标柱C。

⑶ 关于汉诺塔的问题。

利用递归解决汉诺塔，其最巧妙之处在于实参和形参的不断变幻，实际的柱子也改变了，例如move(n-1,x,z,y)，借组z柱，移到y柱在进入递归时：形参move(int n,int x,int y,int z) /，移到z柱而在递归时; //，盘子数量减少了，和以前数学中的递推证明非常接近,z所对应的实参, y 。就是形参x。数学的递推证明的思想是;/ 函数的目的是把x柱的n个盘子，借助y柱，假定n-1的时候是正确的，证明n也是正确就可以了。 递归过程的思想是，如果已经有了解决n的方法（汉诺塔中，移动n-1个盘子），怎么来处理当前n的问题（如果n-1个盘子已经移好了，那只要把最后一个盘子移过去就可以）。当然理解计算机的递归过程，柱子改变了; 这是把x柱的n-1个盘子，还要处理一下递归的结束条件（当n=1的时候），否则递归就不会结束了，在递归过程中是不断改变的。注意

⑷ 河内塔(汉诺塔) 问题50分```求助``

汉诺塔是个典型的函数递归调用的例子。先弄明白递归的思路，再来看代码。
汉诺塔的目的是把1柱上的N个盘子转移到3柱，移动方法如下：
1、借3柱，将1柱上的N-1个盘子移到2柱上；
2、将1柱上最下面的盘子移到3柱；
3、借1柱，将2柱上的N-1个盘子移到3柱。

其中，1、3步是不可能一步完成的。
其实上面的三步就是void hanoi(int n,int p1,int p2,int p3)中的三个语句，只是表达方法不同。
我们不用去关心到底如何“将1柱上的N-1个盘子移到2柱上”或者“将2柱上的N-1个盘子移到3柱”，因为上面的三个语句已经给出了一种正确的方法，不论N是多少，此方法都正确。计算机会将1、3两步展开，直到N是1 。手工也可以将其展开，你可以试试把1、3两步分别展开，N=4时也不难做到，但好像没什么意义。

最后说一句，应该相信正确的方法，而不必知道它的细节，就跟黑箱一样。

⑸ 河内塔问题

3个的话7次，4个的话15次
1个的话1次，2个的话就是把一个先移到柱子2上，把第二个移到柱子3，再把第一个移到柱子3，2*1+1=3次
3个的话，把2个先移到柱子2，用3步，把第三个移到柱子3,1步，再把2个移到柱子3,所以3*2+1=7次
4个的话同理，2*7+1=15,。

⑹ 关于汉诺塔问题的尽可能多的信息

program hanoi(input,output);
VAR total:integer;
procere move(n,a,b,c:integer);
begin
if n=1
then writeln (a,'->',c)
else begin
move(n-1,a,c,b);
writeln(a,'->',c);
move(n-1,b,a,c);
end;{if}
end;{move}
begin{hanoi}
readln(total);
move (total,1,2,3) ;
readln
end.{hanoi汉诺塔的问题；

这个问题对于我这个初学者来说，确实棘手，对于执行的步骤很不理解，虽然递归不用去了解执行的步骤的。但是，不用去了解不等同于不了解。

一个庙里有三个柱子，第一个有64个盘子，从上往下盘子越来越大。要求庙里的老和尚把这64个盘子全部移动到第三个柱子上。移动的时候始终只能小盘子压着大盘子。

1、此时老和尚（后面我们叫他第一个和尚）觉得很难，所以他想：要是有一个人能把前63个盘子先移动到第二个柱子上，我再把最后一个盘子直接移动到第三个柱子，再让那个人把刚才的前63个盘子从第二个柱子上移动到第三个柱子上，我的任务就完成了，简单。所以他找了比他年轻的和尚（后面我们叫他第二个和尚）（呵呵，倚老卖老），命令：

① 你把前63个盘子移动到第二柱子上

② 在我自己把第64个盘子一道第三个柱子上后

③ 你把前63个盘子移动到第三柱子上

2、第二个和尚接了任务，也觉得很难，所以他也和第一个和尚一样想：要是有一个人能把前62个盘子先移动到第三个柱子上，我再把最后一个盘子直接移动到第二个柱子，再让那个人把刚才的前62个盘子从第三个柱子上移动到第三个柱子上，我的任务就完成了，简单。所以他也找了比他年轻的和尚（后面我们叫他第三和尚）（呵呵，又倚老卖老），命令：

① 你把前62个盘子移动到第三柱子上

② 在我自己把第63个盘子一道第二个柱子上后

③ 你把前62个盘子移动到第二柱子上

3、第三个和尚接了任务，又把移动前61个盘子的任务依葫芦话瓢的交给了第四个和尚，等等递推下去，直到把任务交给了第64个和尚为止（估计第64个和尚很郁闷，没机会也命令下别人，因为到他这里盘子已经只有一个了）。

4、到此任务下交完成，到各司其职完成的时候了。

完成回推了：

第64个和尚移动第1个盘子，把它移开，然后第63个和尚移动他给自己分

配的第2个盘子。第64个和尚再把第1个盘子移动到第2个盘子上。到这里第64个和尚的任务完成，第63个和尚完成了第62个和尚交给他的任务的第一步。

从上面可以看出，只有第64个和尚的任务完成了，第63个和尚的任务才能完成，只有第2个和尚—第64个和尚的任务完成后，第1个和尚的任务才能完成。这是一个典型的递归问题。

现在我们以有3个盘子来分析：

第1个和尚命令：

一 第2个和尚你先把第一柱子前2个盘子移动到第二柱子。（借助第三个柱子）

二第1个和尚我自己把第一柱子最后的盘子移动到第三柱子。

三第2个和尚你把前2个盘子从第二柱子移动到第三柱子。

很显然，第二步很容易实现（哎，人总是自私地，把简单留给自己，困难的给别人）

其中第一步。第2个和尚他有2个盘子，他就命令：

① 第3个和尚你把第一柱子第1个盘子移动到第三柱子。（借助第二柱子）

② 第2个和尚我自己把第一柱子第2个盘子移动到第二柱子上。

③ 第3个和尚你把第1个盘子从第三柱子移动到第二柱子。

同样，第步很容易实现，但第3个和尚他只需要移动1个盘子，所以他也不用在下派任务了。（注意：这就是停止递归的条件，也叫边界值）

第三步可以分解为，第2个和尚还是有2个盘子，命令：

①第3个和尚你把第二柱子上的第1个盘子移动到第一柱子。

② 第2个和尚我把第2个盘子从第二柱子移动到第三柱子。

③第3个和尚你把第一柱子上的盘子移动到第三柱子。

分析组合起来就是：1à3 1à2 3à2 1à3 2à1 2à3 1à3共需要七步。如果是4个盘子，则第一个和尚的命令中第1步和第3步各有3个盘子，所以各需要7步，共14步，再加上第1个和尚的1步，所以4个盘子总共需要移动7+1+7=15步，同样，5个盘子需要15+1+15=31步，6个盘子需要31+1+31=64步……由此可以知道，移动n个盘子需要（2的n次方）--1步。

从上面整体综合分析可知把n个盘子从1座（相当第一柱子）移到3座（相当第三柱子）：

（1）把1座上（n-1）个盘子借助3座移到2座。

（2）把1座上第n个盘子移动3座。

（3）把2座上（n-1）个盘子借助1座移动3座。

下面用hanoi（n,a,b,c）表示把1座n个盘子借助2座移动到3座。

很明显，(1)步上是 hanoi(n-1,1,3,2)

(2)步上是hanoi(n-1,2,1,3)

下面便是代码：

#include<stdio.h>

static long int m=1;/*用来计算移动步骤步数,静态变量才能不断叠加*/

void hanoi(int n,int a,int b,int c)

{

if(n==1){

printf("(%d) %d-->%d\n",m,a,c);

m++;

}

else{

hanoi(n-1,a,c,b);

printf("(%d) %d-->%d\n",m,a,c);/*只有当上一句得到结果，它才会执行*/

m++;

hanoi(n-1,b,a,c);

}

}

main()

{

int d;

printf("Enter the hanoi shu:");

scanf("%d",&d);

hanoi(d,1,2,3);

return 0;

}

执行：

Enter the hanoi shu: 3

（1）1à3

（2）1à2

（3）3à2

（4）1à3

（5）2à1

（6）2à3

（7）1à3

这里可能有个疑问：移动n-1个盘子确实是上面的步骤，但移动n-2的时候就不一样了啊？

hanoi(n-1,a,c,b);

printf("(%d) %d-->%d\n",m,a,c);/*只有当上一句得到结果，它才会执行*/

m++;

hanoi(n-1,b,a,c);

其实每一次调用hanoi（n,a,b,c）时a，b，c的值都不同。

如hanoi(n,1,2,3)时a=1,b=2,c=3.

hanoi(n-1,a,c,b);{a=1,b=2,c=3}

就是hanoi(n-1,1,3,2);

所以调用的就是1à2

再次调用成了hanoi(n-2,a,c,b){a=1,b=3,c=2}

就是hanoi(n-2,1,2,3);

所以调用的就是，1à3;

每一次都能不断自动改变。

Hanoi塔问题中函数调用时系统所做工作

一个函数在运行期调用另一个函数时，在运行被调用函数之前，系统先完成3件事：

①将所有的实参、返回地址等信息传递给被调用函数保存。

②为被调用函数的局部变量分配存储区；

③将控制转移到被调用函数的入口。

从被调用函数返回调用函数前，系统也应完成3件事：

①保存被调用函数的结果；

②释放被调用函数的数据区；

③依照被调用函数保存的返回地址将控制转移到调用函数。

当有多个函数构成嵌套调用时，按照“后调用先返回”的原则（LIFO），上述函数之间的信息传递和控制转移必须通过“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为其在栈顶分配一个存储区，每当从一个函数退出时，就释放其存储区，因此当前运行函数的数据区必在栈顶。堆栈特点：LIFO，除非转移或中断，堆栈内容的存或取表现出线性表列的性质。正是如此，程序不要求跟踪当前进入堆栈的真实单元，而只要用一个具有自动递增或自动递减功能的堆栈计数器，便可正确指出最后一次信息在堆栈中存放的地址。

一个递归函数的运行过程类型于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数。因此，和每次调用相关的一个重要的概念是递归函数运行的“层次”。假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层；从第i层递归调用本函数为进入下一层，即i＋1层。反之，退出第i层递归应返回至上一层，即i－1层。为了保证递归函数正确执行，系统需设立一个“递归工作栈”，作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有实参、所有局部变量以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个记录为“活动记录”，并称指示活动记录的栈顶指针为“当前环境指针”。

⑺ 河内塔问题与解题规律.....

解析：对于此题，我们一遇到此类题是不是有点让人烦恼！为什么要来回移动呢？一下整体搬过去不就好了吗？

所以在遇到此类题时，一定要冷静，不要急于做，而要思考，看看我们有什么方法找到一种能够比较简单的规律。

第一，先我们将复杂的问题简单化，考虑一下一些简单的问题，这是我们解决此类问题的关键，就是当我们对一些较大的数形成的复杂逻辑不能够理清时，我们要从最基本最简单的数字如1，2，3，开始。如下：

假如只有1个穿孔圆盘，就需要移动1次。 A→C 1 次

假如只有2个穿孔圆盘，就需要移动3次。A→B， A→C，B→C 3次

假如只有3个穿孔圆盘，这时我们可以将上面的2个圆盘看做是一个整体，也就是将3分解成1+2.来考虑。如我们将最大的第三个圆盘，取消，只剩2个圆盘，这时借助C柱，移动3次可以让2个圆盘到从A到B柱。再考虑最大的圆盘，移动最大的第三个圆盘到C柱。这时借助A柱，移动3次可以让2个圆盘从B到C柱。就需要移动7次。

第二，从移动的次数中，寻找可以被我们利用的规律。

这7次中，前有3次是为了将上面的2个圆盘从A到B柱，中间1次是最大的圆盘A→C移动，后3次是为了将上面的2个圆盘从B到C柱移动。

从上面的两个3次的移动看，两个圆盘的移动必须经过3次方可成功。这也就是是2个圆盘必须经过3次移动才能从一个柱子到另一柱子。同理我们从这一步的7次移动来看，这也就是是3个圆盘必须经过7次移动才能从一个柱子到另一柱子

另外我们从移动次数的结果数据：1，3，7，这样的数据分析，就得出这样一个规律：

每增加1个圆盘的次数就是在前面既原来的次数的两倍的基础上，再加1次。

于是我们就可以根据上面的规律得出以下的结论：

有4个穿孔圆盘，最少的次数，15次。（是否正确，可以自己验证一下）

有5个穿孔圆盘，最少的次数，31次。

有6个穿孔圆盘，最少的次数，63次。

我们将次数写出一个数列，就得到如下数列：

1，3，7，15，31，63，……

这时我们就会发现它和我们知道它和我们上一讲讲到的一个如下数列非常相似。

2，4，8，16，32，64，128 ……

而上面的移动次数与数列有一个配合的规律，这时我们马上就明白了，这道题的答案：
—1

⑻ 6、算法式、手段一目的分析法、逆向推理法、爬山法、计划简化法是五种解决问

摘要 1.手段—目的分析

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

汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒。

第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。

面对庞大的数字(移动圆片的次数)18446744073709551615(2^64-1)，看来，众僧们耗尽毕生精力也不可能完成金片的移动。

相关信息

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。

印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。

僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。