2025年排列(Amn)与组合(Cmn)算法详解

科技前沿 • 2025-03-28 07:55 • 阅读 20

大家好，我是讯享网，很高兴认识大家。

不区分个体差异和顺序时用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; }

我们还可以用递推写法，数组记录，用空间换时间，原理就是杨辉三角形，如下图。

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]

2025年排列(Amn)与组合(Cmn)算法详解

相关推荐