Question

java算法编程题

每一个大于1的整数都可以由多个正整数相加得到，编写一个方法，传入一个数字，打出所有可能的等式，pullAll（int n），如传入4，则打印结果可能是（如果需要，可以另外添加函数）： 4=1+1+1+1 4=1+1+2 4=1+2+1 4=1+3 4=2+1+1 4=2+2 4=3+1

Answer 1

putAll(4)运行结果：
4=1+1+1+1
4=1+1+2
4=1+2+1
4=1+3
4=2+1+1
4=2+2
4=3+1
static
void
putAll(int
n)
{
for(int
i=1;i<n;i++)
{
putAllRec(n+"="+i,
n-i);
System.out.println(n+"="+i+"+"+(n-i));
}
}
static
void
putAllRec(String
prefix,
int
n)
{
for(int
i=1;i<n;i++)
{
putAllRec(prefix+"+"+i,
(n-i));
System.out.println(prefix+"+"+i+"+"+(n-i));
}
}
另外提供一个不用递归的方法，同样的输出：
static
void
putAll(int
n)
{
int[]
a
=
new
int[n];
for(int
i=0;i<n;i++)
a[i]=1;
int
w
=
n-1;
while(a[0]!=n)
{
System.out.print(n+"="+a[0]);
for(int
i=1;i<=w;i++)
System.out.print("+"+a[i]);
System.out.println();
if(a[w]==1)
{
a[w-1]++;
a[w]--;
w--;
}
else
{
a[w-1]++;
int
t
=
a[w]-1;
for(int
i=0;i<t;i++)
a[w+i]=1;
w+=(t-1);
}
}
}
再附加一个上面这个方法的“精简”版（同样输出，就是代码少点，没什么实际意义）：
static
void
putAll(int
n)
{
int[]
a
=
new
int[n];
for(int
i=0;i<n;i++)
a[i]=1;
while(a[0]!=a.length)
{
System.out.print(a.length+"="+a[0]);
for(int
i=1;i<n;i++)
System.out.print("+"+a[i]);
System.out.println();
a[n-2]++;
if(a[n-1]==1)
a[(n--)-1]--;
else
for(int
i=a[(n--)-1]-1;i>0;i--)
a[(++n)-1]=1;
}
}