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

2021年4月4日19:39:46 发表评论 497 次浏览

## 本文概述

``````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``````

## 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``