中午看到一位同学的面试题,觉得很烧脑,烧脑不能一个人烧,要大家一起烧。
村子中有50个人,每人有一条狗。在这50条狗中有病狗(这种病不会传染),于是人们就要找出病狗。每个人可以观察其他的49条狗,以判断它们是否生病,只有自己的狗不能看。观察后得到的结果不得交流,也不能通知病狗的主人。主人一旦推算出自己家的是病狗就要枪毙自己的狗,而且每个人只有权利枪毙自己的狗,没有权利打死其他人的狗。第一天、第二天都没有枪响,到了第三天传来一阵枪声,问:有几条病狗?如何推算得出?
鉴于杀害狗狗太过残忍,我把其改为送医救治。
村子中有50个人,每人有一条狗。在这50条狗中有病狗(这种病不会传染),于是人们就要找出病狗。每个人可以观察其他的49条狗,以判断它们是否生病,只有自己的狗不能看。观察后得到的结果不得交流,也不能通知病狗的主人。主人一旦推算出自己家的是病狗就要送医救治,而且每个人只有权利救治自己的狗,没有权利救治其他人的狗。第一天、第二天都没有人将狗送医,到了第三天就有几个人将狗狗送去救治了,问:有几条病狗?如何推算得出?
其实一开始,我怎么也想出不来,后来群里有位同学发了答案。
我发现答案我都看不懂!
淦!这不是侮辱我的智商吗?
我岂能如此蒙羞,思考良久,颇有顿悟,记录于此,仅供参考。
其实在答案里面,用的穷举法,从1条狗,穷举到n条狗,只是对于每个样品的推导我着实没有看懂(或者说,确实是我智商问题看不懂),所以推导过程,我自己重新进行了思考。
首先,狗主人是一个类(class Owner),狗是一个类(class Dog)。然后根据题干意思,我们分别分析一下Owner类和Dog类的属性和方法。
代码如下:
public class Owner { //属性部分 //狗主人肯定有一条狗,这条狗可以被别的主人检查,所以设置为public //但是这条狗的生病状态,狗主人看不到 public Dog dog; //狗主人也有一辆车,用来将狗狗送医(车不另外设置类型了,用String代替),车肯定是私有咯 private String Koenigsegg = "一辆柯尼塞格"; //因为有很多主人,所以单个主人应该有一个自己的编号, public int ownerCode; //发现其他狗里生病的狗的数量,因为信息不能共享,所以这个属性是私有的 private int sickDogRecord = 0; //自己的狗是否生病,生病为true,没有生病为false public boolean dogIsSick; //方法部分 //狗主人可以检查其他狗主人的狗 public void checkDog(Dog otherOwnerDog){ //如果这条狗有病,sickDog++; if(狗有病){ sickDogRecord++; } } //狗主人判断自己的狗是否生病 public void IsSick(){ //if...如果自己的狗有病, //dogIsSick = true; } //杀狗 public void killDog(Dog myselfDog){ //调用狗的被送医方法 myselfDog.beSendHospital(Koenigsegg);//传入一个送医的工具 //this.dog = NULL; } public Owner(){ } //构造方法重载 public Owner(Dog dog, int code, boolean sick){ this.dog = dog; this.ownerCode = code; this.dogIsSick = sick; } }
public class Dog { //属性部分 //疾病状态,有没有生病,生病了是true,没有生病是false boolean sick; //多少主人,就有多少条狗,狗也有编号 public int dogCode; //方法部分 //狗被送医 public void beSendHospital(){ System.out.println(this.dogCode+"号狗被送去医院。"); } //狗被送医 重载 public void beSendHospital(String tool){ System.out.println(this.dogCode+"号狗被主人用"+tool+"送去医院。"); } public Dog(){ } //构造函数重载 public Dog(boolean sick, int code){ this.sick = sick; dogCode = code; } }
其次,在逻辑上把狗主人在分为两个类,狗有病的主人为A类,狗没有病的主人为B类。
开始推导:
根据题干中“在这50条狗中有病狗(这种病不会传染)”得知,。于是从1开始穷举。
推论1:有病的狗≥1。
假设a:
有一条狗生病。
那么所有的owner中就只有一个A,这个A检查别人的狗之后,A.sickDogRecord = 0。
此时对于A来说,他是知道推论1的,且他没有发现别的病狗,那么生病的狗只能是自己的的狗了,A在第一天,就必须将狗送医。
这与题干结果不符,假设不成立。
推论2:若只有一条狗生病,那第一天一定有人将狗送医治疗。
假设b:
有两条狗生病。
那么A类就有两个对象,首先分析A1对象的推导。
A1在检查其他狗狗之后,A.sickDogRecord = 1,A1将会有两种判断:
1:A1的狗没有病
A1认定自己的狗没病,但是他有看到了1只病狗,A1会认为,所有的狗狗里只有1只病狗。
此时对于A1来说,他会觉得病狗的主人A2会根据推论一和推论二,在第一天就将狗狗送医,但是第一天什么都没发生。
判断1不成立。
2:A1的狗有病
判断1不成立,但是A1确实是看到了病狗,又没有人送医,那唯一可以解释的就是A2也看到了病狗,而且也觉得自己的狗不是病狗,
所以A2没有在第一天就将狗狗送医治疗,也就是说,在第一天,A1和A2的想法是一样的。而在第二天A1知道了A2和他的想法一样。
原文:https://www.cnblogs.com/Azir-s-soldier/p/11461976.html