二进制问题
1、1000瓶药水找毒药（一）
问题：
有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？
解析：
二进制思想：首先一共有1000瓶药水，给每瓶药水编号：1,2,3,4,5,6...1000，2的10次方是1024，刚好大于1000， 也就是说，1000瓶药水可以使用10位二进制数来表示。
如下：
毒药在第一瓶：00 0000 0001
毒药在第二瓶：00 0000 0010
毒药在第三瓶：00 0000 0100
.......
毒药在第999瓶：11 1111 0010
毒药在第1000瓶：11 1111 0011
10只老鼠，按顺序编号，1，2，3，4，5，6，7，8，9，10分别代表从低位到高位每一个位，每只老鼠对应一个二进制位，如果该位上的数字为1，我们则给老鼠喝瓶里的药。 观察，若死亡的老鼠序号为：1，3，6，7，10号，一共死去五只老鼠，则对应的毒药编号为 10 0110 0101，转为十进制数为：613号，即613号瓶子有毒。
2、分金块问题
问题：
工人为老板打工，工作七天可以获得一块金子，工人每天可以分得一点金子，老板必须每天发金子，不能多给，也不能少给，把这个金子切两刀，就可以每天给工人发工资，请问怎么切？
解析：
切两刀将金子分成三份，1/7、2/7、4/7；
工作第一天： 把1/7分给工人；
工作第二天： 把2/7分给工人，并要回1/7那块金子，工人有2/7的金子；
工作第三天： 把1/7给工人 工人有3/7金子；
工作第四天： 把前两块金子要回，给工人4/7的金子 工人有4/7的金子；
工作第五天： 把1/7分给工人 工人有5/7的金子；
工作第六天： 把2/7分给工人，并要回1/7那块金子，工人有6/7的金子；
工作第七天： 把1/7给工人 工人有完整的金子；
先手后手问题
1、抢30游戏
问题：
抢 30 是双人游戏，游戏规则是：第一个人喊“ 1 ”或“ 2 ”，第二个人要接着往下喊一个或两个数，然后再轮到第一个人。两人轮流进行下去，最后喊 30 的人获胜，问喊数字的最佳策略。
解析：尽量喊3的倍数。
倒着看，其实，喊 27 时，就决定胜负了。假设 A 喊了 27，B只能喊 28 或 29 ，下个回合，A 一定可以喊30。也就是说，喊 27 者必胜。
再倒着看，其实喊 24 时，就定胜负了。假设 A 喊了 24 ，B 只能喊 25 或 26 ，下个回合 A 一定能喊 27 。
由于喊 27 者必胜，因此喊 24 者也必胜。
同理可以推出：喊 3 的倍数者必胜。
然后就会发现，这个游戏，谁先喊，谁一定输。
2、轮流拿书
问题：
100本书，两个人轮流拿，每次拿1~5本，你先拿，有没有啥策略可以保证你可以拿到最后一本？
解析：
如果最后一次是我拿，那么上回合最少剩下6本；
只要保持每个回合结束后都剩下6的倍数，且在这个回合中我拿的书和对方拿的书加起来为6本；
因此，第一次我必须先手拿4本(100 % 6 = 4)。
3、轮流拿石子
问题：
一共有N颗石子（或者其他乱七八糟的东西），每次最多取M颗最少取1颗，A，B轮流取，直到一方不能取为输，谁最后会获胜？（假设他们每次都取最优解）。
解析：
1、假如A先取：
- N<M，A获胜；
- N>M，
- 若N能被（M + 1）整除时，A失败；
- 若N不能被（M + 1）整除时，A获胜；
2、假如B先取，（同上）；
分析：
还是以A先手为例，N<M时A一次拿完（不可能给B留机会，前提就是每次取最优），不会给B留机会；
N>M时，A要想赢，必须要在自己倒数第二次取完的时候还剩下（M + 1）颗石子（此时A和B还可以再取一次就可以分出胜负游戏就结束了），这样不论B取几颗，A都获胜！但是要怎样才能控制最后一轮的石子数量？
分两种情况分析，
- N不能被（M + 1）整除，A先拿走n颗石子（使得剩下的石子数量是（M + 1）的整数倍），那么下一次B拿走k颗石子时，A就拿走（M + 1）- k颗石子。这样不论B怎么拿A总能控制剩下的石子数量是（M + 1）的整数倍，那么最后一轮一定剩下（M + 1）颗石子；
- N能被（M + 1）整除，无论A怎么拿，B可以控制石子数量（即当B拿完后总能使剩下的石子数量是（M + 1）的整数倍)，在最后一轮之前B拿完后还剩（M + 1）颗，A拿多少颗都是输。
4、轮流放硬币
问题：
两人轮流在一个圆桌面上放同样大小的硬币，规则是：每人每次只能放一枚，谁放完最后一枚，谁就获胜，那么是先放者胜还是后放者胜？
解析：
先放者胜。
设甲先放，乙后放，甲第一步将一枚硬币放在桌面的中心，乙可以放下一枚硬币，甲只要找到对方的硬币对称位置放，以后，只要乙放一枚硬币，甲就照此办法，最后甲必定获胜。
关键：圆心是圆的对称中心，要想获胜必须先占领圆心。
推理题
1、掰巧克力问题
问题：
一块N * M大小的巧克力，每次掰一块的一行或一列，全部掰成 1 * 1 大小的巧克力需要掰多少次？
解析：
N * M - 1次；
不管怎么掰，每次只能把一个大块掰成两个小块，即每次掰只能增加1块巧克力； 那么将1块巧克力掰成
N * M块小巧克力就需要掰N * M - 1次。
2、辩论赛问题
问题：
1000个人参加辩论赛，1对1进行辩论，淘汰输掉的一方，问需要安排多少场比赛才能角出冠军？
解析：
每场辩论赛只能淘汰一个人，要淘汰999个人则需要安排999场比赛。
3、时钟重合问题
问题：
在一天的24小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次？
解析：
24小时中时针走2圈，而分针走24圈，时针和分针重合24 - 2 = 22次， 而只要时针和分针重合，秒针一定有机会重合，所以总共重合22次。
4、蚂蚁走树枝问题
问题：
放N只蚂蚁在一条长度为M树枝上，蚂蚁与蚂蚁之间碰到就各自往反方向走，问总距离或者时间为多少？
解析：
碰到就当没发生，继续走，相当于碰到的两个蚂蚁交换了一下身体。其实就是每个蚂蚁从当前位置一直走直到停止的总距离或者时间。
最优解问题
1、鸡蛋的硬度
问题：
有2个鸡蛋，从100层楼上往下扔，以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎，在第10层摔碎了，那么鸡蛋不会摔碎的临界点就是9层。如何用最少的尝试次数，测试出鸡蛋不会摔碎的临界点？
解析：
1、暴力法
- 把其中一个鸡蛋，从第1层开始往下扔。如果在第1层没碎，换到第2层扔；如果在第2层没碎，换到第3层扔…
- 如果第59层没碎，换到第60层扔；如果第60层碎了，说明不会摔碎的临界点是第59层。在最坏情况下，这个方法需要扔100次。
2、二分法
- 采用类似于 二分查找 的方法，把鸡蛋从一半楼层（50层）往下扔。
- 如果第一枚鸡蛋，在50层碎了，第二枚鸡蛋，就从第1层开始扔，一层一层增长，一直扔到第49层。
- 如果第一枚鸡蛋在50层没碎了，则继续使用二分法，在剩余楼层的一半（75层）往下扔…
这个方法在最坏情况下，需要尝试50次。
3、均匀法
- 如何让第一枚鸡蛋和第二枚鸡蛋的尝试次数，尽可能均衡呢？
很简单，做一个平方根运算，100的平方根是10。
- 因此，我们尝试每10层扔一次：第1次从10层扔，第2次从20层扔，第3次从30层…一直扔到100层。
这样的
最好情况是在第10层碎掉，尝试次数为 1 + 9 = 10次。
最坏的情况是在第100层碎掉，尝试次数为 10 + 9 = 19次。
- 不过，这里有一个小小的优化点，我们可以从15层开始扔，接下来从25层、35层扔…一直到95层。
这样最坏情况是在第95层碎掉，尝试次数为 9 + 9 = 18次。
4、最优解法
- 可以将楼层划分成多个区间，第一个鸡蛋用来确定临界点属于哪个区间，第二个鸡蛋按顺序遍历该区间找到临界点。那么问题就转换为怎么划分区间满足最坏情况下扔鸡蛋次数最少。
- 我们可以均分楼层，不过这样显然不是最优的，最好的方法是每往下走一次，遍历的层数就减少，这样相互抵消，最终才是最优结果。具体来说，第一个鸡蛋每多遍历一次，第二个鸡蛋要少遍历一次，才使得临界点无论在哪个区间，总共遍历的次数一样。
- 假设第一个区间大小为x，那么第二个区间的大小为x - 1，以此类推。那么x + (x - 1) + (x - 2) + … + 1 = 100，得到x(x + 1) / 2 = 100，即x = 14。故第一个鸡蛋无论在哪个区间破碎，总的尝试次数都为14次。
代码实现（动态规划）
状态表示：f[i][j] 表示i层楼，j个鸡蛋检测出鸡蛋硬度(碎掉的临界楼层)需要的最少次数。
状态转移：
- 不使用第
j个鸡蛋，则f[i][j] = f[i][j - 1]； - 使用第
j个鸡蛋，则 1 ~ i 层中共i种可扔的情况，假设在第k层扔：
- 鸡蛋破碎：搜索区间变为
1 ~ k - 1，最小次数由f[k - 1][j - 1]给出； - 鸡蛋不碎：搜索区间变为
k + 1 ~ i，第j个鸡蛋可重复利用，最小次数由f[i - k][j] + 1给出；
- 我们不能控制鸡蛋的破碎，所以要假设最坏情况发送，因此取max(f[k - 1][j - 1], f[i - k][j]) + 1)。
状态转移方程：f[i][j] = min(f[i][j], max(f[k - 1][j - 1], f[i - k][j]) + 1)
初始化：f[i][1] = i，f[1][j] = 1。
C++代码
#include <iostream> using namespace std; const int N = 110, M = 12; int f[N][M]; int n, m; int main(){ cin>>n>>m; //n表示楼层的高度，m是拥有的鸡蛋个数 for(int i = 1; i <= n; i++) f[i][1] = i; for(int j = 1; j <= m; j++) f[1][j] = 1; for(int i = 2; i <= n; i++){ for(int j = 2; j <= m; j++){ f[i][j] = f[i][j-1]; for(int k = 1; k <= i; k++){ f[i][j] = min(f[i][j], max(f[k - 1][j - 1], f[i - k][j]) + 1); } } cout << f[n][m] << endl; } }
概率问题
1、生日相同概率
问题：
一个班级有50个人，请问恰好有两个人生日相同的概率？
解析：
逆向思考
我们先假设第1个人生日为随机一天；
第2个人的生日跟第1个人不同的概率是364/365；
第3个人的生日跟第1个人、第2个人不同的概率是363/365；
第4个人的生日跟第1个人、第2个人、第3个人不同的概率是363/365；
以此类推，第50个人的生日跟前面人都不同的概率为316/365；
那这个部门50个人的生日都不同的概率 = 364/365 * 363/365 *362/365……*316/365= 0.29 也就是说，这50个人生日全都不同的概率为2.9%，那么一个班级50个人当中，有生日相同的2个人的概率=1 - 2.9% = 97.1%
赛马问题
1、25匹马5条赛道找最快3匹马
问题：
25 匹马，每匹马的速度都不一样。因为只有 5 条跑道，所以一次竞赛只能跑 5 匹马，问最少需要多少次竞赛才能找到最快的 3 匹马？
解析：
分治法
- 先把 25 匹马分成 5 组，进行 5 场赛马，得到每组的排名。
- 再将每组的第 1 名选出，进行 1 场赛马，按照这场的排名将 5 组先后标为 A、B、C、D、E。可以知道，A 组的A1就是所有 25 匹马的第 1 名。
- 而第 2、3 名只可能在 A 组的 A2、A3 ，B 组的 B2、B3 ，和 C 组的C1，总共 5 匹马，让这 5 匹马再进行 1 场赛马，前两名就是第 2、3 名。所以总共是 5+1+1=7 场赛马。
2、64匹马8条赛道找最快4匹马
问题：
64匹马，8条赛道，问最少比赛多少场，可以选出跑得最快的4匹马？
解析：
分治法
- 将全部马分为8组，每组8匹，每组各跑一次，然后淘汰掉每组的后四名（需要比赛8场）；
- 取每组第一名进行一次比赛，然后淘汰最后四名所在组的所有马（E1为左上角，H4为右下角），如下图（需要比赛1场）这个时候总冠军已经诞生，它就是A1；
而其他可能跑得最快的三匹马只可能是下图中的黄域了（A2,A3,A4,B1,B2,B3,C1,C2,D1，共9匹马）
- 只要从上面的9匹马中挑选出跑得最快的三匹马就可以了，但是现在只有8条跑道，如何做？
随机选出8匹马进行一次比赛（需要比赛1场） - 经过上面比赛，选出了前三名，但是9匹马中还有一匹马没跑，它可能是一个潜力股，我们让其和前三名比赛一下，选出前三名。最后加上总冠军，就选出了跑得最快的4匹马（需要1场比赛）
- 最后，一共需要比赛的场次：8 + 1 + 1 + 1 = 11 场
水桶问题
1、取4L的水
问题：
水资源无限，3L和5L水桶各一个，怎样取4L的水？
解析：
步骤如下：
- 5L桶加满水；
- 5L桶倒满3L杯，还剩2L；
- 3L桶倒掉；
- 5L桶里剩下的2L倒到3L杯里；
- 5L桶加满水；
- 3L桶里现有2L，5L桶倒满3L杯，则剩4L；
如图所示：
2、取3L的水
问题
水资源无限，5L和6L水桶各一个，怎样取3L的水？
解析：
步骤如下：
- 6L桶装满水倒入5L水桶，余下1L水；
- 5L桶倒空，将6L桶中剩余的1L水倒入5L桶；
- 6L水桶再次装满水倒入5L水桶，余下2L水；
- 5L水桶倒空， 将6L水桶中剩余2L水倒入5L水桶；
- 6L水桶再次装满水倒入5L水桶，余下3L水；
如图所示：
3、取2个5L的水
问题
一个装了10L水的桶，一个7L的空桶，一个3L的空桶，怎样变成2个5L？
解析：
步骤如下：
110L桶倒入3L空桶，余下7L水；
23L桶全部倒入7L桶，成为空桶；
310L桶倒入3L水给3L桶，余下4L水；
43L桶全部倒入7L桶，成为空桶；
510L桶倒入3L水给3L桶，余下1L水；
63L桶倒入1L水给7L桶，余下2L水；
77L桶全部倒入10L桶，成为空桶；
83L桶全部到入7L桶，成为空桶；
910L桶倒入3L水给3L桶，余下5L水；
103L桶全部到入7L桶，成为空桶；
如图所示：
