为了弄清到底那个组合算法的效率高，我连夜编写了对comb,comb_w_w,comb_w_if,comb_dd,comb_fz和 simpley的f函数的测试程序，该测试程序采用了权威和准确的算法测试方法（对该算法如有任何质疑请发送到dianzi8801@sina.com与我单独讨论）。我很遗憾的告诉simpley板主：正如我所料，你的f函数效率的确不高。下面是测试结果（排在前面的效率高）： comb_dd>comb_w_w>comb_w_if>f>comb>comb_fz，comb_dd函数不仅在运行时间上大获全胜，在占用空间上也是上述所有算法中最少的！由于不同的计算机数据可能不同，所以我没把测试数据帖出来。下面是测试函数，大家可以到自己的计算机上进行测试，看看到底哪个算法的效率高：
以下函数必须在visual c++或visual stdio.net下运行，在tc2.0下运行得到的测试结果没有任何意义！（因为tc工作在“控制台”模式下）：
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAXN 100
#define M 5 /*默认为5选3（可以改为其他）*/
#define K 3
#define MIN_DURATION 10.0
#define MIN_ITER 10
#define SIGDIGIT 5
#ifndef CLOCKS_PER_SEC
#define CLOCKS_PER_SEC CLK_TCK
#endif
int a[MAXN];
int stack[MAXN];
int top;
static clock_t op_start, op_end;
static double baseline, usec, resolution;
static int i_s, prec;
/*以下为测试宏*/
#define BEGIN_TEST(name) printf("%20s ", name); fflush(stdout); i_s = 0; op_start = clock(); while(clock() == op_start); op_start = clock(); while ((op_end = clock()) - op_start < CLOCKS_PER_SEC * MIN_DURATION) { int q; for (q=0; q < MIN_ITER; q++) {
#define END_TEST() i_s++; } } usec = 1000000.0 * (double) (op_end - op_start - baseline * i_s) / (double) CLOCKS_PER_SEC / (double) i_s; if (usec <= 0.0) usec = 0.0; printf("%9.3f usec\n", usec);
/*以下函数是simpley版主编写的非递归组合函数*/
void f(int n,int m){int i=0,j=0,a[10],s[10];
do{
for(;j<n;j++){
s[i]=j;
if(i==m-1){/*for(l=0;l<m;l++)printf("%d",s[l]);printf("\n");*/}
else a[i]=j,i++; }
j=a[--i]+1;}while(a[0]!=n-1);}
/*以下采用“递归-分治策略”实现组合算法（这个算法的效率低）*/
void comb(int m,int k) { /*comb函数不是我编的，是从我以前的高程教材中找出来的*/
int i;
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"); */
}
}
}
void comb_w_if(int m,int k) {
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;} /*满足回溯条件：出栈，恢复参数*/
}
}
void comb_w_w(int m,int k) { /*该函数（及上面的函数）最大栈深为m-k，效果相当不错！*/
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;
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;} /*继续搜索（深度优先）*/
}
}
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,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;
}
}
}
}
int main(void)
{
double tempres;
printf("clocks_per_sec = %d\n", CLOCKS_PER_SEC);
resolution = 1000000.0 / CLOCKS_PER_SEC / MIN_ITER;
printf("worst case resolution = %5.4f usec\n", resolution);
prec = 0;
for (tempres = resolution; tempres < SIGDIGIT; tempres *= 10)
{
prec ++;
}
printf("meaningful precision = %d decimal digits\n", prec);
baseline = 0;
BEGIN_TEST("(cache & vm load)");
END_TEST();
baseline = (double) (op_end - op_start) / (double) i_s;
a[0]=K;
/*以下进行对各种组合函数进行测试*/
BEGIN_TEST("comb testing...");
comb(M,K);
END_TEST();
BEGIN_TEST("comb_fz testing...");
comb_fz(M,K);
END_TEST();
BEGIN_TEST("comb_w_w testing...");
comb_w_w(M,K);
END_TEST();
BEGIN_TEST("f testing...");
f(M,K);
END_TEST();
BEGIN_TEST("comb_w_if testing...");
comb_w_if(M,K);
END_TEST();
BEGIN_TEST("comb_dd testing...");
comb_dd(M,K);
END_TEST();
return 0;
}
以上的程序大概运行1分钟左右（我的机器要40s左右，不同的机器运行速度不一样），请耐心等待！
我不知道我编的这些函数是否有人读懂，如果有读懂的同学请“举手”，我们可以进一步交流。
还有你说我的hanoi程序“这个方法只可用于参数变化有一定规律的情况”的确如此！但是就hanoi程序而言（其它的我们不肯定)，它的效率绝对比同样的“全部参数”进栈高！！！因为它的“全参数进栈”的非递归形式和hanoi_w_if,hanoi_w_w的形式是完全一样的！我就是从“全参数进栈”形式删除x,y,z的进栈语句才得到的，其他的问根本没改，事实上，就hanoi程序而言（有许多函数也是如此）:x,y,z的进栈是根本不需要的！
我很喜欢和你这样的人交流，希望继续保持！谢谢你评论我的帖子！ 最后：请用vc从新测试。