请教一道算法题

从（0，1）中随机抽取N个实数, 问 count 的期望值。(新的随机数大于前面所有数的个数的期望）。

每个随机数都是在（0，1）区间里面取值直到N个随机数。M记录的是当前最大的随机数。问的是在N次取值中会有几次M的值（期望值）会改变（M是递增的）。

其实就是说N个数的序列，新加入个数比前面的数都大的个数的期望。比如从（1，10）随机取整数取十个：
2，3，1，2，4，3，6，5，8，7
cnt = 5

想了很久没有头绪。想请教下思路。谢谢！

count = 0;
M = -∞ ;
for i = 1 to n {
  xi=rand() ; // float from (0,1)
  if (xi > M) then {
  M = xi;
  count + +;
  }
}

简单地说，只要你能求出“当第i号元素为k时，它是1~i号元素中最大数字的概率”p，这道题就很容易做。

比如，“2号元素为k时，它是目前最大数字"等价于“1号元素<k”，而后者的概率是k，所以前者的概率p也是k。那么，要求出“第2号元素是目前最大数字”的概率，只需考虑2号元素取所有k (0~1)的情况，即∫ p dk = ∫ k dk = 1/2。(稍微准确一点写的话，就是P(x2 is Max | x2 = k) = k => P(x2 is Max) =  ∫  P(x2 is Max, x2 = k) dk = ∫  P(x2 is Max | x2 = k) p ( x2 = k ) dk = ∫ k * 1 dk ）既然2号元素有1/2的概率是当前最大，那也就是说，2号位置上出现Max的期望个数是0.5。

p(“3号元素为k时，它是目前最大数字")==p(“1号元素<k”并且“2号元素<k”) = p(“1号元素<k”) * p(“2号元素<k”) = k^2，积分得 ∫ k^2 dk = 1/3，即3号位置上期望能出现0.333...个Max

同理，第i位置上出现Max的期望个数是1/i个。因此，N个位置上总共出现Max的期望个数是(1 + 1/2 + 1/3 + .... 1/N)

比如当N=10时，结果大概是2.93。你可以自行编写模拟程序验证这个结果。