2008信息工程学院集训队——选拔赛

题目大意：给你一个定义的分数矩阵(如上所示)，求它各项上的分数的和。

思路：直接算太麻烦，找规律来解决。

思考N=1，N=2，N=3的情况。

1/1    1/1 1/2    1/1 1/2 1/3

          1/2 1/1    1/2 1/1 1/2

                           1/3 1/2 1/1

多了右下角的那一块。通过找规律发现：右下角都为1，除了1之外，是1/2 + 1/3 + … + 1/N的二倍。

这样直接递推就可以了。用num来计算2倍的1/2 + 1/3 + … + 1/N。用数组a[]来计算结果。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

double a[50010];

int main()
{
    double num = 0;
    for(int i = 1; i <= 50000; ++i)
    {

        if(i == 1)
            a[i] = 1;
        else
        {
            num += 2.0/i;
             a[i] = a[i-1] + num + 1;
        }

    }
    int N;
    while(cin >> N && N)
    {
        printf("%.2lf\n",a[N]);
    }
    return 0;
}

HDU2156 分数矩阵【水题】【递推】