Posted on 2005-10-12 13:52
鋒出磨礪 閱讀(2119)
評論(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;
}
}