方程x1+x2+..+的积分解数xN=k-yiteyi-C++库

给定N和K。任务是计算具有N个变量的线性方程的积分解的数量，如下所示：

null

x1+x2+x3…+xN-1+…+xN=K

例子 :

Input: N = 3, K = 3Output: 10Input: N = 2, K = 2Output: 3

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

方法： 这个问题可以用排列和组合的概念来解决。下面是分别求非负和正积分解的直接公式。

方程x1+x2+…+xn=k的非负积分解的个数由下式给出： （n+k-1）！/（n-1）*K 方程x1+x2+…+的正积分解的个数xn=k由下式给出 （k-1）！/（n-1）！*（k-n）！。

以下是上述方法的实施情况：

C++

                         // C++ program for above implementation                       
                         #include<iostream>                       
           
                         using                                     namespace                                     std ;                       
           
                         int                                     nCr(                                     int                                     n,                                     int                                     r)                       
                         {                       
                                                 int                                     fac[100] = {1} ;                       
                                   
                                                 for                                     (                                     int                                     i = 1 ; i < n + 1 ; i++)                       
                                                 {                       
                                                 fac[i] = fac[i - 1] * i ;                       
                                                 }                       
                                   
                                                 int                                     ans = fac[n] / (fac[n - r] *                       
                                                 fac[r]) ;                       
                                                 return                                     ans ;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 3 ;                       
                                                 int                                     k = 3 ;                       
                                   
                                                 int                                     ans = nCr(n + k - 1 , k) +                       
                                                 nCr(k - 1, n - 1);                       
                                   
                                                 cout << ans ;                       
                                   
                                                 return                                     0 ;                       
                         }                       
           
                         // This code is contributed                       
                         // by ANKITRAI1                       

JAVA

                         // Java program for above implementation                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                         static                                     int                                     nCr(                                     int                                     n,                                     int                                     r)                       
                         {                       
                                                 int                                     fac[] =                                     new                                     int                                     [                                     100                                     ] ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 fac[i] =                                     1                                     ;                       
                                   
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < n +                                     1                                     ; i++)                       
                                                 {                       
                                                 fac[i] = fac[i -                                     1                                     ] * i ;                       
                                                 }                       
                                   
                                                 int                                     ans = fac[n] / (fac[n - r] *                       
                                                 fac[r]);                       
                                                 return                                     ans ;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                                                 int                                     n =                                     3                                     ;                       
                                                 int                                     k =                                     3                                     ;                       
                                   
                                                 int                                     ans = nCr(n + k -                                     1                                     , k) +                       
                                                 nCr(k -                                     1                                     , n -                                     1                                     );                       
                                   
                                                 System.out.println(ans) ;                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by anuj_67                       

Python3

                         # Python implementation of                       
                         # above approach                       
           
                         # Calculate nCr i.e binomial                       
                         # cofficent nCr = n !/(r !*(n-r)!)                       
                         def                                     nCr(n, r):                       
           
                                                 # first find factorial                       
                                                 # upto n                       
                                                 fac                                     =                                     list                                     ()                       
                                                 fac.append(                                     1                                     )                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n                                     +                                     1                                     ):                       
                                                 fac.append(fac[i                                     -                                     1                                     ]                                     *                                     i)                       
           
                                                 # use nCr formula                       
                                                 ans                                     =                                     fac[n]                                     /                                     (fac[n                                     -                                     r]                                     *                                     fac[r])                       
                                                 return                                     ans                       
           
                         # n = number of variables                       
                         n                                     =                                     3                       
           
                         # sum of n variables = k                       
                         k                                     =                                     3                       
           
                         # find number of solutions                       
                         ans                                     =                                     nCr(n                                     +                                     k                                     -                                     1                                     , k)                                     +                                     nCr(k                                     -                                     1                                     , n                                     -                                     1                                     )                       
           
                         print                                     (ans)                       
           
                         # This code is contributed                       
                         # by ChitraNayal                       

C#

                         // C# program for above implementation                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                         static                                     int                                     nCr(                                     int                                     n,                                     int                                     r)                       
                         {                       
                                                 int                                     [] fac =                                     new                                     int                                     [100] ;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 fac[i] = 1;                       
                                   
                                                 for                                     (                                     int                                     i = 1 ; i < n + 1 ; i++)                       
                                                 {                       
                                                 fac[i] = fac[i - 1] * i ;                       
                                                 }                       
                                   
                                                 int                                     ans = fac[n] / (fac[n - r] *                       
                                                 fac[r]);                       
                                                 return                                     ans ;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main ()                       
                         {                       
                                                 int                                     n = 3 ;                       
                                                 int                                     k = 3 ;                       
                                   
                                                 int                                     ans = nCr(n + k - 1 , k) +                       
                                                 nCr(k - 1, n - 1);                       
                                   
                                                 Console.Write(ans) ;                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by ChitraNayal                       

PHP

                         <?php                       
                         // PHP implementation of above approach                       
           
                         // Calculate nCr i.e binomial                       
                         // cofficent nCr = n !/(r !*(n-r)!)                       
                         function                                     nCr(                                     $n                                     ,                                     $r                                     )                       
                         {                       
                                                 // first find factorial                       
                                                 // upto n                       
                                                 $fac                                     =                                     array                                     ();                       
                                                 array_push                                     (                                     $fac                                     , 1);                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $n                                     + 1;                                     $i                                     ++)                       
                                                 array_push                                     (                                     $fac                                     ,                                     $fac                                     [                                     $i                                     - 1] *                                     $i                                     );                       
           
                                                 // use nCr formula                       
                                                 $ans                                     =                                     $fac                                     [                                     $n                                     ] / (                                     $fac                                     [                                     $n                                     -                                     $r                                     ] *                       
                                                 $fac                                     [                                     $r                                     ]);                       
                                                 return                                     $ans                                     ;                       
                         }                       
           
                         // Driver Code                       
           
                         // n = number of variables                       
                         $n                                     = 3;                       
           
                         // sum of n variables = k                       
                         $k                                     = 3;                       
           
                         // find number of solutions                       
                         $ans                                     = nCr(                                     $n                                     +                                     $k                                     - 1,                                     $k                                     ) +                       
                                                 nCr(                                     $k                                     - 1,                                     $n                                     - 1);                       
           
                         print                                     (                                     $ans                                     );                       
           
                         // This code is contributed                       
                         // by mits                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program for above implementation                       
                         function                                     nCr(n, r)                       
                         {                       
                                                 var                                     fac = Array(100).fill(1);                       
                                   
                                                 for                                     (                                     var                                     i = 1 ; i < n + 1 ; i++)                       
                                                 {                       
                                                 fac[i] = fac[i - 1] * i ;                       
                                                 }                       
                                   
                                                 var                                     ans = fac[n] / (fac[n - r] *                       
                                                 fac[r]) ;                       
                                                 return                                     ans ;                       
                         }                       
           
                         // Driver Code                       
                         var                                     n = 3 ;                       
                         var                                     k = 3 ;                       
           
                         var                                     ans = nCr(n + k - 1 , k) +                       
                                                 nCr(k - 1, n - 1);                       
           
                         document.write(ans );                       
           
                         // This code is contributed by noob2000.                       
                         </script>                       

输出：

11.0

上述概念的应用：

方程x1+x2+…+xn=k的非负积分解的数量等于k个相同的球可以分布到N个唯一盒子中的方式的数量。
方程x1+x2+…+xn=k的正积分解的数量等于k个相同的球可以分布到N个唯一的盒子中的方式的数量，每个盒子必须至少包含1个球。

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

THE END

技术文章