数学和概率

7.2 三角形的三个顶点上各有一只蚂蚁。如果蚂蚁开始沿着三角形的边爬行，两只或三只 蚂蚁撞在一起的概率有多大？假定每只蚂蚁会随机选一个方向，每个方向被选到的几率相等，而 且三只蚂蚁的爬行速度相同。 类似问题：在n个顶点的多边形上有n只蚂蚁，求出这些蚂蚁发生碰撞的概率。（第 63 页）

当其中两只蚂蚁互相朝着对方而行，就会发生碰撞。因此，蚂蚁不发生碰撞的前提是，它们 都朝着同一方向爬行（顺时针或逆时针）。我们可以算出这种情况的概率，然后再反推出问题的 答案。 每只蚂蚁可以朝两个方向爬行，一共有3只蚂蚁，它们不发生碰撞的概率位

若要将这个方法推广至n个顶点的多边形，同样的，蚂蚁也只有以顺时针或逆时针同方向爬 行才不致相撞，但总共有2 n 种爬行方式。综上，发生碰撞的概率为：

7.3 给定直角坐标系上的两条线，确定这两条线会不会相交。（第 63 页）

此题有很多不确定的地方：

• 两条线的格式是什么？
• 两条线实为同一条怎么处理？
• • 这些含糊不 清的地方最好跟面试官讨论一下。 下面将做出以下假设：
•  若两条线是相同的（斜率和y轴截距相等），则认为这两条线相交；
•  我们可以决定线的数据结构。 两条线若不平行则必相交。
• 因此，要检查两条线相交与否，我们只需检查两者的斜率是否相 同，或是否为同一条。

遇到这类问题时，务请注意以下几点。

 多提问。此题存在诸多不明之处，多提问以厘清问题。许多面试官会故意提些模糊的问 题，考察你是否会说明自己的假设条件。

 尽量设计并使用数据结构，借此展示你了解并注重面向对象设计。

 仔细考虑要怎么设计数据结构来表示一条线。选择多多，各有优劣，必须权衡取舍。选

择一种数据结构，并说明理由。

 不要假设斜率和y轴截距就是整数。

 了解浮点表示法的限制。切记不要用==检查浮点数是否相等，而是应该检查两者差值是否小于某个极小值（如上面代码中的epsilon值）。

7.4 编写方法，实现整数的乘法、减法和除法运算。只允许使用加号。（第 63 页）

实现

public static int negate(int a) { 
int neg = 0; 
int d = a < 0 ? 1 : -1; 

while (a != 0) { 
    neg += d; 
    a += d; 
} 
return neg;
}

多想想乘法和除法的本质，以逻辑思考的方式解题，这么做很管用。记住，所有（好的） 面试题都能以逻辑、系统的方式解出来！  面试官想找的就是这种能以逻辑思考逐步解决问题的人。  这是个让你展示自己能够写出干净代码的绝佳问题，特别是显示出你复用代码的能力。

例如，如果写代码时没有把negate独立出来，但要是发现相关代码使用多次，就应该将

这些代码写成一个方法。

7.5 在二维平面上，有两个正方形，请找出一条直线，能够将这两个正方形对半分。假定 正方形的上下两条边与x轴平行。（第 63 页）

在着手解题之前，有必要思考一下题中一条“线”的准确含义。一条线是由斜率和y轴截距 确定？还是由这条线上的任意两点定义？抑或，所谓的线其实是线段，以正方形的边作为起点和 终点？

其中第三种情况会让此题变得更有意思一些，因此这里假设：这条线的端点应该落在正方形 的边上。在面试中，你应该与面试官讨论假设条件。

要将两个正方形对半分，这条线必须连接两个正方形的中心点。

7.6 在二维平面上，有一些点，请找出经过点数最多的那条线。（第 63 页）

不过，其中有个地方比较棘手。首先，我们定义，若两条直线的斜率和y轴截距相同，则这 两条直线相等。接着，我们会基于这些值（确切地说，是基于斜率）对直线进行散列。问题是浮 点数不一定能用二进制精确表示。对此，我们的解决办法是检查两个浮点数的差值是否在某个极 小值（epsilon）内。

对散列表而言，这又意味着什么呢？这意味着，斜率“相等”的两条直线，散列值未必相同。 为此，我们将把斜率减去一个极小值，并以得到的结果flooredSlope作为散列键。然后，要取 得所有可能相等的直线， 我们会搜索三个位置： flooredSlope 、 flooredSlope - epsilon 和 flooredSlope + epsilon。这能确保我们已检查了所有可能相等的直线。

浮点数

特殊直线

7.7 有些数的素因子只有 3、5、7，请设计一个算法，找出其中第k个数。（第 63 页）

DP