整数划分问题将以正整数n表示成一系列正整数之和.n=n1+n2+n3+...+nk(n1>=n2>=n3>=nk>=1,k>=1)这就是正整数n的一个划分,正整数n不同的划分个数称为正整数n的划分数,记作p(n)例如：6有如下11种划分则p

Question

整数划分问题
将以正整数n表示成一系列正整数之和.n=n1+n2+n3+...+nk (n1>=n2>=n3>=nk>=1,k>=1)这就是正整数n的一个划分,正整数n不同的划分个数称为正整数n的划分数,记作p(n)例如：6 有如下11种划分则p(6)=116;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;则求任意正整数的划分数p(n).
麻烦有能力的朋友帮我下 请您用JAVA语言做!

Answer 1

我这里有个C语言的,是输出所有划分的.
你自己尝试一下改成JAVA的吧.
#include "stdio.h"
void main()
{
int n;
scanf("%d",&n);
if (n == 1)
{
printf("1=1\n");
return;
}
if (n == 2)
{
printf("2=1+1\n");
return;
}
int *a = new int(n);
int top = 0;
a[0] = n - 1;
a[1] = 1;
top = 2;
int i;
do{
printf("%d=%d",n,a[0]);
for (i = 1; i < top; i++)
{
printf("+%d",a[i]);
}
printf("\n");
int s = 0;
do{
s += a[--top];
}while (top >= 0 && a[top] == 1);
if (top == -1)
{
break;
}
int d = a[top] - 1;
if (d == 1)
{
while (s > 0)
{
a[top++] = 1;
s--;
}
}
else
{
do{
a[top++] = d;
s -= d;
}while (s >= d);
if (s != 0)
{
a[top++] = s;
}
}
}while (1);
}