n个自然数中取r个数的组合

时间:2021-05-11 04:12:52

例:找出n个自然数(1, 2, 3,..., n)中取r个数的组合,设计递归算法进行求解。例如,当n=5, r=3时,从大到小排列的组合数为:

 

   5   4   3
   5   4   2
   5   4   1
   5   3   2
   5   3   1
   5   2   1
   4   3   2
   4   3   1
   4   2   1
   3   2   1

 

分析以上数据,组合规律如下:

(1)固定第一个数为5,则其后就是求解n=4, r=2的组合数;

(2)固定第一个数为4,则其后就是求解n=3, r=2的组合数;

(2)固定第一个数为3,则其后就是求解n=2, r=2的组合数。

 

一般地,递归算法的两个步骤为:

(1)n个数中r个数组合递推到“n-1 ”个数中r-1个数的组合,n-2个数中r-1个数的组合,... ,r-1个数中r-1个数的组合”,共有n-r+1次递归;

(2)递归的停止条件是r=1.

 

递归算法如下:

#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");
  }
  }

}



main()
{  int num;
    a[0]=3;
    comb(5,3);
    //printf("%d ",num);
   
}