Posted on 2005-10-12 13:52
锋出磨砺 阅读(2107)
评论(8) 编辑 收藏 所属分类:
java算法 、
杂谈
如果你有一千个苹果，有十个箱子，那么现在我要把一千个苹果放进十个箱子里面，
放了完之后，不管谁跟我要多少苹果（包括1000以内的哟），我都可以整箱整箱给
他，这个问题有解吗？
我的思路。
我从1开始推理的。如果你需要1个，必然有1个箱子装一个。
需要两个，要么给一个箱子装2个，要么再装一个的箱子。感觉
还是装2个为一箱比较好。那么需要3个时候，就1＋2了，那么你需要4个怎么办。
是装一个4个呢，还是装一个或者2个呢。为了省箱子，我装4个。
此时，我发现了规律，1，2，4。那么下一个是8，再下去就是16了，接着32。
。。。。。。。
如果有100个，到32的时候，下一个就是64了，总数超过100了。思路改为
100－（1＋2＋4＋8＋16＋32）＝37。最后一个箱子装37个。
当要求的苹果数在1＋2＋4＋8＋16＋32＝63 和100之间的时候，将算法推诿
给前面即可。就是先拿37个，剩下的从以前的箱子拼凑。
至此，推理完毕。
java实现代码
/**
* <p>Title: </p>
* <p>Description: </p>
* <p>Copyright: Copyright (c) 2005</p>
* <p>Company: </p>
* @author not attributable
* @version 1.0
*/
public class Box {
private int limit;
private int code;
private int applenum;
public Box(int code,int applenum,int limit) {
this.limit = limit;
this.code = code;
this.applenum = applenum;
}
public int getApplenum() {
return applenum;
}
public int getCode() {
return code;
}
public int getLimit() {
return limit;
}
public void setLimit(int limit) {
this.limit = limit;
}
public void setCode(int code) {
this.code = code;
}
public void setApplenum(int applenum) {
this.applenum = applenum;
}
}
/**
* <p>Title: </p>
* <p>Description: </p>
* <p>Copyright: Copyright (c) 2005</p>
* <p>Company: </p>
* @author not attributable
* @version 1.0
*/
public class Apple {
public Apple() {
}
final private int max=100; // 苹果总数
static int xqs = 99; // 你需要的苹果数
private java.util.Vector Boxvec = new java.util.Vector(); // 箱子和箱子里的苹果
private int ai =0;
private int k = 1;
public static void main(String args[])
{
Apple apple = new Apple();
apple.InBox(1);
System.out.println("共需装"+apple.GetBoxVec().size()+"箱");
for (int i=0;i<apple.GetBoxVec().size();i++)
{
Box box = (Box)apple.GetBoxVec().get(i);
System.out.println("第 ‘"+box.getCode()+"’ 箱装'"+box.getApplenum()+"' ");
}
apple.GetApple(xqs,apple.GetBoxVec());
}
public void GetApple(int x,java.util.Vector vec)
{
if (x==1)
{
System.out.println("拿第一箱玩去，就1个");
}
else
{
if (x != 0) {
int key = 0;
for (int i = 0; i < vec.size() - 1; i++) {
Box xbox = (Box) vec.get(i);
Box ybox = (Box) vec.get(i + 1);
if (x > xbox.getLimit() && x <= ybox.getLimit()) {
key = i + 2;
System.out.println("拿第" + ybox.getCode() + "箱给他，共" +
ybox.getApplenum() + "个");
GetApple(x - ybox.getApplenum(), vec);
}
}
}
else
System.out.println("完成");
}
}
public void InBox(int i)
{
if ((i+i)>=max)
{
Box box = new Box(k,max-ai,max);
Boxvec.add(box);
}
else
{
Box box = new Box(k,i,i+ai);
k++;
Boxvec.add(box);
ai = ai + i;
InBox(i+i);
}
}
public java.util.Vector GetBoxVec()
{
return Boxvec;
}
}