niop-基础题库 “计算组合数”

题目描述:

给出两个非负整数n和m，编写程序计算组合数C(n,m)的值，C(n,m)的意思是n个当中取m个，总共有多少种取法。

输入格式:

一行两个空格隔开的非负整数n,m。

输出格式:

输出一个数表示C(n,m)。

样例输入:

5 2

样例输出:

10

提示:

0<n<=50,0<=m<=n。

C(n,m) = n! / ( m! * (n-m)! )，其中!为阶乘符号，如n! = 1*2*3*4*…*n。

解题：

这道题比较容易想到的思路是分别求出n!，m!，(n-m)!，然后利用组合数公式计算。然而，int类型的变量只能存储13以内的数的阶乘，long long类型的变量只能存储到20的阶乘。要计算组合数，只能边乘边除。

C(n,m) = n! /(m! * (n-m)!) = (m+1)*(m+2)*(m+3)…*n / (1*2*3*…*(n-m))，分子和分母各有(n-m)项，我们用循环来实现。

 
代码：

#include<bits/stdc++.h>
using namespace std;int main()
{
  long long n,m,res=1;
  cin >>n>>m;
  for(int i=1; i<=n-m; i++)
  {
    res=res*(m+i)/i;
  }
  cout << res;  return 0;
}