[算法题]Numerical Summation of a Series

roger

Numerical Summation of a Series from ZOJ（浙大OJ） Problem Set – 1007，

链接http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1007。

题目如下：

Produce a table of the values of the series

Equation 1

for the 2001 values of x, x= 0.000, 0.001, 0.002, ..., 2.000. All entries of the table must have an absolute error less than 0.5e-12 (12 digits of precision). This problem is based on a problem from Hamming (1962), when mainframes were very slow by today's microcomputer standards.

Input

This problem has no input.

Output

The output is to be formatted as two columns with the values of x and y(x) printed as in the C printf or the Pascal writeln.

printf("%5.3f %16.12f\n", x, psix )                writeln(x:5:3, psix:16:12)

As an example, here are 4 acceptable lines out of 2001.

0.000   1.644934066848

...

0.500   1.227411277760

...

1.000   1.000000000000

...

2.000   0.750000000000

The values of x should start at 0.000 and increase by 0.001 until the line with x=2.000 is output.

Hint

The problem with summing the sequence in equation 1 is that too many terms may be required to complete the summation in the given time. Additionally, if enough terms were to be summed, roundoff would render any typical double precision computation useless for the desired precision.

To improve the convergence of the summation process note that

Equation 2

which implies y(1)=1.0. One can then produce a series for y(x) - y(1) which converges faster than the original series. This series not only converges much faster, it also reduces roundoff loss.

This process of finding a faster converging series may be repeated to produce sequences which converge more and more rapidly than the previous ones.

The following inequality is helpful in determining how may items are required in summing the series above.

Equation 3

题目简述：

计算第一个式子，要求计算 2001个x的值, x= 0.000, 0.001, 0.002, …, 2.000. 所有的结果精度必须小于 0.5e-12 (小数点12位)。并且有时间限制。

分析

如果没有时间要求的话，完全可以写一个程序来无限接近于真实值，但是有20秒的时间限制， 那么该怎么办呢，所以题目给了提示，我们可以用该公式2来加速收敛速度，这样就能在很短的时间里快速收敛，但是本题对精度的要求也特别高，即使使用了公式2来加快速度，精度也达不到要求，所以题目又给了公式3来提高精度，只要运用了公式2和公式3就能满足题目要求，计算出合适的公式1的值。这道题的意思应该是用一个新的公式来近似原公式，有较快的收敛速度，而且需要保留精度到合适程度。

下面是推导公式：

第三个公式应该是一个放缩法，确定一个界限。或许你会疑问“最后取得值应该是大于Rn的吧，这里不考虑精度丢失吗？”这里我询问过大佬，他们的回答是：“这可能有部分理由可以不用考虑。或者已经很小了之类的。毕竟加到无穷的表达式，计算机里总要取一个合适的边界的。”图中的10e6次方与要求的精度0.5e-12次方没有关系的，这里写错了，这里将n设置为20000既可以满足题目要求了。

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 20000
int main()
{
    double sum, x;
    int i, ii;
    for (i = 0; i < 2001; i++)
    {
        sum = 0;
        for (ii = 1; ii < MAX; ii++)
        {
            sum += (1.0 - x) / ((double)ii * ((double)ii + x) * ((double)ii + 1.0));
        }
        sum += (1.0 - x) / (2.0 * ((double)MAX - 1.0) * ((double)MAX - 1.0)) + 1.0;
        printf("%5.3lf %16.12lf\n", x, sum);
        x += 0.001;
    }
    return 0;
}

本文解题过程转自http://blog.eonew.cn/archives/500

Gu-f

这个解释6，赞一个

roger

Gu-f 发表于 2019-3-8 23:21