algorytm.org

Algorytm Shaw-Trauba

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Shaw-Trauba
Ocena użytkowników:***** / 5
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 08 sierpnia 2005 21:32

Algorytm ten pozwala obliczyć wartość znormalizowanej pochodnej danego wielomianu danego wzorem:
W(x)=a_nx^n+...+a_1x+a_0
gdzie n oznacza stopień wielomanu. Znormalizowana pochodna ma postać:
\frac{w^{(j)}(x)}{j!}
Mamy dane pewne liczby naturalne p oraz q takie, że n+1=pq. Zdefiniujemy teraz pomocnicze funkcje:
s(j) = (n-j) \mod q\\\\ r(j)=\begin{cases} 0 & \text{ jeżeli } j \mod q \neq 0\\ q & \text{ jeżeli } j \mod q = 0 \end{cases}
Oraz główną funkcję obliczającą znormalizowaną pochodną czyli:
T^{-1}_i = a_{n-i-1}x^{s(i+1)}\\\\ T_j^j = a_nx^{s(0)}\\\\ T_i^{j} = T_{i-1}^{j-1} + T_{i-1}^{j}x^{r(i-j)}\\\\ T_n^j = \frac{w^{(j)}(x)}{j!}x^{j \mod q}
By zaimplementować ten algorytm wystarczy zdefiniować trzy powyższe funkcje. By uzyskać wynik pochodnej rzędu j wielomianu stopnia n należy wynik funkcji Tnj podzielić przez xj mod q, chyba że obliczamy znormalizowaną pochodną j-tego rzędu w punkcie x=0, wówczas jest ona równa aj.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 2
Tomasz LubińskiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 2
Tomasz LubińskiJava
.java
.java
***** / 3
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 26 września 2012 20:10
Dodaj komentarz