题目
在一条无限长的跑道上，有N匹马在不同的位置上出发开始赛马。当开始赛马比赛后，所有的马开始以自己的速度一直匀速前进。每匹马的速度都不一样，且全部是同样的均匀随机分布。在比赛中当某匹马追上了前面的某匹马时，被追上的马就出局。 请问按以上的规则比赛无限长的时间后，赛道上剩余的马匹数量的数学期望是多少
输入描述
每个测试输入包含1个测试用例
输入只有一行，一个正整数N
1 <= N <= 1000
输出描述
输出一个浮点数，精确到小数点后四位数字，表示剩余马匹数量的数学期望
输入例子
1
2
输出例子
1.0000
1.5000
问题分析
条件
- 赛道无限长！！！
- 赛道无限长！！！
- 赛道无限长！！！
重要的事情先说三遍 - 马被追上就出局
马匹的速度不同，所以假设为a1>a2>a3......>an
a1一定能活，概率为1
a2在a1之后才能活，a2有两种情况:a1之前，a1之后。概率为1/2
a2在a1，a2之后才能活，a3有三种情况: a1之前，a1，a2之间，a2之后。概率为1/3
...
ak在a1....ak-1之后才能活。k种情况，概率为1/k
...
an在a1....an-1之后才能活。n种情况，概率为1/n
即总的期望为1 + 1/2 + 1/3 + .... 1/k + ...1/n,归纳得f(n) = f(n-1) + 1/n
代码
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
double sum = 0.0;
for (int i = 1; i <= n; i++) {
sum = sum + 1.0 / i;
}
printf("%.4lf\n", sum);
return 0;
}
