登陆注册
20032900000028

第28章 逻辑思维的妙用(8)

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个人头上帽子的颜色,而最前面那个人谁的帽子都看不见。

现在从最后那个人开始,问他是不是知道自己戴的帽子颜色,如果他回答说不知道,就继续问他前面那个人。假设最前面那个人一定会知道自己戴的是黑帽子。为什么?

【答案解析】

答案是,最前面的那个人听见后面两个人都说了“不知道”,他假设自己戴的是白帽子,于是中间那个人就看见他戴的白帽子。那么中间那个人会作如下推理:“假设我戴了白帽子,那么最后那个人就会看见前面两顶白帽子,但总共只有两顶白帽子,他就应该明白他自己戴的是黑帽子,现在他说不知道,就说明我戴了白帽子这个假定是错的,所以我戴了黑帽子。”问题是中间那人也说不知道,所以最前面那个人知道自己戴白帽子的假定是错的,所以他推断出自己戴了黑帽子。

同类推荐
  • 人生思考致胜22招

    人生思考致胜22招

    本书从大量的人生经验中,精心提炼了以思考致胜的22招,这既是指导人生走出思考误区的22条法则,又是冲破人生瓶颈赢定人生前程的22个胜招。全书朴实自然、贴近生活,通过层层解读学会善思多谋的途径和方法,让人们掌握科学思考的秘诀和诀窍,帮助人们在奋斗的人生中尽量少犯错误。书中既有启发读者乐于思考的忠告,又有开悟读者善于思考的方法;既有生动鲜活的典型案例,又有寓意深刻的人生哲理。
  • 成功规律

    成功规律

    我们迫切希望自己能够出人头地,在芸芸众生中出类拔萃。看到人生舞台上那些耀眼的明星,我们总是对自己说,“总有一天,我也行。”是的,我们也会成功的,成功离我们并不遥远。记住,成功是有规律可循的!拿破仑·希尔和塞缪尔·斯迈尔斯是全美乃至整个世界都享有盛誉的成功学家。他们所总结的成功规律是他们为社会作出的最伟大的贡献之一。我们可以从其中获得成功的12条黄金法则与大量的精神信息。本书即是对这两位大师总结的成功的黄金法则的详细介绍。在这个世界上,我们对成功之人了解不少,可我们对成功的规律,却知之甚少,专注地阅读此书吧,你一定会从中获取诸多使你成功的黄金规律!
  • 交际力:打造属于自己的核心圈

    交际力:打造属于自己的核心圈

    本书共分五章,主要内容包括:人脉就是一种人生正能量;维护人脉,用心经营;火眼金睛识人心;善于用语言,提升交际力;不良交际一键删除。
  • 好心态好命运

    好心态好命运

    好的心态决定好的命运。人的命运是完全由自己掌握的,面对同样一件事,你可以是欢天喜地,也可以是忧愁不已,这完全在于一个人的心态如何。生活的恬淡少浮躁、情绪多稳定少激动、人间多关爱少仇恨、为人多宽容少嫉妒……人生一定会变的很美好。
  • 青春的魅力:青少年的智商与情商

    青春的魅力:青少年的智商与情商

    本书指导青少年朋友在青春的季节,如何提高智商与情商。全书共六章,内容包括:你的脑子“好用”吗、你的想法神奇吗、你的思维升级了吗、揭开EQ的面纱、掌握命运之船等。
热门推荐
  • 道术世界

    道术世界

    道术文明道术世界法术配合能力进化太极无极
  • 英雄少年赖宁

    英雄少年赖宁

    赖宁(1973-1988),原名赖麟,四川雅安市石棉县人,生前石棉中学初中二年级学生。1988年3月13日,为了扑灭突发山火,挽救山村,保护电视与地面卫星接收站的安全,他主动加入了扑火队伍,在烈火中奋战四五个小时后遇难。1988年5月,共青团中央,国家教委授予赖宁“英雄少年”的光荣称号。
  • 重生之豆蔻年华的你

    重生之豆蔻年华的你

    石天佑,一名普通都市上班族一次意外回到2007年,拥有后事的只是以及记忆,重生回来的逆袭。。。
  • 少年吉他手

    少年吉他手

    在一场慈善晚会上,被称为摇滚音乐教父的山住先生捐赠了一把价值一百三十万的吉他,吉他的名字叫天瀑。三年后,天瀑的一弦断了。
  • 都市天官

    都市天官

    一个总觊觎着小师妹的屈凡,偶遇下凡的神仙憨憨,玩大发了
  • 巡铺房

    巡铺房

    在近代发生的一系列案件,产生了一大批的侦探。让我们看一下他们是如何抽丝剥茧,破除那些扑朔迷离的案件。
  • 天行

    天行

    号称“北辰骑神”的天才玩家以自创的“牧马冲锋流”战术击败了国服第一弓手北冥雪,被誉为天纵战榜第一骑士的他,却受到小人排挤,最终离开了效力已久的银狐俱乐部。是沉沦,还是再次崛起?恰逢其时,月恒集团第四款游戏“天行”正式上线,虚拟世界再起风云!
  • 影响你一生的名著——影响孩子一生的100个数学故事

    影响你一生的名著——影响孩子一生的100个数学故事

    有一种东西叫做钻石,如天上的星星,风雨的岁月和空间,凝固成人类精神的永恒,它跨越了国界、语言、年龄。“注音版影响孩子一生的名著”系列图书,每一本都是你生命中不可不读的经典。
  • 凡人意识

    凡人意识

    什么是意识?是所有生物都拥有意识,还是人类独有?察觉杀气果断反杀,遭遇GANK提前离开,意识存在万物之间。在不断萎缩的世界反面,少年背负起旧神的灵龛,从灰暗的历史中走了出来,决定带给凡人们新生。
  • 恒行诸天

    恒行诸天

    陆恒成了自己笔下的小说主角,以内家拳入道,穿梭电影世界。恒行诸天,神魔辟易!已完成世界:1、让子弹飞+危城+师父2、新龙门客栈+剑雨+六指琴魔3、狄仁杰之神都龙王、四大天王+伪西游4、西游降魔+伏妖+大话西游5、星辰变6、仙逆新书《诸天之从新做人》,求支持!读者群号:653079771