|
海盗分金问题 Description:
传说，从前有五个海盗抢得了100枚金币.他们通过了一个如何确定选用谁的分配方案的安排.即：
1.抽签决定各人的号码（1，2，3，4，5）；
2.先由1号提出分配方案，然后5个人表决.当且仅当超过半数人同意时，方案才算被通过，否则他将被扔入大海喂鲨鱼；
3.当1号死后，再由2号提方案，4个人表决，当且仅当超过半数同意时，方案才算通过，否则2号同样将被扔入大海喂鲨鱼；
4.往下依次类推……
根据上面的这个故事，现在提出如下的一个问题.即：
我们假定每个海盗都是很聪明的人，并且都能够很理智地判断自己的得失，从而做出最佳的选择，那么第一个海盗应当提出怎样的分配方案才能够使自己不被扔入大海喂鲨鱼，而且收益还能达到最大化呢？
Solution:
倒推，从后往前推，人数依次增加
如果１－３号强盗都喂了鲨鱼，只剩４号和５号的话，５号一定投反对票让４号喂鲨鱼，以独吞全部金币。所以，４号惟有支持３号才能保命。３号知道这一点，就会提（１００，０，０）的分配方案，对４号、５号一毛不拔而将全部金币归为已有，因为他知道４号一无所获但还是会投赞成票，再加上自己一票，他的方案即可通过。
２号推知到３号的方案，就会提出（９８，０，１，１）的方案，即放弃３号，而给予４号和５号各一枚金币。由于该方案对于４号和５号来说比在３号分配时更为有利，他们将支持他而不希望他出局而由３号来分配。这样，２号将拿走９８枚金币。
２号的方案会被１号所洞悉，１号并将提出（９７，０，１，２，０）或（９７，０，１，０，２）的方案，即放弃２号，而给３号一枚金币，同时给４号（或５号）２枚金币。由于１号的这一方案对于３号和４号（或５号）来说，相比２号分配时更优，他们将投１号的赞成票，再加上１号自己的票，１号的方案可获通过，９７枚金币可轻松落入囊中。这无疑是１号能够获取最大收益的方案了！
帽子/疯狗问题
Description:
一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其他人帽子的颜色，却不知自己的。主持人先让大家看看别人头上戴的什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？
Solution:
递推归纳
假如只有一个人戴黑帽子，那他看到所有人都戴白帽，在第一次关灯时就应自打耳光，所以应该不止一个人戴黑帽子；如果有两顶黑帽子，第一次两人都只看到对方头上的黑帽子，不敢确定自己的颜色，但到第二次关灯，这两人应该明白，如果自己戴着白帽，那对方早在上一次就应打耳光了，因此自己戴的也是黑帽子――― 于是也会有耳光响起；可事实是第三次才响起耳光声，说明全场不止两顶黑帽，依此类推，应该是关几次灯，有几顶黑帽。
称球问题
Description:
一共12 个一样的小球， 其中只有一个重量与其它不一样( 未知轻重) ，给你一个天平， 只称三次， 找出那个不同重量的球？
如果一共13 个一样的小球， 其中只有一个重量与其它不一样( 未知轻重) ，给你一个天平， 只称三次， 找出那个不同重量的球？
Solution:
充分利用所有信息
12个情形:将球编号1~12，分为1-4,5-8,9-12三堆
左1-4－右5-8
若平衡，坏球在9-12,左1-3－右9-11
若不平衡且5-8重，坏球1-8
左1,6,7,8－右5,9,10,11
右重->坏球是1或5
平衡->坏球为2-4且比标准球轻
左重->坏球在拿到左边的6-8且比标准球重
三种情形：再称一次得解
若不平衡且1-4重与上同理
13 个球情形：解法类似 , 分为三组,1-4,5-8,9-12
左1-4 －右5-8
不平衡情形与12 球同
平衡时左1-3 －右9-11
不平衡时与12 球同，平衡时坏球在12/13 ，左1 －右12
平衡，坏球13
不平衡, 坏球12
注意：题目只需要找出重量不同的球即可
分金条问题
Description:
你让某些人为你工作了七天， 你要用一根金条作为报酬。这根金条要被分成七块。你必须在每天的活干完后交给他们一块。如果你只能将这根金条切割两次，你怎样给这些工人分？
Solution:
联想：二进制:1,2,4 其中若干个的和可构成1,7 中任何一个数
1/7 ，2/7 ，4/7 ，第一天给1/7 ，第二天拿2/7 换1/7………………
猴子搬香蕉问题
Description:
一个小猴子边上有100 根香蕉，它要走过50 米才能到家，每次它最多搬50 根香蕉，每走1 米就要吃掉一根，请问它最多能把多少根香蕉搬到家里。
Solution:
猜想＋验证
猜想：
设小猴从0 走到50, 到A 点时候他可以直接抱香蕉回家了, 可是到A 点时候他至少消耗了3A 的香蕉( 到A, 回0, 到A), 一个限制就是小猴只能抱50 只香蕉, 那么在A 点小猴最多49 只香蕉.100-3A=49, 所以A=17. 这样折腾完到家的时候香蕉剩100-3A-(50-A)=50-2A=16.
验证:
以上为最优情形，只需验证这种情形可以达到即可
飞机加油问题
Description:
每个飞机只有一个油箱， 飞机之间可以相互加油（注意是相互，没有加油机） 一箱油可供一架飞机绕地球飞半圈。
为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架飞机？（所有飞机从同一机场起飞，而且必须安全返回机场，不允许中途降落，中间没有飞机场）
Solution:
猜想+验证
猜想：
至少需要出动5 架飞机。思路是这样的，一架飞机要想完成绕地球一周的飞行，至少需要别的飞机给它提供1 箱油。最划算的办法显然是，派飞机和它结伴飞行前四分之一周以及后四分之一周，（因为这两段路程距离基地近所花代价小。）由它独立飞行中间的半程。必须保证两个加油点，前四分之一处，加满，后四分之一点，及时补充。那么必须有两架飞机与目标机结伴飞行四分之一周，这两架飞机需要做折返飞行，正好花费2 箱油。所以补充油的任务实际上该由另外两架飞机完成。这两架飞机飞八分之一周，做折返飞，正好富余1 箱油。因此，5 架飞机刚好完成任务。到了此时，问题只考虑了一半。能够提供多少油并不意味着就能够全部接受，受到结伴飞行的距离，即腾出的油箱空间所限制。而以下做法正好可以满足此条件。
验证:
3 架飞机同时从机场出发，飞行八分之一周，各耗油四分之一。此时某架飞机给其余两架补满油，自己返回基地。另一机和目标机结伴，飞至四分之一周，给目标机补满油，自己返回。目标机独自飞行半周，与从基地反向出发的一机相遇，2 机将油平分，飞至最后八分之一处，与从基地反向出发的另一机相遇，各分四分之一油，返回。
硬币游戏
Description:
16 个硬币，A 和B 轮流拿走一些，每次拿走的个数只能是1 ，2 ，4 中的一个数。
谁最后拿硬币谁输。
问：A 或B 有无策略保证自己赢？
博弈类问题，分清两概念
必胜态：有一种方法导致下一状态为必败态
必败态：每一种方法导致下一状态为必胜态
解决办法：递推
1: 必败
2: 必胜：取1 ，导致变为1 状态( 必败)
3: 必胜：取2-> 必败态
4: 必败：取1 或2 或4 均导致必败态或直接失败
以些类推知16 为必败态，即后手必胜
剩2 个时, 取1 个必胜;
剩3 个时, 取2 个必胜;
剩4 个时, 如果对手足够聪明则必败;
剩5 个时, 去1 个必胜...
记作 2(1) 3(2) 4(x) 5(1) 6(2) 7(x) 8(1) ...
从中找出规律:
当剩余个数K=3N-2,N 为自然数时, 只要对手足够聪明则必败.
当K=3N-1 时, 有必胜策略: 取1 个;
当K=3N 时, 有必胜策略: 取2 个;
所以, 当16 个时, 后取者有必胜策略.
倒水问题
经典形式：
“ 假设有一个池塘，里面有无穷多的水。现有2 个空水壶，容积分别为
5 升和6 升。问题是如何只用这2 个水壶从池塘里取得3 升的水。”
Solution:
形式化倒水问题：无穷多水，容量a,b(a<=b) 的水壶倒出c(c<=b) 升水。
结论：c%***(a,b) == 0 时有解，可用扩展的Euclid 定理加以证明：即存在整数x,y ，使得ax+by=***(a,b).
通用解法:( 容量A,B 的水壶倒C 升水)
int t = 0;
while(t != c){
Do(fill A),Do(pour A B);
t = t+A;
if(t >= B){
t = t – B;
Do(empty B), Do(pour A B);
}
}
本题解答(5,6->3)
Oper a b t (A=5,B=6)
Fill A, Pour A B 0 5 5
Fill A, Pour A B 4 6 10
Empty B, Pour A B 0 4 4
Fill A, Pour A B 3 6 9
Empty B, Pour A B 0 3 3 (success)
倒水问题推广
也可以说是倒酒：）有三个酒杯，其中两个大酒杯每个可以装8两酒，一个可以装3两酒。现在两个大酒杯都装满了酒，只用这三个杯子怎么把酒平均的分给4个人喝？
Solution:
Try and guess
用一个三位数表示三个杯，880 ，前两个为8 升的杯最后一个3 升。开始：880_853A 喝掉3 升变为：850_823_B 喝掉2 升为：803_830_533_560_263_281A 喝掉1 升(A 已经喝4 升完毕）为：280_253_550_523_820_802_703_730_433_460_163_181CD 各喝一升为：080_053_350_323CD 各喝3 升B 喝2 升，分水结束，ABCD 四人各喝4 升。
帽子问题 Description:
有一个牢房，有3个犯人关在其中。因为玻璃很厚，所以3个人只能互相看见，不能听到对方说话的声音。”
有一天，国王想了一个办法，给他们每个人头上都戴了一顶帽子，只叫他们知道帽子的颜色不是白的就是黑的，不叫他们知道自己所戴帽子的是什么颜色的。在这种情况下，国王宣布两条如下：
1．谁能看到其他两个犯人戴的都是白帽子，就可以释放谁；
2．谁知道自己戴的是黑帽子，就释放谁。
其实，国王给他们戴的都是黑帽子。他们因为被绑，看不见自己罢了。于是他们3个人互相盯着不说话。可是不久，心眼灵的A用推理的方法，认定自己戴的是黑帽子。您想，他是怎样推断的?
Solution:
逻辑学，假设思维
现在假设3个犯人是A、B和我
那么我的推断是：
第一种：我戴的是白帽子
那么A会这么想：如果自己戴的是白帽子，那么B就会看到2个白帽子，那么他根据国王的第一条就马上会被释放，但是B现在没有被释放，说明我戴的不是白的，是黑的，哈哈，我知道自己是黑的拉，我可以要求国王释放我拉
结论：如果我戴的是白帽子，那么根据A犯人的想法得出：A和B必然有一个会被释放，但是现在2个人都没有被释放，所以我一定不是白的，而是黑的，所以我会知道自己是黑的，要求国王释放我，这样，我就被放了
同理，A和B根据别人的想法也都算出自己是黑帽子，这样3个犯人同时被释放
年龄问题
Description:
一普查員問一女人,“ 你有多少個孩子, 他們多少歲?” 女人回答:“ 我有三個孩子, 他們的歲數相乘是36, 歲數相加就等於隔離間屋的門牌號碼.” 普查員立刻走到隔鄰, 看了一看, 回來說:” 我還需要多少資料.” 女人回答:“ 我現在很忙, 我最大的孩子正在樓上睡覺.” 普查員說:” 謝謝, 我己知道了
問題: 那三個孩子的歲數是多少。
Solution:
9，2，2
分析，设三个人的年龄组成自然数组合(x,y,z)，一共三个条件，
条件一：三个人岁数乘起来为36；选出满足x*y*z=36的组合;
条件二：知道三个人岁数之和后还是不能确定它们的年龄；从上面的到的组合中找出xyz之和有相同的组合；
只有 (9,2,2)=13,(6,6,1)=13
条件三：三个孩子中有一个年龄比其他两个大。符合条件的组合只有(9，2，2)
 |