首页 > 代码库 > 将一个整数划分为多个正整数之和

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

整数划分问题是将一个正整数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 < 1 或者n < 1时,划分方式共0种。

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

(3) n < m时,因为整数划分中最大加数不可能大于n,因此此种情况等价为split(n, n)。

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

(5) m < n时,同样存在两种划分:一种是最大加数m-1的,共split(n, m-1);另外一种是其中一个加数为m的,紧接着只需要对n-m进行划分即可且最大加数为m,因此共split(n - m,m)种划分方式。因此,m < n时共split(n, m-1) + split(n-m, 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));
}


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