Question

汉塔递归问题

hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
请问，1,3步中，递归在哪？怎样递归的？我就是没闹明白！

Answer 1

你这真是让人郁闷, 函数都不写全, 活该没人帮你.

汉塔问题问如何将A塔的圆盘也按自下而上由大到小堆起来?并且在任何时候都不能允许大圆盘压小圆盘，而且顺序不能乱?既原样的将A塔的圆盘一个一个移向B塔。

解题思维；题中只给了三座塔，我们利用C塔将圆盘堆在B塔。首先将A塔的1号圆盘放在B塔，A塔德2号圆盘放在C塔，再把放在B塔德1号圆盘放在C塔，此
时C塔拥有两个圆盘按要求自下而上从小到大排列。接下来将A塔的3号圆盘放在B塔，将C塔的1号圆盘放在B塔，把C塔德2号圆盘放在A塔，再把B塔的1号
圆盘放在A塔，此时C塔空，1号2号按要求排在A塔，B塔只有3号圆盘。此时把B塔3号圆盘放在C塔，把A塔德1号放在B塔吗，把A塔德2号房在C塔，再
把B塔德1号放在C塔，此时B塔空，C塔按要求排有123号圆盘。这次把A塔的4号圆盘放在B塔，这次就比较麻烦了先把C塔的1号放在A塔，C塔的2号房
在B塔，再把A塔德1号放在B塔，把C塔德3号放在A塔，再把B塔的1号放在C塔，把B塔德2号放在A塔，再把C塔德1号放在A塔，此时C塔空，B塔只有
4号圆盘，A塔按要求房有123到N号圆盘，缺4号圆盘。现在把B塔的4号圆盘房在C塔，现在推回去，把A塔德1号房在C塔，A塔的2号房在B塔，再把C
塔的1号放在B塔，把A塔德3号房再C塔，此时刚好是3号压4号于C塔，再把，B塔的1号房在A塔，把C塔的2号放在C塔，把A塔的1号放在C塔，这下刚
好推回来，此时B塔空，A塔最上面是5号圆盘，C塔按要求放有1234号圆盘。按这样的递推方法，将n-1个圆盘按要求放在C塔，第n个圆盘放在B塔，现
在A塔空。n号圆盘是最大的圆盘，按问题要求我们终于把n号最大的圆盘放在了B塔，这下借助已空的A塔联合BC塔推回来，就可以把n个圆盘按要求放在B
塔。
程序实现：
其实用程序的循环很简单实现。
void Hanoi (int n, char A, char B, char C)
{ if(n>0)
{Hanoi(n-1, A, C, B); /*把n-1号圆盘由A塔借助B塔移向C塔*
Move(n, A, B); /*n号圆盘由A塔移向B塔*/
Hanoi(n-1, C, B, A); /*n-1号圆盘由C塔借A塔移向B塔*/
}
}

追问

我想知道的是
Hanoi(n-1,A,C,B);
计算机是怎样去实现递归的。
a1=10;
a2=a1+2;
a3=!2+2;
这个我明白，但汉塔递归我没看明白。

追答

为了描述方便, 我约定一种记录方法. 如果有10个盘子,1-10按从小到大编号.我会写(A上盘子;B上盘子;C上盘子) . 就是说 如果ABC上分别有1-8号,9号,10号,我就记为 (1-8,9,10) . 看的懂吧.

-----------------------------------------------------

如果让你挪10个盘子从A到B. 就是 (1-10,0,0) -> (0,1-10,0). 实际上可以这样做.
10.1 把1-9从A挪到C. (让10号露出来,并且不要占用B)
10.2 把10挪到B塔.
10.3 把1-9从C挪到B.
这样就完成任务了.

问题来了,人家不允许一次挪动9个. 那你就要想办法实现挪动9个的方法.
(注意,设计挪动1-9个时,不用考虑10号,因为10号最大,放哪都不影响1-9的挪动,相当于没有10)

那么如果要完成10.1把1-9从A挪到C 可以这样做
9.1 把1-8 从A->B
9.2 把9 从A->C
9.3 把1-8 从B->C
类似的方法, 可以完成10.3把1-9从C挪到B.

问题来了,人家不允许一次挪动8个. 那你就要想办法实现挪动8个的方法.
(注意,设计挪动1-8个时,不用考虑9号,因为9号最大,放哪都不影响1-8的挪动,相当于没有9)
....

可以想象,到最后,只需要移动1号盘. 迭代的出口就找到了.

字数限制,后面再续........