计算nCr值的程序-yiteyi-C++库

null

A. 二项式系数 C（n，k）可以定义为（1+X）^n展开式中X^k的系数。
二项式系数C（n，k）也给出了从n个对象中选择k个对象的方法的数量，而不考虑顺序；更正式地说，n-元素集的k-元素子集（或k-组合）的数量。

给定两个数字n和r，求 ^N C _R 例如：

Input :  n = 5, r = 2Output : 10The value of 5C2 is 10Input : n = 3, r = 1Output : 3

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

这个想法只是基于以下公式。

^N C _R =（n！）/（r！*（n-r）！）

C

                         #include <stdio.h>                       
           
                         int                                     factorial(                                     int                                     n) {                       
                                                 int                                     factorial = 1;                       
                                                 for                                     (                                     int                                     i = 2; i <= n; i++)                       
                                                 factorial = factorial * i;                       
                                                 return                                     factorial;                       
                         }                       
           
                         int                                     nCr(                                     int                                     n,                                     int                                     r) {                       
                                                 return                                     factorial(n) / (factorial(r) * factorial(n - r));                       
                         }                       
           
                         int                                     main() {                       
                                                 int                                     n = 5, r = 3;                       
                                                 printf                                     (                                     "%d"                                     , nCr(n, r));                       
                                                 return                                     0;                       
                         }                       
           
                         // This code was contributed by Omkar Prabhune                       

C++

                         // CPP program To calculate The Value Of nCr                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         int                                     fact(                                     int                                     n);                       
           
                         int                                     nCr(                                     int                                     n,                                     int                                     r)                       
                         {                       
                                                 return                                     fact(n) / (fact(r) * fact(n - r));                       
                         }                       
           
                         // Returns factorial of n                       
                         int                                     fact(                                     int                                     n)                       
                         {                       
                                                 int                                     res = 1;                       
                                                 for                                     (                                     int                                     i = 2; i <= n; i++)                       
                                                 res = res * i;                       
                                                 return                                     res;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 5, r = 3;                       
                                                 cout << nCr(n, r);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program To calculate                       
                         // The Value Of nCr                       
                         class                                     GFG {                       
           
                         static                                     int                                     nCr(                                     int                                     n,                                     int                                     r)                       
                         {                       
                                                 return                                     fact(n) / (fact(r) *                       
                                                 fact(n - r));                       
                         }                       
           
                         // Returns factorial of n                       
                         static                                     int                                     fact(                                     int                                     n)                       
                         {                       
                                                 int                                     res =                                     1                                     ;                       
                                                 for                                     (                                     int                                     i =                                     2                                     ; i <= n; i++)                       
                                                 res = res * i;                       
                                                 return                                     res;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     n =                                     5                                     , r =                                     3                                     ;                       
                                                 System.out.println(nCr(n, r));                       
                         }                       
                         }                       
           
                         // This code is Contributed by                       
                         // Smitha Dinesh Semwal.                       

Python 3

                         # Python 3 program To calculate                       
                         # The Value Of nCr                       
           
                         def                                     nCr(n, r):                       
           
                                                 return                                     (fact(n)                                     /                                     (fact(r)                       
                                                 *                                     fact(n                                     -                                     r)))                       
           
                         # Returns factorial of n                       
                         def                                     fact(n):                       
           
                                                 res                                     =                                     1                       
                                   
                                                 for                                     i                                     in                                     range                                     (                                     2                                     , n                                     +                                     1                                     ):                       
                                                 res                                     =                                     res                                     *                                     i                       
                                   
                                                 return                                     res                       
           
                         # Driver code                       
                         n                                     =                                     5                       
                         r                                     =                                     3                       
                         print                                     (                                     int                                     (nCr(n, r)))                       
           
                         # This code is contributed                       
                         # by Smitha                       

C#

                         // C# program To calculate                       
                         // The Value Of nCr                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                         static                                     int                                     nCr(                                     int                                     n,                                     int                                     r)                       
                         {                       
                                                 return                                     fact(n) / (fact(r) *                       
                                                 fact(n - r));                       
                         }                       
           
                         // Returns factorial of n                       
                         static                                     int                                     fact(                                     int                                     n)                       
                         {                       
                                                 int                                     res = 1;                       
                                                 for                                     (                                     int                                     i = 2; i <= n; i++)                       
                                                 res = res * i;                       
                                                 return                                     res;                       
                         }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 5, r = 3;                       
                                                 Console.Write(nCr(n, r));                       
                                                 }                       
                         }                       
           
                         // This code is Contributed by nitin mittal.                       

PHP

                         <?php                       
                         // PHP program To calculate                       
                         // the Value Of nCr                       
           
           
                         function                                     nCr(                                     $n                                     ,                                     $r                                     )                       
                         {                       
                                                 return                                     fact(                                     $n                                     ) / (fact(                                     $r                                     ) *                       
                                                 fact(                                     $n                                     -                                     $r                                     ));                       
                         }                       
           
                         // Returns factorial of n                       
                         function                                     fact(                                     $n                                     )                       
                         {                       
                                                 $res                                     = 1;                       
                                                 for                                     (                                     $i                                     = 2;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 $res                                     =                                     $res                                     *                                     $i                                     ;                       
                                                 return                                     $res                                     ;                       
                         }                       
           
                                                 // Driver code                       
                                                 $n                                     = 5;                       
                                                 $r                                     = 3;                       
                                                 echo                                     nCr(                                     $n                                     ,                                     $r                                     );                       
                                   
                         // This code is contributed by vt_m.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program To calculate The Value Of nCr                       
           
                         function                                     nCr(n, r)                       
                         {                       
                                                 return                                     fact(n) / (fact(r) * fact(n - r));                       
                         }                       
           
                         // Returns factorial of n                       
                         function                                     fact(n)                       
                         {                       
                                                 var                                     res = 1;                       
                                                 for                                     (                                     var                                     i = 2; i <= n; i++)                       
                                                 res = res * i;                       
                                                 return                                     res;                       
                         }                       
           
                         // Driver code                       
                         var                                     n = 5, r = 3;                       
                         document.write(nCr(n, r));                       
           
           
                         </script>                       

输出：

时间复杂性： O（n）

辅助空间： O（1）

更高效的解决方案： 动态规划|集9（二项式系数）时空效率二项式系数 关于二项式系数的所有文章

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章