元素为正整数且和为K的大小为N的数组数-yiteyi-C++库

给定两个正整数 N 和 K 。任务是找到大小为N的数组的数量，这些数组的元素应该是正整数，元素之和等于K。 例如：

null

Input : N = 2, K = 3Output : 2Explanation: [1, 2] and [2, 1] are the only arrays of size 2 whose sum is 3.Input : n = 3, k = 7Output : 15

先决条件： 星条旗

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

假设有K个相同的对象需要放置在N个容器（数组的N个索引）中，这样每个容器至少有一个对象。我们不再开始将对象放置到箱子中，而是开始将对象放置在一条线上，第一个箱子的对象将从左侧取出，然后是第二个箱子的对象，依此类推。因此，一旦知道什么是第一个物体进入第二个箱子，什么是第一个物体进入第三个箱子，就可以确定配置，依此类推。我们可以通过在两个物体之间的某些位置放置N X 1分隔条来表明这一点；由于任何垃圾箱都不允许为空，因此在给定的一对对象之间最多只能有一个条。所以，我们有K个物体在一条有K–1间隙的直线上。现在我们必须选择N–1间隙来放置K–1间隙中的钢筋。这可以由 ^K-1 C _N–1 . 以下是该方法的实施：

C++

                         // CPP Program to find the number of arrays of                       
                         // size N whose elements are positive integers                       
                         // and sum is K                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Return nCr                       
                         int                                     binomialCoeff(                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 int                                     C[k + 1];                       
                                                 memset                                     (C, 0,                                     sizeof                                     (C));                       
           
                                                 C[0] = 1;                                     // nC0 is 1                       
           
                                                 for                                     (                                     int                                     i = 1; i <= n; i++) {                       
                                                 // Compute next row of pascal triangle using                       
                                                 // the previous row                       
                                                 for                                     (                                     int                                     j = min(i, k); j > 0; j--)                       
                                                 C[j] = C[j] + C[j - 1];                       
                                                 }                       
                                                 return                                     C[k];                       
                         }                       
           
                         // Return the number of array that can be                       
                         // formed of size n and sum equals to k.                       
                         int                                     countArray(                                     int                                     N,                                     int                                     K)                       
                         {                       
                                                 return                                     binomialCoeff(K - 1, N - 1);                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     N = 2, K = 3;                       
           
                                                 cout << countArray(N, K) << endl;                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java Program to find the                       
                         // number of arrays of size                       
                         // N whose elements are positive                       
                         // integers and sum is K                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // Return nCr                       
                         static                                     int                                     binomialCoeff(                                     int                                     n,                       
                                                 int                                     k)                       
                         {                       
                                                 int                                     []C =                                     new                                     int                                     [k +                                     1                                     ];                       
           
           
                                                 C[                                     0                                     ] =                                     1                                     ;                                     // nC0 is 1                       
           
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= n; i++)                       
                                                 {                       
                                                 // Compute next row of pascal                       
                                                 // triangle using the previous row                       
                                                 for                                     (                                     int                                     j = Math.min(i, k); j >                                     0                                     ; j--)                       
                                                 C[j] = C[j] + C[j -                                     1                                     ];                       
                                                 }                       
                                                 return                                     C[k];                       
                         }                       
           
                         // Return the number of                       
                         // array that can be                       
                         // formed of size n and                       
                         // sum equals to k.                       
                         static                                     int                                     countArray(                                     int                                     N,                                     int                                     K)                       
                         {                       
                                                 return                                     binomialCoeff(K -                                     1                                     , N -                                     1                                     );                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                                                 int                                     N =                                     2                                     , K =                                     3                                     ;                       
           
                         System.out.println( countArray(N, K));                       
                         }                       
                         }                       
           
                         // This code is contributed by anuj_67.                       

Python3

                         # Python3 Program to find the number                       
                         # of arrays of size N whose elements                       
                         # are positive integers and sum is K                       
           
                         # Return nCr                       
                         def                                     binomialCoeff(n, k):                       
           
                                                 C                                     =                                     [                                     0                                     ]                                     *                                     (k                                     +                                     1                                     );                       
                                   
                                                 C[                                     0                                     ]                                     =                                     1                                     ;                                     # nC0 is 1                       
           
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n                                     +                                     1                                     ):                       
           
                                                 # Compute next row of pascal                       
                                                 # triangle using the previous row                       
                                                 for                                     j                                     in                                     range                                     (                                     min                                     (i, k),                                     0                                     ,                                     -                                     1                                     ):                       
                                                 C[j]                                     =                                     C[j]                                     +                                     C[j                                     -                                     1                                     ];                       
                                                 return                                     C[k];                       
           
                         # Return the number of array that                       
                         # can be formed of size n and                       
                         # sum equals to k.                       
                         def                                     countArray(N, K):                       
           
                                                 return                                     binomialCoeff(K                                     -                                     1                                     , N                                     -                                     1                                     );                       
           
                         # Driver Code                       
                         N                                     =                                     2                                     ;                       
                         K                                     =                                     3                                     ;                       
           
                         print                                     (countArray(N, K));                       
           
                         # This code is contributed by mits                       

C#

                         // C# Program to find the                       
                         // number of arrays of size                       
                         // N whose elements are positive                       
                         // integers and sum is K                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                         // Return nCr                       
                         static                                     int                                     binomialCoeff(                                     int                                     n,                       
                                                 int                                     k)                       
                         {                       
                                                 int                                     []C =                                     new                                     int                                     [k + 1];                       
           
           
                                                 C[0] = 1;                                     // nC0 is 1                       
           
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 {                       
                                                 // Compute next row of                       
                                                 // pascal triangle using                       
                                                 // the previous row                       
                                                 for                                     (                                     int                                     j = Math.Min(i, k);                       
                                                 j > 0; j--)                       
                                                 C[j] = C[j] + C[j - 1];                       
                                                 }                       
                                                 return                                     C[k];                       
                         }                       
           
                         // Return the number of                       
                         // array that can be                       
                         // formed of size n and                       
                         // sum equals to k.                       
                         static                                     int                                     countArray(                                     int                                     N,                       
                                                 int                                     K)                       
                         {                       
                                                 return                                     binomialCoeff(K - 1,                       
                                                 N - 1);                       
                         }                       
           
                         // Driver Code                       
                         static                                     public                                     void                                     Main ()                       
                         {                       
                                                 int                                     N = 2, K = 3;                       
           
                                                 Console.WriteLine(                       
                                                 countArray(N, K));                       
                         }                       
                         }                       
           
                         // This code is contributed by ajit                       

PHP

                         <?php                       
                         // PHP Program to find the                       
                         // number of arrays of size                       
                         // N whose elements are                       
                         // positive integers and                       
                         // sum is K                       
           
                         // Return nCr                       
                         function                                     binomialCoeff(                                     $n                                     ,                                     $k                                     )                       
                         {                       
                                                 $C                                     =                                     array_fill                                     (0, (                                     $k                                     + 1), 0);                       
                                   
                                                 $C                                     [0] = 1;                                     // nC0 is 1                       
           
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 // Compute next row                       
                                                 // of pascal triangle                       
                                                 // using the previous row                       
                                                 for                                     (                                     $j                                     = min(                                     $i                                     ,                                     $k                                     );                       
                                                 $j                                     > 0;                                     $j                                     --)                       
                                                 $C                                     [                                     $j                                     ] =                                     $C                                     [                                     $j                                     ] +                       
                                                 $C                                     [                                     $j                                     - 1];                       
                                                 }                       
                                                 return                                     $C                                     [                                     $k                                     ];                       
                         }                       
           
                         // Return the number of                       
                         // array that can be                       
                         // formed of size n and                       
                         // sum equals to k.                       
                         function                                     countArray(                                     $N                                     ,                                     $K                                     )                       
                         {                       
                                                 return                                     binomialCoeff(                                     $K                                     - 1,                       
                                                 $N                                     - 1);                       
                         }                       
           
                         // Driver Code                       
                         $N                                     = 2;                       
                         $K                                     = 3;                       
           
                         echo                                     countArray(                                     $N                                     ,                                     $K                                     );                       
           
                         // This code is contributed by mits                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript Program to find the number of arrays of                       
                         // size N whose elements are positive integers                       
                         // and sum is K                       
           
                         // Return nCr                       
                         function                                     binomialCoeff(n, k)                       
                         {                       
                                                 var                                     C = Array(k+1).fill(0);                       
           
                                                 C[0] = 1;                                     // nC0 is 1                       
           
                                                 for                                     (                                     var                                     i = 1; i <= n; i++) {                       
                                                 // Compute next row of pascal triangle using                       
                                                 // the previous row                       
                                                 for                                     (                                     var                                     j = Math.min(i, k); j > 0; j--)                       
                                                 C[j] = C[j] + C[j - 1];                       
                                                 }                       
                                                 return                                     C[k];                       
                         }                       
           
                         // Return the number of array that can be                       
                         // formed of size n and sum equals to k.                       
                         function                                     countArray(N, K)                       
                         {                       
                                                 return                                     binomialCoeff(K - 1, N - 1);                       
                         }                       
           
                         // Driver Code                       
                         var                                     N = 2, K = 3;                       
                         document.write( countArray(N, K));                       
           
                         </script>                       

输出：

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

THE END

技术文章