hdu 4986 Little Pony and Alohomora Part I(递推)

题目链接：hdu 4986 Little Pony and Alohomora Part I

题目大意：给定若干个箱子，每个箱子中装着一把钥匙，问最少要敲开多少个箱子才能打开所有箱子。

解题思路：需要敲开的次数即为整个序列循环的个数，知道这点就很容易得到f(i)=f(i−1)+1i,然后对于n小的情况，用递推即可，对于n大的情况，用log函数近似处理。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int maxn = 1e6;

double p[maxn+5];

void init () {
    p[1] = 1;
    for (int i = 2; i <= maxn; i++)
        p[i] = p[i-1] + 1.0 / i;
}

int main () {
    init();
    int n;
    while (scanf("%d", &n) == 1) {
        printf("%.4lf\n", n >= maxn ? 0.577215664901 + log((double)n) : p[n]);
    }
    return 0;
}