这是我需要做的：写一个算法,将一个给定的整数分解为和和产品,但每个后续数字必须大于前一个,即：
6 = 1+5; 6 = 1+2+3; 6 = 1*2+4; 6 = 2+4; 6 = 2*3;
一个基本的分区整数算法不会工作,因为它以不同的顺序返回数字.
解决方法
public class Perms {
/**
* @param args
*/
public static int x;
public static void main(String[] args) {
// TODO Auto-generated method stub
x = 6;
rec(x,new int[1000],new String[1000],0);
}
public static void rec(int n,int all[],String operator[],int size)
{
if (n==0)
{
if (size==1)return;
System.out.print(x + " =");
for (int i=0;i<size;i++)
{
System.out.print(" " + all[i]);
if (i!=size-1)
System.out.print(" " + operator[i]);
}
System.out.println();
return;
}
int i=1;
if (size>0)
i = all[size-1]+1;
for ( ;i<=n;i++)
{
operator[size] = "+";
all[size] = i;
rec(n-i,all,operator,size+1);
}
i=1;
if (size>0)
i = all[size-1]+1;
for (;i<=n;i++)
{
float r = n/(float)i;
if (r == (int)r)
{
operator[size] = "*";
all[size] = i;
rec(n/i,size+1);
}
}
}
}
输出：
6 = 1 + 2 + 3 6 = 1 + 5 6 = 2 + 4 6 = 1 * 2 + 4 6 = 1 * 6 6 = 1 * 2 * 3 6 = 2 * 3
注意：操作具有优先级(评估操作从右到左).
示例：20 = 2 * 3 7 =(2 *(3 7))= 2 * 10 = 20.
