补刀影后古穿今书包网:话说递归与HANOI塔
来源:百度文库 编辑:九乡新闻网 时间:2024/05/04 12:26:01
话说递归与HANOI塔
做IT就要做精英,至少4000/月吧?JAVAV工程师权威认证
[上海央邦]学一送一,超值! 【安博亚威】CCIE考试通过率第一!
定向委培RHCA,通过考试年薪10W
Windows高级工程师的培训地 中国IT实验室整理 佚名 2009-9-3 保存本文 推荐给好友 收藏本页 欢迎进入C/C++编程社区论坛,与200万技术人员互动交流 >>进入
递归做为一种算法在程序设计语言中广泛应用.是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现像.
程序调用自身的编程技巧称为递归( recursion)。
一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。
一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。
注意:
(1) 递归就是在过程或函数里调用自身;
(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。
递归算法一般用于解决三类问题:
(1)数据的定义是按递归定义的。(Fibonacci函数)
(2)问题解法按递归算法实现。(回溯)
(3)数据的结构形式是按递归定义的。(树的遍历,图的搜索)
递归的缺点:
递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
递归与HANOI塔
HANOI塔问题递归算法的最典型的例题。
本程序可同时将HANOI塔问题的解题步骤的中间结果显示在屏幕上和保存在文本文件中。(后一点对于显示结果很多无法在一屏中显示时,特别有用)
程序思路很简单,看注释就明白了。
/*
Name: hanoi2.c
Author: zhuqing
Description: HANOI塔问题的递归解
Date: 06-08-03 11:44
Copyright:
*/
#include
#define N 5
/* 原柱,中间柱,目标柱初值数组 */
char a[]={'1','2','3','4','5'};
char b[]={'0','0','0','0','0'};
char c[]={'0','0','0','0','0'};
int step=0;
main()
{
FILE *fp;
int i;
if((fp=fopen("c:\\hanoi2.txt","w"))==NULL){
printf("\nCannot open the file!\n");
getch();
exit(0);
}
printf("\n============ HANOI TOWER ============\n");
print(N);
fprint(N,fp);
move(N,a,b,c,fp);
fclose(fp);
getch();
}
/* 递归函数 */
void move(int n,char a[],char b[],char c[],FILE* fp)
{
if(n>0){
move(n-1,a,c,b,fp);
c[n-1]=a[n-1];
a[n-1]='0';
print(N);
fprint(N,fp);
move(n-1,b,a,c,fp);
}
}
/* 打印输出结果到屏幕的函数 */
void print(n)
int n;
{
int i;
printf("\nSTEP%d",step++);
printf("\na:");
for(i=0;i
printf("\nb:");
for(i=0;i
printf("\nc:");
for(i=0;i
printf("\n-------------------------------------\n");
}
/* 打印输出结果到文本文件的函数 */
void fprint(n,fp)
int n;
FILE *fp;
{
int i;
fputs("\na:",fp);
for(i=0;i
fputs("\nb:",fp);
for(i=0;i
fputs("\nc:",fp);
for(i=0;i
fputs("\n-------------------------------------\n",fp);
}