URAL - 1828 Approximation by a Progression(最小二乘法)
浏览数：31 /
时间：2015年06月11日
| Time Limit: 500MS | Memory Limit: 65536KB | 64bit IO Format: %I64d & %I64u |
Description
Your are given a sequence of integers a1, …, an. Find an arithmetic progression b1, …, 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 a1,
…, 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<iostream>
#include<iomanip>
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 <<fixed<<setprecision(6)<< a1 << " " <<fixed<<setprecision(6)<<k << endl;
}
}郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
