C++递归问题--罗汉塔

我觉得这样可能比较好理解一点

创新互联主要从事做网站、成都网站设计、网页设计、企业做网站、公司建网站等业务。立足成都服务来安,10年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18980820575

有三根柱子，标记为A, B, C

先要理解函数hanoi(n,A,B,C) 的意思是借助于B柱子将A上面的n个盘子移到C上面，必须充分对应到各个参数。

如果想将n个盘子从A柱子移动到C柱子

可以分为这样几个步骤

（1）必须将A最下面也就是最大的那个盘子移动到C最下面

首先需要借助C柱子将A上面的n-1个盘子移动到B上面

就是hanoi(n-1,A,C,B) 。

此时A上面只有一个最大的盘子，B上面按序放着n-1个盘子，C上面有0个盘子。

（2）将A上面的盘子移动到C上面，只需要1步。

此时A上面有0个盘子，B上面按序放着n-1个盘子，C上面只有一个最大的盘子。

（3）最后借助于A柱子将B上面n-1个盘子移到C上面即可

就是hanoi(n-1,B,A,C) 。

所以实际上数学推导公式为f(n)=2f(n-1)+1，其中f(1)=1，f(n)表示将n个盘子从A柱子移到C柱子的步数

如果还不明白的欢迎hi我 啊

6块罗汉塔a移动到c,每次只能移动1个

move from A to B

move from A to C

move from B to C

move from A to B

move from C to A

move from C to B

move from A to B

move from A to C

move from B to C

move from B to A

move from C to A

move from B to C

move from A to B

move from A to C

move from B to C

move from A to B

move from C to A

move from C to B

move from A to B

move from C to A

move from B to C

move from B to A

move from C to A

move from C to B

move from A to B

move from A to C

move from B to C

move from A to B

move from C to A

move from C to B

move from A to B

move from A to C

move from B to C

move from B to A

move from C to A

move from B to C

move from A to B

move from A to C

move from B to C

move from B to A

move from C to A

move from C to B

move from A to B

move from C to A

move from B to C

move from B to A

move from C to A

move from B to C

move from A to B

move from A to C

move from B to C

move from A to B

move from C to A

move from C to B

move from A to B

move from A to C

move from B to C

move from B to A

move from C to A

move from B to C

move from A to B

move from A to C

move from B to C

运用递归的办法：

A为当前位置，C为目标位置，B为临时存放位置。

base case: 只有1个方块，则直接 move from A to C（直接从A移动到C）。

other case: 当不止1个方块时的递归： 假如有N个方块，把 （1,2,3,4...到N-1）的方块看成一个整体，第N个方块看做一个个体。想把它们全部从A转移到C则要3个步骤：

先把 (1.2,3,4...N-1) 大整体放到临时位置B。（此时n 头上无障碍，且C为空）

把N（最大方块）从 A 移动到C。

最后把 (1.2,3,4...N-1) 大整体 也放到C。

递归时需要注意的点： 3个位置（当前位置，目标位置，临时存放位置）

（1）当要把 （1到N-1）大整体转移到  ！临时位置！时， （1到N-1）大块的当前位置和 N 的位置相同， 但（1到N-1）的 ！目标位置！ 是 N 的 临时存放位置。

（2）当要把（1到N-1）大整体 从 临时位置 放回 N 头上的时候， （1到N-1）的当前位置为 N 的临时位置， （1到N-1）的 目标位置与 N 的目标位置一致。

//c++ 代码：

#include iostream

using namespace std;

void hm(int cu, int mb, int wa, int num)

{

if (num == 1)

{

  cout "move from " cu " to " mb endl; //基础情况

}

else

{

  hm(cu, wa, mb, num - 1);//把1 到 N-1 的大整体移动到N的临时位置，大方块目前和N在一起，所以当前位置一致，N的临时位置则为大方块的目标位置。同理可得大方块的临时位置为N的目标位置。

  cout "move from " cu " to " mb endl;//再把N 从 现在的位置移动到 目标位置

  hm(wa, mb, cu, num - 1);//把大方块移回N头上，大方块目前在N的临时位置，所以N的临时位置=大方块的当前位置，单目标位置一致。 同理可得大方块的临时位置为N的当前位置

}

}

void main()

{

int num;

cout "塔有几层？" endl;

cin num;

int cu = 1, mb = 2, wa = 3;  // cr:目前， mb：目标, wa：临时

hm(1, 2, 3, num);

}

怎样用C语言编罗汉塔？

你可以看看这里的评论：

有我的程序在下面：

void NuoYiWei(int FromTa,int ToTa)//只挪动最上面一个的子函数

{

TopPoint[FromTa]--;//这是个每个塔层高度的记录数组，从哪个塔挪走一个，哪个塔高就减少一个。

DuiZhan[ToTa][TopPoint[ToTa]]=DuiZhan[FromTa][TopPoint[FromTa]];//这是三个塔上面数据的记录，没有用0表示，这里把数据从挪出的塔传到挪到的塔上。

DuiZhan[FromTa][TopPoint[FromTa]]=0;//原来挪出的塔的最上层没有东西了，恢复0值。

TopPoint[ToTa]++;//挪到的那个塔层数自加1

}

void Nuo(int FromTa,int MidTa,int ToTa,int NeedMove)//汉诺塔主程序，给定初始条件和塔高度

{

if(NeedMove=2)//如果需要挪动的塔层高度还大于等于2层

{

Nuo(FromTa,ToTa,MidTa,(NeedMove-1));//先把最下面一个除外的上面的N-1个都挪到中间的塔，怎么挪的，就是迪归调用这个函数实现的。

NuoYiWei(FromTa,ToTa);//然后把最低下一个诺到目标塔上。

Nuo(MidTa,FromTa,ToTa,(NeedMove-1));//最后把挪到中间塔上的N-1个都挪到目标塔上（这里你要先假设这样的函数能实现本功能）

}

else

{

NuoYiWei(FromTa,ToTa);//就剩一个要挪动了就直接挪动

}

}

这个函数是在C++里写的，如果用C语言还要注意些。

我这里还有用C写的汉诺塔的程序，你给我邮箱sxt9840210@163.com发邮件索要吧，说清楚要些什么。

文章题目：罗汉塔函数python,什么是罗汉塔
URL网址：http://kswjz.com/article/dsijopi.html