每天一道算法题：n个球中取出m个球不同思路分析

我不是女神ヾ 2022-10-28 03:59 223阅读 0赞

## 楔子 ##

在开始算法分析之前，这里需要引入数学中**组合**、**排列**的概念，先基本介绍一下组合、排列：

*  **排列**：

1.  定义：从n个不同的元素中任取m个(m<=n)元素，按照一定的顺序排成一列，叫做从n个不同的元素中取出m个元素的排列
2.  使用排列的三个条件：1、n个不同元素；2、任取m个；3、**讲究顺序**
3.  **排列数计算公式：A（n,m）**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70]  
    这里稍微说明一下，因为第一项有n-(1-1)，第二项是n-(2-1),所以说m项就n-(m-1);
4.  举例：A(4,2)

A(4,1) = > (4*3*2*1)/1
    		    =>4！/ (4-1)!
    		    =>(4*3*2*1)/(3*2*1)
    		    =>4	
    A(4,0) => 4！/（4-0)!
    			=>1

*  **组合**：

1.  定义：从n个不同的元素中任取m个(m<=n)元素并为一组，叫做从n个不同的元素中任取m个元素的组合
2.  使用组合的三个条件：1、n个不同的元素；2、任取m个；3、**并为一组，不讲究顺序**
3.  **组合数计算公式：C（n,m）；**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70 1]  
    4.来个例题：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70 2]

*  **组合与排列的区别**：

1.  共同点：都是从n个元素中任取m个元素
2.  不同点：排列与元素的顺序有关，而组合与元素的顺序无关，也就是说，组合是选择的结果，而排列是先选择再排列的结果,举个例子：`ABCD四个数按任意2个进行排列，那么可排列的结果有：AB、AC、AD、BC、BD、CD、BA、CA、DA、CB、DC、DB,而组合的结果有：AB、AC、AD、BC、BD、CD、对于组合来说，是讲究顺序的，所以AB和BA对于组合来说属于同一组合`

## 算法：求n个球中取出m个球的不同取法 ##

*  **循环思路**：根据上面对组合、排序的介绍，通过分析，我们可以知道这是一道组合题型，所以我们可以通过组合的公式轻松得出结果：C(n,m) = A(n,m)/A(m,m)；代码如下，

public static int getBall2(int n,int m){ 
            int stratum_N = 1;//用于计算n的阶层
            int stratum_M = 1;//用于计算m的阶层
            //如果m>n（ps:3个球怎么一次取5个emm,直接返回0）
            if(m>n) return 0;
            //如果m==n，那么肯定只有一种取法
            if(m==n) return 1;
            //如果m=0，那么同样只有一种取法，那就是不取
            if(m==0) return 1;
            //A(n,m)中，m就相当于n的阶层次数，而对于m本身来说，循环m次
            //刚好就是它本身的全部阶层，也就是m的全排列
            for(int i=0;i<m;i++){ 
                stratum_N *= (n-i);
                stratum_M *= (m-i);
            }
            return stratum_N/stratum_M;
        }

*  **递归思路**：在之前数组求和的文章中我们提过，使用递归需要构造相似性，也就是找到使用递归的条件，这个题我们乍一看貌似找不到相似性，那应该怎么做呢？这种时候，就需要我们自己去构造相似性了，我们假设从n个球中取出的m个球中，一定要有我特别中意的一个球，这样一来，我们就可以把\*\*“从n个球中取m个球”\*\*分解成两种情况：
    
    1.  取出的m个球中一定有我中意的那个球，因为我中意的那个球已经内定了，所以剩下的就变成了从n-1个球中取出m-1个球
    2.  取出的m个球中一定没有我中意的那个球，因为要取出的m个球中一定没有我中意的那个球，所以剩下的就变成了从n-1个球中取出m个球

结合这两种情况的取法，就是题目要求的从n个球中取m个球的所有取法，下面我们开始写代码

//递归方式：思路：
        // 构造递归，假设在要取的m个球中一定要取n个球中的某一个球，于是
        //n个球取m个球就变成了：
        // 1.n-1个球中取m-1个球 （一定要取某一个球，那么剩下的就从n-1个球中取m-1个球）
        // 2.n-1个球中取m个球(一定不取某个球，那么剩下的就从n-1个球中取m个)
        public static int getBall(int n,int m){ 
            //在n-1个球中取m个球，n不断减小，当n=m时，只有一种取法
            if(n==m) return 1;
            //当n<m时，这还取个锤子
            if(n<m) return 0;
            //在n-1个球中取m-1个球，这里n是大于m的，所以即使不断减小n还是大于m
            //当m==0的时候，取0个球只有一种取法，那就是不取，这里很容易理解错误
            //取0个球也是可以取得
            if(m==0) return 1;
            return getBall(n-1,m-1) + getBall(n-1,m);
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70]: /images/20221024/3838dba442de491f97b9cc5360b942b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70 1]: /images/20221024/a240252f567146d8a21d734494e064b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70 2]: /images/20221024/491bf77c565c4eeebc110c4f775b3944.png