计算组合数

矫情吗；* 2022-06-11 03:23 180阅读 0赞

#### Problem Description ####

计算组合数。C(n,m),表示从n个数中选择m个的组合数。  
计算公式如下：  
若：m=0，C(n,m)=1  
否则， 若 n=1，C(n,m)=1  
否则，若m=n，C(n,m)=1  
否则 C(n,m) = C(n-1,m-1) + C(n-1,m).

#### Input ####

第一行是正整数N，表示有N组要求的组合数。接下来N行，每行两个整数n，m (0 <= m <= n <= 20)。

#### Output ####

输出N行。每行输出一个整数表示C(n,m)。

#### Example Input ####

#### Example Output ####

代码：

这个题用递归和递推都能实现，用递归不能数据太大，否则打开空间过多，用递推得话，不要忘了定义long long int 
    递推:(递推即从第一个元素开始，利用for循环，算出每一个元素的值)
    #include <stdio.h>
    #include <stdlib.h>
    long int c(int m,int n)
    {
        long long int y;
        if((n==0)||(m==1)||(m==n))
         y = 1;
            else
               y = c(m-1,n-1) + c(m-1,n);
    
    
            return y;
    
    
    }
    
    
    int main()
    {
       int N;
       scanf("%d",&N);
    while(N--)
    {
          long long int y;
          int m,n;
          scanf("%d%d",&m,&n);
          y = c(m,n);
          printf("%lld\n",y);
    }
    
    
    
    
        return 0;
    }
    
    
    递归（即利用函数，多次调用函数。优点：代码简短。缺点，效率不高，占用空间较大）
    #include <stdio.h>
    #include <stdlib.h>
    long int c(int m,int n)
    {
        long long int y;
        if((n==0)||(m==1)||(m==n))
         y = 1;
            else
               y = c(m-1,n-1) + c(m-1,n);
    
    
            return y;
    
    
    }
    
    
    int main()
    {
       int N;
       scanf("%d",&N);
    while(N--)
    {
          long long int y;
          int m,n;
          scanf("%d%d",&m,&n);
          y = c(m,n);
          printf("%lld\n",y);
    }
    
    
    
    
        return 0;
    }