UC知道C语言汉诺塔的问题
来源：百度知道 编辑：UC知道 时间：2024/09/21 15:48:39
{
printf( "%c ---> %c\n", x, y );
}
void hanoi( int n, char one, char two, char three )
{
if ( n == 1 ) move( one , three )
else
{
hanoi( n - 1, one , three, two );
move( one, three );
hanoi( n - 1, two, one, three );
}
}
main()
{
int m;
printf( "Input the number of diskes: " );
scanf( "%d", &m );
printf( "The step to moving %3d dusjes:\n", m );
hanoi( m, 'A', 'B', 'C' );
getch();
return 0;
}
虽然知道是如何移动的,可是却看不懂程序如何递归调用的.看来我太笨了
希望大家帮帮我详细写出这个程序中的 "N值" 一步步的变化过程,还有就是
move( one, three) 明明是输出其 " A--->C ".为什么还可以输出
A--->B, C--->B, B--->A, B--->C. 我真是越看越晕,都快没信心了.
希望大家可以帮帮我.谢谢了
要看懂递归程序，往往应先从最简单情况看起。
先看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柱上。这就是我们所需要的结果！
首先你得知道原理:
N个汉诺塔问题可以转换成:
1 先把N-1个塔从A搬到B.
2 把最下面的盘搬到C
3 把N-1个盘从B搬到C
上面的程序就是利用这个原理:
假若有4个盘子:
hanoi( 4, 'A', 'B', 'C' )
会执行:
4不等于1,所以执行else =>