1.第一反应就是想起高中的等比例数列1,2,4,8.。。。。，答案分7份：1,2,4，全面的扩展代码实现（这代码是某个周末做的，结果没看答题要求，晚上6点以后上传，LZ给个面子啊！多谢啦。）
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
public class Main {
/*
* 问题分析:分金条问题本质是数据分割问题，针对数M，将其分为N块(M>N,M<=N的情况下肯定是可以解决的),（d(1),d(2),...,d(N)）,满足以下条件:
* 从1,2,3,。。。M-1,M结束，对其任意数字M(x)都可以从块中通过某一组合的和得到 这让我自然地联想到比例系数为2的等比例数列，我们知道，它的一个特征就是：
* 给定一个等比例数列a(n)，比例系数为2,那么从从1-n中的任意一个数x，都能从该数列中找到几个元素，来凑足它。下面就是分析的例子，可以从中总结出规律
* M--N-------最小分块组合
* ***********************
* 2--2-------1,1
* 3--2-------1,2 <------分界，表示如果此数能分割，同段位的数据必然也能分割
* **************
* 4--2-------1,3(N=2无效!!段数加1,以下分析类似)
* 4--3-------1,2,1
* 5--3-------1,2,2
* 6--3-------1,2,3
* 7--3-------1,2,4 <------分界
* ***************
* 8--4-------1,2,4,1
* 9--4-------1,2,4,2
* ........
* 14--4------1,2,4,7
* 15--4------1,2,4,8 <------分界
******************
*........
*从以上分析中可以看出，关键是对边界的判断，只要确定了边界的最小分段数，那么所有处于同一段位的数据也能按照该分段数分段，
*而分界数据的分段正是按照标准的等比例数列来确定的。只要确定了M的处在哪个边界之内问题就迎刃而解。如果N小于这个分段数，那么则无法实现分配.
*/
public static void main(String[] args){
System.out.println(add(1.0f, 2.0f));
System.out.println(add(1, 4));
ArrayList<Integer> list=new ArrayList<Integer>();
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));//键盘录入缓冲流
try {
//获得M
System.out.println("请输入M..");
int m=new Integer(br.readLine());
//获得N
System.out.println("请输入N..");
int n=new Integer(br.readLine());
br.close();
System.out.println("分析结果:");
//获得最优分配方案，各个元素存放在list中
list=getBlocks(m);
//打印处理
if(n>=list.size()){
Iterator<Integer> it=list.iterator();
System.out.println("最优数据分块方案:");
while(it.hasNext()){
System.out.print(it.next()+", ");
}
}else{
System.out.println("对不起，无法实现分配!");
}
} catch (NumberFormatException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
public static ArrayList<Integer> getBlocks(int m){
ArrayList<Integer> tmp=new ArrayList<Integer>();
int sum=1;
int a=1;//元素临时变量
int b=0;//末尾余数临时变量
while(sum<=m){
tmp.add(a);
a=a*2;
sum+=a;
}
if(sum>m){//sum超出，求出余数，也就是最后一个元素
b=m-(sum-a);
if(b!=0)//杜绝0元素
tmp.add(b);
}
return tmp;
}
public static float add(float x,float y){
return (float)(x+y);
}
public static int add(int x,int y){
return (int)(x+y);
}
}
2提。2分法思想 4-4 2-2 1-1。 3次 |
收藏
淘帖
踩
