例一:这个程序中采用不同的算法实现组合算法(从m个数中取k个数并列出所有这些数的组合),编写这个程序是在我看到一位版主在“c语言论坛”发的一个名为:“[穷举法]数学里的组合”的帖子以后才有感而发的。关于“穷举法”我不想多说,大家看了那个帖子就明白了。
/*以下程序在TC2.0编译!*/ #include <stdio.h> #define MAXN 100
#define M 5 /*默认为5选3(可以改为其他)*/ #define K 3
int a[MAXN]; /*暂时保存结果*/ int stack[MAXN]; /*定义栈*/ int top;
/*以下采用“递归-分治策略”实现组合算法(这个算法的效率比较低)*/ void comb(int m,int k) { /*comb函数不是我编的,是从我以前的高程教材中找出来的*/ int i,j; for(i=m;i>=k;i--) { a[k]=i; if(k>1) comb(i-1,k-1); else { for(j=a[0];j>0;j--) printf("%4d",a[j]); printf("\n"); } } }
/*以下函数是用“非递归化while-if形式”对comb函数进行单纯转化得到的,比comb的效率高*/ void comb_w_if(int m,int k) { int i; top=0; while(m>=k||top) { /*从comb函数可以看出:递归执行条件为:m>=k||top*/ if(m>=k) { a[k]=m; if(k>1) {stack[top++]=m--; --k;} /*进栈,改变参数。(从comb函数中看出递归体执行条件为:m>=k&&k>1)*/ else { /*否则为递归结束条件*/ for(i=a[0];i>0;i--) printf("%4d",a[i]); /*打印结果*/ printf("\n"); --m; /*--m:参数(递归体)回溯*/ } }else {m=stack[--top]-1; ++k;} /*满足回溯条件:出栈,恢复参数*/ } }
/*以下用”while-while形式“对comb函数进行单纯转化得到的*/ void comb_w_w(int m,int k) { /*该函数(及上面的函数)最大栈深为m-k,效果相当不错!*/ int i; top=0; while(m>=k||top) { while(m>=k) { a[k]=m; if(k>1) stack[top++]=m--,--k; else { for(i=a[0];i>0;i--) printf("%4d",a[i]); printf("\n"); --m; } } if(top) m=stack[--top]-1,++k; } }
/*以下函数是用”回溯-迭代回溯策略“实现,算法的效率很高(在组合算法中应当是一流的),且不需要栈的支持,是我在这个学期编的最经典的算法!理解这个算法要把组合问题的解空间树画出来,因为整个算法都在解空间树上进行*/ void comb_dd(int m,int k) { int i=1,j; if(m<k) return; while(i>0) { /*i为解空间树的高度*/ a[i]=m; if(i==k) { /*搜索达到“预定”深度*/ for(j=1;j<=a[0];j++) printf("%4d",a[j]); /*输出结果*/ printf("\n"); while(a[i]==k-i+1) --i; /*从树的底层回溯*/ if(i!=k) m=a[i]-1; else --m; }else {++i;--m;} /*继续搜索(深度优先)*/ } }
/*comb_fz函数采用“分支界限-广度优先策略”编写,效率一般,但可以帮助理解 ”广度优先策略“,推荐!!*/ void comb_fz(int m,int k) { struct{ int data; int parent; int level; }queue[10*MAXN]; /*定义队列:parent记录父结点,level记录树的层数(深度)*/ int front=0,rear=0; int i,t,data,parent,level; if(m<k) return; for(i=m-k+1,t=m;i>0;--i,--t) { /*初始化队列*/ queue[rear].data=t; queue[rear].parent=-1; queue[rear].level=1; ++rear; } while(rear!=front) { data=queue[front].data; /*出队*/ level=queue[front].level; ++front; if(level==k) { /*输出结果*/ printf("%4d",data); parent=queue[front-1].parent; while(parent!=-1) { data=queue[parent].data; printf("%4d",data); parent=queue[parent].parent; } printf("\n"); } else { /*扩展:进行广度搜索*/ t=data-m-k+1; /*t定义了搜索范围*/ if(t<1) t=1; while(--data>=t) { queue[rear].data=data; queue[rear].parent=front-1; queue[rear].level=level+1; ++rear; } } } }
main() { a[0]=K; /*a[0]为组合个数:k*/ printf("comb output:\n"); comb(M,K); getch(); printf("comb_w_if output:\n"); comb_w_if(M,K); getch(); printf("comb_w_w output:\n"); comb_w_w(M,K); getch(); printf("comb_dd output:\n"); comb_dd(M,K); getch(); printf("comb_fz output:\n"); comb_fz(M,K); printf("End! Remember STN_LCD!"); getch(); }
对于”回溯算法“和”分支界限算法“我就不多说了(几句话也说不清楚)。 今天的主题是”递归程序非递归化”的问题,理解非递归化方法对我们理解和设计递归程序有很大的帮助。我们在理解递归程序时,不要沿着递归程序的语句去想象程序执行递归的过程,我们只需要找到他的"递归执行条件":可能进入递归循环的条件;"递归体执行条件":执行递归语句的条件;"递归回退条件":一般与"递归体执行条件"相反,和"递归回退执行语句":从递归返回以后要执行那些语句,就可以了,具体如何找要根据实际情况,没有什么定式! 在进行非递归化的过程中,涉及到用栈保存参数的问题,许多书都说:”用栈保存所有的参数”,比如上面的comb_w_w函数要保存m和k参数,我们看到过的许多非递归化程序中也的确如此,但事实上跟本不需要保存这么多的参数:如果所有参数都要保存的话,非递归化程序的效率优势如何体现! 在非递归化程序中,栈具有“栈顶跟踪”(自创名词)的特性:栈顶总是保存“当前处理参数”的父结点参数(栈顶一直跟踪当前的参数),我们可以利用这个特性简化非递归程序中的“参数栈”,一般都可以简化到一个参数,比如上面的comb_w_w和comb_w_if函数中的栈stack只保存了参数m,而另一个参数k就可以跟踪m的变化而不必用栈保存它了!为了验证我的结论,下帖是我编写的”汉诺塔“非递归化程序(相信大家都没见过吧):