问题描述
一个未婚男青年要和N个女孩相亲，由于他不记录已经相亲过的女孩，而是每一次随机从这N个女孩中挑选一个进行相亲。由于相亲的女孩可能是已经相亲过的，那么现在的问题就是他平均要相亲多少次，才能将所有的女孩都相亲一遍（期望）。
问题分析
其实呢，这道题只是一道披着编程外表的数学题。他就是要求男孩相亲次数的期望。假设用随机变量$X$表示男孩按上述方式相亲完所有女孩的所需要的次数，那么题目要求的就是$E(X)$，数学上叫做随机变量的期望。
对于离散的随机变量$X$来说，要求他的期望$E(X)$的一般方法就是根据定义来求。也就是说，计算出$X$的每一个可能的取值$x_i$以及对应的概率$p_i$，接下来我们就可以得到它的期望为
$$
E(X) = \sum_{i} {x_i \cdot p_i}
$$
我们可以尝试以这个方式去求得上个问题的期望。首先,我们需要分析出变量$X$所有可能的取值范围。要相亲完N个女孩，考虑最好的情况，这个未婚男青年每次随机挑选到的刚好就是他还没有相亲的，那么他相亲的次数至少也为$N$。然而，这个男青年最多需要多少次，也就是说随机变量$X$的最大值可能是多少？通过简单的分析就可以知道，变量$X$的最大取值是趋于正无穷的，也就是说为了求得期望，我们可能要求一个数学级数，即$E(X) = \sum_{i=N}^{\infty} {i\cdot p_i}$。
先不说这个级数如何求取的问题，这样求解期望的最大问题在于每一个值$i$对应的概率$p_i$是非常难求的。举个例子来说，N个女孩，男青年总共用了$2N$次完成相亲的概率$p_{2N}$是多少？这里面的可能性太多了，就算你能求出来共有$M$中可能，那么$p_{2N} = M / N^{2N}$，这里的运算很容易就溢出了，计算结果根本无法保证精确性。
问题求解
为了正确的解决这个问题，我们需要利用期望函数$E$的线性性质来解决该问题。简单的来说，如果有一个随机变量$X = w_1 Y_1 + w_2 Y_2$，那么$E(X) = w_1E(Y_1) + w_2E(Y_2)$，其中$w_1,w_2$是常数。值得一提的是，这里面我们不需要变量$Y_1$和$Y_2$是相互独立的，哪怕他们相关期望的线性性质也依旧成立。
所以，我们将上面的随机变量$X$进行拆分。首先定义随机变量$Y_i$代表当已经相亲的人数有$i-1$人时，每次随机选一个人相亲，相亲到一个没相亲过的人所需要的次数，所以我们就有了如下的关系
$$
X = Y_1 +Y_2 + … + Y_N
$$
仔细体味一下上面的关系，它是为什么成立的，在这你就不具体分析了。
有了这个公式之后，接下来的问题就是如何求随机变量$Y_i$的期望了。对于随机变量$Y_i$，我们可以分析出他的取值的可能性为$[1,\infty]$，这意味着求取$Y_i$的期望是一样要算级数。不过算级数可以通过数学工具，重点是在这种情况下，$Y_i$的每一种取值$y$对应的概率$p_y$很好求得。
当已经相亲的人数有$i-1$人时，每次随机选一个人相亲，那么选出没有相亲过的人的概率即为$\frac{N-i+1}{N}$,选出相亲过的人的概率为$\frac{i-1}{N}$,令
$$
p = \frac{N-i+1}{N},q = \frac{i-1}{N}
$$
那么这就是一个二项分布，且$y$对应的概率$p_y= q^{y-1}\cdot p$。也就是说前$y-1$次都选的是已经相亲过的，第$y$次选到了一个没有相亲过的。
根据以上的推导，我们可以得到
$$
E(Y_i) = \sum_{y = 1}^{\infty} y\cdot q^{y-1}\cdot p
$$
为了求得该级数的值其实很简单，利用高中的知识就足够了。首先在公式的两边同时乘以$q$，我们得到
$$
qE(Y_i) = \sum_{y = 1}^{\infty} (y-1)\cdot q^{y-1}\cdot p
$$
将上面两个式子相减，得到
$$
(1-q)E(Y_i) = p \cdot \sum_{y = 1}^{\infty} q^{y-1} = p \frac{1 \cdot (1-q^{\infty})}{1-q} = \frac{p}{1-q}
$$
所以我们可以得到
$$
E(Y_i) = \frac{p}{(1-q)^2} = \frac{1}{p}
$$
所以，到此时，我们就可以很轻松的求得$X$的期望
$$
E(X) = E(Y_1) +E(Y_2) + … +E(Y_N)= \frac{1}{\frac{N}{N}} + \frac{1}{\frac{N-1}{N}} + \frac{1}{\frac{N-2}{N}} + … +\frac{1}{\frac{1}{N}}
$$
接下来就是变成求一下上面这个公式的值了，基本上C语言10行以内就解决了，求出来的结果精度较高且不会溢出。
