描述 Description

小张很多年过年都没有回家了。 这次回家父母给他安排了很多个相亲的姑娘， 有一个很长的名单，长度为N。父亲负责安排约会，每次随机的选择一个要相亲的对象， 母亲负责记录哪些姑娘已经约会过了。直到和所有的姑娘都约会完一遍以后，这个浩大的相亲工程才会结束。这些天父母在吵架， 他们之间不会有任何言语沟通。所以父亲不知道那些姑娘已经约会过了。因此下次约会的对象很可能是以前已经约会过的。如果小张要把所有的姑娘都约会一遍， 那么平均需要约会多少个姑娘？

[阿里2017实习笔试]

分析 Analysis

1 随机过程解法：马尔可夫转移
Note: 没有约到0个人的概率，所以pi_0不应该存在；

最后一个人约会到了，就不会再约了，直接结束，所以pi_n的计算不应该加上N/N*pi_n。

2 和1中马尔可夫递推一样，这里直接递推过程。

没搞出来233333

3

多次随机模拟，看均值多少。