c++求组合数。计算 C(m,n)= \frac {m!}{n!(m-n)!} 其中计算C(m,n)的函数首部为:int cmn(int m, int n). 计算阶乘的函数首部为:int fac(int n)↵ 并用cmn函数打印杨辉三角形。

以下是实现代码：

#include<iostream>
using namespace std;

int fac(int n) { // 计算阶乘的函数
    if(n == 0 || n == 1) return 1;
    return n * fac(n - 1);
}

int cmn(int m, int n) { // 计算组合数的函数
    return fac(m) / (fac(n) * fac(m - n));
}

void printYangHui(int n) { // 打印杨辉三角形
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= i; j++) {
            cout << cmn(i, j) << " ";
        }
        cout << endl;
    }
}

int main() {
    printYangHui(10); // 打印10行的杨辉三角形
    return 0;
}

输出结果为：

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
1 8 28 56 70 56 28 8 1 
1 9 36 84 126 126 84 36 9 1 

相关问题

用c++计算出从n个不同的元素中取出m个元素的组合数

在C++中，可以使用动态规划的方法来计算从n个不同的元素中取出m个元素的组合数，这个数值通常称为“组合”的二项式系数，记作C(n, m)。经典的计算公式是：

\[ C(n, m) = \frac{n!}{m!(n-m)!} \]

其中n!表示n的阶乘，即所有小于及等于n的正整数相乘的结果。

由于直接计算阶乘可能会导致整数溢出，特别是当n和m较大时，我们可以使用一种优化算法，如迭代的方式来计算组合数，避免一次性处理大数运算。这里提供一个简单的示例代码：

#include <vector>

// 计算阶乘
unsigned long long factorial(unsigned int n) {
    unsigned long long fact = 1;
    for (int i = 1; i <= n; ++i) {
        fact *= i;
    }
    return fact;
}

// 计算组合数
unsigned long long combination(int n, int m) {
    if (m > n || m == 0) { // 防止除零错误和超出范围
        return 0;
    }
    return factorial(n) / (factorial(m) * factorial(n - m));
}

int main() {
    int n, m;
    std::cin >> n >> m;
    std::cout << "组合数 C(" << n << ", " << m << ") : " << combination(n, m) << std::endl;
    return 0;
}

运行此程序时，输入n和m值即可得到结果。注意，当n和m非常大时，这种方法可能也不是最有效率的，因为仍然存在整数溢出的风险。在这种场景下，可以考虑使用高精度库或者其他数学库提供的功能。

给你两个整数𝑎, 𝑏，输出𝐶𝑎 𝑏 对 998244353 取模的结果 其中为从𝑎个不同元素中每次取出𝑏个不同元素的集合个数。 具体而言，𝐶𝑎 𝑏 = 𝑎! (𝑎−𝑏)!𝑏!，特殊地，𝐶𝑛 0 = 𝐶𝑛 𝑛 = 𝐶0 0 = 1。

题目描述

给你两个整数 $a,b$，输出 $C_a^b$ 对 $998244353$ 取模的结果 其中 $C_a^b$ 为从 $a$ 个不同元素中每次取出 $b$ 个不同元素的集合个数。 具体而言，$C_a^b = \frac{a!}{(a-b)!b!}$，特殊地，$C_n^0 = C_n^n = C_0^0 = 1$。

样例

输入

4 2

输出

6

算法1

(组合数公式+大数取模)

时间复杂度

$O(1)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
long long ksm(long long a,long long b){
long long ans=1;
while(b){
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int main(){
long long n,m,ans=1;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++){
ans=ans*(n-i+1)%mod;//分子
ans=ans*ksm(i,mod-2)%mod;//分母
}
printf("%lld",ans);
return 0;
}