编程之美习题集

1 有一架飞机将要起飞，乘客们按照机票号1，2，3，4.。N的顺序依次登机，来了一只大猩猩，他也有飞机票，他插队登上了飞机，然后随机找了一个位置坐了下来，如果下面的乘客也跟大猩猩一样，不按照他们的座位坐下来的，那么第i个乘客（除去大猩猩）坐到自己原机票位置的概率是多少。
我的解法和书上给出的答案有点不同，首先，到达第i个乘客的时候，前面i-1个乘客和大猩猩做的座位的组合数总共有N*（N-1）*(N-2)....*（N-i））个，然后，如果前面i-1个乘客包括猩猩都不选择第i个乘客位置坐的及第个乘客最总坐在他自己的位子上的组合数是（N-1）（N-1）*...(N-i)*1,所以两者一比，最总的概率是
1/N;
2 如何判断一个点是否在三角形内
这我是看它答案后恍然大悟的，如果一个点在三角形内，那么它与三个点形成的面积应该刚好是三角形的面积，如果大于三角形的面积，说明他在点外。同理，如何判断一个点在一个立方体内，也是可以用同样的办法判别。
3 一个磁盘上有n个文件，每个文件的长度分别是L[0],L[1],L[2]...,且被访问到的概率分别是P[0],P[1]..要定位到磁带上的第n个文件，需要进过前面n-1个文件，才能找到第n个文件，请问，如何安排他们在磁盘上的存储顺序最好？
思路：要达到最佳的访问效率，那么，访问这些文件的平均长度应该是最短的，那么我们可以分别考虑一下如果访问文件的概率相同，长度不同；长度相同，概率不同；长度，概率都不同这三种情况，前两种列出数学表达式之后比较容易得到结果，最后一种情况，其实可以考虑比较P/L,即概率除以长度，来得出平均每个文件在单位长度的访问概率来作为度量的标准。

4 有一个桶，里面有白球，黑球各100个，人们必须按照以下的规则把球取出来：
1 每次从桶里面拿两个球
2 如果两个是同色的球，就再放入一个黑球
3 如果两个异色的球，就再放入一个白球
问：最后桶里面只剩下一个黑球的概率是多少？
思路：一开始，我在看这道题的时候，我也是满脸的茫然，这么多种情况，怎么来界定这个不变的量呢？后来，我才知道原来事情其实是可以化繁为简的。其实如果我们考虑一下，如果袋子里只有一个黑球和一个白球，那么，最后剩下的肯定是白球，如果是2个白球，两个黑球，那么最后无论你最后是怎么拿的，最终剩下的都是黑色的。貌似没有什么规律，编程之美里面给出的解法确实很妙，它根据这两个条件，居然运用到了数学里面的异或（XOR）：两个相同的数，异或等于0；两个不同的数，异或等于1；由于异或满足结合律，即
（aXORb）XORc = aXOR(bXORc),那么其实可以把100个黑球和白球看做是1和0，那么取出这些球的过程其实可以看做是这些数进行异或的过程。
5 蚂蚁爬杆
有一根27厘米的细木杆，在第3厘米，7厘米，11厘米，17厘米，23厘米的这五个地方各有一只蚂蚁。木杆很细，不能同时通过两只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只能朝前或掉头，但不会后退。当任意两只蚂蚁碰头的时候，它们同时调头朝反方向走。假设蚂蚁每一分钟可以走一厘米，求所有蚂蚁都离开木杆的最短时间和最长时间。
思路：其实，我做这道题的时候，罗列了很多种情况，后来才发现，原来，其实换一个思路，其实问题可以很简单的。想象一下，现在只有两只蚂蚁，蚂蚁相碰之后朝反方向走，那么其实可以看做是两只蚂蚁都还在前进，不过时他们的身体“互换”了一下，为什么这么想呢？其实，无论蚂蚁朝哪个方向走，它只要往离木杆最远的地方走，就可以得到最远的时间，反之亦然，那么，其实，你只要计算蚂蚁朝两个方向走的时间分别是多少，计算一下时间，比较一下大小就行了。