前言:
而今看官们对“递归算法例题汽水问题递归”大体比较珍视,小伙伴们都想要学习一些“递归算法例题汽水问题递归”的相关文章。那么小编也在网上汇集了一些对于“递归算法例题汽水问题递归””的相关内容,希望你们能喜欢,看官们一起来学习一下吧!假设有一个池塘,里面有无穷多的水。现有2个空水壶,容积分别为5升和6升。问题是如何只用这2个水壶从池塘里取得3升的水。
由满6向空5倒,剩1升,把这1升倒5里,然后6剩满,倒5里面,由于5里面有1升水,因此6只能向5倒4升水,然后将6剩余的2升,倒入空的5里面,再灌满6向5里倒3升,剩余3升。
【2】周雯的妈妈是豫林水泥厂的化验员。一天,周雯来到化验室做作业。做完后想出去玩。"等等,妈妈还要考你一个题目,"她接着说,"你看这6只做化验用的玻璃杯,前面3只盛满了水,后面3只是空的。你能只移动1只玻璃杯,就便盛满水的杯子和空杯子间隔起来吗?"爱动脑筋的周雯,是学校里有名的"小机灵",她只想了一会儿就做到了。请你想想看,"小机灵"是怎样做的?
设杯子编号为ABCDEF,ABC为满,DEF为空,把B中的水倒进E中即可。
【3】三个小伙子同时爱上了一个姑娘,为了决定他们谁能娶这个姑娘,他们决定用手枪进行一次决斗。小李的命中率是30%,小黄比他好些,命中率是50%,最出色的枪手是小林,他从不失误,命中率是100%。由于这个显而易见的事实,为公平起见,他们决定按这样的顺序:小李先开枪,小黄第二,小林最后。然后这样循环,直到他们只剩下一个人。那么这三个人中谁活下来的机会最大呢?他们都应该采取什么样的策略?
小林在轮到自己且小黄没死的条件下必杀黄,再跟菜鸟李单挑。
所以黄在林没死的情况下必打林,否则自己必死。
小李经过计算比较(过程略),会决定自己先打小林。
于是经计算,小李有873/2600≈33.6%的生机;
小黄有109/260≈41.9%的生机;
小林有24.5%的生机。
哦,这样,那小李的第一枪会朝天开,以后当然是打敌人,谁活着打谁;
小黄一如既往先打林,小林还是先干掉黄,冤家路窄啊!
最后李,黄,林存活率约38:27:35;菜鸟活下来抱得美人归的几率大。
李先放一空枪(如果合伙干中林,自己最吃亏)黄会选林打一枪(如不打林,自己肯定先玩完了)林会选黄打一枪(毕竟它命中率高)李黄对决0.3:0.280.4可能性李林对决0.3:0.60.6可能性成功率0.73李和黄打林李黄对决0.3:0.40.7*0.4可能性李林对决0.3:0.7*0.6*0.70.7*0.6可能性成功率0.64
【4】一间囚房里关押着两个犯人。每天监狱都会为这间囚房提供一罐汤,让这两个犯人自己来分。起初,这两个人经常会发生争执,因为他们总是有人认为对方的汤比自己的多。后来他们找到了一个两全其美的办法:一个人分汤,让另一个人先选。于是争端就这么解决了。可是,现在这间囚房里又加进来一个新犯人,现在是三个人来分汤。必须寻找一个新的方法来维持他们之间的和平。该怎么办呢?按:心理问题,不是逻辑问题是让甲分汤,分好后由乙和丙按任意顺序给自己挑汤,剩余一碗留给甲。这样乙和丙两人的总和肯定是他们两人可拿到的最大。然后将他们两人的汤混合之后再按两人的方法再次分汤。
【5】在一张长方形的桌面上放了n个一样大小的圆形硬币。这些硬币中可能有一些不完全在桌面内,也可能有一些彼此重叠;当再多放一个硬币而它的圆心在桌面内时,新放的硬币便必定与原先某些硬币重叠。请证明整个桌面可以用4n个硬币完全覆盖。要想让新放的硬币不与原先的硬币重叠,两个硬币的圆心距必须大于直径。也就是说,对于桌面上任意一点,到最近的圆心的距离都小于2,所以,整个桌面可以用n个半径为2的硬币覆盖。把桌面和硬币的尺度都缩小一倍,那么,长、宽各是原桌面一半的小桌面,就可以用n个半径为1的硬币覆盖。那么,把原来的桌子分割成相等的4块小桌子,那么每块小桌子都可以用n个半径为1的硬币覆盖,因此,整个桌面就可以用4n个半径为1的硬币覆盖。
【6】一个球、一把长度大约是球的直径2/3长度的直尺.你怎样测出球的半径?方法很多,看看谁的比较巧妙
【7】五个大小相同的一元人民币硬币。要求两两相接触,应该怎么摆?底下放一个1,然后2 3放在1上面,另外的4 5竖起来放在1的上面。
【8】猜牌问题S先生、P先生、Q先生他们知道桌子的抽屉里有16张扑克牌:红桃A、Q、4黑桃J、8、4、2、7、3草花K、Q、5、4、6方块A、5。约翰教授从这16张牌中挑出一张牌来,并把这张牌的点数告诉P先生,把这张牌的花色告诉Q先生。这时,约翰教授问P先生和Q先生:你们能从已知的点数或花色中推知这张牌是什么牌吗?于是,S先生听到如下的对话:P先生:我不知道这张牌。Q先生:我知道你不知道这张牌。P先生:现在我知道这张牌了。Q先生:我也知道了。听罢以上的对话,S先生想了一想之后,就正确地推出这张牌是什么牌。请问:这张牌是什么牌? 方块5
【9】一个教授逻辑学的教授,有三个学生,而且三个学生均非常聪明!一天教授给他们出了一个题,教授在每个人脑门上贴了一张纸条并告诉他们,每个人的纸条上都写了一个正整数,且某两个数的和等于第三个!(每个人可以看见另两个数,但看不见自己的)教授问第一个学生:你能猜出自己的数吗?回答:不能,问第二个,不能,第三个,不能,再问第一个,不能,第二个,不能,第三个:我猜出来了,是144!教授很满意的笑了。请问您能猜出另外两个人的数吗?经过第一轮,说明任何两个数都是不同的。第二轮,前两个人没有猜出,说明任何一个数都不是其它数的两倍。现在有了以下几个条件:1.每个数大于02.两两不等3.任意一个数不是其他数的两倍。每个数字可能是另两个之和或之差,第三个人能猜出144,必然根据前面三个条件排除了其中的一种可能。假设:是两个数之差,即x-y=144。这时1(x,y>0)和2(x!=y)都满足,所以要否定x+y必然要使3不满足,即x+y=2y,解得x=y,不成立(不然第一轮就可猜出),所以不是两数之差。因此是两数之和,即x+y=144。同理,这时1,2都满足,必然要使3不满足,即x-y=2y,两方程联立,可得x=108,y=36。这两轮猜的顺序其实分别为这样:第一轮(一号,二号),第二轮(三号,一号,二号)。这样分大家在每轮结束时获得的信息是相同的(即前面的三个条件)。那么就假设我们是C,来看看C是怎么做出来的:C看到的是A的36和B的108,因为条件,两个数的和是第三个,那么自己要么是72要么是144(猜到这个是因为72的话,108就是36和72的和,144的话就是108和36的和。这样子这句话看不懂的举手):假设自己(C)是72的话,那么B在第二回合的时候就可以看出来,下面是如果C是72,B的思路:这种情况下,B看到的就是A的36和C的72,那么他就可以猜自己,是36或者是108(猜到这个是因为36的话,36加36等于72,108的话就是36和108的和):如果假设自己(B)头上是36,那么,C在第一回合的时候就可以看出来,下面是如果B是36,C的思路:这种情况下,C看到的就是A的36和B的36,那么他就可以猜自己,是72或者是0(这个不再解释了):如果假设自己(C)头上是0,那么,A在第一回合的时候就可以看出来,下面是如果C是0,A的思路:这种情况下,A看到的就是B的36和C的0,那么他就可以猜自己,是36或者是36(这个不再解释了),那他可以一口报出自己头上的36。(然后是逆推逆推逆推),现在A在第一回合没报出自己的36,C(在B的想象中)就可以知道自己头上不是0,如果其他和B的想法一样(指B头上是36),那么C在第一回合就可以报出自己的72。现在C在第一回合没报出自己的36,B(在C的想象中)就可以知道自己头上不是36,如果其他和C的想法一样(指C头上是72),那么B在第二回合就可以报出自己的108。现在B在第二回合没报出自己的108,C就可以知道自己头上不是72,那么C头上的唯一可能就是144了。史上最雷人的应聘者
【10】某城市发生了一起汽车撞人逃跑事件,该城市只有两种颜色的车,蓝15%绿85%,事发时有一个人在现场看见了,他指证是蓝车,但是根据专家在现场分析,当时那种条件能看正确的可能性是80%那么,肇事的车是蓝车的概率到底是多少?15%*80%/(85%×20%+15%*80%)
【11】有一人有240公斤水,他想运往干旱地区赚钱。他每次最多携带60公斤,并且每前进一公里须耗水1公斤(均匀耗水)。假设水的价格在出发地为0,以后,与运输路程成正比,(即在10公里处为10元/公斤,在20公里处为20元/公斤......),又假设他必须安全返回,请问,他最多可赚多少钱?f(x)=(60-2x)*x,当x=15时,有最大值450。450×4
【12】现在共有100匹马跟100块石头,马分3种,大型马;中型马跟小型马。其中一匹大马一次可以驮3块石头,中型马可以驮2块,而小型马2头可以驮一块石头。问需要多少匹大马,中型马跟小型马?(问题的关键是刚好必须是用完100匹马) 6种结果
【13】1=5,2=15,3=215,4=2145那么5=?
因为1=5,所以5=1.
【14】有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)!]。至于为什么不合格数是(2n)!/[(n-1)!(n+1)!],说起来太复杂,这里就不讲了。
【15】一个人花8块钱买了一只鸡,9块钱卖掉了,然后他觉得不划算,花10块钱又买回来了,11块卖给另外一个人。问他赚了多少?
2元
【16】有一种体育竞赛共含M个项目,有运动员A,B,C参加,在每一项目中,第一,第二,第三名分别的X,Y,Z分,其中X,Y,Z为正整数且X>Y>Z。最后A得22分,B与C均得9分,B在百米赛中取得第一。求M的值,并问在跳高中谁得第二名。
因为ABC三人得分共40分,三名得分都为正整数且不等,所以前三名得分最少为6分,40=5*8=4*10=2*2
0=1*20,不难得出项目数只能是5.即M=5.
A得分为22分,共5项,所以每项第一名得分只能是5,故A应得4个一名一个二名.22=5*4+2,第二名得1分,又B百米得第一,所以A只能得这个第二.
B的5项共9分,其中百米第一5分
,其它4项全是1分,9=5+1=1+1+1.即B除百米第一外全是第三,跳高第二必定是C所得.
【17】前提:
1 有五栋五种颜色的房子
2 每一位房子的主人国籍都不同
3 这五个人每人只喝一种饮料,只抽一种牌子的香烟,只养一种宠物
4 没有人有相同的宠物,抽相同牌子的香烟,喝相同的饮料
提示:1 英国人住在红房子里
2 瑞典人养了一条狗
3 丹麦人喝茶
4 绿房子在白房子左边
5 绿房子主人喝咖啡
6 抽PALL MALL烟的人养了一只鸟
7 黄房子主人抽DUNHILL烟
8 住在中间那间房子的人喝牛奶
9 挪威人住第一间房子
10 抽混合烟的人住在养猫人的旁边
11 养马人住在抽DUNHILL烟的人旁边
12 抽BLUE MASTER烟的人喝啤酒
13 德国人抽PRINCE烟
14 挪威人住在蓝房子旁边
15 抽混合烟的人的邻居喝矿泉水
问题是:谁养鱼???
第一间是黄房子,挪威人住,喝矿泉水,抽DUNHILL香烟,养猫;! f/ [% a: \6 L! J. Q9 x第二间是蓝房子,丹麦人住,喝茶,抽混合烟,养马;+ o8 _0 S) L8 i' E' u第三间是红房子,英国人住,喝牛奶,抽PALL MALL烟,养鸟;/ N9 o/ n2 M# U" c第四间是绿房子,德国人住,喝咖啡,抽PRINCE烟,养猫、马、鸟、狗以外的宠物;7 P5 l) G, G, |; C, {7 V第五间是白房子,瑞典人住,喝啤酒,抽BLUE MASTER烟,养狗。
【18】5个人来自不同地方,住不同房子,养不同动物,吸不同牌子香烟,喝不同饮料,喜欢不同食物。根据以下线索确定谁是养猫的人。
1. 红房子在蓝房子的右边,白房子的左边(不一定紧邻)
2. 黄房子的主人来自香港,而且他的房子不在最左边。
3. 爱吃比萨的人住在爱喝矿泉水的人的隔壁。
4. 来自北京的人爱喝茅台,住在来自上海的人的隔壁。
5. 吸希尔顿香烟的人住在养马人的右边隔壁。
6. 爱喝啤酒的人也爱吃鸡。
7. 绿房子的人养狗。
8. 爱吃面条的人住在养蛇人的隔壁。
9. 来自天津的人的邻居(紧邻)一个爱吃牛肉,另一个来自成都。
10.养鱼的人住在最右边的房子里。
11.吸万宝路香烟的人住在吸希尔顿香烟的人和吸“555”香烟的人的中间(紧邻)
12.红房子的人爱喝茶。
13.爱喝葡萄酒的人住在爱吃豆腐的人的右边隔壁。
14.吸红塔山香烟
的人既不住在吸健牌香烟的人的隔壁,也不与来自上海的人相邻。
15.来自上海的人住在左数第二间房子里。
16.爱喝矿泉水的人住在最中间的房子里。
17.爱吃面条的人也爱喝葡萄酒。
18.吸“555”香烟的人比吸希尔顿香烟的人住的靠右
第
一间是兰房子,住北京人,养马,抽健牌香烟,喝茅台,吃豆腐;2 G7 x% z0 v; C第二间是绿房子,住上海人,养狗,抽希尔顿,喝葡萄酒,吃面条;% C2 k4 o8 t" p6 L* x第三间是黄房子,住香港人,养蛇,抽万宝路,喝矿泉水,吃牛肉;& N" S% x# o3 a; g第四间是红房子,住天津人,抽555,喝茶,吃比萨;7 \5 s. J# d, Q/ N% N' O# ]第五间是白房子,住成都人,养鱼,抽红塔山,喝啤酒,吃鸡。
【19】斗地主附残局
地主手中牌2、K、Q、J、10、9、8、8、6、6、5、5、3、3、3、3、7、7、7、7
长工甲手中牌大王、小王、2、A、K、Q、J、10、Q、J、10、9、8、5、5、4、4
长工乙手中牌2、2、A、A、A、K、K、Q、J、10、9、9、8、6、6、4、4
三家都是明手,互知底牌。要求是:在三家都不打错牌的情况下,地主必须要么输要么赢。问:哪方会赢?
无解地主怎么出都会输
【20】一楼到十楼的每层电梯门口都放着一颗钻石,钻石大小不一。你乘坐电梯从一楼到十楼,每层楼电梯门都会打开一次,只能拿一次钻石,问怎样才能拿到最大的一颗?
先拿下第一楼的钻石,然后在每一楼把手中的钻石与那一楼的钻石相比较,如果那一楼的钻石比手中的钻石大的话那就把手中的钻石换成那一层的钻石。
【21】U2合唱团在17分钟 内得赶到演唱会场,途中必需跨过一座桥,四个人从桥的同一端出发,你得帮助他们到达另一端,天色很暗,而他们只有一只手电筒。一次同时最多可以有两人一起 过桥,而过桥的时候必须持有手电筒,所以就得有人把手电筒带来带去,来回桥两端。手电筒是不能用丢的方式来传递的。四个人的步行速度各不同,若两人同行则 以较慢者的速度为准。Bono需花1分钟过桥,Edge需花2分钟过桥,Adam需花5分钟过桥,Larry需花10分钟过桥。他们要如何在17分钟内过 桥呢?
2+1先过 2
然后1回来送手电筒 1
5+10再过 10
2回来送手电筒 2
2+1过去 2
总共2+1+10+2+2=17分钟
【22】一个家庭有两个小孩,其中有一个是女孩,问另一个也是女孩的概率(假定生男生女的概率一样) 1/3
样本空间为(男男)(女女)(男女)(女男)
A=(已知其中一个是女孩)=)(女女)(男女)(女男)
B=(另一个也是女孩)=(女女)
于是P(B/A)=P(AB)/P(A)=(
1/4)/(3/4)=1/3
【23】为什么下水道的盖子是圆的?
不会掉下去
【24】有7克、2克砝码各一个,天平一只,如何只用这些物品三次将140克的盐分成50、90克各一份?
140->70+70 70->35+35
35+70=105
105->50+7 + 55+2
55+35=90
【25】芯片测试:有2k块芯片,已知好芯片比坏芯片多.请设计
算法从其中找出一片 好芯片,说明你所用的比较次数上限. 其中:好芯片和其它芯片比较时,能正确给出另一块芯片是好还是坏. 坏芯片和其它芯片比较时,会随机的给出好或是坏。
把第一块芯片与其它逐一对比,看看其它芯片对第一块芯片给出的是好是坏,如果给出是好的过半,那么说明这是好芯片,完毕。如果给出的是坏的过半,说明第一块芯片是坏的,那么就要在那些在给出第一块芯片是坏的芯片中,重复上述步骤,直到找到好的芯片为止。
【26】12个球一个天平,现知道只有一个和其它的重量不同,问怎样称才能用三次就找到那个球。13个呢?(注意此题并未说明那个球的重量是轻是重)
12个时可以找出那个是重还是轻,13个时只能找出是哪个球,轻重不知。
把球编为①②③④⑤⑥⑦⑧⑨⑩⑾⑿。(13个时编号为⒀)
第一次称:先把①②③④与⑤⑥⑦⑧放天平两边,
㈠如相等,说明特别球在剩下4个球中。
把①⑨与⑩⑾作第二次称量,
⒈如相等,说明⑿特别,把①与⑿作第三次称量即可判断是⑿是重还是轻
⒉如①⑨<⑩⑾说明要么是⑩⑾中有一个重的,要么⑨是轻的。
把⑩与⑾作第三次称量,如相等说明⑨轻,不等可找出谁是重球。
⒊如①⑨>⑩⑾说明要么是⑩⑾中有一个轻的,要么⑨是重的。
把⑩与⑾作第三次称量,如相等说明⑨重,不等可找出谁是轻球。
㈡如左边<右边,说明左边有轻的或右边有重的
把①②⑤与③④⑥做第二次称量
⒈如相等,说明⑦⑧中有一个重,把①与⑦作第三次称量即可判断是⑦与⑧中谁是重球
⒉如①②⑤<③④⑥说明要么是①②中有一个轻的,要么⑥是重的。
把①与②作第三次称量,如相等说明⑥重,不等可找出谁是轻球。
⒊如①②⑤>③④⑥说明要么是⑤是重的,要么③④中有一个是轻的。
把③与④作第三次称量,如相等说明⑤重,不等可找出谁是轻球。
㈢如左边>右边,参照㈡相反进行。
当13个球时,第㈠步以后如下进行。
把①⑨与⑩⑾作第二次称量,
⒈如相等,说明⑿⒀特别,把①与⑿作第三次称量即可判断是⑿还是⒀特别,但判断不了轻重了。
⒉不等的情况参见第㈠步的⒉⒊
【27】100个人回答五道试题,有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人!
【28】陈奕迅有首歌叫十年吕珊有首歌叫3650夜那现在问,十年可能有多少天?
十年可能包含2-3个闰年,3652或3653天。
1900年这个闰年就是28天,1898~1907这10年就是3651天,闰年如果是整百的倍数,如1800,1900,那么这个数必须是400的倍数才有29天,比如1900年2月有28天,2000年2月有29天。
【29】1,11,21,1211,111221,下一个数是什么?
下行是对上一行的解释 所以新的应该是3个1 2个2 1个1 :312211
【30】烧一根不均匀的绳要用一个小时,如何用它来判断半个小时?烧一根不均匀的绳,从头烧到尾总共需要1个小时。现在有若干条材质相同的绳子,问如何用烧绳的方法来计时一个小时十五分钟呢? (微软的笔试题)
一,一根绳子从两头烧,烧完就是半个小时。
二,一根要一头烧,一根从两头烧,两头烧完的时候(30分),将剩下的一根另一端点着,烧尽就是45分钟。再从两头点燃第三根,烧尽就是1时15分。
【31】共有三类药,分别重
1g,2g,3g,放到若干个瓶子中,现在能确定每个瓶子中只有其中一种药,且每瓶中的药片足够多,能只称一次就知道各个瓶子中都是盛的哪类药吗?如果有4类药呢?5类呢?N类呢(N可数)?如果是共有m个瓶子盛着n类药呢(m,n为正整数,药的质量各不相同但各种药的质量已知)?你能只称一次就知道每瓶的药是什么吗?
注:当然是有代价的,称过的药我们就不用了
第一个瓶子拿出一片,第二
个瓶子拿出四片,第三个拿出十六片,……第m个拿出n+1的m-1次方片。把所有这些药片放在一起称重量。
【32】假设在桌上有三个密封的盒,一个盒中有2枚银币(1银币=10便士),一个盒中有2枚镍币(1镍币=5便士),还有一个盒中有1枚银币和1枚镍币。这些盒子被标上10便士、 15便士和20便士,但每个标签都是错误的。允许你从一个盒中拿出1枚硬币放在盒前,看到这枚硬币,你能否说出每个盒内装的东西呢?
取出标着15便士的盒中的一个硬币,如果是银的说明这个盒是20便士的,如果是镍的说明这个盒是10便士的,再由每个盒的标签都是错误的可以推出其它两个盒里的东西。
【33】有一个大西瓜,用水果刀平整地切,总共切9刀,最多能切成多少份,最少能切成多少份?主要是过程,结果并不是最重要的
最少10,最多130
见下表,表中蓝色部分服从2为底的指数函数规律,红色部分的数值均为其左边与左上角的两个数之和。
x 0 1 2 3 4 5 6 7 8 9
x个点最多能把直线分成多少部分 1 2 3 4 5 6 7 8 9 10
x条直线最多能把平面分成多少部分 1 2 4 7 11 16 22 29 37 46
x个平面最多能把空间分成多少部分 1 2 4 8 15 26 42 64 93 130
【34】一个巨大的圆形水池,周围布满了老鼠洞。猫追老鼠到水池边,老鼠未来得及进洞就掉入水池里。猫继续沿水池边缘企图捉住老鼠(猫不入水)。已知V猫=4V鼠。问老鼠是否有办法摆脱猫的追逐?
第一步:游到水池中心。
第二步:从水池中心游到距中心R/4处,并始终保持鼠、水池中心、猫在一直线上。
第三步:沿与中心相反方向的直线游3R/4就可以到达水池边,而猫沿圆周到达那里需要3.14R,所以捉不到老鼠。
三个阶段如下图所示:
[/url] 【35】有三个桶,两个大的可装8斤的水,一个小的可装3斤的水,现在有16斤水装满了两大桶就是8斤的桶,小桶空着,如何把这16斤水分给4个人,每人4斤。没有其他任何工具,4人自备容器,分出去的水不可再要回来。
表示为880,接下来,将一个大桶的水倒入小桶中,倒满,表示为853,(第2个大桶减3,小桶加3)则过程如下:
880——853:将3斤给第1个人,变为850(此时
4人分别有水3-0-0-0)
850——823:将2斤给第2个人,变为803(此时4人分别有水3-2-0-0)
803——830——533——560——263——281:将1斤给第1个人,变为280(此时4人分别有水4-2-0-0)
280——253——703——730——433——460——163:将1斤给第3个人,变为063(此时4人分别有水4-2-1-0)
063——081:将1斤给第4个人,变为080(此时4人分别有水4-2-1-1)
080——053——350——323:将2斤给第2个人,将2个3斤分别给第3、4个人,(此时4人分别有水4
-4-4-4)
【36】从前有一位老钟表匠,为一个教堂装一只大钟。他年老眼花,把长短针装配错了,短针走的速度反而是长针的12倍。装配的时候是上午6点,他把短针指在“6 ”上,长针指在“12”上。老钟表匠装好就回家去了。人们看这钟一会儿7点,过了不一会儿就8点了,都很奇怪,立刻去找老钟表匠。等老钟表匠赶到,已经是下午7点多钟。他掏出怀表来一对,钟准确无误,疑心人们有意捉弄他,一生气就回去了。这钟还是8点、9点地跑,人们再去找钟表匠。老钟表匠第二天早晨8点多赶来用表一对,仍旧准确无误。请你想一想,老钟表匠第一次对表的时候是7点几分?第二次对表又是8点几分?
7点x分:(7+x/60)/12=x/60 x=7*60=420/11=38.2
第一次是7点38分,第二次是8点44分
【37】今有2匹马、3头牛和4只羊,它们各自的总价都不满10000文钱(古时的货币单位)。如果2匹马加上1头牛,或者3 头牛加上1只羊,或者4只羊加上1匹马,那么它们各自的总价都正好是10000文钱了。问:马、牛、羊的单价各是多少文钱?
3600 2800 1600
【38】一天,harlan的店里来了一位顾客,挑了25元的货,顾客拿出100元,harlan没零钱找不开,就到隔壁飞白的店里把这100元换成零钱,回来给顾客找了75元零钱。过一会,飞白来找harlan,说刚才的是假钱,harlan马上给飞白换了张真钱,问harlan赔了多少钱?
100
【39】猴子爬绳这道力学怪题乍看非常简单,可是据说它却使刘易斯.卡罗尔感到困惑。至于这道怪题是否由这位因《爱丽丝漫游奇境记》而闻名的牛津大学数学专家提出来的,那就不清楚了。总之,在一个不走运的时刻,他就下述问题征询人们的意见:一根绳子穿过无摩擦力的滑轮,在其一端悬挂着一只10磅重的砝码,绳子的另一端有只猴子,同砝码正好取得平衡。当猴子开始向上爬时,砝码将如何动作呢?"真奇怪,"卡罗尔写道,"许多优秀的数学家给出了截然不同的答案。普赖斯认为砝码将向上升,而且速度越来越快。克利夫顿(还有哈考特)则认为,砝码将以与猴子一样的速度向上升起,然而桑普
森却说,砝码将会向下降!"一位杰出的机械工程师说"这不会比苍蝇在绳子上爬更起作用",而一位科学家却认为"砝码的上升或下降将取决于猴子吃苹果速度的倒数",然而还得从中求出猴子尾巴的平方根。严肃地说,这道题目非常有趣,值得认真推敲。它很能说明趣题与力学问题之间的紧密联系。
砝码将以与猴子相同的速度上升,因为它们质量相同,受力也相同。
【40】两个空心球,大小及重量相同,但材料不同。一个是金,一个是铅。空心球表面图有相同颜色的油漆。现在
要求在不破坏表面油漆的条件下用简易方法指出哪个是金的,哪个是铅的。
旋转看速度,金的密度大,质量相同,所以金球的实际体积较小,因为外半径相同,所以金球的内半径较大,所以金球的转动惯量大,在相同的外加力矩之下,金球的角加速度较小,所以转得慢。
【41】有23枚硬币在桌上,10枚正面朝上。假设别人蒙住你的眼睛,而你的手又摸不出硬币的反正面。让你用最好的方法把这些硬币分成两堆,每堆正面朝上的硬币个数相同。
分成10+13两堆, 然后翻转10的那堆
【42】三个村庄A、B、C和三个城镇A、B、C坐落在如图所示的环形山内。由于历史原因,只有同名的村与镇之间才有来往。为方便交通,他们准备修铁路。问题是:如何在这个环形山内修三条铁路连通A村与A镇, B村与B镇,C村与C镇。而这些铁路相互不能相交。(挖山洞、修立交桥都不算,绝对是平面问题)。想出答案再想想这个题说明什么问题。
答案如右图:
【43】屋里三盏灯泡,屋外三个开关,一个开关仅控制一盏灯,屋外看不到屋里怎样只进屋一次,就知道哪个开关控制哪盏灯?四盏呢~
温度,先开一盏,足够长时间后关了,开另一盏,进屋看,亮的为后来开的,摸起来热的为先开的,剩下的一盏也就确定了。
四盏的情况:设四个开关为ABCD,先开AB,足够长时间后关B开C,然后进屋,又热又亮为A,只热不亮为B,只亮不热为C,不亮不热为D。
【44】2+7-2+7全部有火柴根组成,移动其中任何一根,答案要求为30说明:因为书写问题作如下解释,2是由横折横三根组成,7是由横折两根组成
1, 改变赋值号.比如+,-,=
2, 注意质数.
3, 可能把画面颠倒过来.
4, 然后就可以去考虑更改其他数字更改了
247-217=30
【45】5名海盗抢得了窖藏的100块金子,并打算瓜分这些战利品。这是一些讲民主的海盗(当然是他们自己特有的民主),他们的习惯是按下面的方式进行分配:最厉害的一名海盗提出分配方案,然后所有的海盗(包括提出方
案者本人)就此方案进行表决。如果50%或更多的海盗赞同此方案,此方案就获得通过并据此分配战利品。否则提出方案的海盗将被扔到海里,然后下一名最厉害的海盗又重复上述过程。所有的海盗都乐于看到他们的一位同伙被扔进海里,不过,如果让他们选择的话,他们还是宁可得一笔现金。他们当然也不愿意自己被扔到海里。所有的海盗都是有理性的,而且知道其他的海盗也是有理性的。此外,没有两名海盗是同等厉害的——这些海盗按照完全由上到下的等级排好了座次,并且每个人都清楚自己和其他所有人的等级。这些金块不能再分
,也不允许几名海盗共有金块,因为任何海盗都不相信他的同伙会遵守关于共享金块的安排。这是一伙每人都只为自己打算的海盗。最凶的一名海盗应当提出什么样的分配方案才能使他获得最多的金子呢?
如果轮到第四个海盗分配:100,0
轮到第三个:99,0,1
轮到第二个:98,0,1,0
轮到第一个:97,0,1,0,2,这就是第一个海盗的最佳方案。
【46】他们中谁的存活机率最大?
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号选择一个
下面决定的就是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号生存机会最大。
【47】有5只猴子在海边发现 一堆桃子,决定第二天来平分.第二天清晨,第一只猴子最早来到,它左分右分分不开,就朝海里扔了一只,恰好可以分成5份,它拿上自己的一份走了.第 2,3,4,5只猴子也遇到同样的问题,采用了同样的方法,都是扔掉一只后,恰好可以分成5份.问这堆桃子至少有多少只?
这堆桃子至少有3121只。
第一只猴子扔掉1个,拿走624个,余2496个;
第二只猴子扔掉1个,拿走499个,余1996个;
第三只猴子扔掉1个,拿走399个,余1596个;
第四只猴
子扔掉1个,拿走319个,余1276个;
第五只猴子扔掉1个,拿走255个,余4堆,每堆255个。
如果不考虑正负,-4为一解
考虑到要5个猴子分,假设分n次。
则题目的解: 5^n-4
本题为5^5-4=3121.
设共a个桃,剩下b个桃,则b=(4/5)((4/5)((4/5)((4/5)((4/5)(a-1)-1)-1)-1)-1)-1),即b=(1024a-8404)/3125 ; a=3b+8+53*(b+4)/1024,而53跟1024不可约,则令b=1020可有最小解,得a=3121 ,设桃数x,得方程
4/5{4/5{4/5[4/5(x-1)-1]-1}-1}=5n
展开得
256x=3125n+2101
故x=(3125n+2101)/256=12n+8+53*(n+1)/256
因为53与256不可约,所以判断n=255有一解.x为整数,等于3121
【48】话说某天一艘海盗船被天下砸下来的一头牛给击中了,5个倒霉的家伙只好逃难到一个孤岛,发现岛上孤零零的,幸好有有棵椰子树,还有一只猴子!大家把椰子全部采摘下来放在一起,但是天已经很晚了,所以就睡觉先.
晚上某个家伙悄悄的起床,悄悄的将椰子分成5份,结果发现多一个椰子,顺手就给了幸运的猴子,然后又悄悄的藏了一份,然后把剩下的椰子混在一起放回原处,最后还是悄悄滴回去睡觉了.
过了会儿,另一个家伙也悄悄的起床,悄悄的将剩下的椰子分成5份,结果发现多一个椰子,顺手就又给了幸运的猴子,然后又悄悄滴藏了一份,把剩下的椰子混在一起放回原处,最后还是悄悄滴回去睡觉了.
又过了一会 ......
又过了一会 ...
总之5个家伙都起床过,都做了一样的事情。早上大家都起床,各自心怀鬼胎的分椰子了,这个猴子还真不是一般的幸运,因为这次把椰子分成5分后居然还是多一个椰子,只好又给它了.问题来了,这堆椰子最少有多少个?
这堆椰子最少有15621
第一个人给了猴子1个,藏了3124个,还剩12496个;
第二个人给了猴子1个,藏了2499个,还剩9996个;
第三个人给了猴子1个,藏了1999个,还剩7996个;
第四个人给了猴子1个,藏了1599个,还剩6396个;
第五个人给了猴子1个,藏了1279个,还剩5116个;
最后大家一起分成5份,每份
1023个,多1个,给了猴子。
【49】小明和小强都是张老师的学生,张老师的生日是M月N日,2人都知道张老师的生日是下列10组中的一天,张老师把M值告诉了小明,把N值告诉了小强,张老师问他们知道他的生日是那一天吗?
3月4日 3月5日 3月8日
6月4日 6月7日
9月1日 9月5日
12月1日 12月2日 12月8日
小明说:如果我不知道的话,小强肯定也不知道
小强说:本来我也不知道,但是现在我知道了
小明说:哦,那我也知道了
请根据以上对话推断出张老师的生日是哪一天
9.1
【50】一逻辑学家误入某部落,被囚于牢狱,酋长欲意放行,他对逻辑学家说:“今有两门,一为自由,一为死亡,你可任意开启一门。现从两
个战士中选择一人负责解答你所提的任何一个问 题(Y/N),其中一个天性诚实,一人说谎成性,今后生死任你选择。”逻辑学家沉思片刻,即向一战士发问,然后开门从容离去。逻辑学家应如何发问?
问:如果我问另一个人死亡之门在哪里,他会怎么回答?
最终得到的回答肯定是指向自由之门的。
【51】说从前啊,有一个富 人,他有30个孩子,其中15个是已故的前妻所生,其余15个是继室所生,这后一个妇人很想让她自己所生的最年长的儿子继承财产,于是,有一天,他就向他 说:"亲爱的丈夫啊,你就要老了,我们应该定下来谁将是你的继承人,让我们把我们的30个孩子排成一个圆圈,从他们中的一个数起,每逢到10就让那个孩子 站出去,直到最后剩下哪个孩子,哪个孩子就继承你的财产吧!"富人一想,我靠,这个题意相当有内涵了,不错,仿佛很公平,就这么办吧~不过,当剔选过程不 断进行下去的时候,这个富人傻眼了,他发现前14个被剔除的孩子都是前妻生的,而且下一个要被剔除的还是前妻生的,富人马上大手一挥,停,现在从这个孩子 倒回去数, 继室,就是这个歹毒的后妈一想,倒数就倒数,我15个儿子还斗不过你一个啊~她立即同意了富人的动议,你猜,到底谁做了继承人呢~
老婆的儿子
【52】“有一牧场,已知养牛27头,6天把草吃尽;养牛23头,9天把草吃尽。如果养牛21头,那么几天能把牧场上的草吃尽呢?并且牧场上的草是不断生长的。”
设牛每天吃掉x,草每天长出y,原来有牧场的草量是a
a=(27x-y)*6=(23x-y)*9
可解出y=15x,a=72x,所以a=(21x-y)*12,所以需要12天。
【53】一个商人骑一头驴要穿越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根。
【54】10箱黄金,每箱100块,每块一两。有贪官,把某一箱的每块都磨去一钱。请称一次找到不足量的那个箱子
第一箱子拿1块,第二箱子拿2块, 第n箱子拿n块,然后放在一起称,看看缺了几钱,缺了n钱就说明是第n个箱子
【55】你让工人为你工作7天,给工人的回报是一根金条。金条平分成
相连的7段,你必须在每天结束时都付费,如果只许你两次把金条弄断,你如何给你的工人付费?
把金条分成1,2,4三段。第一天1,第二天2,第三天1+2……第七天1+2+4。
【56】有十瓶药,每瓶里都装有100片药(仿佛现在装一百片的少了,都是十片二十片的,不管,咱们就这么来了),其中有八瓶里的药每片重10克,另有两瓶里的药每片重9克。用一个蛮精确的小秤,只称一次,如何找出份量较轻的那两个药瓶?
等同54,但此题有一些变化,与众不同的瓶子有两个,只称一次的话,只能得到两个瓶子所缺的克数的总和,我们必须保证能从总和中唯一地得出两个瓶子的所缺数。第一个瓶可拿出1片,第二个拿2片,第三个拿3片,但第四个不能拿4片,因为如果结果缺了5克的话,你就不知道是缺了2+3还是1+4。所以第四个应拿5片,第五个应拿8片,第n个应拿a(n-1)+a(n-2)片。
【57】一个经理有三个女儿, 三个女儿的年龄加起来等于13,三个女儿的年龄乘起来等于经理自己的年龄,有一个下属已知道经理的年龄,但仍不能确定经理三个女儿的年龄,这时经理说只有,一个女儿的头发是黑的,然后这个下属就知道了经理三个女儿的年龄。请问三个女儿的年龄分别是多少?为什么?
显然3个女儿的年龄都不为0,要不爸爸就为0岁了,因此女儿的年龄都大于等于1岁。这样可以得下面的情况:1*1*11=11,1*2**10=20,1*3*9=27,1*4*8=32,1*5*7=35,{1*6*6=36},{2*2*9=36},2*3*8=48,2*4*7=56,2*5*6=60,3*3*7=63,3*4*6=72,3*5*5=75,4*4*5=80因为下属已知道经理的年龄,但仍不能确定经理三个女儿的年龄,说明经理是36岁(因为{1*6*6=36},{2*2*9=36}),所以3个女儿的年龄只有2种情况,经理又说只有一个女儿的头发是黑的,说明只有一个女儿是比较大的,其他的都比较小,头发还没有长成
黑色的,所以3个女儿的年龄分别为2,2,9!
【58】有三个人去住旅馆,住 三间房,每一间房?元,于是他们一共付给老板?,第二天,老板觉得三间房只需要?元就够了于是叫小弟退回?给三位客人,谁知小弟贪心,只退 回每人?,自己偷偷拿了ū,这样一来便等于那三位客人每人各花了九元,于是三个人一共花了?,再加上小弟独吞了不ū,总共是?。可是当初他 们三个人一共付出?那么还有?呢?
应该是三个人付了9*3=27,其中2付给了小弟,25付给了老板
【59】有两位盲人,他们都各自买了两对黑袜和两对白袜,八对袜了的布质、大小完全相同,而每对袜了都有一张商标纸连着。两位盲人不小心将八对袜了混在一起。他们每人怎样才能取回黑袜和白袜各两对呢?
拆开所有的袜子,每人一个
【60】有一辆火车
以每小时 15公里的速度离开洛杉矶直奔纽约,另一辆火车以每小时20公里的速度从纽约开往洛杉矶。如果有一只鸟,以30公里每小时的速度和两辆火车同时启动,从洛杉矶出发,碰到另一辆车后返回,依次在两辆火车来回飞行,直到两辆火车相遇,请问,这只小鸟飞行了多长距离?
设总距离为d,总共用时d/(15+20),两车相遇,所以鸟飞了30*d/(15+20)=6d/7
【61】你有两个罐子,每个罐子各有若干红色弹球和蓝色弹球,两个罐子共有50个红色弹球,50个蓝色弹球,随机选出一个罐子,随机从中选取出一个弹球,要使取出的是红球的概率最大,一开始两个罐子应放几个红球,几个蓝球?在你的计划中,得到红球的准确几率是多少?
一个罐子放1红,一个罐子放49红和50蓝,这样得到红球的概率接近3/4。
【62】你有四个装药丸的罐子,每个药丸都有一定的重量,被污染的药丸是没被污染的重量+1.只称量一次,如何判断哪个罐子的药被污染了?
与前面的54,56题相似。
【63】对一批编号为1~100,全部开关朝上(开)的灯进行以下操作:凡是1的倍数反方向拨一次开关;2的倍数反方向又拨一次开关;3的倍数反方向又拨一次开关……问:最后为关熄状态的灯的编号。
1 4 9
【64】想象你在镜子前,请问,为什么镜子中的影像可以颠倒左右,却不能颠倒上下?
实际上镜子并没有颠倒左右,而是颠倒前后。
【65】一群人开舞会,每人头 上都戴着一顶帽子。帽子只有黑白两种,黑的至少有一顶。每个人都能看到其它人帽子的颜色,却看不到自己的。主持人先让大家看看别人头上戴的是什幺帽子,然 后关灯,如果有人认为自己戴的是黑帽子,就打自己一个耳光。第一次关灯,没有声音。于是再开灯,大家再看一
遍,关灯时仍然鸦雀无声。一直到第三次关灯,才 有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子?
3 。如果只有1人戴黑帽子,那么第一次关灯他就会打自己耳光;如果有2人,第二次关灯他们就会打自己耳光;有n人戴帽子的话第n次关灯他们就会打自己耳光。
【66】两个圆环,半径分别是1和2,小圆在大圆内部绕大圆圆周一周,问小圆自身转了几周?如果在大圆的外部,小圆自身转几周呢?
把大圆剪断拉直。小圆绕大圆圆周一周,就变成从直线的一头滚至另一头。因为直线长就是大圆的周长,是小圆周长的2倍,所以小圆要滚动2圈。
但是现在小圆不是沿直线而是沿大圆滚动,小圆因此还同时作自转,当小圆沿大圆滚动1周回到原出发点时,小圆同时自转1周。当小圆在大圆内部滚动时自转的方向与滚动的转向相反,所以小圆自身转了
1周。当小圆在大圆外部滚动时自转的方向与滚动的转向相同,所以小圆自身转了3周。
这一题非常有迷惑性,小圆在外部时其实是3圈,你可以拿个硬币试试可以把圆看成一根绳子,长绳是短绳的2倍长,假设长绳开始接口在最底下,短绳接口在长绳接口处,然后短绳开始顺时针绕,当短绳接口对着正左时,这时其实才绕了长绳的1/4,转了180+90度,所以绕一圈是270*4=360*3 。同理小圆在内部时是1圈。也可以套用下列公式: 两圆圆心距/转动者半径=转动者切另一圆时的自转数!!
【67】 1元钱一瓶汽水,喝完后两个空瓶换一瓶汽水,问:你有20元钱,最多可以喝到几瓶汽水?
40瓶,20+10+5+2+1+1=39, 这时还有一个空瓶子,先向店主借一个空瓶,换来一瓶汽水喝完后把空瓶还给店主。
【68】有3顶红帽子,4顶黑 帽子,5顶白帽子。让10个人从矮到高站成一队,给他们每个人头上戴一顶帽子。每个人都看不见自己戴的帽子的颜色,却只能看见站在前面那些人的帽子颜色。 (所以最后一个人可以看见前面9个人头上帽子的颜色,而最前面那个人谁的帽子都看不见。现在从最后那个人开始,问他是不是知道自己戴的帽子颜色,如果他回 答说不知道,就继续问他前面那个人。假设最前面那个人一定会知道自己戴的是黑帽子。为什么?
“有3顶黑帽子,2顶白帽子。让三个人从前到后站成一排,给他们每个人头上戴一顶帽子。每个人都看不见自己戴的帽子的颜色,却只能看见站在前面那些人的帽子颜色。(所以最后一个人可以看见前面两个人头上帽子的颜色,中间那个人看得见前面那个人的帽子颜色但看不见在他后面那个人的帽子颜色,而最前面那个人谁的帽子都看不见。现
在从最后那个人开始,问他是不是知道自己戴的帽子颜色,如果他回答说不知道,就继续问他前面那个人。事实上他们三个戴的都是黑帽子,那么最前面那个人一定会知道自己戴的是黑帽子。为什么?”
答案是,最前面的那个人听见后面两个人都说了“不知道”,他假设自己戴的是白帽子,于是中间那个人就看见他戴的白帽子。那么中间那个人会作如下推理:“假设我戴了白帽子,那么最后那个人就会看见前面两顶白帽子,但总共只有两顶白帽子,他就应该明白他自己戴的是黑帽子,现在他说不知道,就说明我戴了白帽子这个假定是错的,所以我戴了黑帽子。”问题是中间那人也说不知道,所以最前面那个人知道自己戴白帽子的假定是错的,所以他推断出自己戴了黑帽子。
我们把这个问题推广成如下的形式:
“有若干种颜色的帽子,每种若干顶。假设有若干个人从
前到后站成一排,给他们每个人头上戴一顶帽子。每个人都看不见自己戴的帽子的颜色,而且每个人都看得见在他前面所有人头上帽子的颜色,却看不见在他后面任何人头上帽子的颜色。现在从最后那个人开始,
问他是不是知道自己戴的帽子颜色,如果他回答说不知道,就继续问他前面那个人。一直往前问,那么一定有一个人知道自己所戴的帽子颜色。”
当然要假设一些条件:
1)首先,帽子的总数一定要大于人数,否则帽子都不够戴。
2)“有若干种颜色的帽子,每种若干顶,有若干人”这个信息是队列中所有人都事先知道的,而且所有人都知道所有人都知道此事,所有人都知道所有人都知道所有人都知道此事,等等等等。但在这个条件中的“若干”不一定非要具体一一给出数字来。
这个信息具体地可以是象上面经典的形式,列举出每种颜色帽子的数目“有3顶黑帽子,2顶白帽子,3个人”,也可以是“有红黄绿三种颜色的帽子各1顶2顶3顶,但具体不知道哪种颜色是几顶,有6个人”,甚至连具体人数也可以不知道,“有不知多少人排成一排,有黑白两种帽子,每种帽子的数目都比人数少1”,这时候那个排在最后的人并不知道自己排在最后——直到开始问他时发现在他回答前没有别人被问到,他才知道他在最后。在这个帖子接下去的部分当我出题的时候我将只写出“有若干种颜色的帽子,每种若干顶,有若干人”这个预设条件,因为这部分确定了,题目也就确定了。
3)剩下的没有戴在大家头上的帽子当然都被藏起来了,队伍里的人谁都不知道都剩下些什么帽子。
4)所有人都不是色盲,不但不是,而
且只要两种颜色不同,他们就能分别出来。当然他们的视力也很好,能看到前方任意远的地方。他们极其聪明,逻辑推理是极好的。总而言之,只要理论上根据逻辑推导得出来,他们就一定推导得出来。相反地如果他们推不出自己头上帽子的颜色,任何人都不会试图去猜或者作弊偷看——不知为不知。
5)后面的人不能和前面的人说悄悄话或者打暗号。
当然,不是所有的预设条件都能给出一个合理的题目。比如有99顶黑帽子,99顶白帽子,2个人,无论怎么戴,都不可能有人知道自己头上帽子的颜色。另外,只要不是只有一种颜色的帽子,在只由一个人组成的队伍里,这个人也是不可能说出自己帽子的颜色的。
但是下面这几题是合理的题目:
1)3顶红帽子,4顶黑帽子,5顶白帽子,10个人。
2)3顶红帽子,4顶黑帽子,5顶白帽子,8个人。
3)n顶黑帽子,n-1顶白帽子,n个人(n>0)。
4)1顶颜色1的帽子,2顶颜色2的帽子,…
…,99顶颜色99的帽子,100顶颜色100的帽子,共5000个人。
5)有红黄绿三种颜色的帽子各1顶2顶3顶,但具体不知道哪种颜色是几顶,有6个人。
6)有不知多少人(至少两人)排成一排,有黑白两种帽子,每种帽子的数目都比人数少1。
大家可以先不看我下面的分析,试着做做这几题。
如果按照上面3顶黑帽2顶白帽时的推理方法去做,那么10个人就可以把我们累死,别说5000个人了。但是3)中的n是个抽象的数,考虑一下怎么解决这个问题,对解决一般的问题大有好处。
假设现在n个人都已经戴好了帽子,问排在最后的那一个人他头上的帽子是什么颜色,什么时候他会回答“知道”?很显然,只有在他看见前面n-1个人都戴着白帽时才可能,因为这时所有的n-1顶白帽都已用光,在他自己的脑袋上只能顶着黑帽子,只要前面有一顶黑帽子,那么他就无法排除自己头上是黑帽子的可能——即使他看见前面所有人都是黑帽,他还是有可能戴着第n顶黑帽。
现在假设最后那个人的回答是“不知道”,那么轮到问倒数第二人。根据最后面那位的回答,他能推断出什么呢?如果他看见的都是白帽,那么他立刻可以推断出自己戴的是黑帽——要是他也戴着白帽,那么最后那人应该看见一片白帽,问到他时他就该回答“知道”了。但是如果倒数第二人看见前面至少有一顶黑帽,他就无法作出判断——他有可能戴着白帽,但是他前面的那些黑帽使得最后那人无法回答“知道”;他自然也有可能戴着黑帽。
这样的推理可以继续下去,但是我们已经看出了苗头。最后那个人可
以回答“知道”当且仅当他看见的全是白帽,所以他回答“不知道”当且仅当他至少看见了一顶黑帽。这就是所有帽子颜色问题的关键!
如果最后一个人回答“不知道”,那么他至少看见了一顶黑帽,所以如果倒数第二人看见的都是白帽,那么最后那个人看见的至少一顶黑帽在哪里呢?不会在别处,只能在倒数第二人自己的头上。这样的推理继续下去,对于队列中的每一个人来说就成了:
“在我后面的所有人都看见了至少一顶黑帽,否则的话他们就会按照相同的判断断定自己戴的是黑帽,所以如果我看见前面的人戴的全是白帽的话,我头上一定戴着我身后那个人看见的那顶黑帽。”
我们知道最前面的那个人什么帽子都看不见,就不用说看见黑帽了,所以如果他身后的所有人都回答说“不知道”,那么按照上面的推理,他可以确定自己戴的是黑帽,因为他身后的人必定看见了一顶黑帽——只能是第一个人他自己头上的那顶。事实上很明显,第一个说
出自己头上是什么颜色帽子的那个人,就是从队首数起的第一个戴黑帽子的人,也就是那个从队尾数起第一个看见前面所有人都戴白帽子的人。
这样的推理也许让人觉得有点循环论证的味道,因为上面那段推理中包含了“如果别人也使用相同的推理”这样的意思,在逻辑上这样的自指式命题有点危险。但是其实这里没有循环论证,这是类似数学归纳法的推理,每个人的推理都建立在他后面那些人的推理上,而对于最后一个人来说,他的身后没有人,所以他的推理不依赖于其他人的推理就可以成立,是归纳中的第一个推理。稍微思考一下,我们就可以把上面的论证改得适合于任何多种颜色的推论:
“如果我们可以从假设断定某种颜色的帽子一定会在队列中出现,从队尾数起第一个看不见这种颜色的帽子的人就立刻可以根据和此论证相同的论证来作出判断,他戴的是这种颜色的帽子。现在所有我身后的人都回答不知道,所以我身后的人也看见了此种颜色的帽子。如果在我前面我见不到此颜色的帽子,那么一定是我戴着这种颜色的帽子。”
当然第一个人的初始推理相当简单:“队列中一定有人戴这种颜色的帽子,现在我看不见前面有人戴这颜色的帽子,那它只能是戴在我的头上了。”
对于题1)事情就变得很明显,3顶红帽子,4顶黑帽子,5顶白帽子给10个人戴,队列中每种颜色至少都该有一顶,于是从队尾数起第一个看不见某种颜色的帽子的人就能够断定他自己戴着这种颜色的帽子,通过这点我们也可以看到,最多问
到从队首数起的第三人时,就应该有人回答“知道”了,因为从队首数起的第三人最多只能看见两顶帽子,所以最多看见两种颜色,如果他后面的人都回答“不知道”,那么他前面一定有两种颜色的帽子,而他头上戴的一定是他看不见的那种颜色的帽子。
题2)也一样,3顶红帽子,4顶黑帽子,5顶白帽子给8个人戴,那么队列中一定至少有一顶白帽子,因为其它颜色加起来一共才7顶,所以队列中一定会有人回答“知道”。
题4)的规模大了一点,但是道理和2)完全一样。100种颜色的5050顶帽子给5000人戴,前面99种颜色的帽子数量是1+……+99=4950,所以队列中一定有第100种颜色的帽子(至少有50顶),所以如果自己身后的人都回答“不知道”,那么那个看不见颜色100帽子的人就可以断定自己戴着这种颜色的帽子。
至于5)、6)“有红黄绿三种颜色的帽子各1顶2顶3顶,但具体不知道哪种颜色是几顶,有6个人”以及“有不知多少人排成一排,有黑白两种帽子,每种帽子的数目都比人数少1”,原理完全相同,
我就不具体分析了。
最后要指出的一点是,上面我们只是论证了,如果我们可以根据各种颜色帽子的数量和队列中的人数判断出在队列中至少有一顶某种颜色的帽子,那么一定有一人可以判断出自己头上的帽子的颜色。因为如果所有身后的人都回答“不知道”的话,那个从队尾数起第一个看不见这种颜色的帽子的人就可以判断自己戴了此颜色的帽子。但是这并不是说在询问中一定是由他来回答“知道”的,因为还可能有其他的方法来判断自己头上帽子的颜色。比如说在题2)中,如果队列如下:(箭头表示队列中人脸朝的方向)
白白黑黑黑黑红红红白→
那么在队尾第一人就立刻可以回答他头上的是白帽,因为他看见了所有的3顶红帽子和4顶黑帽子,能留给他自己戴的只能是白帽子了
【69】假设排列着100个乒乓球,由两个人轮流拿球装入口袋,能拿到第100个乒乓球的人为胜利者。条件是:每次拿球者至少要拿1个,但最多不能超过5个,问:如果你是最先拿球的人,你该拿几个?以后怎么拿就能保证你能得到第100个乒乓球?
首先拿4个 别人拿n个你就拿6-n个
【70】卢姆教授说:“有一次 我目击了两只山羊的一场殊死决斗,结果引出了一个有趣的数学问题。我的一位邻居有一只山羊,重54磅,它已有好几个季度在附近山区称王称霸。后来某个好事 之徒引进了一只新的山羊,比它还要重出3磅。开始时,它们相安无事,彼此和谐相处。可是有一天,较轻的那只山羊站在陡峭的山
路顶上,向它的竞争对手猛扑过 去,那对手站在土丘上迎接挑战,而挑战者显然拥有居高临下的优势。不幸的是,由于猛烈碰撞,两只山羊都一命呜呼了。
现在要讲一讲本题的奇妙之处。对饲养山羊颇有研究,还写过书的乔治.阿伯克龙比说道:“通过反复实验,我发现,动量相当于一个自20英尺高处坠落下来 的30磅重物的一次撞击,正好可以打碎山羊的脑壳,致它死命。”如果他说得不错,那么这两只山羊至少要有多大的逼近速度,才能相互撞破脑壳?你能算出来 吗?
1英尺(ft)=0.3048米(m)
1磅(lb)=0.454千克(kg)
通过实验得到撞破脑壳所需要的机械能是mgh=(30*0.454)*9.8*(20*0.3048)=813.669(J)对于两只山羊撞击瞬间来说,比较重的那只仅仅是站在原地,只有较轻的山羊具有速度,而题目中暗示我们,两只羊仅一次碰撞致死。现在我们只需要求得碰撞瞬间轻山羊的瞬时速度就可以了,根据机械能守恒定律:mgh=1/2(m1v^2)可以得出速度。m1是轻山羊的重量。
【71】据说有人给酒肆的老板娘出了一个难题:此人明明知道店里只有两个舀酒的勺子
,分别能舀7两和11两酒,却硬要老板娘卖给他2两酒。聪明的老板娘毫不含糊,用这两个勺子在酒缸里舀酒,并倒来倒去,居然量出了2两酒,聪明的你能做到吗?
11,0-->4,7-->4,0-->0,4-->11,4-->8,7-->8,0-->1,7-->1,0-->0,1-->11,1-->5,7-->5,0-->0,5-->11,5-->9,7-->9,0-->2,7,这样就有2斤了。
【72】已知: 每个飞机只有一个油箱, 飞机之间可以相互加油(注意是相互,没有加油机) 一箱油可供一架飞机绕地球飞半圈,问题:为使至少一架飞机绕地球一圈回到起飞时的飞机场,至少需要出动几架飞机?(所有飞机从同一机场起飞,而且必须安全返回机场,不允许中途降落,中间没有飞机场)
需要3架飞机(记为A,B,C),A走完全程。如下图,黑色箭头表示飞行方向,红色箭头表示一架给另一架加油,红色数字表示加油量整个油箱容量的比值。
【73】在9个点上画10条直线,要求每条直线上有三个点?
【74】一个岔路口分别通向诚实国和说谎国。来了两个人,已知一个是诚实国的,另一个是说谎国的。诚实国永远说实话,说谎国永远说谎话。现在你要去说谎国,但不知道应该走哪条路,需要问这两个人。请问应该怎么问?
问:请问你从哪里来?
回答肯定都是指向诚实国的。
【75】在一天的24小时之中,时钟的时针、分针和秒针完全重合在一起的时候有几次?都分别是什么时间?你怎样算出来的?
只有两次
假设时针的角速度
是ω(ω=π/6每小时),则分针的角速度为12ω,秒针的角速度为72ω。分针与时针再次重合的时间为t,则有12ωt-ωt=2π,t=12/11小时,换算成时分秒为1小时5分27.3秒,显然秒针不与时针分针重合,同样可以算出其它10次分针与时针重合时秒针都不能与它们重合。只有在正12点和0点时才会重。
证明:将时针视为静止,考察分针,秒针对它的相对速度:
12个小时作为时间单位“1”,“圈/12小时”作为速度单位,
则分针速度为11,秒针速度为719。
由于11与719互质,记12小时/(11*719)为时间单位Δ,
则分针与时针重合当且仅当 t=719kΔ k∈Z
秒针与时针重合当且仅当 t=11jΔ j∈Z
而719与11的最小公倍数为11*719,所以若t=0时三针重合,则下一次三针重合
必然在t=11*719*Δ时,即t=12点。
标签: #递归算法例题汽水问题递归