智力题

巴什博弈

巴什博弈（Bash game）是一个双人博弈：有一堆总数为n的物品，2名玩家轮流从中拿取物品。每次至少拿1件，至多拿m件，不能不拿，最终将物品拿完者获胜。

结论：如果n % (m + 1) == 0那么后手必胜，否则先手必胜

三人三鬼过桥

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

参考回答

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

赛马问题

**25匹马5条跑道找最快的3匹马，需要跑几次？**参考回答：7

将25匹马分成ABCDE5组，假设每组的排名就是A1>A2>A3>A4>A5,用边相连，这里比赛5次

第6次，每组的第一名进行比赛，可以找出最快的马，这里假设A1>B1>C1>D1>E1

D1，E1肯定进不了前3，直接排除掉

第7次，B1 C1 A2 B2 A3比赛，可以找出第二，第三名

所以最少比赛需要7次

**64匹马8条跑道找最快的4匹马，需要跑几次？**参考回答：11

思路与上述类似，最后剩9匹马找出第2、3名，需要比2次

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

给定随机数，生成一个新的随机数

randN生成randK

randN()可以生成1 - N的随机数

公式：t = N * (randN() - 1) + randN()

这个可以生成$1 - N^2$的随机数，比如randN取到1，那么这个公式就是取[1, N]，取2，那么就是[N + 1, N * 2]

然后看需要生成的数是多少，那么就需要取他的倍数，超过倍数的就重新再生成，比如rand5生成rand7，那么1-25,7的倍数最大为21，如果大于21就重新调用rand7

最后在t % K + 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:
    int rand10() {
        int t = (rand7() - 1) * 7 + rand7();
        if(t > 40) return rand10();
        return t % 10 + 1;
    }
};

砝码称轻重，找出最轻的

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

9个就是333分组

8个就是332分组

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

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

空瓶换饮料

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

首先一共有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号。（这才是正解，当然前提是老鼠还没被撑死）

烧绳子问题

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

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

计算30分钟：两头烧

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

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

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

时针分针可以重合22次

时针分针秒针只能重合2次，即0点和12点的时候

100个奴隶猜帽子颜色

一百个奴隶站成一纵列，每人头上随机带上黑色或白色的帽子，各人不知道自己帽子的颜色，但是能看见自己前面所有人帽子的颜色． 然后从最后一个奴隶开始，每人只能用同一种声调和音量说一个字：”黑”或”白”， 如果说中了自己帽子的颜色，就存活，说错了就拉出去斩了，说的参考回答所有奴隶都能听见。 是否说对，其他奴隶不知道。 在这之前，所有奴隶可以聚在一起商量策略，问如果奴隶都足够聪明而且反应足够快，100个人最大存活率是多少？

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

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

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

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

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

另外，此题还有变种：每个奴隶只能看见前面一个人帽子颜色又能最多存活多少人？

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

小猴子搬香蕉

一只猴子想要把身边的香蕉搬回家。它身边有 100 根香蕉；它家在离它目前位置 50 米远的地方；它每次最多只能搬运 50 根香蕉；它在行走过程中每走 1 米就要吃掉 1 根香蕉补充能量。请问，猴子最多能搬运多少根香蕉回家？

答案：

猴子首先搬运 50 根香蕉走 1 米，然后再折返回去，再搬运剩下的 50 根香蕉继续走 1 米。这个过程相当于搬运了所有的香蕉走了 1 米，与此同时消耗了 3 根香蕉。于是，我们可以理解成：搬运 50 根以上的香蕉的话，每走 1 米需要消耗 3 根香蕉。

这时，这道题的解可以理解成：猴子先搬运所有香蕉走足够长的距离（每走 1 米消耗 3 根香蕉），当香蕉数量接近 50 根的时候，这时猴子可以带着这 50 根直接回家（因为剩下的路程小于 50 米），未被消耗的香蕉数量就是可以带回家的香蕉数量。

那么搬运所有香蕉走多少米呢？实际上，就是解这个方程：50=100-3x，解得 x=16.666。由于 x 是整数，因此取 x 等于 16 或者 17。

这时，分情况讨论。当 x=16 时，猴子走了 16 米，此时香蕉还剩 100-163=52 根，遗弃 2 根，带着 50 根香蕉走完接下来的 34 米回到家中，未被消耗的香蕉数量是 50-34=16；当 x=17 时，猴子走了 17 米，此时香蕉还剩 100-173=49 根，带着这 49 根香蕉走完接下来的 33 米回到家中，未被消耗的香蕉数量是 49-33=16。

两种情况得到的结果都是 16，因此猴子最多能搬运 16 根香蕉回到家中。

高楼扔鸡蛋

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

如果N = 1，那么就从第一层开始扔，最坏需要100次

如果N = 无穷，那么可以用二分

如果N等于2，那么比较正常的方法是两个鸡蛋A和B，A鸡蛋分别在10，20，30，40…，100的地方扔，如果A在k*10的地方碎了，那么B就从(k - 1)* 10 + 1到(k - 1)* 10 + 9的地方检查，那么最好是10次，最坏是19次

考虑到A、B两个鸡蛋检验的次数并不平衡，比如A无论丢1-10次，B都需要检验9次，那么是否可以让A检验次数变多，B检验次数变少呢？

那么可以让A在x次第一次检验，第二次在x + x -1处，第三次在x + x - 1 + x - 2，这样A多检验1次，B就少检验一次

x + x - 1 + … + 1 >= 100 那么x = 14

因此这种方法最少检测12次最多检测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%

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

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

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

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

参考回答

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

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

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

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

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

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

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）。

test