c语言实现汉诺塔（程序执行步骤详解）

很久没去接触c语言了，今天翻了翻c语言的书，偶然间看到了大一时让我郁闷了很久的汉诺塔问题，又重新推理了一遍，汉诺塔的实现采用递归算法，涉及到数据结构中的栈的知识。下面是c实现汉诺塔的源码。程序只是实现了文字信息，即用文字描述了圆盘的移动过程，并未真正实现圆盘的移动，该程序难度并不大，要了解递归的原理和方法中参数值的变化。

# include <stdio.h>

 

void hannuota(int n,char one,char two,char three);
void move(char x,char y);

 

int main(void) {
 int n;
 
 printf("please input a  integer number:");
 scanf("%d",&n);

 

 if(n > 10 || n < 0) {
  printf("请输入一个0~10范围内的整数！！");
  return 0;
 }

 

 hannuota(n,'A','B','C');

 

 return 0;
}

 

void hannuota(int n,char one,char two,char three) {
     if(n == 1) {
       move(one,three);   //<1>
    }
   else {
  hannuota((n-1),one,three,two);    //<2>
  move(one,three);                          //<3>
  hannuota((n-1),two,one,three);   //<4>
 }

}

void move(char x,char y) {
 printf("%c ----> %c\n",x,y);
}

 

为了避免运行需要很长的时间，程序限制了输入的整数大小为0-10，以下是程序执行的顺序：（为了篇幅，假设n的值是3）

main方法运行到hannuota(n,'A','B','C')时;该方法里的参数为hannuota(3,'A','B','C');

1、第一部分：把A柱中的n-1个圆盘借助C柱移动到B柱

此时执行hannuota方法，因为n=3>1，因此此时递归执行hantuona方法，此时方法参数为hannuota(2,'A','C','B')，(注意此时hannuota方法的参数改变了，C和B值互换);因为n=2>1，继续递归调用hannuota(1,'A','B','C');(此时hannuota方法的参数改变了，C和B值互换);因为n=1，所以执行move方法，打印出A-->C;

返回n=2时程序未执行完的部分，即执行标志为<3>的move方法，因为此时n=1，打印出A-->B,

继续执行标志为<4>的hannuota((n-1),two,one,three)部分，此时参数为hannuota(1,'C','A','B');   此时n=1，打印出C-->B。到此刻位置标志为<2>部分的 hannuota((n-1),one,three,two)程序执行完毕。

2、第二部分：把A柱的第n个圆盘移动到C盘

此时直接执行标注为<3>部分的程序move(one,three); 此时打印出A-->C;

3、第三部分：把B柱上的n-1个圆盘借助A移动到C柱

此时执行标志为<4>部分的hannuota((n-1),two,one,three)，此时参数为hannuota(2,'B','A','C');

因为n=2>1,执行标志为<2>的代码，此时方法参数为hannuota(1,'B','C','A');因为此时n=1，执行标志为<1>的代码，打印出B-->A;此时，标志为<2>的程序执行完毕，one，two，three的值分别为one=B,two=A,three=C;

继续执行标志<3>的程序move(one,three); 打印出B-->C; 继续执行至标志<4>的代码hannuota((n-1),two,one,three)，参数为hannuota(1'A','B','C')，因此n=1，执行标志<1>的代码，打印出A-->C;

到此为止，程序执行完毕。

程序执行结果如下：

A ----> C
A ----> B
C ----> B
A ----> C
B ----> A
B ----> C
A ----> C

 

汉诺塔问题主要分为以上三个部分，程序中用到了递归算法，递归要用到栈的知识，就是进栈和出栈，每到递归调用一个系统的子系统时，都会为子系统分配内存单元，把正被调用的子系统压入栈顶，按照先进后出的规则，执行完后就弹出栈，释放为其分配的内存单元。然后继续执行栈中的其他部分，直到整个程序执行完毕。