小白编程题：组合数问题

迭代法

int zuhe(int m, int n) {
    if (n < 0 || n > m) return 0;
    int sum = 1;
    for (int i = 1; i <= n; i++) {// 计算 C(m, n) = m! / (n! * (m-n)!)
        sum *= m - n + i;
        sum /= i;
    }
    return sum;
}

递归法

方法1：$C_m^n=\frac{A_m^n}{A_n^n}=\frac{m!}{n!(m?n)!}$

int jiecheng(int x){
    if(x==1) return 1;
    else return x*jiecheng(x-1);
}
int zuhe(int m,int n){
    return jiecheng(m)/(jiecheng(n)*jiecheng(m-n));
}

方法2：$C_m^n=C_{m?1}^{n?1}+C_{m?1}^n$

int zuhe(int m,int n){
    if(m==n) return 1;
    else if(n==1) return m;
    else return zuhe(m-1,n-1)+zuhe(m-1,n);
}