Go语言视频零基础入门到精通

javalearner

组合问题
   
编程输出从自然数1、2、……、n中任取r个数的所有组合。例如n=5，r=3的所有组合为：
   
（1）5、4、3
   
（2）5、4、2
   
（3）5、4、1
   
（4）5、3、2
   
（5）5、3、1
   
（6）5、2、1
   
（7）4、3、2
   
（8）4、3、1
   
（9）4、2、1
   
（10）3、2、1
         分析所列的10个组合，可以采用这样的递归思想来考虑求组合函数的算法。设函数为comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时，其后的数字是从余下的m-1个数中取k-1数的组合。

  
   
  
  
       这就将求m个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字，约定函数将确定的k个数字组合的第一个数字放在a[k]中，当一个组合求出后，才将a[]中的一个组合输出。第一个数可以是m、m-1、……、k，函数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未确定组合的其余元素，继续递归去确定；或因已确定了组合的全部元素，输出这个组合。细节见以下程序中:
   
  

1. public class CombTest{
   
2. static int   a[]=new int[100];
   
3. static void  comb(int m,int k) {
   
4.    int i,j;
   
5.    for (i=m;i>=k;i--)  {
   
6.      a[k]=i;
   
7.       if (k>1)
   
8.          comb(i-1,k-1);
   
9.       else {
   
10.            for (j=a[0];j>0;j--)
    
11.             System.out.printf("%4d",a[j]);
    
12.             System.out.println();
    
13.       }
    
14.    }
    
15. }
    
16. public static void main(String args[]) {
    
17.       a[0]=3;
    
18.       comb(5,3);
    
19.       a[0]=4;
    
20.       comb(10,4);
    
21. }
    
22. }

复制代码

程序运行结果：
C:java>java CombTest
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
10 9 8 7
10 9 8 6
10 9 8 5
10 9 8 4
10 9 8 3
10 9 8 2
10 9 8 1
10 9 7 6
10 9 7 5
10 9 7 4
10 9 7 3
10 9 7 2
10 9 7 1
10 9 6 5
10 9 6 4
10 9 6 3
10 9 6 2
10 9 6 1
10 9 5 4
10 9 5 3
10 9 5 2
10 9 5 1
10 9 4 3
10 9 4 2
10 9 4 1
10 9 3 2
10 9 3 1
10 9 2 1
10 8 7 6
10 8 7 5
10 8 7 4
10 8 7 3
10 8 7 2
10 8 7 1
10 8 6 5
10 8 6 4
10 8 6 3
10 8 6 2
10 8 6 1
10 8 5 4
10 8 5 3
10 8 5 2
10 8 5 1
10 8 4 3
10 8 4 2
10 8 4 1
10 8 3 2
10 8 3 1
10 8 2 1
10 7 6 5
10 7 6 4
10 7 6 3
10 7 6 2
10 7 6 1
10 7 5 4
10 7 5 3
10 7 5 2
10 7 5 1
10 7 4 3
10 7 4 2
10 7 4 1
10 7 3 2
10 7 3 1
10 7 2 1
10 6 5 4
10 6 5 3
10 6 5 2
10 6 5 1
10 6 4 3
10 6 4 2
10 6 4 1
10 6 3 2
10 6 3 1
10 6 2 1
10 5 4 3
10 5 4 2
10 5 4 1
10 5 3 2
10 5 3 1
10 5 2 1
10 4 3 2
10 4 3 1
10 4 2 1
10 3 2 1
9 8 7 6
9 8 7 5
9 8 7 4
9 8 7 3
9 8 7 2
9 8 7 1
9 8 6 5
9 8 6 4
9 8 6 3
9 8 6 2
9 8 6 1
9 8 5 4
9 8 5 3
9 8 5 2
9 8 5 1
9 8 4 3
9 8 4 2
9 8 4 1
9 8 3 2
9 8 3 1
9 8 2 1
9 7 6 5
9 7 6 4
9 7 6 3
9 7 6 2
9 7 6 1
9 7 5 4
9 7 5 3
9 7 5 2
9 7 5 1
9 7 4 3
9 7 4 2
9 7 4 1
9 7 3 2
9 7 3 1
9 7 2 1
9 6 5 4
9 6 5 3
9 6 5 2
9 6 5 1
9 6 4 3
9 6 4 2
9 6 4 1
9 6 3 2
9 6 3 1
9 6 2 1
9 5 4 3
9 5 4 2
9 5 4 1
9 5 3 2
9 5 3 1
9 5 2 1
9 4 3 2
9 4 3 1
9 4 2 1
9 3 2 1
8 7 6 5
8 7 6 4
8 7 6 3
8 7 6 2
8 7 6 1
8 7 5 4
8 7 5 3
8 7 5 2
8 7 5 1
8 7 4 3
8 7 4 2
8 7 4 1
8 7 3 2
8 7 3 1
8 7 2 1
8 6 5 4
8 6 5 3
8 6 5 2
8 6 5 1
8 6 4 3
8 6 4 2
8 6 4 1
8 6 3 2
8 6 3 1
8 6 2 1
8 5 4 3
8 5 4 2
8 5 4 1
8 5 3 2
8 5 3 1
8 5 2 1
8 4 3 2
8 4 3 1
8 4 2 1
8 3 2 1
7 6 5 4
7 6 5 3
7 6 5 2
7 6 5 1
7 6 4 3
7 6 4 2
7 6 4 1
7 6 3 2
7 6 3 1
7 6 2 1
7 5 4 3
7 5 4 2
7 5 4 1
7 5 3 2
7 5 3 1
7 5 2 1
7 4 3 2
7 4 3 1
7 4 2 1
7 3 2 1
6 5 4 3
6 5 4 2
6 5 4 1
6 5 3 2
6 5 3 1
6 5 2 1
6 4 3 2
6 4 3 1
6 4 2 1
6 3 2 1
5 4 3 2
5 4 3 1
5 4 2 1
5 3 2 1
4 3 2 1 C:java>