试题-村子中有50个人，每人有一条狗。

题目

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

上一题 下一题

解答

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