• 打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮
  • 打赏支付宝扫一扫

首页

 > 

设计架构 > 

数据结构

一道有趣的面试题,小鸟和火车的问题,again

winter-cnwinter-cn • 9年前

首先说说上下文:

#url-1
#url-2

这道"有趣"的面试题是:甲乙两地相距100公里,有一辆火车以每小时15公里的速度离开甲地直奔乙地,另一辆火车以每小时20公里的速度从乙地开往甲地。如果有一只鸟,以30公里每小时的速度和两辆火车同时启动,从甲地出发,碰到另一辆车后返回,依次在两辆火车来回飞行,直到两辆火车相遇,请问,这只小鸟往返了多少次

首先说这个题,我觉得出的并无任何不严谨的地方,也没有能明显让人误解的地方。按照通常的表述,显然题意是忽略鸟的转身时间,忽略鸟的身长,把鸟和火车头抽象成三个点。如果非要考虑鸟的转身时间和身长,我觉得有故意曲解的嫌疑。任何一个应用问题都有隐含的忽略条件,答题者如果要求应用题表述无限精确滴水不漏,是不可能的。所以我觉得有些关于量子物理的言论就没有必要了。如果硬要钻牛角尖,还可以说火车道不是严格的直线,可以说鸟并非匀速直线运动,可以说根据相对论速度和距离、时间应该遵守洛伦兹变换而非伽利略变换。

然后是解法,按照原意,鸟往返了无限多次,可以用数学归纳法证明:

假设第k次两车相距m 小鸟在甲车处
飞到乙车时 两车相距
m-m/(20+30)*(15+20)=0.3m
再飞到甲车
0.3m-0.3m/(15+30)*(15+20)=1/15m

第k+1次往返两车距离为m/15

显然若m>0 第k+1次之后两车距离仍不为0

开始是两车相距100公里不为0  所以不论往返多少次 两车距离都不为0 

本来解到这里,这个题目应该已经可以得出答案了。

但是很多朋友为了编程可实现,规定了一个距离精度,小于这个距离就认为两车相距,然后又递归或者迭代写了代码实现。但是程序员不是编码工,不是所有能实现的代码就是好的。不能只知道模拟,不考虑效率。

根据前面的证明 其实最后往返次数只是一个对数运算(注意求的是往返次数,而不是转身次数)

Code

 

最后关于时间无限细分的问题 其实类似很多年前就被提出并解决了:http://en.wikipedia.org/wiki/Zeno's_paradoxes

而且类似的计时制中,次数并不是一个悖论,距离才是。

所以这个问题作为面试题,是非常不错的题目,可以从不同的角度回答者的能力:

1.数学和逻辑思维基础:考察面试者是否了解类似的问题并且知道背景知识,能否独立想出解决方案

2.算法优化意识:考察面试者是否仅仅关注最表面的解决方法。二话不说直接写递归交差的程序员肯定不要

3.理解问题能力:考察面试者是否能正确理解问题,理解有偏差时,是否能主动沟通,弄清别人的真正意图。自己假设一堆条件的程序员肯定不要

4.编程语言基础:考察面试者是否能正确运用一门计算机语言。用==直接比较浮点数的程序员肯定不要

 

“看完这篇还不够?如果你也在学习IT,并希望记录自己的成长日志,请戳这里告诉我们!”
新人作者

好好学习,天天向上,有工作有兼职可以找我。微信号:gethost

文章总数
总阅读量
程序猿们,如果你或你的朋友想升职加薪,请狠戳这里我要成长
参与讨论
后参与讨论
winter-cn
新人作者

文章总数
总阅读量
程序猿们,如果你或你的朋友想升职加薪,请狠戳这里我要成长
48h快讯7天最热月榜More
  • 7年前

    Dijkstra算法(单源最短路径)单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前,必须弄清楚最短路径的最优子结构性质。一.最短路径的最优子结构性质该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路
    收起
  • 7年前

    二叉树的非递归遍历二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现。在三种遍历中,前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点。一.前序遍历前序遍历按照根结点-左孩子-右孩子的顺序进行访问。1.递归实现voi
    收起
  • 7年前

    淘宝名词解释产品和商品的区别:淘宝标准化产品,由类目+关键属性唯一确定。如:手机类目,关键属性是品牌和型号,NokiaN95就是一个产品,nokia是品牌,N95是型号。产品除了关键属性还包括一般信息、销售属性和非关键属性。参考:如"诺基亚N95"就是一个产品。通过类目的关键属性组合来确定唯一的产品。后台标准类目叶子节点下,一组共同特征商品的组合(例如:化妆品+雅芳+保湿单品+容量),属于同一个产品的商品可以认为对消费者的效用及使用感受是没有差别的。产品这个概念对淘宝这种C2
    收起
  • 5年前

    队列特性:先进先出(FIFO)先进队列的元素先出队列。来源于我们生活中的队列(先排队的先办完事)。队列有下面几个操作:InitQueue()  初始化队列EnQueue()进队列DeQueue()出队列IsQueueEmpty()判断队列是否为空IsQueueFull()判断队列是否已满队列可以由数组和链表两种形式实现队列操作(c语言),下面仅以数组为例:数组实现:队列数据结构typedefstructqueue
    收起
  • 7年前

    前言那个啥前面发了2篇文章讲这个商品表的设计,后面越多需求浮出水面才发现设计依旧有问题,好吧,乐观一点,正如我博客的标题一样,我在进化^_^为什么要这样设计先说几个需求,看看您现在是如何去实现:一个用户来到我们网站,在前台页面,1.他要买洗发水,他进入了洗发水的类别,他想买带去屑止痒功效的500ml的洗发水,能否直接搜索出来所有品牌带这个功效属性是500ml的洗发水2.接着他要买一件T恤,他想买V领,短袖的T恤,能否直接通过2个属性搜索出所有品牌的T恤展示给他3.他
    收起
  • 9年前

    1、反转一个链表。循环算法。1Listreverse(Listl){2if(!l)returnl;3listcur=l.next;4listpre=l;5listtmp;6pre.next=null;7while(cur){8tmp=cur;9cur=cur.ne
    收起
  • 7年前

    图的遍历图的遍历有两种遍历方式:深度优先遍历(depth-firstsearch)和广度优先遍历(breadth-firstsearch)。1.深度优先遍历基本思想:首先从图中某个顶点v0出发,访问此顶点,然后依次从v0相邻的顶点出发深度优先遍历,直至图中所有与v0路径相通的顶点都被访问了;若此时尚有顶点未被访问,则从中选一个顶点作为起始点,重复上述过程,直到所有的顶点都被访问。可以看出深度优先遍历是一个递归的过程。如下图中的一个无向图其深度优先遍历得到的序
    收起
  • 7年前

    1:原理以此比较相邻的两个元素,每次比较完毕最大的一个字跑到本轮的末尾。目的:按从小到大排序。方法:假设存在数组:72,54,59,30,31,78,2,77,82,72第一轮比较相邻两个元素,如果左边元素大于右边元素,则交换。72和54比较的结果就是,54在前,72在后;然后72和59比较的结果,59在前,72在后;以此类推,第一轮比较之后的结果是:54,59,30,31,72,2,77,78,72,82经过第一轮比较,最大的元素跑到了最
    收起
  • 9年前

    CodehighlightingproducedbyActiproCodeHighlighter(freeware)http://www.CodeHighlighter.com/-->/*冒泡排序基本思想将n个记录看作按纵向排列,每趟排序时自下至上对每对相邻记录进行比较,若次序不符合要求(逆序)就交换。每趟排序结束时都能使排序范围内关键字最小的记录象一个气泡一样升到表上端的对应位置,整个排序过程共进行n-1趟,依次将关键字最小、次小、第三小的各个记录冒到表的第一个、第二个、第三个位置
    收起