斯伦贝谢软件面试笔试题

  一道斯伦贝谢软件面试笔试题分享:

  软件, 笔试, 斯伦贝

  每个公司的软件题目应该都是其在实际工作当中会遇到的问题,这道斯伦贝谢的算法题我猜测应该也是如此。题目是09届毕业生招聘时出的,如下:

  现在一个广场上有一些木桩,可以知道这些木桩的坐标。给你一根很长的绳子,绕成一圈,将所有木桩都绕在里面。之后收紧绳子,直到其紧绷。此时有木桩与绳子接触,另外一些木桩则是在绳子绕成的圈的内部。 我们将与绳子接触的木桩称作顶点,请编写程序,求出这些木桩中的顶点。

  这道题目其实不难,诸位读者可以思考一下,再看我给的解决方案。另外提醒一下,木桩的坐标是人定的,我们可以将木桩的坐标统一定在第一象限。

  以下是这个问题的解答,我只给出算法大体流程,但不给出具体代码。

  我们的输入是一个数组,这个数组中包含所有木桩的坐标,即一个POINT。

  第一步,找出这些点中,位于最下方,即Y坐标值最小的点,我们称之为木桩A

  我们以A点作为基准点进行下一步分析。找出逆时针方向的下一个顶点。这个顶点的寻找方向,必然是先找右上方,如果右上方没有点,则找左上方。

  在右上方,下一个顶点必然是与A相连,斜率最小的点。如果右上方没有点,那么我们需要从左上方查找斜率也是最小的一个点。这一点读者可以在纸上画图查证。

  按照这种方法,我们很容易找到逆时针的下一个点,我们称之为B点,现在从B点查找B点的逆时针下一个顶点。对于B点来说,我们也需要先查找右上方,如果右上方没有木桩,则查找左上方,左上方没有,则需要查找左下方,如果左下方没有,那就需要查找右下方。按照此次序依次查找。

  对于右上方有木桩的情形,我们需要找到与B点相连斜率最小的木桩。

  右上方无木桩,左上方有木桩的情形,我们需要查找左上方中,与B相连斜率最小的木桩。

  对于左下方的情形,我们需要查找与B相连斜率最小的木桩。

  对于右下方的情形,我们需要查找与B相连斜率最小的木桩。

  虽然都是查找斜率最小,但我们需要依次比较四种情况,而不能混在一起查找。

  按照这种方法,我们可以找到C点。

  重复由B找到C的步骤,我们可以找到C的逆时针下一个顶点,依次查找,则可以找出所有顶点。这里还需要注意一点,我们需要保存上一次的斜率,本次查找时的斜率必须比上一次查找时的斜率大,或者本次查找的下一个顶点的位置,位于四个方位中的下一个方位。

  这个方法很简单,但效率很低,每次查找,都需要计算出当前顶点与其他所有点的斜率,并进行分类排序比较。但目前我只想到这一种方法,如果谁有更好的方法,欢迎给我留言

本文已影响6827
上一篇:中国邮储银行面试问题 下一篇:最新招聘体育教师的面试问题

相关文章推荐

|||||