• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

一组考算法的面试题(寻求最优解)

技术杂谈 勤劳的小蚂蚁 3个月前 (02-05) 56次浏览 已收录 0个评论 扫描二维码

1、要几架飞机(据说是微软的面试题)
每个飞机只有一个油箱,飞机之间可以相互加油(注意是相互,没有加油机),一箱油可供一架飞机绕地球飞半圈。 

问:为使至少一架飞机绕地球一圈回到起飞时的飞机场,至少需要出动几架飞机? (所有飞机从同一机场起飞,而且必须安全返回机场,不允许中途降落,中间没有飞机场)

解答:
我们把全程划分为多个4分之1段,可以知道,要一架飞机全程需要两箱油,假设飞机A为需要全程的飞机,则在4分之1时油必须满箱,由此考虑过程:

ABC同时起飞,至8分之1时,C给AB各4分之1的油,剩下4分之1油返回,AB继续飞行到4分之1时,B给A加4分之1油,将A加满,B剩余2分之1油,返回。

A飞至2分之1时,D反方向起飞,至4分之3时,D给A加4分之1油,E反方向飞,到8分之1的位置,给AD各4分之1的油,ADE同时返回。
注:此方法为最优解,其余加油方式均不能满足。
 
2、某幢大楼有100层。你手里有两颗一模一样的玻璃珠。当你拿着玻璃珠在某一层往下扔的时候,一定会有两个结果,玻璃珠碎了或者没碎。这幢大楼有个临界楼层。低于它的楼层,往下扔玻璃珠,玻璃珠不会碎,等于或高于它的楼层,扔下玻璃珠,玻璃珠一定会碎。玻璃珠碎了就不能再扔。现在让你设计一种方式,使得在该方式下,最坏的情况扔的次数比其他任何方式最坏的次数都少。也就是设计一种最有效的方式。
例如:有这样一种方式,第一次选择在60层扔,若碎了,说明临界点在60层及以下楼层,这时只有一颗珠子,剩下的只能是从第一层,一层一层往上实验,最坏的情况,要实验59次,加上之前的第一次,一共60次。若没碎,则只要从61层往上试即可,最多只要试40次,加上之前一共需41次。两种情况取最多的那种。故这种方式最坏的情况要试60次。
那该如何设计方式呢?

解答:
此问题关键是找到算法的公式,假设最坏情况需要n次,则归纳后得到:

在第一个小球不损害的情况下,第一次:n层,第二次:n+(n-1)层,依次类推到第n-1次:n+(n-1)+…+(n-(n-1)),由此,问题简化为:

1+2+3+…+n,在n大于多少时大于楼层数,得到结果为14。

反向类推:n=14时,结果为105,所以第一次可以选择9到14层中间任意一层,玻璃球不碎则楼层数为(14-次数)+前次楼层,玻璃球摔碎则从前次楼层+1开始,顺序试摔。

如可以选择如下序列:14,27,39,50,60,69,77,84,90,95,99,所有方式在最坏的情况都不会超过14次。

反证:如果假设13即可,则序列变为13,25,36,46,55,63,70,76,81,85,88,90,91,在楼层大于92时可能超出。
 
3、一共有25匹马,有一个赛场,赛场有5个赛道,就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定,不用任何其他工具,只通过马与马之间的比赛,试问,最少得比多少场才能知道跑得最快的5匹马?不能使用撞大运的算法
解答:目前网上最典型的算法认为是10次,后来,stormspire提出一种新的算法,认为9次足以。

经过笔者反复核算,9次是有章可循的算法,属于可以借助归纳公式的典型最优解,但不是本答案可以达到的最优。

以下为笔者核算的结果,最优解是8次。
第一次到第五次:
将25匹马平均分为5组,依次赛出。
得到
A1  A2  A3   A4  A5
B1  B2  B3   B4  B5
C1  C2  C3   C4  C5
D1  D2   D3   D4  D5
E1  E2  E3   E4  E5
第六次,将每组第二进行比赛,假设得到A2>B2>C2,后面的忽略,如此可以得到最快5匹马所在的临时集合{A1,B1,C1,D1,E1,A2,B2,A3,A4,A5,B3}
此处解释一下:对于CDE三组的第二名及向后,因为均比A1、B1、A2、B2、C1慢,所以全部被排除。
第七次,此次的分组是关键,选定马匹为A3、B2、C1、D1、E1。
比赛可能出现的结果有多达120种组合,以下分析关键组合:
组合1:C1、D1、E1排在前三名的情况,假设是C1、D1、E1
此结果得到新的临时集合{A1,C1,D1,E1,B1,A2}   
第八次,选定E1,B1,A2,末位淘汰.
 
组合2:C1、D1、E1其中二匹占据第一二名的情况,假设是C1和D1 
此结果再根据B2或A3的排名得到新的临时集合
A3第三 {A1,A2,C1,D1,A3,B1} 第八次选定B1,A3,二选一
B2第三 {A1,A2,C1,D1,B1} 得到结果
 
组合3:C1、D1、E1其中二匹占据第一三名的情况,假设是C1和D1
此结果再根据B2或A3的排名得到新的临时集合
A3第二 {A1,A2,C1,A3,B1,D1,A4} 第八次选定B1,D1,A4,排除后两位
B2第二 {A1,A2,B1,C1,B2} 得到结果
 
组合4:C1、D1、E1其中一匹占据第一名的情况,假设是C1
此结果再根据B2或A3的排名得到新的临时集合
A3>B2 {A1,A2,C1,A3,B1,A4} 第八次选定B1,A4,二选一
B2>A3 {A1,A2,C1,B1,B2} 得到结果
 
组合5:C1、D1、E1其中二匹占据第二三名的情况,假设是C1和D1
此结果再根据B2或A3的排名得到新的临时集合
A3第一 {A1,A2,A3,B1,C1,D1,A4,A5} 第八次选定B1,C1,D1,A4,A5,排除后两位
B2第一 {A1,A2,B1,B2,B3,C1} 第八次选定B3,C1,二选一
 
组合6:C1、D1、E1其中一匹占据第二名的情况,假设是C1
此结果再根据B2或A3的排名得到新的临时集合
A3第一 {A1,A2,A3,B1,C1,A4,A5} 第八次选定B1,C1,A4,A5,排除后两位
B2第一 {A1,A2,B1,B2,B3,C1} 第八次选定B3,C1,二选一
 
组合7:C1、D1、E1排在后三名的情况
此结果再根据B2和A3的排名得到新的临时集合
A3>B2 {A1,A2,A3,B1,B2,A4,A5} 第八次选定B1,B2,A4,A5,排除后两位
B2>A3 {A1,A2,B1,B2,B3,A3} 第八次选定B3,A3,二选一
 
 以上即为所有关键组合,由此只需8轮即可得到最快的5匹马。


丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:一组考算法的面试题(寻求最优解)
喜欢 (0)
[247507792@qq.com]
分享 (0)
勤劳的小蚂蚁
关于作者:
温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00