| Perfil de xie追忆似水流年FotosBlogListas |  Herramientas  Ayuda |
|
|
26 agosto 手算开平方
16 julio 篱笆的长度一个单位正方形的土地，其内（包括边界）建一些篱笆，使得任何与正方形相交的线段都被篱笆阻断（即与篱笆相交），问所建篱笆的总长度最少要多长？
肯定每个顶点都要有线通过。考虑三角形的情况，这很简单，因为每个底和高的组合都是最短的。那么扩展到多边形，首先一条对角线，划分为两个小的多边形，然后从其中一个多边形的顶点向该对角线画垂线。对于已有多条直角相交的划分线，那么与该“勾”和“股”对应的“弦”也是一条隐形的划分线。不过其长度不计算在内，但是新垂线和该“弦”垂直就行了。比如说，长和宽不相等的矩形，“篱笆”就不是两对角线，而是先做一条对角线，然后从剩下的两个顶点分别引垂线到对角线上，这三条线段长度之和就是“篱笆长度”。
--------------------------------------------------------------------------------------------
现在看来这是错误的。三角形的情况是费马点向顶点的连线。正方形的情况？估计是其中三个顶点做个费马点，然后从第四个点引垂线到对角线上。这样篱笆的长度应该最小。
----------------------------------------------------------------------------------------------
这个月的ponder this 答案出来了，哈，看来我的是对的。
答案网址：http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/July2007.html 15 enero 智力题大集合哈佛入学智力考题
一个酒店里，只有两个避孕套，可是有两对男女。四个人都很open-minded, 今晚每个男的（一共两个） 都要和每个女的（一共两个）有一腿。可是他们四个人中有一个有艾滋病，但不知道是谁。
这四个人要如何使用那两个避孕套才能让大家都有上一腿，但相互之间不会交叉感染病毒？ 首先，这题的前提是套都不会破，或者说相当于他们不能直接接触。再次，我得佩服自己的这方面反应却 是太快了，第一秒就知道每个套都要翻过来用，10秒钟就能解决这个问题了。如果10分钟都答不上来马上
去面壁。设男人为A，B，女人为e，f，第一个套的两个面为12，另一个为34，写成A1表示1和A接触。好了
，第一次是两个套套着用，A1234e，第二第三次是A12f和B34e，第四次又是两个套套着用，B3412f。服了
我没有？
一、摸豆子问题
5个囚犯，分别按1-5号，按顺序在装有100颗绿豆的麻袋里抓绿豆，规定每人至少抓一颗，而抓得最多 和最少的人将被处死，而且，他们之间不能交流，但在抓的时候，可以摸出剩下的豆子数。问他 们中谁的存活几率最大？ 提示： 1.他们都是很聪明的人 2.他们的原则是先求保命，再去多杀人 3.100颗不必都分完 4.若有重复的情况，则也算最大或最小，一并处死。 第四个条件很有趣。先假设狱卒不许犯人拿相等的数目。设1拿到m个，2的策略就是m+1或者m-1，这样使 得3不能拿到平均值。3的策略仍是选一个偏大或者偏小的数紧挨着前两个数，否则第四个就能占到中间了
。如此类推。这样前四个的选择就是，k-1，k，k+1，k+2，不一定按顺序。由于5也不能重复选择，所以
他死定了。不论他选大选小，中间的两个肯定没事。选中间值没事，那么1就选20，2选21还是19？其实都
一样，因为3的选择确定到前三个的中间值，前面是什么对3没很大影响(如果1没有选得太小或者太大)。
我们从前面的设1拿到m，后面的人是随机选大选小，画一个决策树算得他们死亡概率是2：2：4：8：16，
最后一个是死定了。如果他抱着要多些人垫背的想法，那也只会影响到第3和第4号，选一个陪葬。这样随
机选一个，概率还是一样，因为5只能知道4可能是已知4个数的最大或最小。1和2选择什么不要紧，肯定
是相邻两数，但前两个还是比3好，因为在只有三个的情况下他们有可能一个到中间，3肯定在边上。同理
，在只有四个的情况下，4所选的数也肯定在边上。我们最后还是要确定一下1的选择范围，由于5是必死
的，所以选择一颗豆子只有他才会做，而这五个人的选择又受到100颗的限制，所以1的选择x个应该在某
个范围内，因为后选的人会计算剩下的豆子，有可能达到占中间的目的。例如前三个数的平均是21，那么
给第四个人剩下37个豆子，那么他就会选19，留下18给最后一人。因为有最后一人小过他，他所选的19比
平均的21小，所以第四人不用死。而前三个中的最大数会死，前三个及最后一个这四人中的最小也会死，
注意，最后的人未必死定。所以1不会选21，如果1选了21，那么2就不会选22，如果那样平均就会达到21
，而前三的最大会死，所以2不选22，转而选20。这样一来1就变成前三中的最大。所以1也不会选21。如
果1选20呢？1选了20，假设2选21，那么3呢？假设3选22，剩下40。4可以选23或者19。如果4选了23，那
么5就最大只能选40-23=17，这样4和5都是必死。所以4肯定转而选19。这样的话3就死定了。3不选22而选
19，4可以选22或者18。同理如果4选22的话，他和最后的人都是必死。所以4选18，这样3所选的19在中间
而2所选的21最大，2还是有可能死的，所以2还不如选19。这样的话3会选21吗？假设这样，那么剩下40，
情况和前面一样，3所选的21最大，必死。所以3选18，剩下43，4可以选17或者21，而不论4怎么选，5都
可以选到最大和最小。这样好像很好，但是1所选的20并不是中间，还是可能死，所以1不选20选19。由前
面推知前两个数之和不可能再是39，2肯定不选20而选18。问题是3怎么选，我们画一个前两个选择是19，
18的决策树，发现这树是完整的，所有的结果分布是对称均匀分布的，其死亡概率为1：1：2：2：8。所
以说1只能选比19相等或者更小的数。类似的，我们可以确定1只能选比4相等或者更大的数。特别地，当1
选19时，2必选18；而第一人选4时，第二个人必选5；其他情况后面所选的数可以是最大和最小，其死亡
概率都是1：1：2：2：8。
如果第四个条件等价于当犯人感到绝望知道自己死定的情况下会选择一个数使得最多的人同归于尽，那就 要是说他取一个已知的中间数，如果和前面的数相等，那么包括他自己就起码死掉4个人，或者全部死掉
；如果不相等那最好，自己不用死。所以犯人取中间数是肯定的，这要从最后一个人往前推断。如果前四
个数至少有两个相等，那么肯定是m-1，m，m，m+1或者是m-2，m-1，m，m这样相等的数在中间或者在两边
的情况，5选了中间数m或者m-1，大家都得死光。如果前面的数都不相等，m-1，m，m+1，m+2，那么m和m+
1中的一个能活，很可能是1或2号，4肯定死。如果4像5这么想，往回推，前三个不论怎么选，4也只可能
选中间数。由于前面两个肯定是相邻数，3和他们相邻，4会拿到1和2号拿到的数目中一个的数，这样3也
只能死定了，大家都死定了。如果第2个人想到这种情况，不会和1相邻，而是和1所选差一个比较大的奇
数，接着3选一个相差小一点的奇数，这样就给后面两个数留下空位。这样一来无论后面所选数是否互等
，3所选就必生，而1和2必死。所以2号肯定不会这样做，他肯定和1相邻，要死一起死。所以如果第四个
条件第二个理解成立的话，大家都死。
二、本智力题得名于一位美国电视游戏节目的主持人蒙特，他曾在多年之前主持一档档名为成交的节目。
在其中的一个游戏中，Monty向竞猜者展示了三扇门。有一扇门之后是一辆小轿车。另两扇门之后是空房
间。蒙特事先知道门后是什么，但您并不知道。
游戏分为三步： 1. 您选择一扇门。 2. 蒙特将会打开剩余的两扇门中的一扇，展示一个空的房间。（他从不会打开那扇后面藏有汽车的。） 3. 然后您可以选择是仍然选择在步骤1中选择的那扇门，还是选择去打开另一扇仍然关闭的。 假定您选择了A门。然后蒙特打开了另两扇门中的一扇，假定为B门。现在您可以选择改选C门或者仍然坚 持最初的选择，即A门。如果没有改变选择，那么可能会猜对也可能会猜错。另一方面，如果您改选C门，
则还是既可能猜对也可能猜错。您会做出什么选择呢？在蒙特打开一扇门之后，是坚持最初的选择，还是
改变前面已做的选择呢？为什么呢？
其实仔细想想也不难。1、如果我选到了汽车，那么我会坚持。在我知道自己选到汽车的情况下，肯定不 改变主意，这样就肯定拿到汽车，那么自己选到汽车的概率是1/3，所以1的可能是1/3。2、如果我选到了
空房，那么我会改变主意。在我知道自己选到空房的情况下，肯定改变主意，这样就肯定拿到汽车，那么
自己选到空房的概率是2/3，所以2的可能是1/3。综上所述，改变主意是比较好的。
让我们看一下第二种观点：坚持最初选择 理由1 如果您选择 A 门，则猜中的机会是 1/3，现在假定蒙特打开 B 门，展示这是一扇空门, 车在 B 门 之后的机率为 0，因为已经可以肯定那里没有任何东西。 因此在A、C 门之后的机率变为 1/2。机率的总
和仍然为 1。
机率都一样，为什么要改变选择呢？！ 其实第一个理由是站不住的。如果是主持人展示一个空房之后你才选，那概率才是1/2。我们这样想，三 个门，你先选一个，然后主持人展示一个空房之后我才选。你肯定觉得你吃亏了吧？改变主意是在已知你
的概率下我再作选择。汽车肯定在两个门中的一个后面，但并不是说两个的机率是相等的。就像你买彩票
肯定是中头彩和不中头彩，你也不能说你中头彩的概率就是百分之五十吧。由于第一次选择是等概率的，
我们可以这样设想，三个盆子，其中一个是你的，把汽车换成一升水，这样你的盆子里装到1/3升。由于
主持人要显示一个什么都没有的情况，等于是把另两个盆的水倒在一起然后拿掉了空盘。这样你的盆子是
1/3升，另一个就是2/3。还不明白？就当是三个盒子一颗豆子吧，你的盒子有豆子的可能是1/3，落在另
两个盒子的可能是2/3，拿掉其中一个空的，就等于是把他的机会到给了剩下的那个，剩下那个盒子里面
有豆子的机会还是不变，还是2/3。所以说你面对的盒子并不是一个！
理由2 我们不妨改变一下游戏： Monty向竞猜者展示了三扇门，有一扇门之后是一辆小轿车。另两扇门之后是空房间。蒙特事先知道 门后是什么，但竞猜者并不知道。竞猜者有三个人，但是不准选择同一扇门。
游戏分为三步： 1. 每人选择一扇门。 2. 蒙特将会打开三扇门中的一扇，展示一个空的房间，淘汰一个人。（他从不会打开那扇后面藏有 汽车的。）
3. 然后剩余两人可以坚持最初选择，也可以改变选择。 假设1号竞猜者选A门，2号竞猜者选B门，3号竞猜者选C门。蒙特打开B门，展示这是一扇空门，并淘 汰2号竞猜者。假定改变选择是正确答案，机率由 1/3变为2/3。于是1号竞猜者认为A门的机率为1/3，C门
的机率为2/3；3号竞猜者认为C门的机率为1/3，A门的机率为2/3。产生矛盾，假定不成立。
第二个理由也是站不住的，不过这个理由更有迷惑性。我们必须看到，原来的游戏中竞猜者是不会给人选 出局的，而在这个游戏中是有可能的，三个人都有可能的。他们每个人选中奖品、选不中出局、选不中留
下的的概率都是1/3。所以在剩下的两人中，1号竞猜者是选中奖品、选不中留下的的概率都是1/3，2号竞
猜者也一样。这样一来就没必要换了。
三、病狗问题
一个大院子里住了50户人家，每家都养了一条狗，这个院子里的人都有极强的推理能力。 有一天他们接到通知说院子里有狗生病了，并要求所有主人在发现自己家狗生病的当天就要把狗枪 杀掉。然而所有主人和他们的狗都不能够离开自己的房子，主人与主人之间也不能通过任何方式进行沟，
他们能做的只是通过窗户观察别人家的狗是否生病从而判断自己的狗病否。（就是说，每个主人只能看出
其他49家的狗是不是生病，单独看自己的狗是看不出来的）
第一天没有枪声，第二天还是没有枪声，第三天传出一阵枪声，问有多少条狗被枪杀？ A、假设有1条病狗，病狗的主人会看到其他狗都没有病，那么就知道自己的狗有病，所以第一天晚上就会
有枪响。因为没有枪响，说明病狗数大于1。
B、假设有2条病狗，病狗的主人会看到有1条病狗，因为第一天没有听到枪响，是病狗数大于1，所以病狗
的主人会知道自己的狗是病狗，因而第二天会有枪响。既然第二天也每有枪响，说明病狗数大于2。
由此推理，如果第三天枪响，则有3条病狗。
四、小猴子搬香蕉问题
一个小猴子边上有100根香蕉，它要走过50米才能到家，每次它最多搬50根香蕉，多了就被压死了，它每 走1米就要吃掉一根，请问它最多能把多少根香蕉搬到家里。提示：他可以把香蕉放下往返的走，但是必
须保证它每走一米都能有香蕉吃。也可以走到n米时，放下一些香蕉，拿着n根香蕉走回去重新搬50根。
能带回多少香蕉，其实就是问最少吃多少个香蕉。
解决了这个问题，也就自然知道能带回多少香蕉了。 贪心算法：
分析一下路程得知： 总路程=距离+2*返回路程
路程越短当然吃掉的香蕉也越少，而距离是固定的，这道题说穿了就是要尽可能的减少折返的路程。
如何保证折返的距离最短呢？方案就是步步为营。每走一米计算一次。 所以猴子在正向背香蕉的时候一定是背满筐的，能够一次背完，决不走两次，能够两次背完，决不走3次
。
不要忘了，折返一次的代价是两个香蕉，所以，在每一次准备折返之前先想清楚是否值得折返，如果那边 只有一个香蕉，那就直接丢弃好了。
如果是在笔试现场我大概这样想：考虑一下一个极端情况，猴子先往回走25米，再来背另一堆50根香蕉，
这样到目的地一根都没剩。再考虑另一个极端情况，一米一米的移，不难发现剩下的香蕉数量是有规律的
，50，48，47，45，44等等。从50开始隔一个数是50-3n。而其之前一个数比其大1。因为最划算情况是猴
子把两堆香蕉并成一堆背回去，所以要求得50-3n=25的n值，最接近的是n=8，对应的数就是26，观察26附
近的数列，是24，26，27，所以猴子是把26背到24的时候并成一堆，这时26变成了25，剩下香蕉25+24=49
。因为数列每两个相差3的数表示间隔2米，在26处走过了2*n=16，从26到24走了1米，所以剩下50-16-1=3
3米路程，所以到目的地时猴子能剩下49-33=16个。再快速的考虑10米10米的情况，只能剩下10。时间不
多，只好选择答案是16。
五、倒水问题
有三个立方体无盖盒子,不计容器厚度,容积分别为1*1*1,2*2*2,3*3*3. 要求:1.用此三个盒子装13的水 2.每个杯子只能加水一次 3.不能有水浪费掉. 请问有何方法. 算出容积为1，8，27，但是1+8〈13〈27，所以不能只是倒满两个小的杯也不能倒满大杯，当然所以倒满
更不可能。考虑到不计厚度，所以可以放小的杯到大杯里面，这样倒到大杯里面的水就少了。8放到27里
面，倒水到27，装满也只是19。19-13=6，下一步就是把19份水倒出去6，套用这个方法到小杯和中杯上，
小杯装满，倒到8里面，再放小杯到中杯，然后从大杯倒水到中杯直到满，所以中杯装了6，大杯剩下13。
七、分酒问题 有两个八斤的容器，都盛满酒，另有一个三斤的空容器。今有甲、乙、丙、丁四人，如何在没有其他工具 的情况下，仅用这三个无刻度的容器，让上述四人分享美酒？
懒得写了。这里的障眼法是，你不一开始就能量出2斤或者4斤酒，但是你可以先让他们喝进去3斤或者2斤 或者1斤，到最后四个人喝到肚子里面的都是4两就行了。
两个八斤的容器分别设为1号2号，三斤的空容器设为3号。十六斤的酒让四人分享，每人应分到四斤，现 在开始分酒：1、用1号的酒把3号倒满，让甲喝掉3号里的3斤，然后再把1号的酒倒入3号，让乙喝掉1号剩
下的2斤。这时1号容器是空的，2号3号都是满的。甲喝了3斤，乙喝了2斤，丙、丁都没喝。
2、把3号里的3斤倒入空的1号里，接着把2号里的酒倒入3号，3号再倒入1号，再把2号里的酒倒入3号，3 号里有3斤，而1号只能再倒2斤，当1号倒满时，3号里剩下1斤，这样1号是8斤，2号是2斤，3号里剩下1斤
。3号里的1斤让丙喝。
3、把1号倒入空的3号，再把2号倒入1号，这样1号里是7斤，3号是3斤。接着把3号倒入2号，把1号倒入3 号，3号再倒入2号，1号再倒入3号，这时1号有1斤，2号有6斤，3号有3斤，1号的1斤让丁喝。
4、用3号把2号倒满，这样3号剩下1斤，让甲把3号喝掉（甲喝了3+1=4斤）。这是1号和3号是空的，2号是 满的，在把2号倒入3号，让丙把3号喝掉（丙喝了1+3=4斤）。再把2号倒入3号，这时2号里有2斤，3号里
有3斤，让乙把2号喝掉（乙喝了2+2=4斤），丁把3号喝掉（丁喝了1+3=4 斤）。
八、称球问题 （1）一共12个一样的小球，其中只有一个重量与其它不一样(未知轻重)，给你一个天平， 只 称三次， 找出那个不同重量的球 （2）一共13个一样的小球，其中只有一个重量与其它不一样(未知轻重)，给你一个天平， 只 称三次， 找出那个不同重量的球 这两个问题是属于一个问题，解决前者就解决了后者。称12个，可以分成6个6个，3个3个，或者4个4个 一堆。很快就可知4个一堆的分法是最好的。如果天平左右相等，那么问题容易解决。如果不等，设为a1 a2a3a4 < b1b2b3b4, 再对半分开这样称是不行的。这时需要左右互换：两边都要有小球剩下，也要有小 球换到另一边。我们确定了这个原则，如果还是4个一边，a1a2b1c,b2b3a3a4,c代表正常球。如果相等就
直接得知b4重，浪费了一次称重。同时当左轻右重时，下一步不能确定a2轻还是b2重。所以我们该为3个
一边，为a1a2b1,b2a3c，这样就不会出现一种浪费的情况而造成另一种情况不能解决。懒得详细写了。记
得看过答案可以是4个一边的，不过不记得怎样分配了。
十、经典的帽子问题
1、有一个牢房，有3个犯人关在其中。因为玻璃很厚，所以3个人只能互相看见，不能听到对方说话的声 音。”
有一天，国王想了一个办法，给他们每个人头上都戴了一顶帽子，只叫他们知道帽子的颜色不是白的 就是黑的，不叫他们知道自己所戴帽子的是什么颜色的。在这种情况下，国王宣布两条如下：
（1）谁能看到其他两个犯人戴的都是白帽子，就可以释放谁； （2）谁知道自己戴的是黑帽子，就释放谁。 其实，国王给他们戴的都是黑帽子。他们因为被绑，看不见自己罢了。于是他们3个人互相盯着不说 话。可是不久，心眼灵的A用推理的方法，认定自己戴的是黑帽子。您想，他是怎样推断的?
很显然，两白一黑是不可能的，因为戴黑帽的人一眼就看出来。如果是两黑一白呢？A看到的是两黑，现 在他来判断自己是黑还是白。如果自己是白，那么另外两个人随便一个，假设是B，都看到是一黑一白。
那么B就会这样想，如果B自己是白，那么第三个人也就是戴黑帽的(不是A)就看到两个白，就会马上说出
来。没有人说，那就是B自己是黑。这样B就会说出自己的颜色，为什么他不说？所以A不是白色，只能是
黑色。
2、有n个人站成一列,每个人头上有一顶帽子,要么是黑色,要么是白色.每个人只能看见站在自己前面所有
的人的帽子的颜色.现让每个人报一种颜色,请想法使尽量多的人报的颜色是他自己帽子的颜色.
这种题目应该要想到是奇偶问题。正确答案应该是这样的： 人们先商量好,等排好队后，每个人都先记下在自己前面人的黑帽子的个数和白帽子的个数．排在最后面 的人的答案是关键的，他掌控着所有人的生死大权哦，这样,他前面所有的人都要记下他的答案，而且要
记下他后面每一个人的答案．
比如说： 倒数第一个人，他前面所有人的白色帽子是奇数个数,那他就说自己的帽子白色，这是事先协商好的． 倒数第二个人，他就知道白是奇数，这时如果他前面看到的n-1个人中白色是偶数的话，那他自己一定就 是白色的了，他就要说是白．
倒数第Ｎ个人，以此类推啦．．．． 运气好的话，一个都不用死哦.当然，最后一个人惨一点，不过他也有50%可能不用死的.当然，这个方法 是管不了他了，听天由命吧.
十二、苹果橘子问题 有3箱水果，一箱全是苹果，一箱全是橘子，还有一箱是两种水果的混装。三个箱子上都贴了标 签，不过所有的标签都贴错了~现在要求你只拿出一个水果，来判断3个箱子里的情况~ 方法是在贴着混装的箱子拿，假设是拿到苹果，那么贴着橘子的箱子里的就是混装，而贴着苹果的箱子是 橘子。
十四、一道关于飞机加油的问题
已知： 每个飞机只有一个油箱，飞机之间可以相互加油（注意是相互，没有加油机） 一箱油可供一架 飞机绕地球飞半圈。 问题： 为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架飞机？（所有飞机从同一 机场起飞，而且必须安全返回机场，不允许中途降落，中间没有飞机场） 我们可以考虑到只有一架飞机绕一圈，而且也只是这飞机飞过半圈，因为飞过半圈就不能回头。这里飞机 加油的前提是没有油的时候能瞬间加满。为他人作嫁衣裳的飞机飞回到机场肯定是刚好没有油，而受油的
飞机肯定是加满油箱的。如果是两架飞机，不能飞到还剩1/4圈，如果是三架飞机，一架飞机先回来，然
后另一架飞机再回来，这样第三架飞机能飞到剩1/4圈更靠近机场1/8圈的地方，在这个时机空中加油，派
一架飞机去不够油回来，所以要两架。所以答案是3架，如果开始飞回来的两架飞机能在机场加满油又反
方向再飞的话，否则就是5架。
十五、取硬币题
16个硬币，A和B轮流拿走一些，每次拿走的个数只能是1，2，4中的一个数。 谁最后拿硬币谁输。 问：A或B有无策略保证自己赢？假设都很聪明 我们看到1，2，4，16的性质，先退化到8个硬币。这时a有必胜策略，就是拿2，剩下的自己推。在这种情 况下a就想如果是16个的话，我就让b那前8个中的最后一次，然后让我开始最后一轮8个。同样的，b也这
样想。这样，a先拿4个，也是必胜。好像这样的想法能推倒24，32等等。
17．三个小伙子同时爱上了一个姑娘，为了决定他们谁能娶这个姑娘，他们决定用手枪进行一次决斗。阿
历克斯的命中率是30％，克里斯比他好些，命中率是 50％，最出色的枪手是鲍博，他从不失误，命中率
是100％。由于这个显而易见的事实，为公平起见，他们决定按这样的顺序：阿历克斯先开枪，克里斯第
二，鲍博最后。然后这样循环，直到他们只剩下一个人。那么这三个人中谁活下来的机会最大呢？他们都
应该采取什么样的策略？
记录他们为a，k，b。首先想如果轮到b，b会杀k，因为k比a准。所以k好在轮在前面，k肯定杀b。问题是a ，在第一轮，k和b都不会杀他，所以a只用考虑他活到下一轮的概率。如果a杀k，一不小心杀死了，b肯定
杀死a，这样的概率是0.3；如果a杀b，杀死了，接下来是k杀a，概率是0.3*0.7=0.21；不过有个策略是不
杀，故意不中，这样活到下一轮的概率是100%。所以a不杀，k杀b，b杀k。
18．2个盲人每人买了2双黑袜2双白袜，（每双袜子连在一起，）不小心吧这把8双袜子混在了一起，请问
他俩怎样才能拿会自己的袜子（2双黑袜2双白袜）
这里题意有点问题，不是说要取回原本的,只要他们各拿回2双黑袜&2白袜就行了。或者说有一个前提，就 是大小通用的袜子。方法是逐对分开，一人一只。
22. 有一个男人带着两个儿子，有一个女人带着两个女儿，还有一个猎人带着一只猎狗，要过河．只有一
条船．
问题在于： 船只能容纳两个人或者容纳一只狗和一个人； 只有男人和女人和猎人会撑船； 猎人不在，猎狗就会把其他的人杀死； 男人不在，女人就会把他的儿子杀死； 女人不在，男人就会把她的女儿杀死。 解这类题首先必须明确思路，不能靠撞（要撞也给计算机去撞），每一步的目的是什么必须很明确。
通过分析题目我们可知，猎人与狗在绝大多数时候都是不能分开的，能分开的只有一种情况，便是猎
人将狗放到没有人的一岸。基于此，我们可以推定猎人在整个运送过程中绝不是主力军，他的作用在于开
头跟结尾，以及中途一些特定时刻将船送到对岸。明白了这点之后，我们就可以将男人或女人作为主要渡
手进行运送。
因为男人一家与女人一家不能相容，我们首先想到的是将男人一家先运过去。然后 再想办法将女人与其中一个女儿以及猎人跟猎犬运过去。最后猎人带着猎犬将剩下那个 女儿替换过来，整个运送过程便告终结。 有了这个大步骤，小步骤便容易入手了。以下为具体过程：
猎人、猎狗过－－－猎人回
猎人、儿子1过－－－猎人、猎狗回 男人、儿子2过－－－男人回 男人、女人过－－－女人回（到这步男人一家全部安全抵达对岸） 猎人、猎狗过－－－男人回 男人、女人过－－－女人回（到这步男人一家与猎人猎犬在对岸） 女人、女儿1过－－－猎人、猎犬回 猎人、女儿2过－－－猎人回 猎人、猎犬过－－－完 23.三人住店
有三个人去住旅馆，住三间房，每一间房$10元，于是他们一共付给老板$30，第二天，老板觉得三间 房只需要$25元就够了于是叫小弟退回$5给三位客人，谁知小弟贪心,只退回每人$1，自己偷偷拿了$2，这
样一来便等于那三位客人每人各花了九元，于是三个人一共花了$27，再加上小弟独吞了不$2，总共是$29
。可是当初他们三个人一共付出$30那么还有$1呢？
解题思路： 其实房客的确付了27元，但是30元的算法有问题，这里偷换了概念。10乘3等于30没有错；每人拿回1 元等于每人出了9元也不错；老板得了25元，退回5元，总计30元没有错；客人付了30元，拿回3元得27元
没有错；小弟拿5元给客人3元自己留2元也没有错；房客付了27元，老板25元小弟2元没有错；但是现在非
要27加2得30，当然有错！聪明的你看出来了吧。
参考答案：$27不应加$2，而应减；也不存在少$1。 27. 你让工人为你工作7天，给工人的回报是一根金条。金条平分成相连的7段，你必须在每天结束时给他
们一段金条，如果只许你两次把金条弄断，你如何给你的工人付费？
答案：把金条分成1／7、2／7和4／7三份。这样，第1天我就可以给他1／7；第2天我给他2／7，让他找回 我1／7；第3天我就再给他1／7，加上原先的2／7就是3／7；第4天我给他那块4／7，让他找回那两块1／7
和2／7的金条；第5天，再给他1／7；第6天和第2天一样；第7天给他找回的那个 1／7。
28. 现在小明一家过一座桥，过桥的时候是黑夜，所以必须有灯。现在小明过桥要1秒，小明的弟弟要3秒
，小明的爸爸要6秒，小明的妈妈要8秒，小明的爷爷要12 秒。每次此桥最多可过两人，而过桥的速度依
过桥最慢者而定，而且灯在点燃后30秒就会熄灭。问小明一家如何过桥？
这类过桥题目有些诀窍，就是速度相差最小的要一起过桥，而最慢的两个人不能最早和最后过桥。知道这 个就容易解决了。
数学趣题2则~
1.老题目：1＜X＜Y＜30，将X+Y告诉甲，将X*Y告诉乙 下面是甲乙对话 甲说：“我不知道X和Y是多少，但你也不知道” 乙说：“我知道X和Y分别是多少了！” 甲说：“我也知道了” 问X和Y分别是多少？ 下面的答案来自互联网，我如果遇到这种题马上放弃，因为就算你做得出来都头晕脑胀了。
甲说：“我不知道X和Y是多少，但你也不知道”
说明x+Y一定不能拆成2个素数,且1<x<Y<30.如果是素数的话知道其乘积的人就能猜到是哪两个数了。为什
么？因为x和y都是素数，也就是说他们内部没有其他因数，所以根据其积就只能推算出x和y这两个因数。
(素数2,3,5,7,11,13,17,19,23,29) 排除:5,7,8,9,10,12,13,14,15,16,18,19,20,21,22,24,25,26,28,30,31,32,34,36, 40,42,46,48,52. 剩下:6,11,17,23,37,29,33,35,37,38,39,41,43,44,45,47,49,50,51,53~59. 乙说：“我知道X和Y分别是多少了！”
说明x*y仅有一种方式分解后的和在上面所例的 剩下中 6:2*4=8
11:2*9=18、3*8=24、4*7=28、5*6=30 17:2*15=30、3*14=42、4*13=52、5*12=60、6*11=66、7*10=70、8*9=72 23:2*21=42、3*20=60~~~~~ ~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~ 表不写了我用c++，编程打出来了~~~~~~~~~~~
这里30,42,60等出现了很多次
因为他们是6=2*3的倍数，象这样同为两个素数乘级的倍数将常常不止一组分拆 所以乙得到的不可能是这样的数(这里必须同时满足2数和也在上表中所以不一定都排除) 这里满足要求的有
甲,乙 6,8(但8只能有2*4,乙一开始就可以知道,甲不会说你也不知道) 11,18 11,24 17,52 23,76
23,112 27,50 27,92 29,54 29,168 35,304(但304=16*19=8*38=4*76=2*152,x,y同在30以内只有16*19,所以排除,理由同8) 37,232(但304=8*29=4*58=2*116,x,y同在30以内只有8*29,所以排除,理由同8) 甲说：“我也知道了”
说明甲的数只能有唯一的乙数才可以 这里只有17,52 对的4,13了~~~~~~~ 2.还一个就简单了10秒钟出答案 一位教授把16张扑克牌放在桌上,如下: 黑桃: A 7 Q 红心: 3 4 7 9 J Q 梅花: 2 3 5 Q K 方块: A 5 教授从中选出一张。把这张牌的数告诉了他的学生“甲”，把花色告诉了“乙”。然后教授问“甲”说： “你知道是那一张牌吗？”
甲：“我不能确定是那张牌。” 乙：“我知道你会这样说。” 甲：“现在我知道了。” 乙：“现在我也知道了。” 教授高兴的点点头。甲、乙二人都是有很强逻辑推理能力的，并且都说了实话。 根据以上信息，通过你的推理告诉我这张是什么牌？ 甲：“我不能确定是哪张牌。”
可以排除掉没有重复数字的，只剩下黑：A 7 Q 红：3 7 Q 梅：3 5 Q 方：A 5 乙：“我知道你会这样说。” 可以排除掉没有重复数字所在的花色，因为乙知道花色，如果甲能确牌，那么肯定是在没有重复数字的花 色中，现在花色只剩黑和方
甲：“现在我知道了。” 根据黑和方两种花色，甲可以确定是哪张牌，所以排除A,只有黑：7 Q 方：5 乙：“现在我也知道了。” 如果乙也能确定，那只能是方5（如果是黑7或Q,他确定不了） 四个砝码的问题。有30个砝码，重量从1g到30g。那么要求在给你一个天平的情况下，让你选择4个砝码，
能够称取1g到40g之间的整数重量.请问选择哪四个砝码？
我们可以尝试前两个为，1，2；1，3；1，4；2，3；这四种情况。1，2能称出1，2，3；1，3能称出1，2 ，3，4；1，4能称出1，3，4，5；2，3能称出1，2，3，5。看出1，3能称出连续4个数，比较理想。下一
个数应该是9，因为前两个数称不出5，而9-3-1=5，这样又比较省砝码。我们从1，3，9可以看出可以称出
从1到1+3+9=13，14称不出来，所以最后一个是13+14=27，刚好1+3+9+27=40。
但这样的方法并没有上升到数学的高度。以下的解释来自互联网，十分有道理。http://topic.csdn.net/ t/20011220/22/433578.html的十六楼。
其实这个问题的实质是一个数的进制问题。考虑用3进制,且只用数字0或1来表示一个自然数，在允许4位 的情况下，最小为0001，最大为1111，转化10进制为1-40，这就是题目提出的40的来历。当然，为什么只
允许用数字1来表示一个数呢，这是因为3进制有一个特点，2恰好是1的补码。所以，当用3进制来表示一
个自然数时，假如需要用2来表示的时候，我们就可以采取进1升位再减1表示，比如（后面两个式子里的
都是三进制的数），2=10-1,122=200-1=1000-100-1=1000-101，而减法运算就可以在天平上采取分放两边
的方法来实现。比如，用1,3,9,27要称出19的话，方法是这样的。将19转化成3进制，19=2*3^2+1=201=10
01-100，所以在天平的一边放上27和1，在另一边放上9就可以了。
1. 有一个长方形蛋糕，切掉了长方形的一块(大小和位置随意)，你怎样才能直直的一刀下去，将剩下的
蛋糕切成大小相等的两块？
答案：将完整的蛋糕的中心与被切掉的那块蛋糕的中心连成一条线。这个方法也适用于立方体！请注 意，切掉的那块蛋糕的大小和位置是随意的，不要一心想着自己切生日蛋糕的方式，要跳出这个圈子。
2.
5个海盗抢到了100颗宝石，每一颗都一样的大小和价值连城。他们决定这么分： 1、抽签决定自己的号码1，2，3，4，5 2、首先，由1号提出分配方案，然后大家5人进行表决，当且仅当半数和超过半数的人同意时（如果是只 能超过半数人同意才通过时，答案会不同），按照他的提案进行分配，否则将被扔入大海喂鲨鱼。
3、如果1号死后，再由2号提出分配方案，然后大家4人进行表决，当且仅当半数和超过半数的人同意时， 按照他的提案进行分配，否则将被扔入大海喂鲨鱼。
4、以次类推...... 条件： 每个海盗都是很聪明的人，都能很理智的判断得失，从而做出选择。 问题：第一个海盗提出怎样的分配方案才能够使自己的收益最大化 请采用逆推思路： --假如死了3个，剩下4和5。 由4提出方案，不言而喻，4把100颗宝石聚为己有，5什么也没得到，由于4号肯定会为自己提出的这个方 案投赞成票，因为肯定会获得通过。
--假如剩下3、4、5 5号海盗知道，如果3号的方案被否决，那么5将一无所获，所以5号只要得到一点点甜头就行，而3号也知 道这样的形势，所以只要分给5号一颗宝石，自己可以独享99颗宝石，而4号将一无所获。 --而当2号加入
时，也差不多，为了使其有半数或半数以上的投票，那么也要拉一个人作为其同党，于是他可以分4号一
颗宝石，因为如果2号被否决而3号得以通过，那么4号将一无所获。因此2号的分配方法是：99颗归自己，
4号地一颗，3和5号一颗也没有。 --当1号加入时，他需要收买两个海盗，所以至少得用两颗宝石去贿赂
才能使自己的方案被采纳，他最终的分配方法是：98颗归自己，1颗给3号，另一颗给5 号。
3.你有一袋糖，有红色的，蓝色的，绿色的。闭上眼睛，拿出两块颜色一样的糖，你需要拿多少次才能确 保有两块颜色相同的？
四次（鸽笼原理，四块糖，三种色，所以里面至少有两块是同一颜色的） 4. 为什么下水道的井盖是圆的？
提示：方形的对角线比边长！(这个答案比较sb，因为这样就不会掉到下水道里面去？正三角形也不 会啊正五边形也不会啊)其他答案：1圆形的井盖可以由一个人搬动，因为它可以在地上滚。2圆形的井盖
不必为了架在井口上而旋转它的位置。
5.假设一张圆盘像唱机上的唱盘那样转动。这张盘一半是黑色，一半是白色。假设你有数量不限的一些颜
色传感器。要想确定圆盘转动的方向，你需要在它周围摆多少个颜色传感器？它们应该怎样摆放？
两个挨着放，千万不要对称的放置。有一个探测器测到变色，紧跟着另一个就会测到。而下次探测到变色 要走过半张盘才会遇到。那么，转盘的方向是从第一个测到变色的转向第二个。
7. 一列时速15英里的火车从洛杉矶出发，驶向纽约。另外一列时速20英里的火车从纽约出发，驶向洛杉 矶。如果一只鸟以每小时25英里的速度飞行，在同一时间从洛杉矶出发，在两列火车之间往返飞行，到火
车相遇时为止，鸟飞了多远？
小学的题目，我永远记得怎样做，因为当时我竟然想到了极限和积分。 8. 你有两个罐子，分别装着50个红色的玻璃球和50个蓝色的玻璃球。随意拿起一个罐子，然后从里面拿
出一个玻璃球。怎样最大程度地增加让自己拿到红色球的机会？利用这种方法，拿到红色球的几率有多大
？
如果原来那样拿，概率是0.5。如果一个瓶子里装一个红球，其他都装到另一个瓶子里，取到红球的概率 是149/198 。
10. 你有5瓶药，每个药丸重10克，只有一瓶受到污染的药丸重量发生了变化，每个药丸重9克。给你一个
天平，你怎样一次就能测出哪一瓶是受到污染的药呢？
答案： 1 给5个瓶子标上1、2、3、4、5。 2 从1号瓶中取1个药丸，2号瓶中取2个药丸，3号瓶中取3个药丸，4号瓶中取4个药丸，5号瓶中取5个 药丸。
3 把它们全部放在天平上称一下重量。 4 现在用1×10＋2×10＋3×10＋4×10＋5×10的结果减去测出的重量。 5 结果就是装着被污染的药丸的瓶子号码。 11. 如果你有一个容量为5夸脱的水桶和一个容量为3夸脱的水桶，怎样准确地量出4夸脱的水？
这个太容易了，不说了。 14. 有4条狗分别在一个广场的4个角落里。突然，它们同时以同样的速度追赶在自己顺时针方向的狗，而
且会紧追这个目标不放。它们需要多少时间才能相遇，相遇地点在哪里？
直觉告诉我们地点是在中央，他们跑的路线就像漩涡一样，是吧？ 15. 从空中放下两列火车，每列火车都带着降落伞，降落到一条没有尽头的笔直的铁道上。两列火车之间
的距离不清楚。两列车都面向同一个方向。在落地后，降落伞掉在地上，与火车分离。两列火车都有一个
微芯片，可以控制它们的运动。两个芯片是相同的。两列火车都不知道自己的位置。你需要在芯片中写入
编码，让这两列火车相遇。每行编码都有一定的执行命令的时间。
你能使用以下指令(而且只能用这些指令)： MF—让火车朝前开 MB—让火车朝后开 IF(P)—如果火车旁边有降落伞，这个条件就得到了满足。 GOTO 这道题挺有意思的，必须理解到最后一句话的意思。 答案： A：MF IF(P) GOTO B GOTO A B：MF GOTO B 解释：第一行只是让它们离开各自的降落伞。必须让它们离开自己的降落伞，这样后面的火车才能发 现前面火车的降落伞，这样就满足了一个条件，它们就可以跳出起初遵守的编码。它们起初都在A这部分
循环，直到后面的火车发现前面火车的降落伞，这时就转入B：并陷入B的循环。前面的火车还是没有找到
降落伞，所以就不段在A的循环里面，又由于A的循环里面代码多，耗时也多，所以后面的火车肯定能追上
前面的火车。
16.有10个人要从城市甲出发去往城市乙.他们只有一辆车(除开司机只有一个位)已知甲乙两城市相距1000
公里,开车速度100公里/小时,步行速度5公里/小时.问要10个人都到达城市乙最少要花多长时间?
要想用时最少，可以遵循以下步骤：
1） 依然是车和人（车2人，步行8人）同时出发，车行驶了X公里后把乘客放下，乘客继续向B城进发，车 返回直到与8人相遇（历时t1）；
2） 车与8人相遇后，搭上1人调头向B城方向出发，直到追上最前面的1人，将乘客放下，车返回直到与7 人相遇（历时t2）；
3） 重复上述步骤（历时t3-t8），直到车搭上最后1名步行者到达B城（历时t9），同时8名已经被搭载过 的步行者也到达B城。
这样10个人同时出发，又同时到达B城，所用时间是最少的。现在关键是要算出车到底要行驶X公里把乘客
放下，才能使最后10个人同时到达B城。
t1=t2=t3=t4=t5=t6=t7=t8=2x/(100+5) t9=(1000-2*5*8x/105)/100 对于第1名乘客，他需要步行的时间是8*t1+t9-(x/100) 所以有以下方程 5*[8*t1+t9-(x/100)]+x=1000 解得x=567.58公里 代入可得t=t1+t2+...+t9=8*t1+t9=92.16小时 09 enero 又看到了面试题1 有一座山，山上有座庙，只有一条路可以从山上的庙到山脚，每周一早上8点有一个聪明 的小和尚去山下化缘，周二早上8点从山脚回山上庙里，小和尚的上下山的速度是任意的 ，在每个往返中，他总是能在周一和周二的同一钟点到达山路上的同一点，例如有一次 他发现有一次他发现星期一的8点30和星期二的8点30他都到了山路靠山脚的3/4的地方， 问这是为什么。 这道题在网上很难找到答案。估计是小和尚是变速的，由快到慢，由慢到快，上下山是不同的。是这样吗? 两天后我找到答案了，看来我的思维还是太原始了，远没有到数学的高度。。。 以下文字来自http://book.hackbase.com/data/web5302/20050228/20050228__3522574.html “画个坐标图，纵坐标是山的高度，横坐标是时间。在x=0的地方任意定一个y值 A 表示山顶，在y=0的地方任意定一个值 B 表示下山的时间。现在开始计算，周一从山顶下到山脚，就是在（0，A）到（B，0）之间画一条线，周二从山脚到山顶，就是在（0,0）到（B，A）画一条 线，你会发现无论怎么画总有一点会交叉的，这个点就是周一和周二的同一钟点到达山路上的那个点” 2 一楼到十楼的每层电梯门口都放着一颗钻石，钻石大小不一。你乘坐电梯从一楼到十楼，每层楼电梯门都会打开一次，只能拿一次钻石，问：怎样才能拿到最大的一颗？ 网上流传的一个比较像样的答案是，选择前五层楼都不拿，观察各层钻石的大小，做到心中有数。后面五个楼层再选择，选择大小接近前五层楼出现过最大钻石大小的钻石。 从编程的角度来看，“心中有数”到底是能记录多少个数，如果是一个那么就是最大值。然后从中间开始往后的楼层中，如果看到比记录数大或者只是小一个单位的，就拿；否则就到上一层观察，若都不满意则只能拿最后一个。这个方法有个蜕化问题，就是，如果最大和第二大的钻石都在前五层，那么这些情况下只能拿最后一个。除非心中有数记录完前面一半楼层的所有的单位数，否则都会有这个问题。 我在纸上乱画了一下，在随机情况下，4层楼，每个钻石大小是1，2，3，4，这个策略能比随机抽取强20%，随机的期望是60，而此方法达到72。 网上有人说这是数学里面的“秘书问题”。 以下文字来自http://topic.csdn.net/t/20030417/23/1676005.html之46楼 如何选择是没有绝对最优解的 想象一下四种最简单的可能： 价值有小到大递增 价值有小到大递减 价值中间最大 价值中间最小 假定算法1是： 跳过前面K个，后面超过平均值则取。 假定算法2是： 跳过前面K个，后面超过最大值则取。 假定算法3是： 跳过前面K个，后面超过最小值则取。 假定算法4(大龄青年算法)是： 跳过前面三分之一，第二组三分之一有超过最大值则则取，最后三分之一有超过最小值则取。 |
|
|
