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]

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ą.

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

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.

Pari / GP , 12 bajtów

Tak, wbudowany. Krótszy niż Mathematica.

polchebyshev

Wypróbuj online!

Bez wbudowanego:

Pari / GP , 34 bajty

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

Wypróbuj online!

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.

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

Python + SymPy , 66 bajtów

from sympy.abc import*
T=lambda n:n<2and x**n or 2*x*T(n-1)-T(n-2)

Wypróbuj online!

Z reprezentacją malejących współczynników

from sympy import*
x=symbols('x')
T=lambda n:n<2and x**n or expand(2*x*T(n-1)-T(n-2))

Wypróbuj online!

SageMath, 25 bajtów

lambda n:chebyshev_T(n,x)

Wypróbuj online

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

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

Rubinowy + wielomian , 59 58 + 13 = 72 71 bajtów

Używa -rpolynomialflagi.

f=->n{x=Polynomial.new 0,1;n<2?[1,x][n]:2*x*f[n-1]-f[n-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!

Python 2 , 79 bajtów

f=lambda n:n>1and[2*a-b for a,b in zip([0]+f(n-1),f(n-2)+[0,0])]or range(1-n,2)

Wypróbuj online!

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

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

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.