IBM经典面试题:50个人50条狗的推理和编程实现

时间: 2008-11-24 / 分类: 学习心得, 收藏推荐, 软件网络 / 浏览次数: 3,853 / 2个评论 发表评论

有一个IBM的面试题,比较变态的,是关于50个人、50条狗,推算病狗数目的,题目如下:

村子中有50个人,每人有一条狗。在这50条狗中有病狗(这种病不会传染)。于是人们就要找出病狗。每个人可以观察其他的49条狗,以判断它们是否生病,只有自己的狗不能看。观察后得到的结果不得交流,也不能通知病狗的主人。主人一旦推算出自己家的是病狗就要枪毙自己的狗,而且每个人只有权利枪毙自己的狗,没有权利打死其他人的狗。第一天,第二天都没有枪响。到了第三天传来一阵枪声,问有几条病狗,如何推算得出?

其实网上有很多的解答,而且这些解答也都是一样的,估计是官方的?其实题目设定在第三天听到枪声推理很简单,如果是设定在第47天呢?一步一步推理就有点不靠谱了,还得通过计算机程序的方式来变成解答吧,虽然计算机比较笨,这种算术题还是算的比较快的。解答如下:

第一种推论:
A、假设有1条病狗,病狗的主人会看到其他狗都没有病,那么就知道自己的狗有病,所以第一天晚上就会有枪响。因为没有枪响,说明病狗数大于1。

B、假设有2条病狗,病狗的主人会看到有1条病狗,因为第一天没有听到枪响,是病狗数大于1,所以病狗的主人会知道自己的狗是病狗,因而第二天会有枪响。既然第二天也没有枪响,说明病狗数大于2。

由此推理,如果第三天枪响,则有3条病狗。

第二种推论
1 如果为1,第一天那条狗必死,因为狗主人没看到病狗,但病狗存在。
2 若为2,令病狗主人为a,b。a看到一条病狗,b也看到一条病狗,但a看到b的病狗没死故知狗数不为1,而其他人没病狗,所以自己的狗必为病狗,故开枪;而b的想法与a一样,故也开枪。
由此,为2时,第一天看后2条狗必死。
3 若为3条,令狗主人为a,b,c。a第一天看到2条病狗,若a设自己的不是病狗,由推理2,第二天看时,那2条狗没死,故狗数肯定不是2,而其他人没病狗,所以自己的狗必为病狗,故开枪;而b和c的想法与a一样,故也开枪。
由此,为3时,第二天看后3条狗必死。
4 若为4条,令狗主人为a,b,c,d。a第一天看到3条病狗,若a设自己的不是病狗,由推理3,第三天看时,那3条狗没死,故狗数肯定不是3,而其他人没病狗,所以自己的狗必为病狗,故开枪;而b和c,d的想法与a一样,故也开枪。
由此,为4时,第三天看后4条狗必死。
5余下即为递推了,由年n-1推出n。
答案:n为4。第四天看时,狗已死了,但是在第三天死的,故答案是3条。

编程实现:
int iDog; //病狗数量
int nDog; //狗的数量
int pDog; //人数;等于狗的数量br />
bool HaveLook=false;

for (int i=1;i<=nDog;i++)
{
 iDog=i; //推出的病狗数量
 for (int j=1;j<=pDog;j++) //每人
 {
  int LookiDog=LookDog();  //观察狗,返回看到的病狗数量
  if(lookiDog==iDog-1) //观察到的数量比实际病狗数量少1,推出自己的是病狗
  {
   killDog(pDog[j]);
   HaveLook=true;
  }
 }
 if (HaveLook) return iDog;   //返回病狗数量
}

上述程序未经验证,如有错误请回复告知,谢谢。

历史上的今天

2016年:除草文(45条评论)

2013年:快乐星期天285期:幽默语录(67)(36条评论)

2011年:卡当网抵用券大放送(46条评论)

2010年:替代微软官方MSN客户端:MSN Lite绿色版(28条评论)

2009年:解谜:修改浏览器的User Agent,能够做什么?(107条评论)

2007年:[11.24]我的拿手好菜(0条评论)

2个评论

  1. Aiden朋
    2015/09/23 09:53:39

    这个是什么鬼!!

发表评论

您的昵称 *

您的邮箱 *

您的网站