Есенен турнир 2004, Задача B2. СРЕДНА СТОЙНОСТ И ВАРИАЦИЯ
Уловието на задачата може да прочетете
тук.
Решение
Първото нещо, което трябва да се направи, е да се
опрости формулата за средното аритметично на квадратите на отклоненията на
отделните точки от средната стойност E.Използвайки формулата за
повдигане на квадрат и групирайки събираемите получаваме:
S
= ((x1-E)2 + (x2-E)2 + ... + (xn-E)2)/n
= (x12 + x22 + … + xn2
– 2.E.(x1 + x2 + .. + xn) + n.E2
)/n
От дефиницията за E имаме
E
= (x1 + x2 + x3 + ... + xn) / n
Следователно
(x1 + x2 + x3 + ... + xn) = E.n
Оттук
S
= ((x1-E)2 + (x2-E)2 + ... + (xn-E)2)
/ n = (x12 + x22 + ... + x
n2 – 2.E.(x1
+ x2 + ... + xn) + n.E2) / n = (x12
+ x22 + ... + xn2)/n – (2.E2.n
+ n.E2) / n = (x12
+ x22 + ... + xn2)/n – E2
За решението се използва един
стандартен подход, който е подходящ когато се изисква да се намери сума на последователност от числа в
масив. За целта използваме един допълнителен масивT, в който на позиция T[i] си пазим сумата от първитеi числа в масива. Така
T[0]
= 0
T[1]
= s[1]
T[2]
= s[1] + s[2] = T[1] + s[2]
T[3] = s[1] +
s[2] + s[3] = T[2] + s[3]
...
T[n]
= T[n-1] + s[n]
Където с s[i]
сме отбелязали i-тия елемент от
входния масив. Очевидно този масив се получава с O(N) операции. Тогава от начина, по който сме дефинирали T следва, че сумата на елементите между
дадени два индекса a и b е точно
Sum(a,b)
= T[b] – T[a-1]
а да решим поставената ни задача ще дефинираме два
масива, които притежават горното свойство – масив T, който ще пази сумата на
първите K числа и масивTsqr, който ще пази сумата от квадратите на първите
K числа. Тогава стойностите на E и S
за даден интервал [p;q]са съответно:
Е = (T[p]-T[q-1]) / (p-q+1)
S
= (Tsqr[p]-Tsqr[q-1]) / (p-q+1) + E2
Тогава за всеки интервала ние отговаряме със сложност
O(1). Така сложността на дадения алгоритъм е O(N+K*1) = O(N+K).
Примерна реализация:
#include <stdio.h>
#define MAXN 500001
int sum[MAXN]; // sum[X] = sumata na pyrwite X chisla ot whoda
int sqr[MAXN]; // sqr[X] = sumata ot kwadratite na pyrwite X chisla ot whoda
int main () {
double E;
int n,m,i,a,b;
scanf("%d%d",&n,&m);
// presmiatame masiwite sum i sqr
for (i=1;i<=n;i++) {
scanf("%d",&a);
sum[i] = sum[i-1] + a;
sqr[i] = sqr[i-1] + a*a;
}
for (i=0;i<m;i++) {
scanf("%d%d",&a,&b);
// izchisliawame E i S po opisanata formula
printf("%.4lf %.4lf\n",E = ((sum[b] - sum[a-1])/
(double)(b-a+1)),(sqr[b] - sqr[a-1])/(double)(b-a+1) - E*E);
}
return 0;
}
Автор: Слави Маринов
обратно към брой 26
|