Posted on 2005-10-12 13:52
锋出磨砺 阅读(2098)
评论(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;
}
}