不区分个体差异和顺序时用Cmn(m小n大),需要区分个体和顺序时候用Amn。
例1:从10个相同的球里取出5个球,不需要区分先后顺序,也不区分其他个体特征,一把抓过去够5个就行,这就是C510(m=5,n=10)。
例2:有10把凳子,需要安排10个人去坐,问有多少种可能性。这里,就需要体现顺序。那么,坐第一个凳子有10种选择,做第二个凳子的有9种选择,以此类推,坐最后一个凳子的就只剩1种选择,每个选择之间是“和”的关系,即为10x9x8x7x6x5x4x3x2x1=A1010=10!。
下面是排列与组合的一般公式:(!代表阶乘)
A510 = 10! ÷ 5! = 6 x 7 x 8 x 9 x 10
int A(int m, int n)
{
int ret = 1;
for (int i = m + 1; i <= n; i++)
ret *= i;
return ret;
}
C38 = (8 x 7 x 6) / (3 x 2 x 1)
注意"ret = ret * (n - i + 1) / i;"不能写成"ret *= (n - i + 1) / i;" 因为(n - i + 1) / i可能是小数,会计算错误
int C(int m, int n) {
int ret = 1;
for (int i = 1; i <= m; i++)
ret = ret * (n - i + 1) / i;
return ret;
}
我们还可以用递推写法,数组记录,用空间换时间,原理就是杨辉三角形,如下图。
文章来源:https://www.toymoban.com/news/detail-757700.html
void init_C() {
for (int i = 0; i < N; i++) { //N表示预处理最大的下标
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i)//每一行最右边和最左边的数是1
c[i][j] = 1;
else
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
}
注意:函数写法前一个数(m)比后一个数(n)要小,递推写法数组c[m][n]的前一个数(m)比后一个数n要大。例如:函数写法C(3, 8) = 递推写法数组c[8][3]文章来源地址https://www.toymoban.com/news/detail-757700.html
到了这里,关于排列(Amn)与组合(Cmn)算法详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!