乔治棍子算法JAVA实现

乔治棍子算法JAVA实现"/>

乔治棍子算法JAVA实现

乔治拿来一组等长的木棒，将它们随机地裁断，使得每一节木棍的长度都不超过50个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序，帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。

package algorithm;public class stickTest {public static void main(String[] args) {// TODO Auto-generated method stubint stickSplit[]={5,2,1};//获取棍子2分次数int splitcount=stickSplit.length/2;if(stickSplit.length%2!=0){splitcount++;}//数组默认-1；splitcount=splitcount-1;//排序stickTest.sort(stickSplit);//求和int sum=arraySum(stickSplit);System.out.println("总长度为"+sum);//定义棍子长度默认为0int stickMinLength=stickSplit.length;//默认棍子的最小长度为sum/stickSplit.length如果if(stickSplit[0]>sum/stickSplit.length){stickMinLength=sum/stickSplit[0];}System.out.println("假设有"+stickMinLength+"根棍子");if(sum%stickMinLength==0){doa:do {System.out.println("能被整除则进行计算");System.out.println("假设当此棍子长度"+sum/stickMinLength);if(stickMinLength<=1){break doa;}//遍历校验boolean flaga=true;//定义模拟长度doaa:do{int stickDefineLength=sum/stickMinLength;int ia=0;int ib=stickSplit.length-1;if(sum%stickMinLength!=0){stickMinLength--;continue;}if(ia>=splitcount||ib<splitcount){System.out.println("最小长度为"+stickDefineLength);break doa;}//如果模拟长度小于最大长度则将模拟长度设为最大长度if(stickSplit[ia]>stickDefineLength){break doaa;}//如果发现模拟长度为棍子最大长度则向下继续拼接if(stickSplit[ia]==stickDefineLength){ia++;continue doaa;}//深度拼接 开始  和最小数组成是否等于定义长度boolean flagaa=true;int thisValue=stickSplit[ia]+stickSplit[ib];do{//发现拼接总和过大，则跳出if(thisValue>stickDefineLength){break doaa;}//如果拼接后发现相等则进行下次拼接if(thisValue==stickDefineLength){ia++;ib--;continue doaa;}//发现小，则继续加最小值if(thisValue<stickDefineLength){ib--;thisValue+=stickSplit[ib];}}while(flagaa);}while(flaga);stickMinLength--;} while (stickMinLength>1);}System.out.println("最小长度为"+stickMinLength);System.out.println("棍子长度为"+sum/stickMinLength);}//求和public static int arraySum(int[]arr){int sum=0;for(int i=0;i<arr.length;i++){sum+=arr[i];System.out.print(arr[i]);}return sum;}/*** 较低效冒泡* @param arr*/public static void sort(int[]arr){for(int i=0;i<arr.length-1;i++){for(int j=i+1;j<arr.length;j++){if(arr[i]<arr[j]){int temp=arr[i];arr[i]=arr[j];arr[j]=temp;}}}}
}