将n写为两个或多个正整数之和的方法

本文概述

• C/C++
• Java
• python
• C#
• 的PHP

对于给定的n> 0, 找到不同的方式可以将n写入两个或多个正整数之和的方式。

例子：

Input : n = 5
Output : 6
Explanation : All possible six ways are :
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Input : 4
Output : 4
Explanation : All possible four ways are :
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

这个问题可以通过与硬币找零问题, 不同之处仅在于, 在这种情况下, 我们应该迭代1到n-1, 而不是像硬币找零问题那样重复特定的硬币值。

C/C++

// Program to find the number of ways, n can be
// written as sum of two or more positive integers.
#include <bits/stdc++.h>
using namespace std;
  
// Returns number of ways to write n as sum of
// two or more positive integers
int countWays( int n)
{
     // table[i] will be storing the number of
     // solutions for value i. We need n+1 rows
     // as the table is consturcted in bottom up
     // manner using the base case (n = 0)
     int table[n+1];
  
     // Initialize all table values as 0
     memset (table, 0, sizeof (table));
  
     // Base case (If given value is 0)
     table[0] = 1;
  
     // Pick all integer one by one and update the
     // table[] values after the index greater
     // than or equal to n
     for ( int i=1; i<n; i++)
         for ( int j=i; j<=n; j++)
             table[j] += table[j-i];
  
     return table[n];
}
  
// Driver program
int main()
{
     int n = 7;
     cout << countWays(n);
     return 0;
}

Java

// Program to find the number of ways, // n can be written as sum of two or 
// more positive integers.
import java.util.Arrays;
  
class GFG {
      
     // Returns number of ways to write
     // n as sum of two or more positive 
     // integers
     static int countWays( int n)
     {
          
         // table[i] will be storing the 
         // number of solutions for value
         // i. We need n+1 rows as the 
         // table is consturcted in bottom
         // up manner using the base case
         // (n = 0)
         int table[] = new int [n + 1 ];
      
         // Initialize all table values as 0
         Arrays.fill(table, 0 );
      
         // Base case (If given value is 0)
         table[ 0 ] = 1 ;
      
         // Pick all integer one by one and
         // update the table[] values after 
         // the index greater than or equal 
         // to n
         for ( int i = 1 ; i < n; i++)
             for ( int j = i; j <= n; j++)
                 table[j] += table[j - i];
      
         return table[n];
     }
      
     //driver code
     public static void main (String[] args)
     {
         int n = 7 ;
          
         System.out.print(countWays(n));
     }
}
  
// This code is contributed by Anant Agarwal.

python

# Program to find the number of ways, n can be
# written as sum of two or more positive integers.
  
# Returns number of ways to write n as sum of
# two or more positive integers
def CountWays(n):
  
     # table[i] will be storing the number of
     # solutions for value i. We need n+1 rows
     # as the table is consturcted in bottom up
     # manner using the base case (n = 0)
     # Initialize all table values as 0
     table = [ 0 ] * (n + 1 )
  
     # Base case (If given value is 0)
     # Only 1 way to get 0 (select no integer)
     table[ 0 ] = 1
  
     # Pick all integer one by one and update the
     # table[] values after the index greater
     # than or equal to n
     for i in range ( 1 , n ):
  
         for j in range (i , n + 1 ):
  
             table[j] + =  table[j - i]            
  
     return table[n]
  
# driver program
def main():
  
     n = 7
  
     print CountWays(n)
  
if __name__ = = '__main__' :
     main()
  
#This code is contributed by Neelam Yadav

C#

// Program to find the number of ways, n can be
// written as sum of two or more positive integers.
using System;
  
class GFG {
      
     // Returns number of ways to write n as sum of
     // two or more positive integers
     static int countWays( int n)
     {
          
         // table[i] will be storing the number of
         // solutions for value i. We need n+1 rows
         // as the table is consturcted in bottom up
         // manner using the base case (n = 0)
         int []table = new int [n+1];
       
         // Initialize all table values as 0
         for ( int i = 0; i < table.Length; i++)
             table[i] = 0;
       
         // Base case (If given value is 0)
         table[0] = 1;
       
         // Pick all integer one by one and update the
         // table[] values after the index greater
         // than or equal to n
         for ( int i = 1; i < n; i++)
             for ( int j = i; j <= n; j++)
                 table[j] += table[j-i];
       
         return table[n];
     }
      
     //driver code
     public static void Main()
     {
         int n = 7;
          
         Console.Write(countWays(n));
     }
}
  
// This code is contributed by Anant Agarwal.

的PHP

<?php
// Program to find the number of ways, n can be
// written as sum of two or more positive integers.
  
// Returns number of ways to write n as sum 
// of two or more positive integers
function countWays( $n )
{
     // table[i] will be storing the number of
     // solutions for value i. We need n+1 rows
     // as the table is consturcted in bottom up
     // manner using the base case (n = 0)
     $table = array_fill (0, $n + 1, NULL);
  
     // Base case (If given value is 0)
     $table [0] = 1;
  
     // Pick all integer one by one and update 
     // the table[] values after the index 
     // greater than or equal to n
     for ( $i = 1; $i < $n ; $i ++)
         for ( $j = $i ; $j <= $n ; $j ++)
             $table [ $j ] += $table [ $j - $i ];
  
     return $table [ $n ];
}
  
// Driver Code
$n = 7;
echo countWays( $n );
  
// This code is contributed by ita_c
?>

输出如下：

14

时间复杂度O(n2)

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。