校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 产品项目分析 > 数值分析
题目

村子中有50个人,每人有一条狗。在这50条狗中有疯狗(这种病不会传染)。于是人们就要找出疯狗。每个人可以观察其他的49条狗,以判断它们是否是疯狗,但是无法看出自己的狗是否有问题。观察后得到的结果不得交流,也不能通知疯狗的主人。主人一旦推算出自己家的是疯狗就要枪毙自己的狗,而且每个人只有权利枪毙自己的狗,没有权利打死其他人的狗。
只有晚上才能看出是否是疯狗,并且发现是疯狗后只能在清晨太阳升起的瞬间枪杀疯狗
第一天,第二天都没有枪响。到了第三天传来一阵枪声,问有几条疯狗,如何推算得出?(黎明太阳升起之前算作一天)

解答

递推归纳法 (第N个人总是把自己当做N-1时的旁观者,直到之后一天才幡然醒悟)
① 如果只有一只疯狗,那么当晚疯狗主人就能知道自己的狗是疯狗,第一天最后黎明时刻就会枪毙自己的疯狗
②如果有两只疯狗,那么第一天在互相知道对方的狗后,等待对方在第一天黎明结束前枪毙自家的疯狗,等到第二天两人会明白自己的狗也是疯狗,所以第二天黎明就会枪毙自己的疯狗
③同理,如果有三只疯狗,那么第一天疯狗的主人会发现另外2只疯狗,这样问题就进入了步骤②的情形,狗主人会作为旁观者等待另外两个狗主人在第二天黎明枪杀疯狗,三个人进入互相等待中(都把自己当成情形②中的旁观者),这样第二天不会有枪声。于是,第三天这三个狗主人会明白自家是疯狗,所以第三天黎明会有枪声。
④同理,若果有四只疯狗,每个疯狗主人会把自己作为③中的旁观者,知道第三天无枪声才会觉悟自家是疯狗
所以,N只狗,第N天黎明会有枪声

C 2条回复 评论
一盏课堂

学的是计算机专业,虽有一些基础,可还是有难度

发表于 2023-02-05 22:00:00
0 0
星夜

只会写初级sql的我看不大懂

发表于 2021-09-09 19:35:00
0 0