第三题是约瑟夫(Joseph)环问题，一看很高兴啊。以前在Poj上做过，而且在Baidu比赛还做过变种的约瑟夫问题。很顺利的写了出来，给出递归和循环两种解决方法。第四题给出一个PI/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 ……的公式要求写一个求PI的程序精确到小数点后500位。按这个要求应该是让自己写个数据结构来实现高精度。在我看来在考试期间完成是 mission impossible。 第五题是挖石油的放弃了。

今天去斯伦贝谢BGC参加笔试，感觉BGC并不太考技术细节，侧重考察思维能力和英语表达能力。一道设计题，一道名词解释题，一道算法题，一道智力题，一道跟石油相关的半开放问题，好坏不知。

笔试在9点半。试题比较有意思，最后一题让设计一个海底甲烷水合物开采方案，我想到用循环热水管道，在海底把固体矿物质加热使甲烷逸出，甲烷再随着水循环上升到海面上。对于这个创意我自己还比较得意，但估计人家看了就觉得可笑了。

斯伦贝谢软件笔试题

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

这个方法很简单，但效率很低，每次查找，都需要计算出当前顶点与其他所有点的斜率，并进行分类排序比较。