Posted on 2005-10-12 13:52
鋒出磨礪 閱讀(2120)
評(píng)論(8) 編輯 收藏 所屬分類(lèi):
java算法 、
雜談
如果你有一千個(gè)蘋(píng)果，有十個(gè)箱子，那么現(xiàn)在我要把一千個(gè)蘋(píng)果放進(jìn)十個(gè)箱子里面，
放了完之后，不管誰(shuí)跟我要多少蘋(píng)果（包括1000以?xún)?nèi)的喲），我都可以整箱整箱給
他，這個(gè)問(wèn)題有解嗎？
我的思路。
我從1開(kāi)始推理的。如果你需要1個(gè)，必然有1個(gè)箱子裝一個(gè)。
需要兩個(gè)，要么給一個(gè)箱子裝2個(gè)，要么再裝一個(gè)的箱子。感覺(jué)
還是裝2個(gè)為一箱比較好。那么需要3個(gè)時(shí)候，就1＋2了，那么你需要4個(gè)怎么辦。
是裝一個(gè)4個(gè)呢，還是裝一個(gè)或者2個(gè)呢。為了省箱子，我裝4個(gè)。
此時(shí)，我發(fā)現(xiàn)了規(guī)律，1，2，4。那么下一個(gè)是8，再下去就是16了，接著32。
。。。。。。。
如果有100個(gè)，到32的時(shí)候，下一個(gè)就是64了，總數(shù)超過(guò)100了。思路改為
100－（1＋2＋4＋8＋16＋32）＝37。最后一個(gè)箱子裝37個(gè)。
當(dāng)要求的蘋(píng)果數(shù)在1＋2＋4＋8＋16＋32＝63 和100之間的時(shí)候，將算法推諉
給前面即可。就是先拿37個(gè)，剩下的從以前的箱子拼湊。
至此，推理完畢。
java實(shí)現(xiàn)代碼
/**
* <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; // 蘋(píng)果總數(shù)
static int xqs = 99; // 你需要的蘋(píng)果數(shù)
private java.util.Vector Boxvec = new java.util.Vector(); // 箱子和箱子里的蘋(píng)果
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個(gè)");
}
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() + "個(gè)");
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;
}
}