一道面试题
给定两个正整数m,n(m>=n!),将m拆成n个数相加:m=a(1)+a(2)+...+a(n),使之满足:a(1)<a(2)<...<a(n);
编成列出所有的拆法.
例如:若m=7,n=3则只有一种拆法:
7=1+2+4
并测试：m:100，n:4，Total No应为:5952，请打出清单，统计所用时间。
答：用到回溯的概念。
一般而言，回溯的问题比递归难一点。而且，为了节省资源，只用循环不用函数自身调用。
把下面存成：Math1.java
编译：javac -d . Math1.java
m=100，n=4时
运行：java per.chen09.itpub.Math1 100 4
结果：
..
..
..
..
=======================================
Sum : 100 Split : 4
Total result: 5952 Used Time : 20
m=100，n=5时
运行：java per.chen09.itpub.Math1 100 5
结果：
..
..
..
..
Sum : 100 Split : 5
Total result: 25337 Used Time : 90
Programed by Chen09.
以下java代码：
------------------------------------------------------------
//split number
//give M,N
//let m=a(1)+a(2)+...+a(n), a(1)<a(2)<...<a(n)
// etc. 7=1+2+4
package per.chen09.itpub;
import java.util.ArrayList;
class Math1
{
//the last process time in call splitNumber function.
private static long longProcTime;
//There are just test code it main function.
//The program will not use Junit for test, so must put test code there.
public static void main(String[] strArgs)
{
System.out.println();
ArrayList al = Math1.splitNumber(strArgs[0],strArgs[1]);
int intSize = al.size();
for(int i = 0; i<intSize;i++)
{
int[] intArrayTemp = (int[])al.get(i);
System.out.print("result "+(i+1) +" : ");
for(int j=0;j<intArrayTemp.length;j++)
{
System.out.print(intArrayTemp[j]+" ");
}
System.out.println();
}
System.out.println("=======================================");
System.out.println("Sum : " + strArgs[0] + "\tSplit : " + strArgs[1]);
System.out.println("Total result: "+intSize+"\tUsed Time : "+ Math1.getProcTime());
System.out.println("Programed by Chen09.");
}
//if paramates' type is String
public static ArrayList splitNumber(String strM, String strN)
{
return splitNumber(Integer.parseInt(strM),Integer.parseInt(strN));
}
//the type of ArrayList's item is int[]
public static ArrayList splitNumber(int intM, int intN)
{
long longBeginTime = System.currentTimeMillis();
ArrayList alResults = new ArrayList();
int[] intResult = new int[intN];
int intPoint = 0;
intResult[intPoint] = 0;
int intRemain = intM;
while(intPoint >= 0)
{
intResult[intPoint]++;
intRemain = intRemain- intResult[intPoint];
//System.out.println(intRemain);
if(intPoint==intN-2) //arrive the last
{
intResult[intPoint+1] = intRemain;
intRemain = intRemain + intResult[intPoint];
//add the result array
alResults.add(intResult);
//create new result array, and copy from old
intResult = backupIntArray(intResult);
if(intResult[intPoint+1] - intResult[intPoint] <= 2)
{
//not result any more, intPoint be back.
intPoint--;
intRemain = intRemain + intResult[intPoint];
}
}
else if(getSum(intResult[intPoint]+1,intN-intPoint-1) > intRemain)
{
//not arrive the last, but not result
intRemain = intRemain + intResult[intPoint];
intPoint--;
if(intPoint>=0)
intRemain = intRemain + intResult[intPoint];
}
else
{
//have result
//set the next item
intResult[intPoint+1] = intResult[intPoint];
intPoint++;
}
}
//save the time of process
setProcTime(System.currentTimeMillis() - longBeginTime);
return alResults;
}
//get process time
public static long getProcTime()
{
return longProcTime;
}
//set process time
protected static void setProcTime(long longProcTime)
{
Math1.longProcTime = longProcTime;
}
//get the sum = intBase + (intBase + 1) + ... + (intBase + intCount)
private static int getSum(int intBase,int intCount)
{
return (intBase+ (intBase + intCount - 1))*intCount/2;
}
//clone a int array
private static int[] backupIntArray(int[] intOldArray)
{
int intCount = intOldArray.length;
int[] intNewArray = new int[intCount];
for(int i=0;i<intCount;i++)
intNewArray[i] = intOldArray[i];
return intNewArray;
}
}