C语言汉诺塔问题,用C语言实现汉诺塔
汉诺塔问题是指:一块板上有三根针 A、B、C。A 针上套有 64 个大小不等的圆盘,按照大的在下、小的在上的顺序排列,要把这 64 个圆盘从 A 针移动到 C 针上,每次只能移动一个圆盘,移动过程可以借助 B 针。但在任何时候,任何针上的圆盘都必须保持大盘在下,小盘在上。从键盘输入需移动的圆盘个数,给出移动的过程。
因此,解决汉诺塔问题可设计一个递归函数,利用递归实现圆盘的整个移动过程,问题的解决过程是对实际操作的模拟。
算法思想
对于汉诺塔问题,当只移动一个圆盘时,直接将圆盘从 A 针移动到 C 针。若移动的圆盘为 n(n>1),则分成几步走:把 (n-1) 个圆盘从 A 针移动到 B 针(借助 C 针);A 针上的最后一个圆盘移动到 C 针;B 针上的 (n-1) 个圆盘移动到 C 针(借助 A 针)。每做一遍,移动的圆盘少一个,逐次递减,最后当 n 为 1 时,完成整个移动过程。因此,解决汉诺塔问题可设计一个递归函数,利用递归实现圆盘的整个移动过程,问题的解决过程是对实际操作的模拟。
程序代码
#include <stdio.h> int main() { int hanoi(int,char,char,char); int n,counter; printf("Input the number of diskes:"); scanf("%d",&n); printf("\n"); counter=hanoi(n,'A','B','C'); return 0; } int hanoi(int n,char x,char y,char z) { int move(char,int,char); if(n==1) move(x,1,z); else { hanoi(n-1,x,z,y); move(x,n,z); hanoi(n-1,y,x,z); } return 0; } int move(char getone,int n,char putone) { static int k=1; printf("%2d:%3d # %c---%c\n",k,n,getone,putone); if(k++%3==0) printf("\n"); return 0; }
调试运行结果
当移动圆盘个数为 3 时,具体移动步骤如下所示:
Input the number of diskes:3
1: 1 # A---C
2: 2 # A---B
3: 1 # C---B
4: 3 # A---C
5: 1 # B---A
6: 2 # B---C
7: 1 # A---C
总结
本实例中定义的 hanoi() 函数是一个递归函数,它有四个形参"n""x""y""z"。"n" 是移动的圆盘个数,"x""y""z" 分别表示三根针,其功能是把 x 上的 n 个圆盘移动到 z 上。当 n=1 时,直接把 x 上的圆盘移到 z 上,输出"x---Z"。当 n!=1 时,则递归调用 hanoi() 函数,把 (n-1) 个圆盘从 x 移到 y,输出"x—-z";再递归调用 hanoi() 函数,把 (n-1) 个圆盘从 y 移到 z。在递归调用函数的过程中"n=n-1",n 的值逐次递减,最后 n=1,终止递归调用,逐层返回,移动过程结束。所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频