给定两个正整数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; }
}
转自:http://www.itpub.net/11450.html 
|