算法-轮流煮饭的问题。
生活中遇到一个该谁煮饭的问题,我和同学争论了不休:
四个人一起煮晚饭。每个人煮一天,然后煮起来大家一起吃。意思就是一个人可以只煮一次,然后吃四天的饭。突然有一天我因为有事早上离开了,而且离开了几天。然后后我回来了,因为离开那天的前一天是我煮的饭。但是我回来的时候正好也轮到我煮饭了。我就不想煮,而是想让他们轮一圈,我再煮饭。而其中一个同学(如果我不煮就该他煮)不同意,他认为要按顺序来,轮到谁了就该谁。
现在撇开一些为人处世的道理或者吃亏就是福的哲学思想。我想弄清楚到底哪种方法才能够让事情最公平。同学觉得这是一个无解的问题。我自己想了一下,我解决的思路如下:
循环插队问题:
有n个人轮流煮饭,每天只煮一次饭。每个人每天都要吃饭,轮到自己煮饭的时候就必须煮饭,其他时候只负责吃饭。突然有一天其中一人离开,离开的日期和离开的天数都是随机的。但这个人肯定要回来,设计思路,该如何安排回来的那个人在哪一天煮饭最公平。
我解决的思路:
当其中的一个人要离开时,记录下他距离上一次自己煮饭的距离值i(即天数i)。如果他离开的前一天正好是他煮饭,则他回来后可以先吃n-i天饭。然后再插入到循环队列中继续接下来的循环。
需要注意的问题:
每个人的亏损盈利计算周期只有在他离开前后的两个循环外加他离开的周期计算才有意义。因为时间拖得越长,整个平均值越趋于以前的平均值。如果计算的周期无限扩大,相当于把亏损的份额无限细分,整个差额就显示不出来了。
设计思路:
Person类
成员变量:吃饭的天数 煮饭的天数 离开时距离上一次自己煮饭循环的天数
吃饭和煮饭天数的比值 煮饭标识符
成员方法:吃饭的方法 煮饭的方法
Cook类
成员变量:整个循环的天数
Egress类
成员变量:离开的日期 回来的日期
成员方法:判断是否该自己煮饭
问题1:如何计算自己离开的时候还没有吃完的天数?(本人已解决)。
问题2:在设计程序的过程中。我想到如果要创建100个人(Person类的实例),有没有可能通过for循环解决或者用一个方法。我目前没有找到。因为如果全部是自己去一个一个的new。那违背了(do not repeat yourself )原则。
代码如下:(我零零闪闪花了一天的时间,把代码写出来之后发现没有太大的参考价值,而且里面有的类里面的成员变量都没有去设置,有些方法也没有用到却创建了。但我还是贴出来吧,仅供娱乐和感兴趣的高人给我纠正一下,或者你想出你的解决方案)
public class Partner { //吃饭的天数 private double eatDayCount; //煮饭的天数 private double cookDayCount; //离开时距离下一次自己煮饭循环的天数 private double holdDayCount; //吃饭天数和煮饭天数的比值。 private double scale; //定义一个煮饭的int型标识符 private final int cookFlag; public int getCookFlag() { return cookFlag; } public double getEatDayCount() { return eatDayCount; } public void setEatDayCount(double eatDayCount) { this.eatDayCount = eatDayCount; } public double getCookDayCount() { return cookDayCount; } public void setCookDayCount(double cookDayCount) { this.cookDayCount = cookDayCount; } public double getHoldDayCount() { return holdDayCount; } public void setHoldDayCount(double holdDayCount) { this.holdDayCount = holdDayCount; } public double getScale() { return scale; } public void setScale(double scale) { this.scale = scale; } //定义一个构造函数,用于赋值。 public Partner(double cookDayCount,double eatDayCount,double scale,int cookFlag,double holdDayCount) { this.cookDayCount=cookDayCount; this.eatDayCount=eatDayCount; this.scale=scale; this.holdDayCount=holdDayCount; this.cookFlag=cookFlag; } //重载构造函数,缺少holdDayCount的值 public Partner(double cookDayCount,double eatDayCount,double scale,int cookFlag) { this.cookDayCount=cookDayCount; this.eatDayCount=eatDayCount; this.scale=scale; this.cookFlag=cookFlag; //将距离的天数设置成一个负值。 this.holdDayCount=-1; } //累加吃饭的天数 public void eat(Partner partner) { partner.setEatDayCount(partner.getEatDayCount()+1); } //累加煮饭的天数 public void cook(Partner partner) { partner.setCookDayCount(partner.getCookDayCount()+1); } //计算吃饭的天数和租房的天数的比值 public void caculateScale(Partner partner) { partner.setScale(partner.getEatDayCount()/partner.getCookDayCount()); } //定义一个外出的方法 public void goOutToDoSometing(int i,Cook cook,Partner partner) { //设置一个值,用于计算自己离开的那一天距离自己下一次煮饭的天数。 //如果离开的那一天正好是轮到我煮饭的那一天。 if((i%cook.getPersonNums())==partner.getCookFlag()) { //那么我哪天回来就该我直接煮饭。 this.setHoldDayCount(0); }//如果我离开的那一天该煮饭的人标识符大于我煮饭的标志符,意思是我已经煮了饭,而且我已经吃了几顿,不过还有几顿没有吃完。 else if((i%cook.getPersonNums())>partner.getCookFlag()) { //计算我还没有吃完的饭的顿数。 this.setHoldDayCount(cook.getPersonNums()+partner.getCookFlag()-i%cook.getPersonNums()); }//如果我离开的那一天该煮饭的人的标识符小于我租房的标志符。 else if(i%cook.getPersonNums()<partner.getCookFlag()) { //计算我还没有吃完的饭的顿数。 this.setHoldDayCount(partner.getCookFlag()-i%cook.getPersonNums()); } } public String toString() { return "Partner [cookDayCount=" + cookDayCount + ", cookFlag=" + cookFlag + ", eatDayCount=" + eatDayCount + ", holdDayCount=" + holdDayCount + ", scale=" + scale + "]"; } }/** * 外出方法类 * @author huxing * */public class Egress { private int egressDate=0; private int backDate=0; public int getEgressDate() { return egressDate; } public void setEgressDate(int egressDate) { this.egressDate = egressDate; } public int getBackDate() { return backDate; } public void setBackDate(int backDate) { this.backDate = backDate; } //定义一个构造函数,用于生成Egress对象,其中分别给两个成员变量赋值。 //第一个参数i表示外出的那一天。第二个参数主要是想获取轮的日期。 public Egress(Cook cook) { this.egressDate=(int)(Math.random()*(cook.getDays()-4)+1); this.backDate=(int)((Math.random()*(cook.getDays()-4-egressDate))+egressDate); } //定义一个外出的方法。 public void beOut(Partner partner,int i) { } }/** * 煮饭类 * @author huxing * */public class Cook { //需要一起做饭的天数 private int days; //一共有多少人参与了做饭 private int personNums; public int getPersonNums() { return personNums; } public void setPersonNums(int personNums) { this.personNums = personNums; } public int getDays() { return days; } public void setDays(int days) { this.days = days; } public Cook(int days,int personNums) { this.days=days; this.personNums=personNums; } public static void main(String args[]) { Cook cook=new Cook(30,4); //创建四个Partner对象 Partner huxing=new Partner(0,0,0,0,0); Partner xulei=new Partner(0,0,0,1,0); Partner kouhao=new Partner(0,0,0,2,0); Partner zhangzhonghua=new Partner(0,0,0,3,0); //产生一个随机数表示出去的日期。 //int beginDate=(int) (Math.random()*30+1); //产生一个随机数表示回来的日期 //int backDate=(int) (Math.random()*(30-beginDate)+beginDate); //构造一个做饭的实例, Egress egress=new Egress(cook); //选择我要离开一些天。 egress.beOut(huxing, egress.getEgressDate()); //开始做饭 for(int i=0;i<cook.getDays();i++) { //如果这一天我还没有出去,按照四个人的顺序做饭。或者在我出去后回来的日子里。按照我设计的思路开始煮饭(后面设计了要多吃的顿数)。 if(i<egress.getEgressDate()||i>=egress.getBackDate()+4) { switch(i%cook.getPersonNums()) { case 0:huxing.cook(huxing);break; case 1:xulei.cook(xulei);break; case 2:kouhao.cook(kouhao);break; case 3:zhangzhonghua.cook(zhangzhonghua);break; } huxing.eat(huxing); xulei.eat(xulei); kouhao.eat(kouhao); zhangzhonghua.eat(zhangzhonghua); }//在我出去的日子里面,按照三个人的顺序做饭。 else if(i>=egress.getEgressDate()&&i<egress.getBackDate()+huxing.getHoldDayCount()) { switch(i%(cook.getPersonNums()-1)) { case 0:xulei.cook(xulei);break; case 1:kouhao.cook(kouhao);break; case 2:zhangzhonghua.cook(zhangzhonghua);break; } xulei.eat(xulei); kouhao.eat(kouhao); zhangzhonghua.eat(zhangzhonghua); //我已经回来了,但先不忙煮饭,而是吃玩了我该吃的顿数才开始煮饭。 if(i>=egress.getBackDate()) { huxing.eat(huxing); } } } System.out.println(huxing.toString()); System.out.println(kouhao.toString()); System.out.println(xulei.toString()); System.out.println(zhangzhonghua.toString()); }}