Approximation by a Progression
| Time Limit: 500MS |
|
Memory Limit: 65536KB |
|
64bit IO Format: %I64d & %I64u |
Submit Status
Description
Your are given a sequence of integers
a
1, …,
an. Find an arithmetic progression
b
1, …,
bn for which the value ∑(
ai ?
bi)
2 is minimal. The elements of the progression can be non-integral.
Input
The first line contains the number
n of elements in the sequence (2 ≤
n ≤ 10
4). In the second line you are given the integers
a
1, …,
an; their absolute values do not exceed 10
4.
Output
Output two numbers separated with a space: the first term of the required arithmetic progression and its difference, with an absolute or relative error of at most 10
?6. It is guaranteed that the answer is unique for all input data.
Sample Input
| input |
output |
4
0 6 10 15
|
0.400 4.900
|
4
-2 -2 -2 -2
|
-2 0
|
arithmetic progression 等差数列的通式an=a1+（n-1)*d，即an=（a1-d）+n*d 是直线方程的形式，而（i，mi）是分布在直线两边的点，要求直线的 k=d，b=a1-d，于是想到最小二乘法，对Y=kX+b ， 有 k=（（XY）平--X平*Y平）/（（X^2）平--(X平）^2）， b=Y平--kX平。按公式求就好了。
#include
#include
using namespace std; const int MAXN = 10005; double a[MAXN]; int main() { int n; while (cin >> n) { for (int i = 1; i <= n; i++) cin >> a[i]; double xy=0, x=0, y=0, x2=0; for (int i = 1; i <= n; i++) { xy = xy + a[i] * i; x = x + i; y = y + a[i]; x2 = x2 + i*i; } double k = (xy/n -(x/n)*(y/n)) / (x2/n - (x/n)*(x/n)); double b = y / n - k*(x / n); double a1 = b + k; double d = k; cout <