将一个整数划分为多个正整数之和

整数划分问题是将一个正整数n拆分成一组数连加并等于n的形式，显然这组数中最大加数不大于n。 令n为需要划分的整数，m为划分后的最大整数。例如将6划分为最大加数为6的划分形式如下： 65 + 14 + 2, 4 + 1 + 13 + 3, 3 + 2 +1, 3 + 1 + 1 + 12 + 2 + 2, 2 + 2

整数划分问题是将一个正整数n拆分成一组数连加并等于n的形式，显然这组数中最大加数不大于n。

令n为需要划分的整数，m为划分后的最大整数。例如将6划分为最大加数为6的划分形式如下：

6

5 + 1

4 + 2, 4 + 1 + 1

3 + 3, 3 + 2 +1, 3 + 1 + 1 + 1

2 + 2 + 2, 2 + 2+ 1 + 1, 2 + 1 + 1 + 1 + 1

1 + 1 + 1 + 1 +1 + 1

共11中划分方法。若划分后最大整数为2，则划分形式为最后两行，共4种划分方法。易得可利用递归方式求解，设划分函数split(int n,int m)，其中n为需要划分的整数，m为划分后的最大加数。

(1) m

(2) m = 1或者n = 1时，划分方式共1中。

(3) n

(4) m=n时，划分分为两种：一种是最大加数为m-1的，共split(n, m-1)中划分方式；一种是其中一个加数为m的（当然不存在另一个加数，或者说另一个加数为0）。因此，m=n时共split(n, m-1) + 1种划分方式。

(5) m

源代码如下：

#include <stdio.h>
int split(int n, int m)
{
   if(n < 1 || m < 1) return 0;
   if(n == 1 || m == 1) return 1;
   if(n < m) return split(n, n);
   if(n == m) return (split(n, m - 1) + 1);
   if(n > m) return (split(n, m - 1) + split((n - m), m));
}