用递归法求N个数R个数的组合的问题?
这是软考书上的一段代码;
[程序片断(递归函数)]
void comb( int n, int r )
{
int i = 0;
for( i = n; i > = r; i -- )
{
if( ( i != n ) && ( k != r ) ) //k为过程外定义的
{
int temp = 0;
for( temp = 1; temp < ( k - r ) * 3; temp++ )
{
printf( " " );
}
}
printf( "%3d ", i );
if( i > 1 )
{
comb( i - 1, r - 1 );
}
else
{
printf( "\n " );
}
}
}
我的问题是,我调用此函数输出的结果不对;
comb( 5, 3 )
求5个数中3个数的组合,正确的输出应该是;
543
542
541
532
531
521
432
431
421
321
这是什么问题,我觉得是输出方面不对,书上只给出了程序的片段.
谢谢各位 !!
[解决办法]
贴一个程序让你，看看 前段时间也研究了这个，有什么地方不懂我再给你说。
# include <stdio.h>
# define MAXN 100
int a[MAXN];
void comb(int m,int k)
{ 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 ");
}
}
}
void main()
{ a[0]=3;
comb(5,3);
}
[解决办法]
哦，明白了。
首先，楼主把程序打错了：
1：if( i > 1 ) 应当是 if( r > 1 )
2: 为了美观，for( temp = 1; temp < ( k - r ) * 3; temp++ ) 应当改为：
for( temp = 1; temp <= ( k - r ) * 3; temp++ )
一般的方法是采用数组保存选入的元素（如chzuping()贴的代码），以便于在最后输出找到的组合中的所有元素。
因此，用这样的方法做的，输出就应该是下面这样：
543
542
541
532
531
521
432
431
421
321
但是，楼主看的书上的代码，却并不是这样的。
定义k，并另k=3，按我说的改正代码后，输出如下：
5 4 3
2
1
3 2
1
2 1
4 3 2
1
2 1
3 2 1
上面的输出，其实就是楼主想要的东东。
每一行表示一个组合，其意义是：
若为空格，表示该组合此位置的值和上一组此位置的值相同。
若为数值，则就是该组合此位置的值。
这样去“翻译”输出结果，容易知道，其实输出的就是所有组合了。
至于k的意义，其实，k只是一个控制输出宽度的全局变量，只是方便“阅读”输出结果而已。
