6有2n个人排队进电影院，票价是50美分。在这2n个人当中，其中n个人只有50美分，另外n个人有1美元（纸票子）。愚蠢的电影院开始卖票时1分钱也没有。问：有多少种排队方法使得每当一个拥有1美元买票时，电影院都有50美分找钱。
注：1美元=100美分拥有1美元的人，拥有的是纸币，没法破成2个50美分。
【答案解析】
本题可用递归算法，但时间复杂度为2的n次方，也可以用动态规划法，时间复杂度为n的平方，实现起来相对要简单得多，但最方便的就是直接运用公式：排队的种数=(2n)！/[n！(n+1)！]。
如果不考虑电影院能否找钱，那么一共有(2n)！/[n！n！]种排队方法（即从2n个人中取出n个人的组合数），对于每一种排队方法，如果他会导致电影院无法找钱，则称为不合格的，这种的排队方法有(2n)！/[(n-1)！(n+1)！]（从2n个人中取出n-1个人的组合数）种，所以合格的排队种数就是(2n)！/[n！n！]- (2n)！/[(n-1)！(n+1)！] =(2n)！/[n！(n+1)！]。
7有一种体育竞赛共含M个项目，有运动员A，B，C参加，在每一项目中，第一，第二，第三名分别的X，Y，Z分，其中X，Y，Z为正整数且X>Y>Z。最后A得22分，B与C均得9分，B在百米赛中取得第一。求M的值，并问在跳高中谁得第二名。
【答案解析】
因为ABC三人得分共40分，三名得分都为正整数且不等，所以前三名得分最少为6分，40=5x8=4x10=2x20=1x40，不难得出项目数只能是5，即M=5，
A得分为22分，共5项，所以每项第一名得分只能是5，故A应得4个一名一个二名，22=5x4+2，第二名得1分，又B百米得第一，所以A只能得这个第二，
B的5项共9分，其中百米第一5分，其它4项全是1分，9=5+1=1+1+1，即B除百米第一外全是第三，跳高第二必定是C所得，
8一楼到十楼的每层电梯门口都放着一颗钻石，钻石大小不一。你乘坐电梯从一楼到十楼，每层楼电梯门都会打开一次，只能拿一次钻石，问怎样才能拿到最大的一颗？
【答案解析】
先拿下第一楼的钻石，然后在每一楼把手中的钻石与那一楼的钻石相比较，如果那一楼的钻石比手中的钻石大的话那就把手中的钻石换成那一层的钻石。
9一个家庭有两个小孩，其中有一个是女孩，问另一个也是女孩的概率（假定生男生女的概率一样）
【答案解析】
样本空间为（男男）（女女）（男女）（女男）
A＝（已知其中一个是女孩）＝）（女女）（男女）（女男）
B＝（另一个也是女孩）＝（女女）
于是P（B/A）＝P（AB）/P（A）＝（1/4）/（3/4）＝1/3。
10 芯片测试：有2k块芯片，已知好芯片比坏芯片多．请设计算法从其中找出一片好芯片，说明你所用的比较次数上限。 其中：好芯片和其它芯片比较时，能正确给出另一块芯片是好还是坏． 坏芯片和其它芯片比较时，会随机的给出好或是坏。
【答案解析】
把第一块芯片与其它逐一对比，看看其它芯片对第一块芯片给出的是好是坏，如果给出是好的过半，那么说明这是好芯片，完毕。如果给出的是坏的过半，说明第一块芯片是坏的，那么就要在那些在给出第一块芯片是坏的芯片中，重复上述步骤，直到找到好的芯片为止。
11100个人回答五道试题，有81人答对第一题，91人答对第二题，85人答对第三题，79人答对第四题，74人答对第五题，答对三道题或三道题以上的人算及格，那么，在这100人中，至少有多少人及格。
【答案解析】
首先求解原题。每道题的答错人数为（次序不重要）：26，21，19，15，9。
第3分布层：答错3道题的最多人数为：（26+21+19+15+9）/3=30。
第2分布层：答错2道题的最多人数为：（21+19+15+9）/2=32。
第1分布层：答错1道题的最多人数为：（19+15+9）/1=43。
Max_3=Min(30，32，43)=30。因此答案为：100-30=70。
其实，因为26小于30，所以在求出第一分布层后，就可以判断答案为70了。
要让及格的人数最少，就要做到两点：
1，不及格的人答对的题目尽量多，这样就减少了及格的人需要答对的题目的数量，也就只需要更少的及格的人。
2，每个及格的人答对的题目数尽量多，这样也能减少及格的人数。
由1得每个人都至少做对两道题目。
由2得要把剩余的210道题目分给其中的70人：210/3=70，让这70人全部题目都做对，而其它30人只做对了两道题。
也很容易给出一个具体的实现方案：
让70人答对全部五道题，11人仅答对第一、二道题，10人仅答对第二、三道题，5人答对第三、四道题，4人仅答对第四、五道题。
显然稍有变动都会使及格的人数上升。所以最少及格人数就是70人！
12烧一根不均匀的绳要用一个小时，如何用它来判断半个小时？烧一根不均匀的绳，从头烧到尾总共需要1个小时。现在有若干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢？（微软的笔试题）
【答案解析】
一，一根绳子从两头烧，烧完就是半个小时。
二，一根要一头烧，一根从两头烧，两头烧完的时候（30分），将剩下的一根另一端点着，烧尽就是45分钟。再从两头点燃第三根，烧尽就是1时15分。
13屋里三盏灯泡，屋外三个开关，一个开关仅控制一盏灯，屋外看不到屋里怎样只进屋一次，就知道哪个开关控制哪盏灯？四盏呢？
【答案解析】
温度，先开一盏，足够长时间后关了，开另一盏，进屋看，亮的为后来开的，摸起来热的为先开的，剩下的一盏也就确定了。
四盏的情况：设四个开关为ABCD，先开AB，足够长时间后关B开C，然后进屋，又热又亮为A，只热不亮为B，只亮不热为C，不亮不热为D。
？
14他们中谁的存活机率最大？
5个囚犯，分别按1-5号在装有100颗绿豆的麻袋抓绿豆，规定每人至少抓一颗，而抓得最多和最少的人将被处死，而且，他们之间不能交流，但在抓的时候，可以摸出剩下的豆子数。问他们中谁的存活几率最大？提示：
1，他们都是很聪明的人。
2，他们的原则是先求保命，再去多杀人。
3，100颗不必都分完。
4，若有重复的情况，则也算最大或最小，一并处死。
【答案解析】
第一个人选择17时最优的。它有先动优势。他确实有可能被逼死，后面的2、3、4号也想把1号逼死，但做不到（起码确定性逼死做不到）
可以看一下，如果第1个人选择21，他的信息时暴露给第2个人的，那么，1号就将自己暴露在一个非常不利的环境下，2-4号就会选择20，五号就会被迫在1-19中选择，则1、5号处死。所以1号不会这样做，会选择一个更小的数。
1号选择一个<20的数后，2号没有动力选择一个偏离很大的数（因为这个游戏偏离大会死），只会选择+1或-1，取决于那个死的概率小一些，再考虑这些的时候，又必须逆向考虑，1号必须考虑2-4号的选择，2号必须考虑3、4号的选择，，，，，，，只有5号没得选择，因为前面是只有连着的两个数（且表示为N，N+1），所以5号必死，他也非常明白这一点，会随机选择一个数，来决定整个游戏的命运，但决定不了他自己的命运。
下面决定的就是1号会选择一个什么数，他仍然不会选择一个太大或太小的数，因为那样仍然是自己处于不利的地位（2-4号肯定不会留情面的），100/6=16，7（为什么除以6？因为5号会随机选择一个数，对1号来说要尽可能的靠近中央，2-4好也是如此，而且正因为2-4号如此，1号才如此，，，，，，），最终必然是在16、17种选择的问题。
对16、17进行概率的计算之后，就得出了3个人选择17，第四个人选择16时，为均衡的状态，第4号虽然选择16不及前三个人选择17生存的机会大，但是若选择17则整个游戏的人必死（包括他自己）！第3号没有动力选择16，因为计算概率可知生存机会不如17。
所以选择为17、17、17、16、X（1-33随机），1-3号生存机会最大。
？？
15话说某天一艘海盗船被天下砸下来的一头牛给击中了，5个倒霉的家伙只好逃难到一个孤岛，发现岛上孤零零的，幸好有有棵椰子树，还有一只猴子！大家把椰子全部采摘下来放在一起，但是天已经很晚了，所以就睡觉先，
晚上某个家伙悄悄的起床，悄悄的将椰子分成5份，结果发现多一个椰子，顺手就给了幸运的猴子，然后又悄悄的藏了一份，然后把剩下的椰子混在一起放回原处，最后还是悄悄滴回去睡觉了，
过了会儿，另一个家伙也悄悄的起床，悄悄的将剩下的椰子分成5份，结果发现多一个椰子，顺手就又给了幸运的猴子，然后又悄悄滴藏了一份，把剩下的椰子混在一起放回原处，最后还是悄悄滴回去睡觉了，
又过了一会……
又过了一会……
总之5个家伙都起床过，都做了一样的事情。早上大家都起床，各自心怀鬼胎的分椰子了，这个猴子还真不是一般的幸运，因为这次把椰子分成5分后居然还是多一个椰子，只好又给它了，问题来了，这堆椰子最少有多少个？
【答案解析】
这堆椰子最少有15621。
第一个人给了猴子1个，藏了3124个，还剩12496个；
第二个人给了猴子1个，藏了2499个，还剩9996个；
第三个人给了猴子1个，藏了1999个，还剩7996个；
第四个人给了猴子1个，藏了1599个，还剩6396个；
第五个人给了猴子1个，藏了1279个，还剩5116个；
最后大家一起分成5份，每份1023个，多1个，给了猴子。
16一个商人骑一头驴要穿越1000公里长的沙漠，去卖3000根胡萝卜。已知驴一次性可驮1000根胡萝卜，但每走一公里又要吃掉一根胡萝卜。问：商人共可卖出多少胡萝卜？
【答案解析】
商人带驴驮1000根胡萝卜，先走250公里，这时，驴已吃250根，放下500根，原地返回，又吃掉250根。商人再带驴驮1000根胡萝卜，走到250公里处，这时，驴已吃250根，再驮上原先放的500根中的250根，继续前行至500公里处，这时，驴又吃250根，放下500根，剩250根返回250公里处，在驮上250公里处剩下的250根返回原地，这时驴又吃250根。商人再带驴驮1000根胡萝卜，走到500公里处，这时，驴已吃500根，再驮上原先放的500根，走出沙漠，驴吃掉500根，还剩500根。
17有3顶红帽子，4顶黑帽子，5顶白帽子。让10个人从矮到高站成一队，给他们每个人头上戴一顶帽子。每个人都看不见自己戴的帽子的颜色，却只能看见站在前面那些人的帽子颜色。（所以最后一个人可以看见前面9个人头上帽子的颜色，而最前面那个人谁的帽子都看不见。
现在从最后那个人开始，问他是不是知道自己戴的帽子颜色，如果他回答说不知道，就继续问他前面那个人。假设最前面那个人一定会知道自己戴的是黑帽子。为什么？
【答案解析】
答案是，最前面的那个人听见后面两个人都说了“不知道”，他假设自己戴的是白帽子，于是中间那个人就看见他戴的白帽子。那么中间那个人会作如下推理：“假设我戴了白帽子，那么最后那个人就会看见前面两顶白帽子，但总共只有两顶白帽子，他就应该明白他自己戴的是黑帽子，现在他说不知道，就说明我戴了白帽子这个假定是错的，所以我戴了黑帽子。”问题是中间那人也说不知道，所以最前面那个人知道自己戴白帽子的假定是错的，所以他推断出自己戴了黑帽子。
