【考研】计算机考研复试之智力题测试

本文主要是介绍【考研】计算机考研复试之智力题测试，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

更新历史：

• 2021年02月24日完成初稿
• 2021年03月多次更新文章
  • 第三题方向 [ 感谢博主WTSRUVF指正 ]
  • 第六题污染的药丸 [ 感谢博主qq_39006092指正 ]
• 2021年04月03日汇总文章
• 2022年03月20日更新第12题

  本文为 Yang 同学 2021 年哈尔滨工业大学计算机考研复试中智力题测试记录，将持续更新。
  本文在2021年04月03日汇总之前发布的三篇文章，并合并为一篇文章，感谢在其他文章点赞和评论的同学，谢谢！

1. 回到原点

  地球上存在多少个点，向南走一英里，向东走一英里，向北走一英里能够回到原点？
【0x00 思考】

  如果不是特殊的地方，则肯定不能回到原点，那么这个点必须是在特殊的地方，我们考虑赤道¹、南极点²和北极点³。那么下面我们考虑一下在赤道、南极和北极处的方位问题（此处涉及一些地理知识，如下图）：

位置	方位特征
赤道	有东、南、西、北四个方位
南极点	在这一点所指向的任何方向都是北方
北极点	在这一点所指向的任何方向都是南方

  那么就可以考虑南极点和北极点：

【0x01 解答】

  向南走一英里，向东走一英里，向北走一英里能够回到原点？考虑以下地点：

1. 南极点及其附近的点
     在南极点，所有方位都是向北，那么向南走一英里则是原地旋转，向东走一英里还是原地旋转，利用在南极点向北走一英里则是向任意方向走一英里的特点，则向北走一英里则是向任意方向走一英里，肯定不能回到原点。
     考虑南极点附近的点，注意到在南极附近向东、西方向走一定距离就是走一段圆弧。如果向东走一英里可以回到原点的话，那么向南走一英里，向东走一英里，向北走一英里就相当于向南走一英里，向北走一英里，这样或许就能回到原点。要想向东走一英里可以回到原点，则从起点（设为A点）向南走一英里到达的地方（设为B点）应满足：B点到南极点的距离r = 1/2kπ (k为正整数) ，在B点向东走一英里就相当于绕地球若干圈回到B点，再从B点向北走一英里即可回到原点，故离南极点1+1/2kπ的所有点均符合题意，其走过的路程如下图所示。
   
2. 北极点及其附近的点
     在北极点，向南走1英里，即向任意方向走1英里，假设走到了A点，在A点处向东走，实际上是走一个圆弧，假设到达B点。之后在B点向北走，那么就是向北极点走去，即可回到北极点（原点），故北极点符合题意。其走过的路程如下图所示。
     在北极附近的点，同样如上述的那样，找到向东走一英里可以回到原点的点，即离北极点1/2kπ的点（设为C点）。但是在该点处，向北走一英里是不存在的（向北走1/2kπ就到了北极点，之后向北走就是原地转圈了，故最终地点就是北极点，若它是原点，则起点也是北极点，向南走一英里到不了C点），故在北极附近的点都不符合题意。
   

【0x02 答案】

  北极点和离南极点1+1/2kπ (k为正整数)的所有点 。

【0x03 方法论】

  作为非 常识问题，从正向推理解决问题是复杂的，而是从问题的特殊情况考虑（本题的特殊情况就是赤道、北极和南极），把握特殊成为了问题的关键。无论是自然现象，还是数学问题，特殊情况（特殊现象、特殊点等）往往是推翻所谓真理的有效工具。

【0x04 小结】

  本题实际上和C语言中的循环有密切的联系，也即在南极点（北极点）向除北（南）以外的点前进都是原地转圈，在南极点（北极点）附近向东、西方向前进则是绕着圆弧行走，故可以可以是回到原地，其实质就是循环。
  不过说实话，本题对地理知识要求也很高，对于地理基础不好的理工科生来说确实是一个难题。

2. 开灯

  有100栈灯，编号为1~100，一开始灯都是开着的。之后依次进行以下操作：

1. 按下所有开关；
2. 按下编号为2的倍数的开关；
3. 按下编号为3的倍数的开关。

  请问，最后有多少灯是开着的？

【0x00 思考】

1. 数学与计算思维

  认真分析题目不难发现，可以用数学语言对其进行描述：

  设X,Y是集合，X = {1,2,...,100}, Y = {0,1}。f是从X到Y的映射，初始时f(X) = {1} （用1代表灯开，0代表灯关，从1到0或者从0到1的变化称为变号）。需经过下面的操作：

1. 对于任意的x，f(x)变号；
2. 对于任意的x，若x|2（x被2整除），则f(x)变号；
3. 对于任意的x，若x|3（x被3整除），则f(x)变号；

  求集合A（X包含A），使f(A) = {1}且|A|最大。

2. 逻辑思维

  灯的状态与初始状态、开关操作情况密切相关，问题则变为：有100栈灯，编号为1~100，一开始灯都是开着的，依次按下编号为1、2、3的倍数的开关，问哪些灯按了偶数次开关？

【0x01 解答】

  用逻辑思维考虑问题则有：一开始灯都是开着的，之后按下所有开关，则灯全部关闭，再按下按下编号为2的倍数的开关，则编号为2的倍数的灯是打开状态，编号不是2的倍数的灯是关闭状态。最后，按下编号为3的倍数的开关，则编号为不是2的倍数，但是3的倍数的灯和编号是2的倍数，但不是3的倍数的灯处于打开状态，其余处于关闭状态。
  用数学与计算思维考虑问题则有：一开始灯都是开着的，经过上面3个步骤，对于任意的1 <= x <= 100而言有，

1. 若x是1、2、3的倍数，则f(x)变号3次；
2. 若x是1、2的倍数，但不是3的倍数，则f(x)变号2次；
3. 若x是1、3的倍数，但不是2的倍数，则f(x)变号2次；
4. 若x是2、3的倍数，但不是1的倍数，则f(x)变号2次；
5. 若x是1的倍数，但不是2、3的倍数，则f(x)变号1次；
6. 若x是2的倍数，但不是1、3的倍数，则f(x)变号1次；
7. 若x是3的倍数，但不是1、2的倍数，则f(x)变号1次；
8. 若x不是1、2、3的倍数，则f(x)变号0次。

  由于x肯定是1的倍数，则上述可能性可减少为：

1. 若x是1、2、3的倍数，则f(x)变号3次；
2. 若x是1、2的倍数，但不是3的倍数，则f(x)变号2次；
3. 若x是1、3的倍数，但不是2的倍数，则f(x)变号2次；
4. 若x是1的倍数，但不是2、3的倍数，则f(x)变号1次；

  故也可以得到结论：编号为不是2的倍数，但是3的倍数的灯和编号是2的倍数，但不是3的倍数的灯处于打开状态，其余处于关闭状态。

  上面两种思维是殊途同归的，但是对于计算机而言，用数学与计算思维考虑问题是更好的，因为可以利用程序进行求解。

【0x02 答案】

  依据上面的分析，有以下程序（此处为了普遍性，设有n个灯泡）

#include <stdio.h>
#define MAXSIZE 500
#define STEP 3
int main()
{int i, j, n ,bulb[MAXSIZE] = {0} ;int cnt, flag ;                                    /* in order to print */scanf("%d", &n) ;for(i = 1; i <= n; i++)                            /* initialization */{bulb[i] = 1 ;}for(j = 1; j < STEP+1; j++)                        /* step 1/2/3*/{for(i = 1; i <= n; i++){if(i%j == 0)                               /* step j */{bulb[i] = (bulb[i] == 0) ? 1 : 0 ;     /* change */}}}cnt = 0, flag = 0 ;for(i = 1; i <= n; i++)                             /* print */{if(bulb[i] == 1){printf("%-4d", i) ;cnt ++ ;flag = 1 ;}if(cnt > 0 && cnt%10 == 0 && flag == 1)        /* print \n every 10 numbers*/{printf("\n") ;flag = 0 ;}}printf("\n") ;return 0 ;
}

/* example: 100 bulbs */
100
2   3   4   8   9   10  14  15  16  20
21  22  26  27  28  32  33  34  38  39
40  44  45  46  50  51  52  56  57  58
62  63  64  68  69  70  74  75  76  80
81  82  86  87  88  92  93  94  98  99
100

【0x03 方法论】

  从逻辑思维考虑问题是清晰的，但对于研究工作者（特别是数学科学工作者）而言，用准确的数学语言描述问题是更加关键的，它不一定使问题得到简化，但会使问题更加清晰，并可以扩展并解决一类问题，因此掌握数学工具是一个有效的解决问题的手段，应学会用数学语言描述自然现象。

【0x04 小结】

  本题实际上考察了整数求余问题，灯的打开和关闭状态(0、1)实际上可以对应二进制数，而灯的编号是1、2、3的倍数确定了灯的开/关次数，从而决定灯的打开和关闭状态(0、1)。若能确定灯的编号和灯的打开和关闭状态(0、1)的映射关系，那么就可以知道最后灯的状态。

  该问题的进阶问法是：有100栈灯，编号为1~100，一开始灯都是开着的，依次按下编号为1、2、…、100的倍数的灯的开关，那么最后哪些灯是亮着的

3. 方向

  一个圆盘被涂上了黑白两种颜色，两种颜色各占一个半圆，圆盘以一个未知的速度、按一个未知的方向旋转。现有一些颜色传感器（可以判断是黑色还是白色）可供使用。问如何用最少的传感器测试出圆盘是在顺时针转还是逆时针转？最少要用几个传感器？

【0x00 思考】

  首先应明白顺时针旋转和逆时针旋转的区别，取白色圆盘边缘的两个紧挨着的点，顺时针的圆盘和逆时针的圆盘经过这两个点的顺序是不一样的（具体顺序见下述），如下图所示。因此利用这个特性可以判断圆盘的选择的方向。

【0x01 解答】

  取两个颜色传感器，设为A和B，将两个传感器紧挨着（假设传感器反应时间足够短），如下图所示。启动传感器A、B，当传感器A、B显示都是白色时（如图中传感器A、B正检测白色圆盘区域），开始记录传感器A、B显示转变为黑色的时间，记为Ta和Tb。

  如下图所示，若圆盘是顺时针旋转的，那么Ta < Tb；若圆盘是逆时针旋转的，那么Ta > Tb，故由Ta和Tb的大小可知圆盘的旋转方向。

  好了，这个问题解答完毕，用两个传感器即可判断圆盘的旋转方向，但是如何证明它是最少的呢？证明它是最少的，也就是证明用一个传感器无法判断方向。但是事实是这样吗？

  在上面，我们利用时间差来判断方向，那么如果只有一个传感器，也需要用时间差来判断方向，那么一个传感器如何有时间差呢？很自然的想到，我们可以让传感器旋转起来，因此我们可以尝试去求解：

  如下图所示，现只用传感器A，则有以下四种情况，我们只需要判断传感器A沿圆盘边缘顺时针移动和沿圆盘边缘逆时针移动时，是否能够判断出圆盘的方向。

  当圆盘顺时针转动时，当传感器顺时针移动时，圆盘的相对速度（以传感器为参考系）为V1，当传感器逆时针移动时，圆盘的相对速度（以传感器为参考系）为V2，由高中物理知识可知V2 > V1。同理可知，当圆盘顺时针转动时，V1 > V2。因此当传感器顺时针移动时传感器显示的颜色变化快，则圆盘是逆时针旋转的；当传感器逆时针移动时传感器显示的颜色变化快，则圆盘是顺时针旋转的。至此问题才很好地解答了。

【0x02 答案】

  只用一个传感器即可，只需让传感器顺时针/逆时针旋转时，观察传感器显示的颜色变化快慢即可判断圆盘的旋转方向。

  指正：题中提及的 “未知速度” 若不能保证是匀速，而可能是随时间变化的情况，那么一个传感器不能实现，需要两个传感器。此处感谢博主WTSRUVF的指正。

【0x03 方法论】

  直接想到一个传感器的方案是困难的，但是从两个传感器的方案中认识到什么是关键因素（本题是时间差）是至关重要的，这会给最佳答案进行铺垫。这是一种渐进的思想，先找到局部最优解，再从局部最优解出发，判断是否能够有更优的解，最终找到全局最优解（当然全局最优解可能不存在）。

【0x04 小结】

  本题考察的知识点其实是如何设计方案，不一定一开始就想到最优情况，但是在设计方案的过程中，找到影响全局的变量，从该变量出发，进而设计最优的方案。

4. 找假币

  有12枚一模一样的硬币，已知其中只有一枚是假币，并且假币和真币的重量不一样，问如何用一个天平把假币从这12枚硬币中找出来？最少要称几次？

【0x00 思考】

  由于硬币只有重量不一样，所拥有的工具也只有天平，故只能通过平衡来判断硬币的真假，假币在12枚硬币当中，从12枚硬币出发是困难的，那么我们让硬币少一点：

（1）只有两个硬币

  用天平称一次，可辨别轻重，但是不能判断哪一枚是假币（因为不知道假币是重一点还是轻一点）。但如果用已知的一枚真币和另外一枚硬币去称量，通过一次称量就可以得知该硬币是不是假币。

（2）有三枚硬币

  有三枚硬币，那么可以从三枚硬币中去出两枚放置在天平上称量，有两种情况：（若已知假币谁轻谁重，一次称量即可）

1. 天平平衡，那么未称量的硬币是假币；（总共称1次）

2. 天平不平衡，那么未称量的硬币是真币，那么需要再称一次，取该真币和另两枚硬币之一比较即可得知哪一枚是假币。（总共称2次）

  好了，思路到这里就可以变得开阔了，问题就转化为如何将12枚硬币转化为2枚硬币或者3枚硬币的问题？或许利用 分治 的思想就可以解答了。

【0x01 解答】

（1）将12枚硬币转化为“2枚硬币”
  如何转化，那便是将12枚硬币分成 6枚硬币 + 6枚硬币 ，那么问题就得到了转化，因此有：

1）将12枚硬币分成 6枚硬币（A1） + 6枚硬币（A2），用天平称量第一次，假设结果为A1比A2重；

2）继续将 6枚硬币（A1）分成 3枚硬币（B1） + 3枚硬币（B2），用天平称量第二次；将6枚硬币（A2）分成 3枚硬币（B3） + 3枚硬币（B4），用天平称量第三次。由于A1和A2必然有一堆是真的，故第二次称量和第三次称量中必有一次是平衡的，假设第二次称量是平衡的，而B3比B4重，那么6枚硬币（A1）全为真币，A1比A2重，则假币比真币轻一点，故假币在B4中。

3）B4中有三枚硬币，通过用天平称量第四次即可知道假币（由上面分析此时一次称量即可）。

4）故需要称量4次才能判断假币。

（2）将12枚硬币转化为“3枚硬币”

  有了上面的经验，便可将12枚硬币分成 4枚硬币 + 4枚硬币 + 4枚硬币 ，那么问题就得到了转化，因此有：

1）将12枚硬币分成 4枚硬币 （A1）+ 4枚硬币（A2） + 4枚硬币（A3），取两堆硬币称量，假设取A1和A2用天平称量第一次，有两种结果，下面分述之。

2）若平衡，那假币在A3中，A1和A2全为真币，此时可将4枚硬币（A3）转化为“2枚硬币”，将4枚硬币（A3）分为2枚硬币（B1）+2枚硬币（B2），以及取A1中的2枚硬币（B3，真币），取2枚硬币（B1）+2枚硬币（B3）用天平称量第二次。那么又有两种情况，假设平衡，那么假币在B2中，取一枚真币和2枚硬币（B2）中的一枚用天平称量第三次即可知晓假币。

3）若不平衡，则A3为真币，假币在A1或A2中，那么需要取A3和A1用天平称量第二次，有两种情况。若平衡，则锁定假币在A2中，由2）知还需两次称量才能判断假币；若不平衡，则锁定假币在A1中，由2）知还需两次称量才能判断假币。

4）综上所述，该方案也需要称量4次才能判断假币。

【0x02 答案】

  至少称量4次才能判断假币，方案如上所述。

【0x03 方法论】

  分治的思想是将大问题化为较小的、可以直接求解的问题，本题从2/3枚硬币的判断出发，求解了12枚硬币的问题，是典型的分而治之的思想。

【0x04 小结】

  从12枚硬币找出假币，关键在于判断假币所在硬币的范围，用分治的思想可以缩小假币的范围，从而使得问题得到一定程度的简化，最终达到可以直接求解答的程度。在C语言中用if语句的分支，可以确定假币在哪一个分支中，从而不断确定假币所在分支，直至分支中可求解为止。

【0x05 扩展】

  有7克、2克砝码各一个，天平一只，如何只用这些物品三次将140克的盐分成50、90克各一份？

  欢迎大家在评论区讨论！

5. 帽子（病狗问题）

  一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，已知至少有一顶黑帽子。每个人都能看到其它人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什幺帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。
  第一次关灯，没有打耳光的声音。于是再开灯，大家再看一遍，第二次关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？

【0x00 分析】

  刚接触该问题时，没有思路是正常的，对于这类问题，就需要总结信息，总结题设所给信息说明了什么：

1. 第一次关灯，没有打耳光的声音
   此时，每个人都不能确定自己是不是戴了黑帽子，那么肯定自己看到了别人戴了黑帽子（题设中已经说明一定有黑帽子），这些戴黑帽子的人也看到了别人戴了黑帽子，因此这里至少有两顶黑帽子；

2. 第二次关灯时，也没有打耳光的声音
   此时，每个人都至少看到了两顶黑帽子（若只有一个人（设为A）只看到一顶黑帽子（设为B），而A第一次关灯没有听到打耳光的声音，就能判断B也看到了黑帽子，而A只看到一顶黑帽子，故可以判断自己就是戴了黑帽子，那么第二次关灯时自己会打自己耳光），因此戴了黑帽子的人也看到了至少两顶黑帽子，故至少有三顶黑帽子；

3. 第三次关灯时，有多人打了耳光
   最后，戴黑帽子的人第二次关灯后确定自己戴了黑帽子，那么关键在于为什么能判断出自己戴了黑帽子，如果每个人看到戴黑帽子的人很多，那么肯定不能确定自己是不是黑帽子，因此戴黑帽子的人比较少，以至于可以确定自己戴了黑帽子，因此可以用排除法来确定黑帽子的数量。

【0x01 解答】

  根据上面的分析，黑帽子至少有三顶，不过在这里可以再去分析一下为什么只有1、2定帽子不符合题意，然后再推理3顶帽子是否符合题意：

1. 若只有一顶黑帽子：那么则这个戴黑帽子的人会知道自己戴了黑帽子，那么在第一次关灯的时候会打自己耳光，与题设不符；
2. 若只有两顶黑帽子：那么一个戴黑帽子的人看到只有一个人戴了黑帽子，但是后者在第一次关灯的时候没有打自己耳光，那么可以确定后者也看到了黑帽子，这个黑帽子就是自己的，故这个人在第二次关灯的时候就会打自己耳光；
3. 若只有三顶黑帽子：假设戴黑帽子的人为A、B、C，由于第1、2点的分析，那么戴黑帽子的人（A、B、C）会看到两顶黑帽子或更多，但是由于只有三顶黑帽子，故刚开始的时候A、B、C相互看到了对方，而其他人看到了A、B、C，此时由于A知道 “B会看到C戴黑帽子，C会看到B戴黑帽子，故A知道B、C不会打耳光” ，B、C也是如此思考。第一次关灯后，再开灯，A思考：“ 如果自己不是黑帽子，那么只有B、C戴了黑帽子，B看到C没有打耳光后会意识到自己（B）戴了黑帽子 ”，那么B在第二次关灯后打自己的耳光，但是第二次关灯时没有人打耳光，那么A意识到B看到了C戴黑帽子之外，还看到别人戴黑帽子，这个就是自己，故此时A知道了自己是黑色帽子，B、C也知道了，故第三次关灯，A、B、C打了自己的耳光。
4. 若只有四顶帽子：那么第二次关灯后，戴黑帽子的四人A、B、C、D不能意识到自己是黑帽子，故第三晚没有打耳光的声音，与题意不符。若黑帽子更多，那么就更加不清楚了。

  综上所述，有3人戴着黑帽子。

【0x02 小结】

  这道题十分巧妙，其实继续分析可以知道：若有N顶黑帽子，那么第N晚的时候这N个戴黑帽子的人会打自己的耳光，而这一结论是从“ 若有一顶黑帽子 ”得出的结论，因此由小问题到复杂问题的求解思路仍然是可行的。

【0x03 扩展】
  上面的问题也叫做病狗问题：村子中有50个人，每人有一条狗,每天傍晚大家都在同一个地方遛狗。在这50条狗中有病狗(这种病不会传染)。于是人们就要找出病狗。每个人可以观察其他的49条狗，以判断它们是否生病，只有自己的狗不能看。观察后得到的结果不得交流，也不能通知病狗的主人。主人一旦推算出自己家的是病狗就要枪毙自己的狗，而且每个人只有权利枪毙自己的狗，没有权利打死其他人的狗。第一天，第二天都没有有枪响。到了第三天村子传来一阵枪声，问有几条病狗，如何推算得出？

  仔细分析可知，两道题的答案是相同的。

6. 污染的药丸

  有10瓶药丸装有若干药粒，其中有一瓶药丸受到污染，正常药丸每粒10g，受到污染的药丸每粒9g，如何用带有砝码的天平只称一次就找出受污染的药丸？

【0x00 思考与解答】

  由于只能称量一次，那么称量一次之后必须标识出不同的药丸，那么每瓶药丸就不能取相同颗数的药粒，因此若取相同颗粒的药粒就不能确保一次称量就可以找到被污染的药丸。因此应该从药瓶中取出不同数量的药丸，比较简单的方法是给10瓶药丸编号1 ~ 10，然后从中依次取出1, 2, ..., 10颗药粒（编号为i的药瓶中取i粒），然后用天平称量，称得重量为m。

  下面就是通过重量m如何来确定那瓶药丸的重量是有问题的？

  假设第i瓶药瓶受到污染，那么取出药粒的重量应该为m' = i * 9 + (1 + 2 + ... + 10 - i) * 10 = 550 - i。因此i = 550 - m即为被污染药瓶的编号。

【0x01 小结】

  本题思路上是值得学习的，一次称量就意味着必须在一次称量中就能区分不同的药丸，从而能够找到其中污染的药丸，

7. 运动员

  50名运动员按顺序排成一排，教练下令：“单数运动员出列！”剩下的运动 员重新排列编号，教练又下令：“单数运动员出列！”如此下去，最后只剩下一个人，他是最开始的几号运动员？

【 0x00 思考】

  由于最后只剩下一个人，那么需要清楚经过几轮之后会变成一个人？另外剩下的那个运动员一定在每一轮都是偶数编号的，那么是否存在这样的编号？

  这个问题是容易想到的，但是问题的起点应该是什么？这涉及到一个思维问题，那就是正向和反向思考问题，而本题中回答第一个轮次的问题需要从正向去考虑，因为逆向推理会增加情况的总数，而第二个编号的问题则应该从反向考虑问题，尤其是在确定轮次后更加应该能确定每一轮有哪一些编号。

【0x01 解答】

  首先解决经过几轮才会变成一个人的问题：

1. 运动员编号为1, 2, 3, ..., 50，单数出列后剩下编号为2, 4, 6, ..., 50的运动员（25人）。

2. 运动员重新编号为1, 2, 3, ..., 25，单数出列后剩下编号为2, 4, 6, ..., 24的运动员（12人）。

3. 运动员编号为1, 2, 3, ..., 12，单数出列后剩下编号为2, 4, 6, ..., 12的运动员（6人）。

4. 编号为1, 2, 3, ..., 6，单数出列后剩下编号为2, 4, 6的运动员（3人）。

5. 编号为1, 2, 3，单数出列后剩下编号为2的运动员（1人）。

  因此只需要5轮便只剩下1个人了，那么最后一个人之前的编号为多少呢？下面反向推理可得：

1. 最后一个运动员第五轮的编号为2

2. 第四轮时，剩下编号为2, 4, 6的运动员中，编号为4的运动员会在第五轮编号为2

3. 第三轮时，剩下编号为2, 4, 6, ..., 12的运动员中，编号为8的运动员会在第四轮编号为4

4. 第二轮时，剩下编号为2, 4, 6, ..., 24的运动员中，编号为16的运动员会在第三轮编号为8

5. 第一轮时，剩下编号为2, 4, 6, ..., 50的运动员中，编号为32的运动员会在第二轮编号为16

  最终可知，剩下的最后一名运动员是最开始的32号运动员。

【0x02 小结】

  回答这个问题看似不难，但却从两个方向去思考问题，这种双向思维的训练是有必要的，而且是值得大家学习的。

8. 选快马

  在一个有5条跑道的训练场，其中有25匹马，现想选择其中跑得最快的3匹马前去比赛。已知每次预选马匹的时候，只能跑5匹，而且只能通过赛跑来决定哪匹马跑得快（不可以计时后排名）。问如何用最少的次数选出最快的前3匹马，给出具体的方案。

【0x00 思考】

  如果懂得竞赛的思想，那么一个简单（可能不是最优）的方案是可以得到的：

1. 将25匹马分成5组（设为A、B、C、D、E组），每个小组5匹马（和跑道数相同），然后每个小组比赛决出第一名（设为A1、B1、C1、D1、E1），本轮需要比赛5次；

2. 然后将各组第一名（A1、B1、C1、D1、E1）同场比赛，然后决出第一名（假设是A1），则A1是25匹马中跑得最快的一匹马，将A1选出，本轮需要比赛1次；

3. 那么剩下的24匹马谁是跑得最快的呢？首先，B1、C1、D1、E1分别是B、C、D、E组最快的一匹马，因此如果剩下的24匹马中跑得最快的那匹马在B、C、D、E组中，那么必定是B1、C1、D1、E1，因此跑得最快的那匹马在A组4匹马和B1、C1、D1、E1中，由于A组4匹马已经比过赛，因此可以直接选出A组跑得第二快的马（设为A2），那么剩下的24匹马中跑得最快的那匹马在A2、B1、C1、D1、E1中，让其同场比赛，然后决出第一名（假设是C1），则C2是25匹马中跑得第二快的一匹马，本轮需要比赛1次；

4. 按照第3轮的规则，同理可知，通过一场比赛便可选出跑得第三快的一匹马，本轮需要比赛1次。

  因此在这个方案中，需要比赛8次选出速度在前三的马，其过程如图所示：

  那么接下来要思考或是证明这种解法是否是最优解？下面在【解答】里面证明是否还有更佳的方案。

【0x01 解答】

  我们上面利用的方法其实是败者树，该方法可以证明是正确的，但是能否用更少的比赛场次呢？

  答案是肯定的，利用败者树的方法很容易得到一个方案，不过这个方案是忽略了重要的一点：只需要知道前三即可。那么如果只关注前三的话，那么不可能成为前三的就没必要考虑了。那么第一轮就可以是：

  第一轮：将25匹马分成5组（设为A、B、C、D、E组），每个小组5匹马（和跑道数相同），然后每个小组比赛决出前三名（本轮需要比赛5次）。

  这样保证了用最少的场次比较了每一匹马，当且仅当所有马都经过比较之后才能知道前三。

  此时每组的前三名都可能是全部赛马的前三名，因此暂时不能排除任何一匹赛马。那么我们自然会想：

1. 每个小组的第一如果是全部赛马的第一，那么该组赛马的第二、第三也可能是全部赛马的第二、第三；

2. 每个小组的第一如果是全部赛马的第二，那么该组赛马的第二可能是全部赛马的第三，该组赛马的第三肯定不是所有赛马的前三；

3. 每个小组的第一如果是全部赛马的第三，那么该组赛马的第二、第三不可能是全部赛马的前三。

4. 每个小组的第一如果是全部赛马的第四及更后，那么该组所有赛马不可能是全部赛马的前三。

  那么每个小组第一的最终名次是关键的，那么我们进行第二轮：

  第二轮：将各组第一名（假设为A1、B1、C1、D1、E1）同场比赛，然后得出排名（假设排名是A1、B1、C1、D1、E1），本轮需要比赛1次。

  那么根据上面的分析，可以排除B3（B组第三，下同）、C2、C3、D组和E组全部，而且可以断定A1就是全部赛马的第一，如下图所示：

  那么剩下A2、A3、B1、B2、C1可能在前三之列，那么有第三轮比赛：

  第三轮：将A2、A3、B1、B2、C1进行同场比赛，然后决出第一、第二，本轮需要比赛1次。

  这里的第一、第二和A1（总第一）就是前三了，而这里只比较了7次，因为利用了只需要决出前三的特点。

【0x02 答案】

  用只需决出前三的思想，至少进行7场比赛才可决出前三，方案如前【0x01 解答】所述。

【0x03 小结】

  事实上，从已知的最优解出发求解理论最优解是可行的，这个思路是需要掌握的，而且有时候想出局部解是简单的，但由此推广到全局最优解是困难的，往往需要抓住关键。同时，在这里所说的败者树思想（也有相应的胜者树）是数据结构中实现多路归并的技术，想进一步了解的可以进一步参考文章末尾的链接⁴。

【0x04 拓展】

  如果要决出前5匹马呢，最少需要几次？欢迎大家在评论区讨论！⁵

9. 药瓶毒白鼠

  有1000个一模一样的瓶子，其中有999瓶是普通的水，有1瓶是毒药。任何喝下毒药的生命都会在一星期之后死亡。现在你只有10只小白鼠和1个星期的时间，如何检验出哪个瓶子有毒药？

【0x00 思考】

  根据题意，1000个瓶子里面有一瓶装有毒药，如果选出10个瓶子让小白鼠做实验，那么肯定不能得出答案。不过如果想到 2¹⁰ = 1024 > 1000 时，那么1000瓶子可以用10位2进制数表示，那么问题就迎刃而解了。

【0x01 解答】

  将1000个瓶子编号：

1. 第1个瓶子编号0000000000
2. 第2个瓶子编号0000000001
3. 第3个瓶子编号0000000010
4. …

  可知该编号是唯一的，之后将小白鼠编号为1 ~ 10，对于1000个瓶子，若其编号xxxxxxxxxx中若哪几位为1，则让几号小白鼠喝一些该瓶中的水（假设小白鼠可以喝完这些水而不撑死），例如编号为0001001100（从低位到高位中第3, 4, 7位为1），则让第3, 4, 7号小白鼠喝喝一些该瓶中的水。过一个星期后观察，若y号小白鼠死亡，那么编号xxxxxxxxxx中第y位是1，否则为0，由此便可确定编号，从而确定哪个瓶子有毒药。

【0x02 小结】

  问题的求解过程是简单的，但思路的源头是十分复杂的，它源于一定的计算素养，2¹⁰ = 1024是不难解答的，但是将其和本问题联系起来是不便的，而这种能力的提升往往只能通过大量的训练来完成。

【0x03 拓展】
  有10瓶药，每瓶有10粒药，其中有一瓶是变质的。好药每颗重1克，变质的药每颗比好药重0.1克。问怎样用天秤称一次找出变质的那瓶药。

  欢迎在评论区进行解答！

10. 猎人与狐狸

  有五个一字排开的山洞，每个山洞除地理位置外其他一模一样，有一只狐狸会住在某个洞，而且每天晚上会换住到相邻的洞中，而一个猎人只能每天早上去一个洞抓狐狸，问猎人需要几天才能抓住狐狸，每天进哪个洞？

【0x00 思考】

  站在猎人的角度，当天早上的结果会决定狐狸所在的地方，那么先一一列举猎人的进洞顺序是比较可靠的方法，给洞从左至右编号1 ~ 5，考虑最坏的情况（即猎人每次进洞只有有可能抓不到狐狸，那就假设结果是抓不到狐狸），而且考虑下面的几条原则：

• 不进1、5号洞
  当狐狸在1或者5号洞时，我们可以确定狐狸下一次的所在地只有2或者4，因此尽量不进1、5号洞，而尽量使狐狸在1或者5号洞。

• 若可以使得狐狸仅可能在1、3、5号洞则尽量使这种情况发生
  若狐狸仅可能在1、3、5号洞，则之后仅可能在2、4号洞，就可以抓住狐狸了

• 尽量不在连续时间内重复进同一个洞
  即今天进一个洞，明天就换一个洞，因为重复进一个洞对于情况的排除是不利的，除非剩下的情况比较简单。

  同时注意到洞除了物理位置不一致外，其他是一致的，因此1号洞在问题的求解上和5号洞是一样的，而2号洞在问题的求解上和4号洞是一样的，因此只需要考虑猎人进1、2、3号洞的情况就可以了。

【0x01 解答】

1. 若猎人进1号洞

猎人进洞编号	狐狸所在洞的编号	狐狸下一晚所在洞的编号
1	2、3、4、5	1、2、3、4、5
-	-	-

  由于排除不了狐狸下一晚所在洞的编号，因此首先进1号洞无法确保抓到狐狸。

2. 若猎人进2号洞

时间	猎人进洞编号	狐狸所在洞的编号	狐狸下一晚所在洞的编号
第一晚	2	1、3、4、5	2、3、4、5
第二晚	3	2、4、5	1、3、4、5
第三晚	4	1、3、5	2、4
第四晚	2	4	3、5
第五晚	3	5	4
第六晚	4	抓住

  在这些原则下，也是可以调换进洞顺序的，不过不一定是最少天数：

时间	猎人进洞编号	狐狸所在洞的编号	狐狸下一晚所在洞的编号
第一晚	2	1、3、4、5	2、3、4、5
第二晚	3	2、4、5	1、3、4、5
第三晚	4	1、3、5	2、4
第四晚	4	2	1、3
第五晚	3	1	2
第六晚	2	抓住	-

时间	猎人进洞编号	狐狸所在洞的编号	狐狸下一晚所在洞的编号
第一晚	2	1、3、4、5	2、3、4、5
第二晚	4	2、3、5	1、2、3、4
第三晚	3	1、2、4	1、2、3、5
第四晚	2	1、3、5	2、4
第五晚	2	4	3、5
第六晚	3	5	4
第七晚	4	抓住	-

3. 若猎人进3号洞

  按照上面同样的分析可知

时间	猎人进洞编号	狐狸所在洞的编号	狐狸下一晚所在洞的编号
第一晚	3	1、2、4、5	1、2、3、4、5
-	-	-	-

  由于排除不了狐狸下一晚所在洞的编号，因此首先进3号洞无法抓到狐狸。

  综上所述，最少需要6天就可以确保抓住狐狸（最少一天只能猜中狐狸位置，不能确保抓住），其具体方案见前述，有多种方案可以采用。

【0x02 小结】

  事实上，本题采用了排除法，使用排除法的关键在于如何排除不合适的情况，本题一开始的三个原则就是起到排除可能性的作用，可能性越少使得问题的求解越简单，也使得不确定性减少，这是需要掌握的方法。

11. 整数和

  连续正整数之和为1000的共有几组？

【0x00 思考】

  首先答案<1000>是很容易想到的，那么要思考还有哪些连续的整数之和为1000？

  假设有连续n个整数<a, a+1, a+2, ..., a+n-1>之和为1000，即n*(n + 2*a - 1) = 2000，由于n是大于1的整数，且是2000的因子，故由2000 = 2 * 2 * 2 * 2 * 5 * 5 * 5可知n和(n + 2*a - 1) 由若干个2和若干个5的乘积构成，因此接下来可以讨论n的取值即可，并且考虑到2*a - 1是奇数，那么可以将n分偶数和奇数进行讨论。

【0x01 解答】

  由上面的分析可知有：

1. 若n是偶数，则(n + 2*a - 1) 是奇数，那么(n + 2*a - 1) 可能为5, 25, 125，因此可以解得(n, a)为(400, -197)、(80, -27)、(16, 55)，由于a要求大于0，故(n, a)为(16, 55)。

2. 若n是奇数，那么n可能为5, 25, 125，因此可以求解到(n, a)为(5, 198)、(25, 28)、(125, -54)，由于a要求大于0，则(n, a)为(5, 198)、(25, 28)。

  综上有：

1. 1000 = 1000

2. 55 + 56 + ... + 70 = 1000

3. 198 + 199 + ... +202 = 1000

4. 28 + 29 + ... + 52 = 1000

【0x02 小结】

  本题的突破口是对于n的奇偶性进行讨论，从而缩小讨论的范围以得出答案。这仍然是利用了前述的排除法，排除法的关键在于排除的条件，本题由于要求求解所有的情况，因此排除条件是至关重要的。

12. 找灯泡

  有N个灯泡，一半以上的都是好灯泡，我们可以向一个灯泡询问另一个灯泡是否是好灯泡，好灯泡都说真话，坏灯泡都说假话，只询问N-2次，如何找到一个好灯泡？

设给N个灯泡编号为1, 2, ...,N，并且用i --> j表示向灯泡i询问灯泡j是否是好灯泡，按照下面的流程便可在N-2次询问内确定一个好灯泡。在此之前，先分析一个性质：当且仅当两个灯泡是同一种灯泡时，被询问的灯泡才会回答“是”，下面举一个例子：

• 1 --> 2：向灯泡1询问灯泡2是否是好灯泡，当且仅当灯泡1和灯泡2是同一种灯泡时，灯泡1才回答“是”，若灯泡1和灯泡2不是同一种灯泡时，灯泡1将回答“否”，原因如下：
  • 若灯泡2是好灯泡
    • 若灯泡1是好灯泡，那么灯泡1回答：“是”
    • 若灯泡1是坏灯泡，那么灯泡1回答：“否”
  • 若灯泡2是坏灯泡
    • 若灯泡1是好灯泡，那么灯泡1回答：“否”
    • 若灯泡1是坏灯泡，那么灯泡1回答：“是”

有了这样的性质，下面就根据以下过程确定灯泡的好坏：

• 向灯泡i询问灯泡i+1是不是好灯泡
  • 若灯泡i回答“是”，那么就向灯泡i+1询问i+2是不是好灯泡…
  • 若灯泡i回答“否”，那么就将灯泡i和灯泡i+1丢掉
    • 若灯泡i-1未被丢掉，则向灯泡i-1询问i+2是不是好灯泡…
    • 若灯泡i-1已被丢掉或小于0，向灯泡i+2询问i+3是不是好灯泡…

因此按照下面的流程进行：1 --> 2，若灯泡1回答“是”，将灯泡1和灯泡2串起来放在一条“链”上，之后那么接着2 --> 3；若灯泡1回答“否”，那么将灯泡1和灯泡2都丢掉，依次类推…我们知道串起来形成的这条“链”上面的灯泡是同一种灯泡（同好同坏），总有一个时刻这条“链”上面的灯泡会超过剩余未被询问灯泡的一半，此时这条“链”上面的灯泡都是好灯泡；或者链上没有灯泡，只剩下一个灯泡（此时无法进行询问），此时剩下的灯泡一定是好灯泡。

注意：每当丢掉两个灯泡时，丢掉的灯泡一定是一好一坏，丢掉后还是会维持好灯泡占多数的情况，可以认为是规模减小后的原始情况。

13. 飞机

  有N架一样的飞机停靠在同一个机场，每架飞机都只有一个油箱，每箱油可使飞机绕地球飞半圈。 如果使某一架飞机平安地绕地球飞一圈，并安全地回到起飞时的机场，问：至少需要出动几架飞机？ 注：天空没有加油站，飞机之间只是可以相互加油，而且路途中间没有飞机场，每架飞机都必须安全返回起飞时的机场，不许中途降落。

14. 分水果

  老师让幼儿园的小朋友排成一行，然后开始发水果。老师分发水果的方法是这样的：从左面第一个人开始，每隔2人发一个梨；从右边第一个人开始，每隔4人发一个苹果。如果分发后的结果有10个小朋友既得到了梨，又得到了苹果，那么这个幼儿园有多少个小朋友？（写出小朋友的数目的范围）

15. 海盗分金

  5个海盗抢得100枚金币，他们按抽签的顺序依次提方案：首先由1号提出分配方案，然后5人表决，投票要超过半数同意方案才被通过，否则他将被扔入大海喂鲨鱼，依此类推。请问1号如何提出分配方案才能使得自己的利益最大化？

16. 爬山

  第一天，你从8点爬到20点，从山脚到山顶，第二天，你从8点到20点，从山顶到山脚，问会不会有中间某一刻，俩天的同一时刻在同一地点。如果有，这样的时间有多少。

17. 扔鸡蛋

  有2个鸡蛋，从100层楼上往下扔，以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎，在第10层摔碎了，那么鸡蛋不会摔碎的临界点就是9层。问：如何用最少的尝试次数，测试出鸡蛋不会摔碎的临界点？

---

1. 维基百科_赤道 ↩︎

2. 维基百科_南极点 ↩︎

3. 维基百科_北极点 ↩︎

4. CSDN_胜者树和败者树 ↩︎

5. 牛客网_面试常问智力题40道（逻辑题）+ 参考答案 ↩︎

这篇关于【考研】计算机考研复试之智力题测试的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---