1、 台阶问题
题目：一个人上台阶可以一次上一个或两个，问这个人上n层的台阶，一共有多少种走法。
本题可以采用递归的方法来设计模型，先从数字的规律入手：假设共有i阶台阶，走完所有的台阶有n种走法，则存在如表6- 3所示。
表6- 3组合情况
| i | n | 组合情况 |
| 1 | 1 | {1} |
| 2 | 2 | {1, 1}{2} |
| 3 | 3 | {1, 1, 1}{1, 2}
{2, 1} |
|
4
|
5
|
{1, 1, 1, 1}{1, 1, 2}
{1, 2, 1} {2, 1, 1} {2, 2} |
| … | … | … |
| n-2 | F(n-2) | |
| n-1 | F(n-1) | |
| n | F(n)= F(n-1)+ F(n-2) |
根据递推可以知道，F(n)= F(n-1)+ F(n-2)。此式很熟悉，为常见的Fibonacci数列，此处不再赘述其求解算法。
2、 电线线头问题
题目：在一幢100层大楼下，有21根电线线头分别标有数字1到21。这些电线一直延伸到大楼楼顶，楼顶的线头处标有字母A到U，一共21个字母。此时不知道下面的数字和上面的字母的对应关系，有一个电池，一个灯泡，和许多很短的电线，如何只上下楼一次就能确定电线线头的对应关系？
在下面把2，3连在一起，把4到6全连在一起，把7到10全连在一起，等等，这样就把电线分成了6个“等价类”，大小分别为1，2，3，4，5，6。然后爬到楼顶，测出哪根线和其它所有电线都不相连，哪些线和另外一根相连，哪些线和另外两根相连等等，从而确定出字母A到U各属于哪个等价类。
然后把每个等价类中的第一个字母连在一起，形成一个大小为6的新等价类；再把后5个等价类中的第二个字母连在一起，形成一个大小为5的新等价类；以此类推。再回到楼下，把新的等价类区别出来。此时就知道了每个数字对应了哪一个原等价类的第几个字母，从而解决问题。
3、 蚂蚁相撞问题
题目：在一个等边三角形的三个顶点上各有一只蚂蚁，它们向另一个顶点运动，目标随机（可能为另外两个顶点的任意一个）。问三只蚂蚁不相撞的概率是多少？
1/4。
先取三只蚂蚁中任意一只做研究，它的行动路线可以向另外两个顶点的任意一个移动，然后取第二只蚂蚁，为了要使三只蚂蚁互不相撞，它必须不能与第一只蚂蚁相向而行，所以只有1种行动路线，而它总共有两条线路可供选择，所以它们互不相撞的可能性是1/2。最后取第三只蚂蚁，前面两只蚂蚁的路线都确定好以后，它只能从可选的两条路里面走唯一一条使它们互不相撞的路线，也就是3个蚂蚁做相同方向的绕圈运动，而第三只蚂蚁为了它们互不相撞，选择路线的可能性也是1/2。所以三只蚂蚁不相撞的概率是1/2*1/2=1/4。
还可以换一种思维来进行，以二进制中的0和1来表示蚂蚁的爬行方向，蚂蚁顺时针爬行记为0，逆时针爬行记为1，那么三只蚂蚁的状态可能为000，001，……，110，111 中的任意一个，而且每种状态的概率相等，而在这8种状态中，只有000和111表示可以避免相撞，所以蚂蚁不相撞的概率为1/4。
4、 小老鼠与毒酒问题
题目：有1000桶酒，其中只有1桶有毒，而一旦喝了有毒的酒，毒性就会在1周后发作，现在用小老鼠做实验，要在1周内找出那桶毒酒，问最少需要多少只小老鼠。
10只。因为2的10次方等于1024，所以10只小老鼠最多可以测1024桶酒。
先假设有1024个瓶子，其中只有1瓶毒药。
（1） 将1024个瓶子分成两个512，即512a和512b。从512a的各瓶中，各取1滴水，给1号小老鼠吃。
（2） 将两个512分别分成两个256，即，512a分成了256a、256b，并且512b也分成了256a、256b。从两个256a中，照旧每瓶取一滴，给2号小老鼠吃。
（3） 同样的道理，依次分为4个128a、128b，将a各取一滴，给3号小老鼠吃。
（4） 8个64a、64b，将a各取一滴，给4号小老鼠吃。
（5） 16个32a、32b，将a各取一滴，给5号小老鼠吃。
（6） 32个16a、16b，将a各取一滴，给6号小老鼠吃。
（7） 64个8a、8b，将a各取一滴，给7号小老鼠吃。
（8） 128个4a、4b，将a各取一滴，给8号小老鼠吃。
（9） 256个2a、2b，将a各取一滴，给9号小老鼠吃。
（10） 512个1a、1b，将a各取一滴，给10号小老鼠吃。
然后，经过一周的等待，则可以得出如下结论：
（1） 如果1号小老鼠死，则毒药在512a中；否则，在512b中。
（2） 如果2号小老鼠死，则在256a中；否则，在256b中；同时，根据1的结果，可判定这个256来自512a还是512b。
以此类推，可以唯一地确定这个“1”来自哪里，也就确定了它是第几瓶。
除了以上这种方法外，还可以采用另外一种方法，就是二进制表示的方法，首先，将酒编号为1~1000号，然后将十只小老鼠分别编号为1、2、4、8、16、32、64、128、256、512。
给小老鼠喂酒时，让酒的编号等于小老鼠编号的加和，例如：17号酒喂给1号和16号小老鼠 ，76号酒喂给4号、8号和64号小老鼠，七天后将死掉的小老鼠编号加起来，得到的编号就是有毒的那桶酒。因为对于任何一个小于1024的数，都可以采用前面的唯一一组二进制数（例如：01，10，100，1000，……，1000000000）来表示，所以结论成立。
5、 糖水问题
题目：有5杯水，其中有一杯是糖水，再给你一个空杯子，设计一种方案最多只尝三次，找出这杯糖水。
此题可以使用类似于二分查找的方法进行解答。首先选取其中的3杯水，都倒一点到空杯中，搅拌均匀，然后尝一下，此时杯中水的味道可能出现两种情况：有甜味与无甜味。
如果杯中水有甜味，则表明这3杯水中必有一杯是糖水，此时从这3杯水中选2杯，都到一点到空杯中，搅拌均匀，然后尝一下，如果没有甜味，那么没选中的那一杯就是糖水，如果有甜味，则品尝其中的一杯水就知道哪杯是糖水了。
如果杯中水没有甜味，那就尝一下没有选中的2杯水中的一杯，此时就知道哪杯是糖水了。
6、 握手问题
题目：一对夫妇邀请N-1对夫妇参加聚会（因此聚会上总共有2N人）。每个人都和所有自己不认识的人握了一次手。然后，男主人问其余所有人（共2N-1个人）各自都握了几次手，得到的答案全部都不一样。假设每个人都认识自己的配偶，那么女主人握了几次手？
由于聚会上一共有2N个人，每个人都和所有自己不认识的人握了一次手，所以女主人握手次数只可能是从0到2N-2这2N-1个数。除去男主人外，一共有2N-1个人，因此每个数恰好出现了一次。其中有一个人(0)没有握手，即握手次数为0，有一个人(2N-2)和所有其他的夫妇都握了手，即握手次数为2N-2，而这两个人肯定是一对夫妻，否则后者将和前者握手（从而前者的握手次数不再是0）。除去这对夫妻外，有一个人(1)只与(2N-2)握过手，有一个人(2N-3)和除了(0)以外的其它夫妇都握了手，这两个人肯定是一对夫妻，否则后者将和前者握手（从而前者的握手次数不再是1）。依此类推，直到握过N-2次手的人和握过N次手的人配成一对。此时，除了男主人及其配偶以外，其余所有人都已经配对。根据排除法，最后剩下来的那个握手次数为N-1的人就是女主人了。
7、 飞船处理器问题
题目：一个飞船上，飞船上的计算机有n个处理器。突然，飞船遭遇意外，一些处理器被损坏了。此时知道有超过一半的处理器仍然是好的，同时可以向一个处理器询问另一个处理器是好的还是坏的，好的处理器总是说真话，坏的处理器总是说假话，用n-2次询问找出一个好的处理器。
首先给处理器从1到n进行编号。用符号a->b表示向标号为a的处理器询问处理器b是不是好的。
然后执行1->2，如果1说不是，就把他们俩都去掉，因为如果1是好的，则2是坏的，如果1是坏的，则2是好的，所以能够保证两个处理器一个是好的，一个是坏的，去掉它们两，则剩下的处理器中好的仍然过半），然后从3->4开始继续发问。如果1说2是好的，就继续问2->3，3->4，……直到某一次j说j+1是坏的，把j和j+1去掉，然后问j-1 -> j+2；或者从j+2 -> j+3开始发问，如果前面已经没有j-1了（之前已经被去掉过了）。注意到整个推理过程，始终维护着一个类似于“链”的结构，即前面的每一个处理器都说后面那个是好的。这条链里的所有处理器要么都是好的，要么都是坏的。当这条链越来越长，剩下的处理器越来越少时，总有一个时候这条链超过了剩下的处理器的一半，此时可以肯定这条链里的所有处理器都是好的。或者，越来越多的处理器都被去掉了，链的长度依旧为0，而最后只剩下一个或两个处理器没被问过，那它们一定就是好的了。另外注意到，第一个处理器的好坏从来没被问过，因为最后一个处理器的好坏不可能被问到，因为一旦链长超过剩余处理器的一半，或者最后没被去掉的就只剩这一个了时，就不需要问了，因此询问次数不会超过n-2。
8、 机器人相遇问题
题目：有两个机器人，初始时位于数轴上的不同位置，如何给这两个机器人输入一段相同的程序，使得这两个机器人保证可以相遇。注意，程序只能包含“左移n个单位”、“右移n个单位”，条件判断语句if，循环语句while，以及两个返回Boolean值的函数“在自己的起点处”和“在对方的起点处”，不能使用其它的变量和计数器。
为了保证两个机器人可以相遇，可以将两个机器人刚开始同时以单位速度右移，直到一个机器人走到另外一个机器人的起点处，然后，该机器人以双倍速度追赶对方，这样两个机器人必能相遇。原理如下：假设两个机器人相距x个单元，标记位于左边的机器人为A，位于右边的机器人为B，当A向右移动x个单元到达B的起点处时，此时B也向右移动了x个单元，然后A以两倍的速度追赶元素B，假设花费t时间追赶上B，则满足等式：2*t=1*t+x，则t=x，则在距离B为2x的位置，A追赶上B。
转载：《程序员面试宝典》何昊
