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ę stopniamiwielomianu 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
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