PHP程序员面试算法宝典
上QQ阅读APP看书,第一时间看更新

2.1 逻辑计算

2.1.1 老鼠相遇的概率是多少

难度系数:★★★☆☆

被考查系数:★★★☆☆

题目描述:

一个三角形三个顶点有3只老鼠,一声枪响,3只老鼠开始沿三角形的边匀速运动,请问它们相遇的概率是多少?

分析与解答:

75%。

每只老鼠都有顺时针、逆时针两种运动方向。3只老鼠共有23(8)种运动情况,只有当3只老鼠的运动方向都为顺时针或者逆时针时,它们才不会相遇,而剩余的6种情况老鼠都会相遇,故老鼠相遇的概率为6/8=75%。

2.1.2 如何计算时钟的三针重叠

难度系数:★★★☆☆

被考查系数:★★★☆☆

题目描述:

在一天的24小时中,时钟的时针、分针和秒针完全重合在一起的时候有几次?都分别是什么时间?你是怎样算出来的?

分析与解答:

只有两次。

假设时针的角速度是ω(ω=π/6每小时),则分针的角速度为12ω(2π每小时),秒针的角速度为720ω(120π每小时)。分针与时针再次重合的时间为t,则有12ωt-ωt=2π,t=12/11小时,换算成时分秒为1小时5分27.3秒,显然秒针不与时针、分针重合,同样可以算出其他10次分针与时针重合时秒针都不能与它们重合。只有在正12点和0点时才会重合。将时针视为静止,考查分针,秒针对它的相对速度:

1)12个小时作为时间单位“1”,“圈/12小时”作为速度单位,则分针速度为11,秒针速度为719。

2)由于11与719互质,记12小时/(11×719)为时间单位Δ,则分针与时针重合当且仅当t=719kΔk∈Z,秒针与时针重合当且仅当t=11jΔj∈Z。

3)而719与11的最小公倍数为11×719,所以若t=0时三针重合,则下一次三针重合必然在t=11×719×Δ时,即t=12点。

2.1.3 如何喝到最多瓶汽水

难度系数:★★★☆☆

被考查系数:★★★☆☆

题目描述:

1元钱可以买一瓶汽水,喝完后的两个空瓶可以换一瓶汽水。问:如果有20元钱,那么最多可以喝到几瓶汽水?

分析与解答:

40瓶。

最初可以喝到的汽水瓶数为:20+10+5+2+1+1=39。剩一个空瓶,可以先向店主借一个空瓶,换来一瓶汽水,喝完后再把空瓶还给店主,所以一共可以喝到40瓶汽水。

2.1.4 住旅店花了多少钱

难度系数:★★★☆☆

被考查系数:★★★☆☆

题目描述:

有三个人去旅馆,分别住在三间房,每一间房10元,于是他们一共付给老板30元。第二天,老板觉得三间房只需要25元就够了,于是叫小弟退回5元给三位客人。谁知小弟贪心,只退回每人1元,自己偷偷拿了2元。这样一来便等于那三位客人每人各花了9元,于是三个人一共花了27元,再加上小弟独吞了2元,总共是29元。可是当初他们三个人一共付出30元,那么还有1元钱去哪里了呢?

分析与解答:

三个人其实只付了27元(9×3=27)。其中,2元付给了小弟,25元付给了老板。因为在27元中包括了小弟独吞的2元,所以27元加上2元是不对的。27元加上退回来的3元等于30元,这样才是合理的。

2.1.5 商人可卖出多少根胡萝卜

难度系数:★★★☆☆

被考查系数:★★★☆☆

题目描述:

一个商人骑一头驴要穿越1000公里的沙漠,去卖3000根胡萝卜。已知驴一次性可驮1000根胡萝卜,但每走一公里就要吃掉一根胡萝卜。问:商人可卖出多少根胡萝卜?

分析与解答:

商人可卖出534根胡萝卜。

可以把1000公里分为三段。

1)第一段保证运到第一储存点2000根。来回总共走了5次这段路。假设驴走X公里第一次卸下胡萝卜,则:5×X=1000(吃萝卜的数量,也等于所行走的公里数),X=200,则总共是2000根胡萝卜了;

2)第二段保证到达有1000根。来回总共走3次这段路,因为第二次驴只需要驮两次,设驴走Y公里第二次卸下胡萝卜,则:3×Y=1000,Y=333.3,剩下1000根胡萝卜;

3)而此时总共走了:200+333.3=533.3公里;

4)而剩下的1000-533.3=466.7公里只需要1次驮出,吃466根萝卜。

所以,可以卖萝卜的数量就是1000-466=534(根)。

2.1.6 如何判断哪个开关控制着哪盏灯

难度系数:★★★☆☆

被考查系数:★★★★☆

题目描述:

屋里有三盏灯,屋外有三个开关,一个开关仅控制一盏灯,屋外看不到屋里情况。只进屋一次,如何才能知道哪个开关控制着哪盏灯?如果增加到四盏灯,那么又该如何判断呢?

分析与解答:

根据温度判断三盏灯:先开一盏,足够长的时间后再关掉,然后开另一盏,进屋看,亮的为后来开的,摸起来热的为先开的,剩下的一盏也就确定了。

四盏灯的情况:假设四个开关分别为A、B、C、D,先开A、B,足够长的时间后关B开C,然后进屋,又热又亮的是A,只热不亮的是B,只亮不热的是C,不亮不热的是D。

2.1.7 如何用烧绳来计算时间

难度系数:★★★☆☆

被考查系数:★★★☆☆

题目描述:

烧一根不均匀的绳,从头烧到尾总共需要一个小时,如何用它来判断半个小时?现在有若干条材质相同的绳子,如何用烧绳的方法来计时1小时15分钟呢?

分析与解答:

由题意可知,用一根绳子从两头烧,烧完就是半个小时。现在先用两根绳,其中一根要一头烧,另一根从两头烧。两头烧完的时候(也就是30分钟),将剩下一根的另一端也点着,烧尽就是45分钟。再从两头点燃第三根,烧尽就是1时15分。

2.1.8 如何用水壶获取指定的水量

难度系数:★★★☆☆

被考查系数:★★★☆☆

题目描述:

假设有一个池塘,里面有无穷多的水。现有2个空水壶,它们的容积分别为5升和6升。如何只用这2个水壶从池塘里取得3升的水?

分析与解答:

具体实现如下:

1)先把5升的水壶灌满,倒在6升水壶里,这时6升的水壶里有5升水;

2)再把5升的水壶灌满,用5升的壶把6升的灌满,这时5升的壶里剩4升水;

3)接着把6升的水倒掉,然后把5升壶里剩余的水倒入6升的壶里,这时6升的壶里有4升水;

4)最后把5升壶灌满,倒满6升的壶,这时5升的壶剩下的水就是3升(5-2=3)。

2.1.9 卖鸡总共赚了多少

难度系数:★★★☆☆

被考查系数:★★★★☆

题目描述:

一个人花8块钱买了一只鸡,9块钱卖掉了,然后他觉得不划算,花10块钱又买回来了, 11块卖给另外一个人。问他赚了多少?

分析与解答:

赚了2元。

可以假设买进来算负,卖出算正,根据题目描述可以这样计算:-8+9-10+11=2。所以最后这个人赚了2元。

2.1.10 跳高名次是多少

难度系数:★★★☆☆

被考查系数:★★★★☆

题目描述:

有一种体育竞赛共含M个项目,运动员A、B、C参加了所有的项目。在每一个项目中,第一、第二、第三名分别得X、Y、Z分,其中X、Y、Z为正整数且X > Y> Z。最后A得22分,B与C均得9分,B在百米赛中取得第一。求M的值以及在跳高中谁得了第二名?

分析与解答:

M=5,C得了第二名。

由题意可以得出下面两个公式:

M(X+Y+Z)=22+9+9=40,①

又因为X+Y+Z≥1+2+3=6,②

所以,6M≤M(X+Y+Z)=40,从而M≤6。

由题设知至少有百米和跳高两个项目,从而M≥2,又因为M|40,所以M可取2、4、5。

如果M=2,那么只有跳高和百米,而B百米第一,但总分仅9分,故必有:9≥p1+p3,所以p1≤8,这样A不可能得22分。

如果M=4,那么X+Y+Z=10,由X>Y>Z可知,它们可能会有如下的取值:

又因为A得22分,故4X>22,那么只有第一种情况满足要求,即A得分为7 7 7 1,但是在这种情况下,B和C得分永远不能为9,故矛盾。

如果M=5,那么X+Y+Z=8,由X>Y>Z可知,它们会有如下的取值:

又因为A=22,故只有第一种情况满足,故A、B、C得分如下:

因此,百米赛中,A得第二,B得第一,C得第三,由于C其他项目均得第二,即跳高中C得第二。

2.1.11 如何根据银币猜盒子

难度系数:★★★☆☆

被考查系数:★★★★☆

题目描述:

假设在桌上有三个密封的盒子,一个盒子中有2枚银币(1银币=10便士),一个盒中有2枚镍币(1镍币=5便士),还有一个盒中有1枚银币和1枚镍币。这些盒子被标上10便士、15便士和20便士,但每个标签都是错误的。允许你从一个盒中拿出1枚硬币放在盒前,看到这枚硬币,你能否说出每个盒内装的东西呢?

分析与解答:

取出标着15便士的盒中的一个硬币,如果是银的,那么说明这个盒子是20便士的;如果是镍的,那么说明这个盒子是10便士的,再由每个盒子的标签都是错误的可以推出其他两个盒里的东西。

因为每个标签对应的盒子是错误的,所以知道15便士的盒子里面不会是一银一镍,要么是10便士,要么是20便士。如果从15便士的盒子中取出的硬币是银的,那么说明该盒子有两枚银币,标签是20便士。如果从15便士的盒子中取出的硬币是镍的,那么说明该盒子有两枚镍币,标签是10便士。确定了15便士盒对应的硬币和标签后,通过标签和便士值是不对应的,可以推断出10便士盒子和20便士盒子里的硬币和标签。

2.1.12 马牛羊的价格各是多少文钱

难度系数:★★★☆☆

被考查系数:★★★★☆

题目描述:

今有2匹马、3头牛和4只羊,它们各自的总价都不满10000文钱(古时的货币单位)。如果2匹马加上1头牛、或者3头牛加上1只羊、又或者4只羊加上1匹马,那么它们各自的总价都正好是10000文钱。问:马、牛、羊的单价各是多少文钱?

分析与解答:

马:3600,牛:2800,羊:1600。

设马的单价为x,牛的单价为y,羊的单价为z。则根据题目可得到三个式子:2x+y=10000;3y+z=10000;x+4z=10000。最终求解出x=3600,y=2800,z=1600。

2.1.13 赔了多少钱

难度系数:★★★☆☆

被考查系数:★★★★☆

题目描述:

一天,店里来了一位顾客,挑了25元的货,顾客拿出100元,店里没零钱找不开,就到隔壁的店里把这100元换成零钱,回来给顾客找了75元零钱。过一会儿,隔壁来找这家店,说刚才的100元是假钱,店里马上给隔壁店换了张真钱,问店里赔了多少钱?

分析与解答:

100元。

根据题目的意思,将店里的钱收入部分为正,支出部分为负。可以得到式子:-25+100-75-100=-100。从而知道店里赔了100元。亏的部分主要是货物的25元和找零的75元。

2.1.14 海盗如何分金才能让他获得最多的金子

难度系数:★★★☆☆

被考查系数:★★★★☆

题目描述:

5名海盗抢得了窖藏的100块金子,他们打算瓜分这些战利品。这是一些讲民主的海盗(当然是他们自己特有的民主),他们的习惯是按下面的方式进行分配:最厉害的一名海盗提出分配方案,然后所有的海盗(包括提出方案者本人)就此方案进行表决。如果50%或更多的海盗赞同此方案,此方案就获得通过并据此分配战利品。否则提出方案的海盗将被扔到海里,然后下一名最厉害的海盗又重复上述过程。

所有的海盗都乐于看到他们的一位同伙被扔进海里,不过,如果让他们选择的话,那么他们还是宁可只得一笔现金,也不愿意自己被扔到海里。所有的海盗都是有理性的,而且知道其他的海盗也是有理性的。此外,没有两名海盗是同等厉害的——这些海盗按照完全由上到下的等级排好了顺序,并且每个人都清楚自己和其他所有人的等级。这些金块不能再分,也不允许几名海盗共有金子,因为任何海盗都不相信他的同伙会遵守关于共享金子的安排。这是一伙每人都只为自己打算的海盗。

最凶的一名海盗应当提出什么样的分配方案才能使他获得最多的金子呢?

分析与解答:

如果轮到第四个海盗分配:100,0

轮到第三个:99,0,1

轮到第二个:99,0,1,0

轮到第一个:98,0,1,0,1,这就是第一个海盗的最佳方案。

可以从后往前推测每次最优的方案,从而确定第一种方案就是最好的。

1)当只剩两个海盗分金时,因为只要有50%或以上的支持率则方案通过,所以第四个海盗和第五个海盗分金时,无论第五个海盗是否支持自己,第四个海盗都可以给自己分配100块金子。

2)当只剩三个海盗分金时,第三个海盗分金的方案,除了自己的支持外,还需要一个海盗的支持,否则方案不通过。所以,如果第三个海盗想要拿最多金子,最好的方案就是让第五个海盗得到金子来支持他,因为第四个海盗可以通过否定第三个海盗的方案实现自己的利益最大化。所以,第三个海盗得块99块金子,而第五个海盗得1块金子的方案是最好的。

3)当只剩下四个海盗分金时,第二个海盗的方案,只需要一个海盗支持他即可通过方案。由2)的分析知道,要第四个海盗支持自己是最有利的,所以可以得到最好的方案是:第二个海盗99块金子,第四个海盗1块金子的方案。

4)最初的情况,5个海盗分金,第一个海盗必须要其余2名海盗支持自己,它才有可能得到最多的金子。通过3)的分析知道,分配金子给第三个海盗和第五个海盗1块金子,让它们支持自己是最优的方案。

2.1.15 张老师的生日是哪一天

难度系数:★★★☆☆

被考查系数:★★★★☆

题目描述:

小明和小强都是张老师的学生,张老师的生日是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日。

1)分析这10组日期,经观察不难发现,只有6月7日和12月2日这两组日期是唯一的。由此可知,如果小强得知的N是7或者2,那么他必定知道了老师的生日。

2)小明说:“如果我不知道的话,小强肯定也不知道”,而该10组日期的月数分别为3, 6,9,12,而且相应月的日期都有两组以上,所以小明得知M后是不可能知道老师生日的。

3)进一步分析小明说:“如果我不知道的话,那么小强肯定也不知道”,结合第2步结论,可知小强得知N后也绝不可能知道。

4)结合第3和第1步,可以推断:所有6月和12月的日期都不是老师的生日,因为如果小明得知的M是6,而若小强的N=7,则小强就知道了老师的生日(由第1步已经推出)。同理,如果小明的M=12,若小强的N=2,则小强同样可以知道老师的生日,即:M不等于6和12。现在只剩下“3月4日、3月5日、3月8日、9月1日、9月5日”五组日期。而小强知道了,所以N不等于5(因为有3月5日和9月5日),此时,小强的N∈(1,4,8)。虽然N有三种可能,但对于小强只要知道其中的一种,就能得出结论。所以有“小强说:本来我也不知道,但是现在我知道了,”至此继续推理知道,剩下的可能是“3月4日、3月8日、9月1日”。

5)分析“小明说:哦,那我也知道了,”说明M=9,N=1(N=5已经被排除,3月份的有两组也已排除)。

2.1.16 拿几个乒乓球

难度系数:★★★☆☆

被考查系数:★★★★☆

题目描述:

假设排列着100个乒乓球,由两个人轮流拿球装入口袋,能拿到第100个乒乓球的人为胜利者。条件是:每次拿球者至少要拿1个,但最多不能超过5个。问:如果你是最先拿球的人,那么你该拿几个?以后怎么拿就能保证你能得到第100个乒乓球?

分析与解答:

拿出4个,然后按照6的倍数和另外一人分别拿球。即:

另外一人拿1个,我拿5个;

另外一人拿2个,我拿4个;

另外一人拿3个,我拿3个;

另外一人拿4个,我拿2个;

另外一人拿5个,我拿1个。

最终第100个在我手上。

因为最多可拿的乒乓球数为6个,所以100除6余4,只要最开始拿4个出来后,每次保证拿的数量是6的倍数,即别人拿n个你就拿(6-n)个。最后一个人拿的球都可以保证第100个乒乓球被自己拿到。