Многочлены Чебышёва (Chebyshev Polynomials)


26

Wielomiany Czebyszewa to rodzina wielomianów ortogonalnych, które pojawiają się w różnych miejscach matematyki i mają wiele interesujących właściwości. Jedną z ich cech charakterystycznych jest to, że są to wyjątkowe wielomiany, które spełniają .Tn(cos(x)) = cos(n*x)

Wyzwanie

Biorąc pod uwagę nieujemną liczbę całkowitą n, należy nwypisać -ty wielomian Czebyszewa. .Tn(x)

Definicja

n-Ty Wielomiany Czebyszewa jest przez następujące trzy pojęcia rekurencji:

T0(x) = 1
T1(x) = x
Tn+1(x) = 2*x*Tn(x) - Tn-1(x)

Detale

Jeśli twój język ma rodzimy typ wielomianu, możesz użyć go jako wyniku, w przeciwnym razie powinieneś wypisać listę współczynników w porządku rosnącym lub malejącym, lub jako ciąg reprezentujący wielomian.

Przykłady

T0(x) = 1
T1(x) = x 
T2(x) = 2x^2 - 1
T3(x) = 4x^3 - 3 x
T4(x) = 8x^4 - 8x^2 + 1
T5(x) = 16x^5 - 20x^3 + 5x
T10(x) = 512x^10 - 1280x^8 + 1120x^6 - 400x^4 + 50x^2 - 1

W formacie malejącej listy stopni otrzymywalibyśmy, aw malejącym formacie stopni otrzymywalibyśmyT3(x) = [4,0,-3,0]T3(x) = [0,-3,0,4]


Jeśli wypisuję listę, czy mogę wypisać 0 1(tj. 0*x+1) Dla T_0?
Luis Mendo,

Dopóki kolejność monomialów jest spójna, to jest ok!
flawr

@ flawr jest 2*x*(2*x**2 - 1) - xok jako wyjście dla 3 dla języka wspierającego wielomian, czy też potrzebujemy reprezentacji jako współczynników opisu?
Uriel,


2
Czy dopuszczalne są niedokładności zmiennoprzecinkowe? tj.T_5(n) = [0, 5, 3.55271e-15, -20, 0, 16]
mile

Odpowiedzi:


15

Mathematica, 15 bajtów

#~ChebyshevT~x&

Oczywiście Mathematica ma wbudowaną funkcję.

Jeśli dozwolony jest alternatywny formularz wejściowy (10 bajtów):

ChebyshevT

przyjmuje liczbę całkowitą ni zmienną.


3
Nie mogłem zgadnąć. : P
HyperNeutrino,

14

Oktawa , 39 bajtów

@(n)round(2^n/2*poly(cos((.5:n)/n*pi)))

Wypróbuj online!

Wyjaśnienie

cos((.5:n)/n*pi)buduje wektor z pierwiastkami wielomianu , podanymi przez

wprowadź opis zdjęcia tutaj

polydaje wielomian moniczny z tymi pierwiastkami. Mnożenie przez 2^n/2skaluje odpowiednio współczynniki. roundzapewnia, że ​​wyniki są liczbami całkowitymi pomimo precyzji liczbowej.




10

Haskell , 62 bajty

t n|n<2=1:[0|n>0]|x<-(*2)<$>t(n-1)++[0]=zipWith(-)x$0:0:t(n-2)

Wypróbuj online!

flawr zapisał bajt.


To jest bardzo eleganckie! ( zipWith
Wciąż

1
Myślę, że możesz nawet zapisać jeszcze jeden bajt, korzystając ze strażników: t n|n<2=1:[0|n>0]|x<-(*2)<$>t(n-1)++[0]=zipWith(-)x$0:t(n-2)w ten sposób możesz usunąć środkową parę nawiasów w ostatniej linii :)
flawr

Myślę, że musisz zmienić 0:na 0:0:- OP po prostu zabronił tego rodzaju pomijania zer.
Ørjan Johansen

7

CJam (21 bajtów)

1a2,qi{0X$+2f*@.-}*;`

Jest to pełny program: odpowiednik bloku anonimowego ma tę samą długość:

{1a2,@{0X$+2f*@.-}*;}

Demo online




5

MATL , 17 bajtów

lFTi:"0yhEbFFh-]x

Współczynniki są wyprowadzane w kolejności rosnącej.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

Dla wejścia n kod stosuje relację rekurencyjną n razy. Dwa najnowsze wielomiany są zawsze przechowywane na stosie. Podczas obliczania nowego wielomianu najstarszy jest usuwany.

Na końcu wyświetlany jest wielomian przedostatni (ostatni wielomian jest usuwany), ponieważ wykonaliśmy jedną zbyt wiele iteracji.

l        % Push 1
FT       % Push [0 1]. These are the first two polynomials
i:"      % Input n. Do the following n times
  0      %   Push 0
  y      %   Duplicate most recent polynomial
  h      %   Concatenate: prepends 0 to that polynomial
  E      %   Multiply coefficients by 2
  b      %   Bubble up. This moves second-most recent polynomial to top
  FF     %   Push [0 0]
  h      %   Concatenate: appends [0 0] to that polynomial
  -      %   Subtract coefficients
]        % End
x        % Delete. Implicitly display

4

Galaretka , 18 bajtów

Cr1µ’ßḤ0;_’’$ß$µỊ?

Wypróbuj online!

Zwraca listę współczynników w porządku rosnącym.

Istnieje inne rozwiązanie dla 17 bajtów z niedokładnościami zmiennoprzecinkowymi.

RḤ’÷Ḥ-*ḞÆṛæ«’µ1Ṡ?

Wypróbuj online!

Wyjaśnienie

Cr1µ’ßḤ0;_’’$ß$µỊ?  Input: integer n
                Ị   Insignificant - abs(n) <= 1
                    If true, n = 0 or n = 1
   µ                  Monadic chain
C                       Complement, 1-x
 r1                     Range to 1
                    Else
               µ      Monadic chain
    ’                   Decrement
     ß                  Call itself recursively
      Ḥ                 Double
       0;               Prepend 0
         _              Subtract with
            $             Monadic chain
          ’’                Decrement twice
              $           Monadic chain
             ß              Call itself recursively



2

J , 33 bajty

(0>.<:)2&*1:p.@;9:o._1^+:%~1+2*i.

Wypróbuj online!

Zakłada, że ​​niedokładności zmiennoprzecinkowe są dopuszczalne i tworzy emoji (0>.<:)

Dla 41 bajtów istnieje inne rozwiązanie, które pozwala uniknąć liczb zmiennoprzecinkowych.

(0&,1:)`(-&2((-,&0 0)~2*0&,)&$:<:)@.(>&1)

Wypróbuj online!



2

Aksjomat, 40 bajtów

f(n,x)==(n<2=>x^n;2*x*f(n-1,x)-f(n-2,x))

wyniki

(9) -> for i in [0,1,2,3,4,5,10] repeat output ["f(y)",i,"=", f(i,y)]
   ["f(y)",0,"=",1]
   ["f(y)",1,"=",y]
                   2
   ["f(y)",2,"=",2y  - 1]
                   3
   ["f(y)",3,"=",4y  - 3y]
                   4     2
   ["f(y)",4,"=",8y  - 8y  + 1]
                    5      3
   ["f(y)",5,"=",16y  - 20y  + 5y]
                      10        8        6       4      2
   ["f(y)",10,"=",512y   - 1280y  + 1120y  - 400y  + 50y  - 1]
                                                               Type: Void

możliwe jest zdefiniowanie jednego prawa podstawienia dla wzoru w aksjomacie powyżej funkcji f () dla rozszerzenia cos (n * x), gdzie n jest jedną liczbą całkowitą

(9) -> o:=rule cos(n*%y)==f(n,cos(%y))
   (9)  cos(%y n) == 'f(n,cos(%y))
                    Type: RewriteRule(Integer,Integer,Expression Integer)
                                                              Time: 0 sec
(10) -> b:=o cos(20*x)
   (10)
                 20                18                16                14
     524288cos(x)   - 2621440cos(x)   + 5570560cos(x)   - 6553600cos(x)
   +
                  12                10               8              6
     4659200cos(x)   - 2050048cos(x)   + 549120cos(x)  - 84480cos(x)
   +
               4            2
     6600cos(x)  - 200cos(x)  + 1
                                                 Type: Expression Integer
                       Time: 0.48 (EV) + 0.02 (OT) + 0.10 (GC) = 0.60 sec

1

C # (.NET Core) , 126 bajtów

f=n=>n==0?new[]{1}:n==1?new[]{0,1}:new[]{0}.Concat(f(n-1)).Select((a,i)=>2*a-(i<n-1?f(n-2)[i]:0)).ToArray();

Liczba bajtów obejmuje również:

using System.Linq;

Wypróbuj online!

Funkcja zwraca wielomian jako tablicę współczynników w porządku rosnącym (od x^0do x^n)

Wyjaśnienie:

f = n =>                          // Create a function taking one parameter (int)
    n == 0 ? new[] { 1 } :        // If it's 0, return collection [1]
    n == 1 ? new[] { 0, 1 } :     // If it's 1, return collection [0,1] (so x + 0)
    new[] { 0 }                   // Else create new collection, starting with 0
        .Concat(f(n - 1))         // Concatenate with f(n-1), effectively multiplying polynomial by x
        .Select((a, i) => 2 * a - (i < n - 1 ? f(n - 2)[i] : 0))
                                  // Multiply everything by 2 and if possible, subtract f(n-2)
        .ToArray();               // Change collection to array so we have a nice short [] operator
                                  // Actually omitting this and using .ElementAt(i) is the same length, but this is my personal preference

1

JavaScript (ES6), 65 bajtów

f=n=>n?n>1?[0,...f(n-1)].map((e,i)=>e+e-(f(n-2)[i]||0)):[0,1]:[1]

Niewystarczające dla dużych n. Ciekawe, ale niestety nieefektywne:

n=>[...Array(n+1)].map(g=(m=n,i)=>i<0|i>m?0:m<2?i^m^1:g(m-1,i-1)*2-g(m-2,i))

Bardzo wydajny dla 68 bajtów:

f=(n,a=[1],b=[0,1])=>n?f(n-1,b,[0,...b].map((e,i)=>e+e-(a[i]||0))):a

Zwraca tablicę współczynników w porządku rosnącym.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.