整数划分(C语言)
参考博客:https://www.cnblogs.com/wkfvawl/p/11486992.html
思路整理
n=m1+m2+…+mi; (其中mi为正整数,并且1 <= mi <= n),则{m1,m2,…,mi}为n的一个划分。
如果{m1,m2,…,mi}中的最大值不超过m,即max(m1,m2,…,mi)<=m,则称它属于n的一个m划分。这里我们记n的m划分的个数为q(n,m);
当n=6时我们可以获得以下这几种划分(注意,例子中m>=6)
根据n和m的关系,考虑以下几种情况:
- 当n=1时,不论m的值为多少(m>0),只有一种划分即{1}。因此 q(1,m) =1 。
- 当m=1时,不论n的值为多少,只有一种划分即n个1,{1,1,1,…,1}。 因此 q(n,1) =1。;
- 当n<m时,由于划分中不可能出现负数,因此就相当q(n,n),即q(n,m)=q(n,n),m>=n。
- 但n>m时,根据划分中是否包含最大值m,可以分为两种情况:
(1) 划分中包含m的情况,即{m, {x1,x2,…xi}}, 其中{x1,x2,… xi} 的和为n-m,可能再次出现m,因此是(n-m)的m划分,因此这种划分个数为q(n-m, m)。 (2) 划分中不包含m的情况,则划分中所有值都比m小,即n的(m-1)划分,个数为f(n,m-1)。因此 q(n, m) = q(n-m, m)+q(n,m-1)。 - 当n=m时,根据划分中是否包含n,可以分为两种情况:
(1) 划分中包含n的情况,只有一个即{n}; (2) 划分中不包含n的情况,这时划分中最大的数字也一定比n小,即n的所有(n-1)划分。因此 q(n,n) =1 + q(n,n-1)。
代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 5
int mark[200];
int q2(int n,int m)
{
if(n==1|| m==1) return 1;
if(m==n)
{
return 1+q2(n,n-1);
}
if(m>n) return q2(n,n);
if(m<n) return q2(n,m-1)+q2(n-m,m);
}
void print(int sum, int k, int prio)
{
if (sum > MAXSIZE)
return;
if (sum == MAXSIZE)
{
int i;
for (i = 0; i < k - 1; i++)
{
printf("%d+",mark[i]);
}
printf("%d\n",mark[i]);
}
else {
for (int j = prio; j > 0; j--)
{
mark[k] = j;
sum += j;
print(sum, k + 1, j);
sum -= j;
}
}
}
int main()
{
int i;
int num = q2(MAXSIZE,MAXSIZE);
printf("%d有%d种分法:\n",MAXSIZE,num);
print(0,0,MAXSIZE);
return 0;
}
结果
|