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