SPOJ Problem Set (main)

4381. Aproksymacja średniokwadratowa dyskretna

Problem code: ASDWIEL

Projekt nr 5

Aproksymacja średniokwadratowa dyskretna przy pomocy wielomianu.

Zadanie nie jest oceniane automatycznie. Należy przesłać kody źródłowe w języku C++.

Napisać program, który dla danych węzłów x

0

,x

1

,...,x

n

oraz wartości funkcji

f(x

0

),f(x

1

),...,f(x

n

)

wyznacza współczynniki a

0

,a

1

,...,a

n

wielomianu

aproksymacyjnego F(x) = a

0

+ a

1

x + a

2

x

2

+ ... + a

n

x

n

. Aproksymacja powinna

być aproksymacją średniokwadratową w sensie Lagrange’a.

Należy zwrócić uwagę na minimalizację liczby wykonywanych operacji arytmetycznych i wymagań
dotyczących pamięci.

W sprawozdaniu proszę uwzględnić€wyniki testów dla kilku przypadków różniących się
stopniami€wielomianu aproksymującego oraz węzłami aproksymacji. Wyniki aproksymacji należy
przedstawić również na wykresach. Proszę nie zapomnieć o obliczeniu wartości błędu. Sprawdź jaki
wpływ na wynik aproksymacji ma zmiana wartości f(x

i

) dla kilku węzłów x

i

.

Pomimo braku automatycznej oceny przez SPOJ należy zastosować poniższe formatowanie danych
wejściowych i wyjściowych.

Input

t [ liczba funkcji aproksymowanych ]

s [ stopień wielomianu aproksymującego ]
n [ liczba węzłów aproksymacji ]
x

1

y

1

x

2

y

2

. . .
x

n

y

n

m [ liczba zapytań o aproksymowane wartości ]
x’

1

x’

2

. . .
x’

m

. . . [dane dla kolejnych funkcji jeżeli t>1 ]

1

Output

Dla każdej funkcji aproksymowanej na wyjściu powinno pojawić się m par liczb ( x’

i

,F(x’

i

)

),

i=1,2,...,m

(każda para w osobnej linii). Bloki wyników dla poszczególnych funkcji należy

oddzielić pustą linią.

Added by:

Piotr

Date:

2009-05-16

Time limit: 1s
Source limit:50000B
Languages: C C99 strict C++ 4.0.0-8 C++ 4.3.2

2