一道经典的分油问题

作者: ldsea 分类: 程序生活 发布时间: 2009-03-03 18:51

[quote]题目要求:一个桶中有12斤油,要求倒出6斤,可现在另外只有两个桶,分别可装8斤与5斤,请问应如何来倒。补充:这里的12,6,8,5都是变量,应该可以自己设置,输出是每一次分油的步骤。[/quote]
题目可理解为对8和5进行加减,使之能产生6即可。
其中,+代表往改桶里倒满油。-代表将该桶的里油全部倒出。
此题的一个简单结果是8+8-5-5=6,这意味着,只要连续2次将8的桶灌满然后2次将5的桶灌满则8斤的桶里面剩下的刚好是6斤的油。
由此可以归纳出来算法就是找到满足x*8+y*5使之满足最后所求即可,x和y是可正可负的一个系数。
[code]
import java.util.ArrayList;
import java.util.List;

public class SplitOil {

  /**
   * 题目要求:一个桶中有12斤油,要求倒出6斤,可现在另外只有两个桶,分别可装8斤与5斤,请问应如何来倒?
   * 补充:这里的12,6,8,5都是变量,应该可以自己设置,输出是每一次分油的步骤。
   *
   * 题目可理解为对8和5进行加减,使之能产生6即可。
   * 其中,+代表往改桶里倒满油。-代表将该桶的里油全部倒出。
   * 此题的一个简单结果是8+8-5-5=6,这意味着,只要连续2次将8的桶灌满然后2次将5的桶灌满则8斤的桶里面剩下的刚好是6斤的油。
   * 由此可以归纳出来算法就是找到满足x*8+y*5使之满足最后所求即可,x和y是可正可负的一个系数。
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    List<OilQuestion> resultList = new ArrayList<OilQuestion>();
    int a=8;//桶1的容量
    int b=5;//桶2的容量
    int c=6;//要求的结果
    resultList=getXY(a,b,c);
    for(int i=0;i<resultList.size();i++){
      OilQuestion o = (OilQuestion)resultList.get(i);
      System.out.println("x="+o.getA()+";"+"y="+o.getB());
    }
  }
  
  public static List<OilQuestion> getXY(int a ,int b,int result){
    //考虑到可能有多种结果,所以把结果OilQuestion放到一个List当中,每一个OilQuestion是一个由a,b系数组成的对象
    //选出一个结果 为 result=x*a+y*b ,这里的x,y可正可负
    List<OilQuestion> resultList = new ArrayList<OilQuestion>();
    int max=50;
    int x=0;
    int y=0;
    for(int i=-max;i<max;i++)
      for(int j=-max;j<max;j++){
        if((i*a+j*b)==result) {
          x=i;
          y=j;
          OilQuestion o = new OilQuestion();
          o.setA(x);
          o.setB(y);
          resultList.add(o);
          }
        else continue;
      }
        
    return resultList;
  }
}

class OilQuestion{//定义一个内部类,该内部类有两个属性a和b
  int a;
  int b;
  public void setA(int a)
  {
    this.a=a;
  }
  public void setB(int b)
  {
    this.b=b;
  }
  public int getA(){
    return a;
  }
  public int getB(){
    return b;
  }
}
[/code]

发表回复

您的电子邮箱地址不会被公开。