# 智力题

### &#x20;:pen\_fountain:1、 **“火柴棍式”**

下面是一个C程序，其想要输出20个减号，不过，粗心的程序员把代码写错了，你需要把下面的代码修改正确，不过，你只能增加或是修改其中的一个字符，请你给出三种答案。

```cpp
int n = 20;
for(int i = 0; i < n; i--){
    printf("-");
}
```

**答案：**

```cpp
//第一种解法：在for循环中给 i 加一个负号
for(int i = 0; -i < n; i--)
//第二种解法：在for循环中把 i-- 变成 n--
for(int i = 0; i < n; n--)
//第三种解法：把for循环中的 < 变成 +
for(int i = 0; i + n; i--)
```

通过修改或增加一个字符，让其输出21个减号（补码）

```cpp
for(int i = 0; ~i < n; i--)
```

通过修改或增加一个字符，让其不输出减号

```cpp
for(int i = 0; i << n; i--)

for(int i = 0; i < -n; i--)

for(int i = 0; i < ~n; i--)

for(int i = 0; i < !n; i--)

int n = 0;
for(int i = 20; i < n; i--)
```

### :pen\_fountain: 2、**火车运煤问题**

你是山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿区到市场有1000公里，你手里有一列烧煤的火车，这个火车最多只能装1000吨煤，且其能耗比较大——每一公里需要耗一吨煤。请问，作为一个懂编程的煤老板的你，你会怎么运送才能运最多的煤到集市？

**答案：**

1. 装1000吨煤，走250公里，扔下500吨煤，回矿山。
2. 装1000吨煤，走到250公里处，拿起250吨煤继续向前到500公里处，扔下500吨煤，回矿山。此时火车上还有250吨，再加上在250公里处还有250吨煤，所以，火车是可以回矿山的。
3. 装上最后1000吨煤，走到500公里处，装上那里的500吨煤，然后一直走到目的。

### :pen\_fountain: 3、倒水

有两个水壶，容量分别为5夸脱（美制：1夸脱=0.946升，英制：1夸脱=1.136升）和3夸脱，若水的供应不限量（但没有量杯），怎么用这两个水壶得到刚好4夸脱的水？注意，这两个水壶呈不规则形状，无法精准地装满“半壶”水。

![](https://2394460149-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MB7Io-ER4uA8ffGsDSz%2F-MEBVY026K3p8GXKmQll%2F-MEBY1OyuF9JWT03YnyN%2Fimage.png?alt=media\&token=3c158daa-0a64-4df7-bb7d-9de8c200358d)

只要这两个水壶的容量互质（即两个数没有共同的质因子），我们就能找出一种倒水的顺序组合，量出1到2个水壶容量总和（含）之间的任意水量。

### :pen\_fountain: 4、柜子状态

走廊上有100个关上的储物柜。有个人先是将100个柜子全都打开。接着，每隔一个柜子关上一个。然后，在第三轮时，再每隔两个就切换第三个柜子的开关状态（也就是将关上的柜子打开，将打开的关上）。照此规律反复操作100次，在第 i 轮，这个人会每数 i 个就切换第 i 个柜子的状态。当第100轮经过走廊时，只切换第100个柜子的开关状态，此时有几个柜子是开着的？&#x20;

**解法：**&#x8981;解决这个问题，我们必须弄清楚所谓切换储物柜开关状态是什么意思。这有助于我们推断最终哪些柜子是开着的。

1. 问题：柜子会在哪几轮切换状态（开或关）？ 柜子n会在n的每个因子（包括1和n本身）对应的那一轮切换状态。也就是说，柜子15会在第1、3、5和15轮开或关一次。（i=1开，3关，5开，15关。因子个数：偶数关，奇数开）
2. 问题：柜子什么时候还是开着的？ 如果因子个数（记作x）为奇数，则这个柜子是开着的。你可以把一对因子比作开和关，若还剩一个因子，则柜子就是开着的。&#x20;
3. 问题：x什么时候为奇数？ 若n为完全平方数，则x的值为奇数。理由如下：将n的两个互补因子配对。例如，如n为36，则因子配对情况为：(1, 36)、(2, 18)、(3, 12)、(4, 9)、(6, 6)。注意，(6, 6)其实只有一个因子，因此 n 的因子个数为奇数。&#x20;
4. 问题：有多少个完全平方数？ 一共有10个完全平方数（1、4、9、16、25、36、49、64、81、100）， 因此，最后共有10个柜子是开着的。

### :pen\_fountain: 5、疯狗问题

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

逻辑推理如下： 第一天没人杀狗，说明所有人都看到了病狗。如果某个人的狗有病，而他也观察到病狗，说明病狗至少两只。 第二天，大家都知道病狗至少两只了，但还是没有人杀狗，说明病狗的主人也看到了至少两只，所以病狗至少三只。 第三天，大家都知道病狗至少三只了，但病狗主人只看到两只，所以就判断出自家的狗是病狗，于是开枪打死。

### :pen\_fountain: 6、药丸问题

有20瓶药丸，其中19瓶装有1克/粒的药丸，余下一瓶装有1.1克/粒的药丸。给你一台称重精准的天平，怎么找出比较重的那瓶药丸？天平只能用一次。

**解答：**&#x4ECE;药瓶#1取出一粒药丸，从药瓶#2取出两粒，从药瓶#3取出三粒，依此类推。如果每粒药丸均重1克，则称得总重量为210克（1 + 2 + … + 20 = 20 \* 21 / 2 = 210），“多出来的”重量必定来自每粒多0.1克的药丸。 药瓶的编号可由算式(weight - 210 grams) / 0.1 grams得出。

### :pen\_fountain: 7、赛马问题

有25匹马，速度都不同，但每匹马的速度都是定值。现在只有5条赛道，无法计时，即每赛一场最多只能知道5匹马的相对快慢。问最少赛几场可以找出25匹马中速度最快的前3名？

**解答：**&#x37;场

64匹马，8个赛道，求最快的4匹马，答案是：大概率下是10次，小概率下11次。

### :pen\_fountain: 8、棋盘问题

有个8×8棋盘，其中对角的角落上，两个方格被切掉了。给定31块多米诺骨牌，一块骨牌恰好可以覆盖两个方格。用这31块骨牌能否盖住整个棋盘？请证明你的答案。

![在这里插入图片描述](https://img-blog.csdnimg.cn/20200130202903510.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9oYW9zeS5ibG9nLmNzZG4ubmV0,size_16,color_FFFFFF,t_70)

尝试用骨牌盖住第1行，而第1行只有7个方格，因此有一块骨牌必须铺至第2行。而用骨牌盖住第2行时，我们又必须将一块骨牌铺至第3行。要盖住每一行，总有一块骨牌必须铺至下一行。无论尝试多少次、多少种方法，我们都无法成功铺下所有骨牌。\
其实，还有更简洁更严谨的证明说明为什么不可能。棋盘原本有32个黑格和32个白格。将对角角落上的两个方格（相同颜色）切掉，棋盘只剩下30个同色的方格和32个另一种颜色的方格。为方便论证起见，我们假定棋盘上剩下30个黑格和32个白格。\
放在棋盘上的每块骨牌必定会盖住一个白格和一个黑格。因此，31块骨牌正好盖住31个白格和31个黑格。然而，这个棋盘只有30个黑格和32个白格，所以，31块骨牌盖不住整个棋盘。

### :pen\_fountain: 9、毒药和小老鼠

1000瓶药水，1瓶有毒药，几只小白鼠能够找出毒药，**1000瓶药水，1瓶有毒药，服用后一小时毒发，毒药可以无限稀释，那么一小时内用几只小白鼠能够找出毒药？**

假如是8瓶药水，3只小白鼠。

　　000=0\
　　001=1\
　　010=2\
　　011=3\
　　100=4\
　　101=5\
　　110=6\
　　111=7

每位数表示一只老鼠，0-7表示8个瓶子。即将1，3，5，7号瓶子的药混合取样给鼠1吃，2，3，6，7号瓶子混合取样给老鼠2吃……死鼠相应的位标为1。如鼠1死了，鼠2没死，鼠3死了，那么就是101=5号瓶子有毒。N只老鼠的量程为2^N，1000只瓶子位于`2^9 ~ 2^10`，即10只小鼠可以测1000瓶水。

**第二种变体：服用后一小时毒发，那么两小时内用几只小白鼠能够找出毒药？**

两个小时就可以测试两轮，且第一轮死了的小白鼠不能参与第二轮，可以用3进制

* 0表示两轮都不喝
* 1表示第一轮喝，第二轮不喝
* 2表示第一轮不喝，第二轮喝

00=0    01=1    02=2    10=3    11=4    12=5    20=6    21=7

如果鼠1第二轮死，鼠二第一轮死，就是12=5，最后推出公式为（测试次数+1）^x >= 药水瓶数     x为白鼠数量   求x的最小整数值。

**第三种变体：有16瓶水1瓶有毒，用多少只小白鼠能测出14瓶无毒的水？**

将16瓶药水用二进制XXXX表示，取3只小白鼠来测，测出的状态为XXX，那么毒在XXX0或XXX1中，剩下14瓶无毒。
