数一数将一个数字分成4部分的方法-yiteyi-C++库

给定一个正整数n，找到多种方法将n除以四部分或将n表示为四个正整数的和。这里n从0到5000不等。 例如：

null

Input:  n =  5Output: 1There is only one way (1, 1, 1, 2)Input:  n =  6Output: 2There are two ways (1, 1, 1, 3) and (1, 1, 2, 2)Input:  n =  8Output: 5There are five ways (2, 2, 2, 2), (1, 1, 1, 5),(1, 1, 3, 3), (1, 1, 2, 4) and (1, 2, 2, 3)

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法1（简单解决方案） 运行四个嵌套循环，以生成所有可能的不同四重态。下面是C++实现的简单算法。以下是上述方法的实施情况：

C++

                         // A Simple C++ program to count number of ways to                       
                         // represent a number n as sum of four.                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns count of ways                       
                         int                                     countWays(                                     int                                     n)                       
                         {                       
                                                 int                                     counter = 0;                                     // Initialize result                       
           
                                                 // Generate all possible quadruplet and increment                       
                                                 // counter when sum of a quadruplet is equal to n                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 for                                     (                                     int                                     j = i; j < n; j++)                       
                                                 for                                     (                                     int                                     k = j; k < n; k++)                       
                                                 for                                     (                                     int                                     l = k; l < n; l++)                       
                                                 if                                     (i + j + k + l == n)                       
                                                 counter++;                       
                                                 return                                     counter;                       
                         }                       
           
                         // Driver program                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 8;                       
                                                 cout << countWays(n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // A Simple Java  program to count number of ways to                       
                         // represent a number n as sum of four.                       
           
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
                                   
                         // Returns count of ways                       
                         static                                     int                                     countWays(                                     int                                     n)                       
                         {                       
                                                 int                                     counter =                                     0                                     ;                                     // Initialize result                       
           
                                                 // Generate all possible quadruplet and increment                       
                                                 // counter when sum of a quadruplet is equal to n                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < n; i++)                       
                                                 for                                     (                                     int                                     j = i; j < n; j++)                       
                                                 for                                     (                                     int                                     k = j; k < n; k++)                       
                                                 for                                     (                                     int                                     l = k; l < n; l++)                       
                                                 if                                     (i + j + k + l == n)                       
                                                 counter++;                       
                                                 return                                     counter;                       
                         }                       
           
                         // Driver program                       
                                   
                                                 public                                     static                                     void                                     main (String[] args) {                       
                                                 int                                     n =                                     8                                     ;                       
                                                 System.out.println (countWays(n));                       
                                                 }                       
                         }                       

Python3

                         # A Simple python3 program to count                       
                         # number of ways to represent a number                       
                         # n as sum of four.                       
           
                         # Returns count of ways                       
                         def                                     countWays(n):                       
           
                                                 counter                                     =                                     0                                     # Initialize result                       
           
                                                 # Generate all possible quadruplet                       
                                                 # and increment counter when sum of                       
                                                 # a quadruplet is equal to n                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n):                       
                                                 for                                     j                                     in                                     range                                     (i, n):                       
                                                 for                                     k                                     in                                     range                                     (j, n):                       
                                                 for                                     l                                     in                                     range                                     (k, n):                       
                                                 if                                     (i                                     +                                     j                                     +                                     k                                     +                                     l                                     =                                     =                                     n):                       
                                                 counter                                     +                                     =                                     1                       
                                                 return                                     counter                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
           
                                                 n                                     =                                     8                       
                                                 print                                     (countWays(n))                       
           
                         # This code is contributed by ita_c                       

C#

                         // A Simple C# program to count number                       
                         // of ways to represent a number n as                       
                         // sum of four.                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // Returns count of ways                       
                         static                                     int                                     countWays(                                     int                                     n)                       
                         {                       
                                                 int                                     counter = 0;                                     // Initialize result                       
           
                                                 // Generate all possible quadruplet                       
                                                 // and increment counter when sum of                       
                                                 // a quadruplet is equal to n                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 for                                     (                                     int                                     j = i; j < n; j++)                       
                                                 for                                     (                                     int                                     k = j; k < n; k++)                       
                                                 for                                     (                                     int                                     l = k; l < n; l++)                       
                                                 if                                     (i + j + k + l == n)                       
                                                 counter++;                       
                                                 return                                     counter;                       
                         }                       
           
                         // Driver Code                       
                         static                                     public                                     void                                     Main ()                       
                         {                       
                                                 int                                     n = 8;                       
                                                 Console.WriteLine(countWays(n));                       
                         }                       
                         }                       
           
                         // This code is contributed by Sachin                       

PHP

                         <?php                       
                         // A Simple PHP program to count                       
                         // number of ways to represent                       
                         // a number n as sum of four.                       
           
                         // Returns count of ways                       
                         function                                     countWays(                                     $n                                     )                       
                         {                       
                                                 // Initialize result                       
                                                 $counter                                     = 0;                       
           
                                                 // Generate all possible quadruplet                       
                                                 // and increment counter when sum                       
                                                 // of a quadruplet is equal to n                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 for                                     (                                     $j                                     =                                     $i                                     ;                                     $j                                     <                                     $n                                     ;                                     $j                                     ++)                       
                                                 for                                     (                                     $k                                     =                                     $j                                     ;                                     $k                                     <                                     $n                                     ;                                     $k                                     ++)                       
                                                 for                                     (                                     $l                                     =                                     $k                                     ;                                     $l                                     <                                     $n                                     ;                                     $l                                     ++)                       
                                                 if                                     (                                     $i                                     +                                     $j                                     +                                     $k                                     +                                     $l                                     ==                                     $n                                     )                       
                                                 $counter                                     ++;                       
                                                 return                                     $counter                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 8;                       
                         echo                                     countWays(                                     $n                                     );                       
                                   
                         // This code is contributed by m_kit                       
                         ?>                       

Javascript

                         <script>                       
                                                 // A Simple Javascript  program to count number of ways to                       
                         // represent a number n as sum of four.                       
                                   
                                                 // Returns count of ways                       
                                                 function                                     countWays(n)                       
                                                 {                       
                                                 let counter = 0;                                     // Initialize result                       
                                   
                                                 // Generate all possible quadruplet and increment                       
                                                 // counter when sum of a quadruplet is equal to n                       
                                                 for                                     (let i = 1; i < n; i++)                       
                                                 for                                     (let j = i; j < n; j++)                       
                                                 for                                     (let k = j; k < n; k++)                       
                                                 for                                     (let l = k; l < n; l++)                       
                                                 if                                     (i + j + k + l == n)                       
                                                 counter++;                       
                                                 return                                     counter;                       
                                                 }                       
                                   
                                                 let n = 8;                       
                                                 document.write(countWays(n));                       
                                   
                                                 // This code is contributed by rag2127                       
           
                         </script>                       

输出：

上述解的时间复杂度为O（n） ^4. ) 方法2（使用动态规划） 这个想法基于下面的递归解决方案。

countWays(n, parts, nextPart) = ∑countWays(n, parts, i)                          nextPart <= i  Input numberparts    --> Count of parts of n. Initially parts = 4nextPart --> Starting point for next part to be tried             We try for all values from nextPart to n.We initially call the function as countWays(n, 4, 1)

下面是基于上述思想的动态规划解决方案。

C++

                         // A Dynamic Programming based solution to count number                       
                         // of ways to represent n as sum of four numbers                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                         int                                     dp[5001][5001][5];                       
           
                         // "parts" is number of parts left, n is the value left                       
                         // "nextPart" is starting point from where we start trying                       
                         // for next part.                       
                         int                                     countWaysUtil(                                     int                                     n,                                     int                                     parts,                                     int                                     nextPart)                       
                         {                       
                                                 // Base cases                       
                                                 if                                     (parts == 0 && n == 0)                                     return                                     1;                       
                                                 if                                     (n <= 0 || parts <= 0)                                     return                                     0;                       
           
                                                 // If this subproblem is already solved                       
                                                 if                                     (dp[n][nextPart][parts] != -1)                       
                                                 return                                     dp[n][nextPart][parts];                       
           
                                                 int                                     ans = 0;                                     // Initialize result                       
           
                                                 // Count number of ways for remaining number n-i                       
                                                 // remaining parts "parts-1", and for all part                       
                                                 // varying from 'nextPart' to 'n'                       
                                                 for                                     (                                     int                                     i = nextPart; i <= n; i++)                       
                                                 ans += countWaysUtil(n-i, parts-1, i);                       
           
                                                 // Store computed answer in table and return                       
                                                 // result                       
                                                 return                                     (dp[n][nextPart][parts] = ans);                       
                         }                       
           
                         // This function mainly initializes dp table and                       
                         // calls countWaysUtil()                       
                         int                                     countWays(                                     int                                     n)                       
                         {                       
                                                 memset                                     (dp, -1,                                     sizeof                                     (dp));                       
                                                 return                                     countWaysUtil(n, 4, 1);                       
                         }                       
           
                         // Driver program                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 8;                       
                                                 cout << countWays(n) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // A Dynamic Programming based solution to count number                       
                         // of ways to represent n as sum of four numbers                       
                         class                                     GFG                       
                         {                       
           
                         static                                     int                                     dp[][][] =                                     new                                     int                                     [                                     5001                                     ][                                     5001                                     ][                                     5                                     ];                       
           
                         // "parts" is number of parts left, n is the value left                       
                         // "nextPart" is starting point from where we start trying                       
                         // for next part.                       
                         static                                     int                                     countWaysUtil(                                     int                                     n,                                     int                                     parts,                                     int                                     nextPart)                       
                         {                       
                                                 // Base cases                       
                                                 if                                     (parts ==                                     0                                     && n ==                                     0                                     )                                     return                                     1                                     ;                       
                                                 if                                     (n <=                                     0                                     || parts <=                                     0                                     )                                     return                                     0                                     ;                       
           
                                                 // If this subproblem is already solved                       
                                                 if                                     (dp[n][nextPart][parts] != -                                     1                                     )                       
                                                 return                                     dp[n][nextPart][parts];                       
           
                                                 int                                     ans =                                     0                                     ;                                     // Initialize result                       
           
                                                 // Count number of ways for remaining number n-i                       
                                                 // remaining parts "parts-1", and for all part                       
                                                 // varying from 'nextPart' to 'n'                       
                                                 for                                     (                                     int                                     i = nextPart; i <= n; i++)                       
                                                 ans += countWaysUtil(n-i, parts-                                     1                                     , i);                       
           
                                                 // Store computed answer in table and return                       
                                                 // result                       
                                                 return                                     (dp[n][nextPart][parts] = ans);                       
                         }                       
           
                         // This function mainly initializes dp table and                       
                         // calls countWaysUtil()                       
                         static                                     int                                     countWays(                                     int                                     n)                       
                         {                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i <                                     5001                                     ; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j =                                     0                                     ; j <                                     5001                                     ; j++)                       
                                                 {                       
                                                 for                                     (                                     int                                     l =                                     0                                     ; l <                                     5                                     ; l++)                       
                                                 dp[i][j][l] = -                                     1                                     ;                       
                                                 }                       
                                                 }                       
                                                 return                                     countWaysUtil(n,                                     4                                     ,                                     1                                     );                       
                         }                       
           
                         // Driver program                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     n =                                     8                                     ;                       
                                                 System.out.println(countWays(n));                       
                         }                       
                         }                       
           
                         /* This code contributed by PrinciRaj1992 */                       

Python3

                         # A Dynamic Programming based solution                       
                         # to count number of ways to represent                       
                         # n as sum of four numbers                       
           
                         dp                                     =                                     [[[                                     -                                     1                                     for                                     i                                     in                                     range                                     (                                     5                                     )]                       
                                                 for                                     i                                     in                                     range                                     (                                     501                                     )]                       
                                                 for                                     i                                     in                                     range                                     (                                     501                                     )]                       
           
                         # "parts" is number of parts left, n is                       
                         # the value left "nextPart" is starting                       
                         # point from where we start trying                       
                         # for next part.                       
                         def                                     countWaysUtil(n, parts, nextPart):                       
                                   
                                                 # Base cases                       
                                                 if                                     (parts                                     =                                     =                                     0                                     and                                     n                                     =                                     =                                     0                                     ):                       
                                                 return                                     1                       
                                                 if                                     (n <                                     =                                     0                                     or                                     parts <                                     =                                     0                                     ):                       
                                                 return                                     0                       
           
                                                 # If this subproblem is already solved                       
                                                 if                                     (dp[n][nextPart][parts] !                                     =                                     -                                     1                                     ):                       
                                                 return                                     dp[n][nextPart][parts]                       
           
                                                 ans                                     =                                     0                                     # Initialize result                       
           
                                                 # Count number of ways for remaining                       
                                                 # number n-i remaining parts "parts-1",                       
                                                 # and for all part varying from                       
                                                 # 'nextPart' to 'n'                       
                                                 for                                     i                                     in                                     range                                     (nextPart, n                                     +                                     1                                     ):                       
                                                 ans                                     +                                     =                                     countWaysUtil(n                                     -                                     i, parts                                     -                                     1                                     , i)                       
           
                                                 # Store computed answer in table                       
                                                 # and return result                       
                                                 dp[n][nextPart][parts]                                     =                                     ans                       
                                                 return                                     (ans)                       
           
                         # This function mainly initializes dp                       
                         # table and calls countWaysUtil()                       
                         def                                     countWays(n):                       
                                                 return                                     countWaysUtil(n,                                     4                                     ,                                     1                                     )                       
           
                         # Driver Code                       
                         n                                     =                                     8                       
                         print                                     (countWays(n))                       
           
                         # This code is contributed                       
                         # by sahishelangia                       

C#

                         // A Dynamic Programming based solution to count number                       
                         // of ways to represent n as sum of four numbers                       
                         using                                     System;                       
                                   
                         class                                     GFG                       
                         {                       
           
                         static                                     int                                     [,,]dp =                                     new                                     int                                     [5001, 5001, 5];                       
           
                         // "parts" is number of parts left, n is the value left                       
                         // "nextPart" is starting point from where we start trying                       
                         // for next part.                       
                         static                                     int                                     countWaysUtil(                                     int                                     n,                                     int                                     parts,                                     int                                     nextPart)                       
                         {                       
                                                 // Base cases                       
                                                 if                                     (parts == 0 && n == 0)                                     return                                     1;                       
                                                 if                                     (n <= 0 || parts <= 0)                                     return                                     0;                       
           
                                                 // If this subproblem is already solved                       
                                                 if                                     (dp[n,nextPart,parts] != -1)                       
                                                 return                                     dp[n,nextPart,parts];                       
           
                                                 int                                     ans = 0;                                     // Initialize result                       
           
                                                 // Count number of ways for remaining number n-i                       
                                                 // remaining parts "parts-1", and for all part                       
                                                 // varying from 'nextPart' to 'n'                       
                                                 for                                     (                                     int                                     i = nextPart; i <= n; i++)                       
                                                 ans += countWaysUtil(n - i, parts - 1, i);                       
           
                                                 // Store computed answer in table and return                       
                                                 // result                       
                                                 return                                     (dp[n,nextPart,parts] = ans);                       
                         }                       
           
                         // This function mainly initializes dp table and                       
                         // calls countWaysUtil()                       
                         static                                     int                                     countWays(                                     int                                     n)                       
                         {                       
                                                 for                                     (                                     int                                     i = 0; i < 5001; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = 0; j < 5001; j++)                       
                                                 {                       
                                                 for                                     (                                     int                                     l = 0; l < 5; l++)                       
                                                 dp[i, j, l] = -1;                       
                                                 }                       
                                                 }                       
                                                 return                                     countWaysUtil(n, 4, 1);                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main(String[] args)                       
                         {                       
                                                 int                                     n = 8;                       
                                                 Console.WriteLine(countWays(n));                       
                         }                       
                         }                       
           
                         // This code contributed by Rajput-Ji                       

PHP

                         <?php                       
                         // A Dynamic Programming based solution to                       
                         // count number of ways to represent n as                       
                         // sum of four numbers                       
                         $dp                                     =                                     array_fill                                     (0, 501,                       
                                                 array_fill                                     (0, 501,                       
                                                 array_fill                                     (0, 5, -1)));                       
           
                         // "parts" is number of parts left, n is                       
                         // the value left "nextPart" is starting                       
                         // point from where we start trying                       
                         // for next part.                       
                         function                                     countWaysUtil(                                     $n                                     ,                                     $parts                                     ,                                     $nextPart                                     )                       
                         {                       
                                                 global                                     $dp                                     ;                       
                                   
                                                 // Base cases                       
                                                 if                                     (                                     $parts                                     == 0 &&                                     $n                                     == 0)                                     return                                     1;                       
                                                 if                                     (                                     $n                                     <= 0 ||                                     $parts                                     <= 0)                                     return                                     0;                       
           
                                                 // If this subproblem is already solved                       
                                                 if                                     (                                     $dp                                     [                                     $n                                     ][                                     $nextPart                                     ][                                     $parts                                     ] != -1)                       
                                                 return                                     $dp                                     [                                     $n                                     ][                                     $nextPart                                     ][                                     $parts                                     ];                       
           
                                                 $ans                                     = 0;                                     // Initialize result                       
           
                                                 // Count number of ways for remaining                       
                                                 // number n-i remaining parts "parts-1",                       
                                                 // and for all part varying from                       
                                                 // 'nextPart' to 'n'                       
                                                 for                                     (                                     $i                                     =                                     $nextPart                                     ;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 $ans                                     += countWaysUtil(                                     $n                                     -                                     $i                                     ,                       
                                                 $parts                                     - 1,                                     $i                                     );                       
           
                                                 // Store computed answer in table                       
                                                 // and return result                       
                                                 return                                     (                                     $dp                                     [                                     $n                                     ][                                     $nextPart                                     ][                                     $parts                                     ] =                                     $ans                                     );                       
                         }                       
           
                         // This function mainly initializes dp                       
                         // table and calls countWaysUtil()                       
                         function                                     countWays(                                     $n                                     )                       
                         {                       
                                                 return                                     countWaysUtil(                                     $n                                     , 4, 1);                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 8;                       
                         echo                                     countWays(                                     $n                                     );                       
           
                         // This code is contributed by chandan_jnu                       
                         ?>                       

Javascript

                         <script>                       
                         // A Dynamic Programming based solution to count number                       
                         // of ways to represent n as sum of four numbers                       
                                                 let dp =                                     new                                     Array(5001);                       
                                   
                                                 for                                     (let i = 0; i < 5001; i++)                       
                                                 {                       
                                                 dp[i] =                                     new                                     Array(5001);                       
                                                 for                                     (let j = 0; j < 5001; j++)                       
                                                 {                       
                                                 dp[i][j] =                                     new                                     Array(5);                       
                                                 }                       
                                                 }                       
                                   
                                                 // "parts" is number of parts left, n is the value left                       
                                                 // "nextPart" is starting point from where we start trying                       
                                                 // for next part.                       
                                                 function                                     countWaysUtil(n,parts,nextPart)                       
                                                 {                       
                                   
                                                 // Base cases                       
                                                 if                                     (parts == 0 && n == 0)                       
                                                 return                                     1;                       
                                                 if                                     (n <= 0 || parts <= 0)                       
                                                 return                                     0;                       
                                   
                                                 // If this subproblem is already solved                       
                                                 if                                     (dp[n][nextPart][parts] != -1)                       
                                                 return                                     dp[n][nextPart][parts];                       
                                   
                                                 let ans = 0;                                     // Initialize result                       
                                   
                                                 // Count number of ways for remaining number n-i                       
                                                 // remaining parts "parts-1", and for all part                       
                                                 // varying from 'nextPart' to 'n'                       
                                                 for                                     (let i = nextPart; i <= n; i++)                       
                                                 ans += countWaysUtil(n - i, parts - 1, i);                       
                                   
                                                 // Store computed answer in table and return                       
                                                 // result                       
                                                 return                                     (dp[n][nextPart][parts] = ans);                       
                                                 }                       
                                   
                                                 // This function mainly initializes dp table and                       
                                                 // calls countWaysUtil()                       
                                                 function                                     countWays(n)                       
                                                 {                       
                                                 for                                     (let i = 0; i < 5001; i++)                       
                                                 {                       
                                                 for                                     (let j = 0; j < 5001; j++)                       
                                                 {                       
                                                 for                                     (let l = 0; l < 5; l++)                       
                                                 dp[i][j][l] = -1;                       
                                                 }                       
                                                 }                       
                                                 return                                     countWaysUtil(n, 4, 1);                       
                                                 }                       
                                   
                                                 // Driver program                       
                                                 let n = 8;                       
                                                 document.write(countWays(n));                       
                                   
                                                 // This code is contributed by avanitrachhadiya2155                       
                         </script>                       

输出：

时间复杂性： O（n） ^3. ).有Θ（n） ^2. )条目，每个条目只填写一次，填写一个条目需要O（n）个时间。 辅助空间： O（n） ^2. )

方法3（A）O（n） ^2. 日志（n）解决方案） 我们可以使用中讨论的解决方案这发布以查找所有四胞胎。幸亏高拉夫·阿希瓦感谢您提出上述解决方案。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

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

THE END

技术文章