我的校招记录：校招笔记（零）_写在前面 ，以下是校招笔记总目录。

备注
算法能力（“刷题”） 这部分就是耗时间多练习，Leetcode-Top100 是很好的选择。 补充练习：codeTop
计算机基础(上)（“八股”） 校招笔记（一）__Java_Java入门 C++后端后续更新
校招笔记（一）__Java_面对对象
校招笔记（一）__Java_集合
校招笔记（一）__Java_多线程
校招笔记（一）__Java_锁
校招笔记（一）__Java_JVM
计算机基础(下)（“八股”） 校招笔记（二）__计算机基础_Linux&Git
校招笔记（三）__计算机基础_计算机网络
校招笔记（四）__计算机基础_操作系统
校招笔记（五）__计算机基础_MySQL
校招笔记（六）__计算机基础_Redis
校招笔记（七）__计算机基础_数据结构
校招笔记（八）__计算机基础_场景&智力题
校招笔记（九）__计算机基础_相关补充
项目&实习 主要是怎么准备项目，后续更新

八、场景题&智力题

8.1 场景题

1. 设计一个微信运动排行榜？（Redis）

  • 被CSIG伤过的的心还可以爱谁（第一次回答）

    “可以使用mysql, 将用户的好友列表关联的运动记录查询出来，然后通过order by 来进行排序，就可以实现了。”

    一旦数据量大达到千万级别的时候，不可避免地会出现慢查询，效率就会降低。所以这不是面试官想听到的回答！

  • Redis–高效

    使用Redis的有序集合 zset（有序且不重复） 。因为 zset 排序的下标从0 开始，自带一个score 值，该值可以当作排行的标准 。

    • 添加用户和步数： zadd key score member
    • 查询指定排名范围内用户： （从小到大）zrange key start stop withscores or （从大到小）zrevrange key start stop withscores

    根据上面，所以用户按score从小到大排序完毕了，如果还要获取排名也可以使用下面命令：

    • 查询指定用户排名 ： zrank key member or zrevrank key member

    一个简单的排行榜就设计完成了。

    如果面试官进一步问：一周排行榜怎么设计？

    一周的数据其实就是7天数据的累加，累加完后再排序，一个月的数据原理也是一样。可以使用 ：

    • ZINTERSTORE ： 计算给定一个或多个有序集的交集并将结果放到一个新的有序集合destination中。

      1
      ZINTERSTORE destination numkeys key [key ...] [WEIGHTS weight [weight ...]] [AGGREGATE SUM|MIN|MAX]

      默认情况使用的函数是求和。

    所以可以使用：

    1
    zunionstore last_seven_days 7 20210315  20210316 20210317 20210318 20210319 20210320 20210321

2. 海量数据问题

参考：https://blog.csdn.net/v_JULY_v/article/details/6279498

在海量数据中，针对top K类问题，通常比较好的方案是：

  • Top数问题：小根堆

    有1亿个浮点数，如何找出其最大的10000个？

    直接进行排序，大约需要10^8*4字节 = 400M ，如果内存够可以直接进行排序；如果内存不够采用：

    1. 最小堆法 ：（1）先读入10000个数来创建大小为10000的最小堆（假设这10000个数是最大的10000个，然后每次和这10000中最小的比较）（2）遍历后续数字，和堆顶最小数字比较：如果小于堆顶数字，继续；如果大于堆顶数字，则替换堆顶并重新调整为最小堆（3）整个过程直至1亿个数全部遍历完为止
    2. 分治法。 （1）1亿分为100份，每份100万个数据，找到每份的最大的1万个 （2）在剩下的100*1万个数据找到最大的1万个
    3. 哈希法。 如果这1亿个书里面有很多重复的数，先通过Hash法，把这1亿个数字去重复。 然后再采用方法 1 或 2 。

  • 最多重复（频率最高）：Hash映射+HashMap频率计算

    【最多重复】海量日志数据，提取出某日访问百度次数最多的那个IP。

    • 分治法（基于Hash）。 （1）按照IP地址的Hash(IP)%1024值，把海量IP日志分别存储到1024个小文件中 （2）对于每一个小文件，可以构建一个IP为key，出现次数为value的Hash map （3）可以得到1024个小文件中的出现次数最多的IP ，再根据常规排序得到。

    ⚠️ 使用Hash分散ip可以保证相同ip都在同一个文件夹，如果只是简单均分是不行的。

    【最多重复】有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。

    • 同上，分治法（基于Hash）。 首先计算下：1G / 1M = 1000个小文件，为保险分为2000个（1）Hash(词)%2000 映射到2000个文件中（2）分别计算2000个文件频率最高的那个单词，然后常规排序即可（2000个单词占：2k*16B=32KB<<1M）

    【最多重复】有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。

    • 同上，分治法（基于Hash）。 顺序读取10个文件，然后将query重新映射到若干个文件中，保证相同query都在同一个文件。其余同上。

  • 不重复数：位图

    【不重复】 在2.5亿个整数中找出不重复的整数。注，内存不足以容纳这2.5亿个整数。

    • 采用2位图（BitMap）。00表示不存在，01表示出现一次，10表示多次，11无意义，需要2.5∗108b=2.5∗0.1Gb=0.25Gb=25MB2.5*10^8b = 2.5*0.1Gb=0.25Gb=25MB。但是我们需要把所有的整数都表示出来2∗232bit=1GB2*2^{32}bit=1GB（1）扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变（2）查看bitmap，把对应位是01 的整数输出即可。

      注，int类型占32个字节，2322^{32} 表示其能表示的整数个数。

    【不重复·腾讯】给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

    • 采用2位图（BitMap）。 需要40亿bit，大约500M，但实际是要表示所有整数，故还是1GB。其余同上。

  • 共同数

    【相同数】 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？

    • 分治法（基于Hash）。 （1）分别将a，b两个大文件各自映射为10000个小文件，这样相同url会映射到a,b相同哈希值小文件中。（2）在a,b每一对小文件找到相同的url。

3. 分布式相关

谈一谈，分布式集群中如何保证线程安全？

  • 对于单一服务来说，只要保证一台机器上的对于共享资源的访问是同步进行的就能保证线程安全了；但是对于分布式系统而已，保证一台服务器的同步，并不能保证访问共享资源是同步的；

  • 所以可以考虑使用分布式锁的方式来保证分布式中的线程的安全线，这样不同的服务不同的线程通过竞争分布式锁来获取共享资源的操作权限；

  • 例如redis的分布式锁、zookeeper锁，都可以作为分布式线程安全的手段。

在淘宝购物，这个场景下，你会怎样来设计消息队列？

  • 什么是消息队列？

    消息队列（MQ）可以简单理解为：把要传输的数据放在队列中，一种先进先出的结构。

  • 怎么去设计淘宝消息队列？

    待补充。

4. 微信抢红包

例如一个人在群里发了100块钱的红包，群里有10个人一起来抢红包，每人抢到的金额随机分配。

  1. 所有人抢到的金额之和要等于红包金额，不能多也不能少。

  2. 每个人至少抢到1分钱。

  3. 要保证红包拆分的金额尽可能分布均衡，不要出现两极分化太严重的情况。

二倍均值法：假设剩余红包金额为m元，剩余人数为n，那么有如下公式：

  • 每次抢到的金额 = [0.01，m /n × 2 - 0.01]

  • 这个公式，保证了每次随机金额的平均值是相等的，不会因为抢红包的先后顺序而造成不公平。

举例说明：

  • 假设有5个人，红包总额100元。100÷5×2 = 40，所以第1个人抢到的金额随机范围是[0.01，39.99]元，在正常情况下，平均可以抢到20元。假设第1个人随机抢到了20元，那么剩余金额是80元。80÷4×2 = 40，所以第2个人抢到的金额的随机范围同样是[0.01，39.99]元，在正常的情况下，还是平均可以抢到20元。假设第2个人随机抢到了20元，那么剩余金额是60元。60÷3×2 = 40，所以第3个人抢到的金额的随机范围同样是[0.01，39.99]元，平均可以抢到20元。以此类推，每一次抢到金额随机范围的均值是相等的。

8.2 智力题

1. 厉害了我的杯

有一种玻璃杯质量确定但未知，需要检测。 有一栋100层的大楼，该种玻璃杯从某一层楼扔下，刚好会碎。 现给你两个杯子，问怎样检测出这个杯子的质量，即找到在哪一层楼刚好会碎？

参考：https://cloud.tencent.com/developer/article/1497944

2. 赛马问题

64匹马，8个跑道，问最少比赛多少场，可以选出跑得最快的4匹马。

  • Assumptions：每场比赛每个跑道只允许一匹马，且不存在并列情形。

3. 三人三鬼过桥

有三个人跟三个鬼要过河,河上没桥只有条小船,然后船一次只能渡一个人和一个鬼,或者两个鬼或者两个人,无论在哪边岸上,只有是人比鬼少的情况下(如两鬼一人,三鬼两人,三鬼一人)人会被鬼吃,然而船又一定需要人或鬼操作才能航行(要有人或鬼划船),问,如何安全的把三人三鬼渡过河对岸?

参考回答

  • 先两鬼过去。在一鬼回来。对面有一鬼。这边有三人两鬼。
  • 再两鬼过去。在一鬼回来。对面有两鬼。这边有三人一鬼。
  • 再两人过去。一人一鬼回来。对面一人一鬼。这边两人两鬼。
  • 最后两人过去。一鬼回来。对面三人。这边三鬼。
  • 剩下的就三个鬼二个过去一个回来在接另外个就OK了。

3. 给定随机函数，生成别的随机数

给定生成1到5的随机数Rand5()，如何得到生成1到7的随机数函数Rand7()？

由大的生成小的容易，比如由Rand7()生成Rand5()，所以我们先构造一个大于7的随机数生成函数。 记住下面这个式子：

1
2
3
4
// 生成1到N^2之间的随机数,可以看作是在数轴上撒豆子。N是跨度/步长，是RandN()生成的数的范围长度
// RandN()-1的目的是生成0到N-1的数，是跳数。后面+RandN()的目的是填满中间的空隙Copy to clipboardErrorCopied

RandNN= N( RandN()-1 ) + RandN() ;

比如Rand25= 5( Rand5()-1 ) + Rand5()可以生成1到25之间的随机数。我们可以只要1到21（3*7）之间的数字，所以可以这么写

1
2
3
4
5
6
7
int rand7(){
  int x=INT_MAX;
  while(x>21){
    x=5*(rand5()-1)+rand5();
  }
  return x%7+1;
}Copy to clipboardErrorCopied

4. 砝码称轻重，找出最轻的

其实这都是一类题，这里列举几个经典的：

1、有一个天平，九个砝码，其中一个砝码比另八个要轻一些，问至少要用天平称几次才能将轻的那个找出来？

参考回答：至少2次。第一次，一边3个，哪边轻就在哪边，一样重就是剩余的3个； 第二次，一边1个，哪边轻就是哪个，一样重就是剩余的那个；至少称2次．

2、十组砝码每组十个，每个砝码都是10g重，但是现在其中有一组砝码每个都只有9g重，现有一个能显示克数的秤，最少称几次能找到轻的那组？

参考回答：至少1次。

将砝码分组1~10，第一组拿一个，第二组拿两个以此类推。。第十组拿十个放到秤上称出克数x，则y = 550 - x，第y组就是轻的那组。

5. 利用空瓶换饮料，最多喝几瓶

1000瓶饮料，3个空瓶子能够换1瓶饮料，问最多能喝几瓶？

第一种思路

拿走3瓶，换回1瓶，相当于减少2瓶。

但是最后剩下4瓶的时候例外，这时只能换1瓶。所以我们计算1000减2能减多少次，直到剩下4.（1000-4=996，996/2=498）所以1000减2能减498次直到剩下4瓶，最后剩下的4瓶还可以换一瓶，所以总共是1000+498+1=1499瓶。

第二种思路

  • 1000瓶饮料，3个空瓶子能换1瓶饮料，最多可以喝几瓶？

  • 第一种思维：可以考虑成dp思路

    • 初始情况，3个瓶子时将发生一次交换，因此视为特殊情况

    • 之后每增加两个瓶子又可以再换一瓶

    • 即dp[i] = dp[i - 2] + (i - (i - 2)) + 1

      • 由dp[i - 2]可求得dp[i]
      • (i - (i - 2))，即为当前增加的2瓶饮料（写成这样便于理解）
      • 1即为增加了2个空瓶，之后又可以换一瓶饮料

    • 简化为dp[i] = dp[i - 2] + 2 + 1

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      public int method(int n) {
          // n为0/1/2的特殊情况省略了
          // 定义dp数组
          int[] dp = new int[n + 1];
          // 初始状态
          dp[0] = 0;
          dp[1] = 1;
          dp[2] = 2;
          for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 2] + 2 + 1;
         }
          return dp[n];
       }Copy to clipboardErrorCopied

  • 回归正题

    • 特殊情况：从上面的分析中，留下2个瓶子
    • 剩下998个瓶子相当于每消耗2个瓶子即可获得一瓶，即为499瓶
    • 最后剩下的2个瓶子无法再进行兑换，因此总共为1000 + 499 = 1499

  • 第二种思维

    • 因为兑换一瓶饮料需要三个空瓶，这瓶饮料如果是找老板借来的，那么喝完后这个空瓶将会还给他，同时需要附赠给他另外两个空瓶，即每消耗手里两个空瓶就获得一瓶饮料
    • 但是值得注意的是，上面只是一种假设，实际情况老板是不会借给你的，因此我们至少需要保留2个空瓶，这样可以在998个瓶子剩下一个瓶子时，对其进行补足为3个空瓶，从而兑换一瓶新饮料
    • 此时使用998个瓶子进行上述的兑换，将获得499瓶饮料
    • 之前留下的两个瓶子正好无法兑换，最终获得饮料为1000 + 499 = 1499瓶

6. 毒药毒白鼠，找出哪个瓶子中是毒药

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

参考回答

  1. 将10只老鼠剁成馅儿，分到1000个瓶盖中，每个瓶盖倒入适量相应瓶子的液体，置于户外，并每天补充适量相应的液体，观察一周，看哪个瓶盖中的肉馅没有腐烂或生蛆。（你要是胆子够大就可以这么回答，是个狼人）

  2. 首先一共有1000瓶，2的10次方是1024，刚好大于1000，也就是说，1000瓶药品可以使用10位二进制数就可以表示。从第一个开始：

    第一瓶 ： 00 0000 0001

    第二瓶： 00 0000 0010

    第三瓶： 00 0000 0011

    ……

    第999瓶： 11 1111 0010

    第1000瓶： 11 1111 0011

    需要十只老鼠，如果按顺序编号，ABCDEFGHIJ分别代表从低位到高位每一个位。 每只老鼠对应一个二进制位，如果该位上的数字为1，则给老鼠喝瓶里的药。

    观察，若死亡的老鼠编号为：ACFGJ，一共死去五只老鼠，则对应的编号为 10 0110 0101，则有毒的药品为该编号的药品，转为十进制数为：613号。（这才是正解，当然前提是老鼠还没被撑死）

类似问题：8瓶酒一瓶有毒，用小老鼠测试。每次测试结果8小时后才会得出，而你只有8个小时的时间。最少需要（ ）老鼠测试？

  • A 、2 B、3 C、4 D、6

解析：用3位2进制代表8瓶酒，如下表所示

瓶序号 二进制 中毒情况

第一瓶 000 全没中毒

第二瓶 001 只有第一个老鼠中毒

第三瓶 010 只有第二个老鼠中毒

第四瓶 011 第一个老鼠、第三个老鼠同时中毒

第五瓶 100 只有第三个老鼠中毒

第六瓶 101 第一个老鼠、第三个老鼠同时中毒

第七瓶 110 第二个老鼠、第三个老鼠同时中毒

第八瓶 111 三个老鼠同时中毒

其中，第一个老鼠喝下最低位为1对应的酒，第二个老鼠喝下中间位为1对应的酒，第三个老鼠喝下最高位为1对应的酒。

最后将所有中毒的老鼠，对应的位次进行与操作即可以知道那瓶毒药有毒了。

7. 利用烧绳子计算时间

现有若干不均匀的绳子，烧完这根绳子需要一个小时，问如何准确计时15分钟，30分钟，45分钟，75分钟。。。

  • 计算15分钟：对折之后两头烧(要求对折之后绑的够紧，否则看45分钟解法)

  • 计算30分钟：两头烧

  • 计算45分钟：两根，一根两头烧一根一头烧，两头烧完过了30分钟，立即将第二根另一头点燃，到烧完又过15分钟，加起来45分钟

  • 计算75分钟：将30和45分钟的方式加起来就可以了

其余类似

8. 在24小时里面时针分针秒针可以重合几次

24小时中时针走2圈，而分针走24圈，时针和分针重合24-2=22次，而只要时针和分针重合，秒针一定有机会重合，所以总共重合22次。

9. 100个奴隶猜帽子颜色

一百个奴隶站成一纵列，每人头上随机带上黑色或白色的帽子，各人不知道自己帽子的颜色，但是能看见自己前面所有人帽子的颜色． 然后从最后一个奴隶开始，每人只能用同一种声调和音量说一个字：”黑”或”白”， 如果说中了自己帽子的颜色，就存活，说错了就拉出去斩了，说的参考回答所有奴隶都能听见。 是否说对，其他奴隶不知道。

在这之前，所有奴隶可以聚在一起商量策略，问如果奴隶都足够聪明而且反应足够快，100个人最大存活率是多少？

参考回答：这是一道经典推理题

  1. 最后一个人如果看到奇数顶黑帽子报“黑”否则报“白”，他可能死

  2. 其他人记住这个值（实际是黑帽奇偶数），在此之后当再听到黑时，黑帽数量减一

  3. 从倒数第二人开始，就有两个信息：记住的值与看到的值，相同报“白”，不同报“黑”

99人能100%存活，1人50%能活

变种：每个奴隶只能看见前面一个人帽子颜色又能最多存活多少人？

增加限制条件后，上面的方法就失效了，此时只能约定偶数位奴隶说他前一个人的帽子颜色，奇数奴隶获取信息100%存活，偶数奴隶50几率存活。

10. 小猴子搬香蕉

一个小猴子边上有100根香蕉，它要走过50米才能到家，每次它最多搬50根香蕉，（多了就被压死了），它每走 1米就要吃掉一根，请问它最多能把多少根香蕉搬到家里？

（提示：他可以把香蕉放下往返的走，但是必须保证它每走一米都能有香蕉吃。也可以走到n米时，放下一些香蕉，拿着n根香蕉走回去重新搬50根。）

这种试题通常有一个迷惑点，让人看不懂题目的意图。此题迷惑点在于：走一米吃一根香蕉，一共走50米，那不是把50根香蕉吃完了吗？如果要回去搬另外50根香蕉，则往回走的时候也要吃香蕉，这样每走一米需要吃掉三根香蕉，走50米岂不是需要150根香蕉？

其实不然，本题关键点在于：猴子搬箱子的过程其实分为两个阶段，第一阶段：来回搬，当香蕉数目大于50根时，猴子每搬一米需要吃掉三根香蕉。第二阶段：香蕉数<=50，直接搬回去。每走一米吃掉1根。

  1. 第一阶段：假如把100根香蕉分为两箱，一箱50根

    第一步，把A箱搬一米，吃一根。

    第二步，往回走一米，吃一根。

    第三步，把B箱搬一米，吃一根。

    这样，把所有香蕉搬走一米需要吃掉三根香蕉。这样走到第几米的时候，香蕉数刚好小于50呢？

    100−(n∗3)<50&&100−(n−1∗3)>50100-(n*3)<50 \&\& 100-(n-1*3)>50

    走到16米的时候，吃掉48根香蕉，剩52根香蕉。这步很有意思，它可以直接搬50往前走，也可以再来回搬一次，但结果都是一样的。

    到17米的时候，猴子还有49根香蕉。这时猴子就轻松啦，直接背着走就行。

  2. 第二阶段：走一米吃一根

    把剩下的50-17=33米走完。还剩49-33=16根香蕉。

11. N只蚂蚁走树枝，问总距离或者总时间

问题：放N只蚂蚁在一条长度为M树枝上，蚂蚁与蚂蚁之间碰到就各自往反方向走，问总距离或者时间为多少？

这个其实就一个诀窍：蚂蚁相碰就往反方向走，可以直接看做没有发生任何事：大家都相当于独立的

A蚂蚁与B蚂蚁相碰后你可以看做没有发生这次碰撞，这样无论是求时间还是距离都很简单了。

12. N个强盗分配M个金币，求方案使得自己分配最多

5个海盗抢到了100枚金币，每一颗都一样的大小和价值。 他们决定这么分：

  1. 抽签决定自己的号码（1，2，3，4，5）

  2. 首先，由1号提出分配方案，然后大家5人进行表决，当 半数以上的人同意时（ 不包括半数，这是重点），按照他的提案进行分配，否则将被扔入大海喂鲨鱼。

  3. 如果1号死后，再由2号提出分配方案，然后大家4人进行表决，当且仅当半超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。

  4. 依次类推…

假设每一位海盗都足够聪明，并且利益至上，能多分一枚金币绝不少分，那么1号海盗该怎么分金币才能使自己分到最多的金币呢？

从后向前推，如果1至3号强盗都喂了鲨鱼，只剩4号和5号的话，5号一定投反对票让4号喂鲨鱼，以独吞全部金币。所以，4号惟有支持3号才能保命。

  • 3号知道这一点，就会提出“100，0，0”的分配方案，对4号、5号一毛不拔而将全部金币归为已有，因为他知道4号一无所获但还是会投赞成票，再加上自己一票，他的方案即可通过。

  • 不过，2号推知3号的方案，就会提出“98，0，1，1”的方案，即放弃3号，而给予4号和5号各一枚金币。由于该方案对于4号和5号来说比在3号分配时更为有利，他们将支持他而不希望他出局而由3号来分配。这样，2号将拿走98枚金币。

  • 同样，2号的方案也会被1号所洞悉，1号并将提出（97，0，1，2，0）或（97，0，1，0，2）的方案，即放弃2号，而给3号一枚金币，同时给4号（或5号）2枚金币。由于1号的这一方案对于3号和4号（或5号）来说，相比2号分配时更优，他们将投1号的赞成票，再加上1号自己的票，1号的方案可获通过，97枚金币可轻松落入囊中。这无疑是1号能够获取最大收益的方案了！

1号强盗分给3号1枚金币，分给4号或5号强盗2枚，自己独得97枚。分配方案可写成（97，0，1，2，0）或（97，0，1，0，2）。

变种：就是只需要一半人同意即可，不需要一半人以上同意方案就可以通过，在其他条件不变的情况下，1号该怎么分配才能获得最多的金币？

  • 4号：4号提出的方案的时候肯定是最终方案，因为不管5号同意不同意都能通过，所以4号5号不必担心自己被投入大海。那此时5号获得的金币为0，4号获得的金币为100。

  • 5号：因为4号提方案的时候 ，自己获取的金币为0 。所以只要4号之前的人分配给自己的金币大于0就同意该方案。

  • 4号：如果3号提的方案一定能获得通过（原因：3号给5号的金币大于0， 5号就同意 因此就能通过），那自己获得的金币就为0，所以只要2号让自己获得的金币大于0就会同意。

  • 3号：因为到了自己提方案的时候可以给5号一金币，自己的方案就能通过，但考虑到2号提方案的时候给4号一个金币，2号的方案就会通过，那自己获得的金币就为0。所以只要1号让自己获得的金币大于0就会同意。

  • 2号：因为到了自己提方案的时候只要给4号一金币，就能获得通过，根本就不用顾及3 号 5号同意不同意，所以不管1号怎么提都不会同意。

  • 1号：2号肯定不会同意。但只要给3号一块金币，5号一块金币（因为5号如果不同意，那么4号分配的时候，他什么都拿不到）就能获得通过。

所以参考回答是： 98，0，1，0，1。

14. 火枪手决斗，谁活下来的概率大？

问题：彼此痛恨的甲、乙、丙三个枪手准备决斗。甲枪法最好，十发八中；乙枪法次之，十发六中；丙枪法最差，十发四中。如果三人同时开枪，并且每人每轮只发一枪；那么枪战后，谁活下来的机会大一些？

一般人认为甲的枪法好，活下来的可能性大一些。但合乎推理的结论是，枪法最糟糕的丙活下来的几率最大。

那么我们先来分析一下各个枪手的策略。

如同田忌赛马一般，枪手甲一定要对枪手乙先。因为乙对甲的威胁要比丙对甲的威胁更大，甲应该首先干掉乙，这是甲的最佳策略。

同样的道理，枪手乙的最佳策略是第一枪瞄准甲。乙一旦将甲干掉，乙和丙进行对决，乙胜算的概率自然大很多。

枪手丙的最佳策略也是先对甲。乙的枪法毕竟比甲差一些，丙先把甲干掉再与乙进行对决，丙的存活概率还是要高一些。

我们根据分析来计算一下三个枪手在上述情况下的存活几率： 第一轮：甲射乙，乙射甲，丙射甲。

  • 甲的活率为24%（40% X 60%）

  • 乙的活率为20%(100% - 80%)

  • 丙的活率为100%（无人射丙）

由于丙100％存活率，因此根据上轮甲乙存活的情况来计算三人第二轮的存活几率：

  • 情况1：甲活乙死（24% X 80% = 19.2%） 甲射丙，丙射甲：甲的活率为60%，丙的活率为20%。
  • 情况2：乙活甲死（20% X 76% = 15.2%） 乙射丙，丙射乙：乙的活率为60%，丙的活率为40%。
  • 情况3：甲乙同活（24% X 20% = 4.8%） 重复第一轮。 情况4：甲乙同死（76% X 80% = 60.8%） 枪战结束。

据此来计算三人活率：

  • 甲的活率为(19.2% X 60%) + (4.8% X 24%) = 12.672%
  • 乙的活率为(15.2% X 60%) + (4.8% X 20%) = 10.08%
  • 丙的活率为(19.2% X 20%) + (15.2% X 40%) + (4.8% X 100%) + (60.8% X 100%) = 75.52%

通过对两轮枪战的详细概率计算，我们发现枪法最差的丙存活的几率最大，枪法较好的甲和乙的存活几率却远低于丙的存活几率。

15. 先手必胜的问题

100本书，每次能够拿1-5本，怎么拿能保证最后一次是你拿？

寻找每个回合固定的拿取模式，最后一次是我拿，那么上个回合最少剩下6本。那么只要保持每个回合结束后都剩下6的倍数，并且在这个回合中我拿的和对方拿的加起来为6（这样这个回合结束后剩下的还是6的倍数），就必胜。

关键是第一次我必须先手拿（100%6=4）本（这不算在第一回合里面）。

16. 掰巧克力问题或者参加辩论赛

1、掰巧克力问题 NM块巧克力，每次掰一块的一行或一列，掰成11的巧克力需要多少次？

2、1000个人参加辩论赛，1V1，输了就退出，需要安排多少场比赛？

每次拿起一块巧克力，掰一下（无论横着还是竖着）都会变成两块，因为所有的巧克力共有NM块，所以要掰NM-1次，-1是因为最开始的一块是不用算进去的。

每一场辩论赛参加两个人，消失一个人，所以可以看作是每一场辩论赛减少一个人，直到最后剩下1个人，所以是1000-1=999场。