Zaimplementuj metodę Eulera

9

Celem tego wyzwania jest zastosowanie metody Eulera do przybliżenia rozwiązania równania różniczkowego postaci f (n) (x) = c.

Dane wejściowe będą listą liczb całkowitych, w których n- ta wartość reprezentuje wartość f (n) (0). Pierwsza liczba całkowita to f (0), druga to f '(0) i tak dalej. Ostatnia liczba całkowita na tej liście jest stała i zawsze pozostanie taka sama.

Jako dane wejściowe zostanie również podana dodatnia (niezerowa) liczba całkowita x , która reprezentuje wartość docelową (próbujesz oszacować f (x)). Rozmiar kroku dla metody Eulera będzie zawsze wynosił 1. W związku z tym konieczne będzie wykonanie sumy x kroków.

Jeśli nie jesteś zaznajomiony z metodą Eulera, oto szczegółowy przykład z objaśnieniem wprowadzonych danych [4, -5, 3, -1], x = 8.

x       f(x)      f'(x)     f''(x)    f'''(x)
0          4         -5          3         -1
1   4-5 = -1  -5+3 = -2   3-1 =  2         -1
2  -1-2 = -3  -2+2 =  0   2-1 =  1         -1
3  -3+0 = -3   0+1 =  1   1-1 =  0         -1
4  -3+1 = -2   1+0 =  1   0-1 = -1         -1
5  -2+1 = -1   1-1 =  0  -1-1 = -2         -1
6  -1+0 = -1   0-2 = -2  -2-1 = -3         -1
7  -1-2 = -3  -2-3 = -5  -3-1 = -4         -1
8  -3-5 = -8

Zasadniczo każda komórka w wygenerowanej tabeli jest sumą komórki nad nią i komórki nad i po prawej stronie. Zatem f (a) = f (a-1) + f '(a-1); f '(a) = f' (a-1) + f '' (a-1); oraz f '' (a) = f '' (a-1) + f '' (a-1). Ostateczna odpowiedź to f (8) ≈ -8. ††

Lista wejściowa zawsze będzie zawierać 2 lub więcej elementów, z których wszystkie będą miały wartości bezwzględne mniejsze niż 10. x ≥ 1 jest również zagwarantowane. Dane wyjściowe to jedna liczba całkowita, przybliżenie f (x). Dane wejściowe można przyjmować w dowolnej kolejności (lista przed x lub x przed listą). W razie potrzeby x może być pierwszym lub ostatnim elementem listy.

Przypadki testowe:

[4, -5, 3, -1], x = 8 => -8
[1, 2, 3, 4, 5, 6], x = 10 => 3198
[1, 3, 3, 7], x = 20 => 8611
[-3, 3, -3, 3, -3, 3, -3, 3, -3], x = 15 => -9009
[1, 1], x = 1 => 2

†: warto zauważyć, że zastosowanie metody przybliżenia w tej sytuacji jest w rzeczywistości głupie. jednak dla celów tego wyzwania wybrano najprostszą możliwą funkcję.

††: rzeczywista wartość wynosi -25⅓, co kwalifikowałoby to przybliżenie jako „niezbyt dobre”.

Klamka
źródło

Odpowiedzi:

3

Haskell , 38 bajtów

l%n|n<1=l!!0|m<-n-1=l%m+tail(l++[0])%m

Wypróbuj online!

Poprawiono z 39 bajtów:

l%0=l!!0
l%n=l%(n-1)+tail(l++[0])%(n-1)

Rekurencyjnie wyraża wynik l%n. Przesunięcie w górę odpowiada zmniejszeniu n, a przesunięcie w prawo odpowiada tail lprzesunięciu wszystkich elementów listy o jedno miejsce w lewo. Tak więc, wynik l%njest wartością powyżej l%(n-1), plus wartość powyżej i po prawej stronie(tail l)%(n-1)

Podstawowym przypadkiem n==0jest pobranie pierwszego elementu listy.

Idealnie byłoby, gdyby dane wejściowe były wypełnione nieskończenie wieloma zerami po prawej stronie, ponieważ pochodne wielomianu ostatecznie stają się zerowe. Symulujemy to, dodając, 0kiedy wykonujemy tail.

Weird alt 41:

(iterate(\q l->q l+q(tail l++[0]))head!!)
xnor
źródło
3

MATL , 9 bajtów

:"TTZ+]1)

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

Wyjaśnienie

:"      % Implicitly input x. Do the following x times
  TT    %   Push [1 1]
  Z+    %   Convolution, keeping size. Implicitly inputs array the first time
]       % End
1)      % Get first entry. Implictly display
Luis Mendo
źródło
3

Galaretka , 6 5 bajtów

Ḋ+$¡Ḣ

Wypróbuj online!

-1 bajt dzięki @Doorknob

Wyjaśnienie

Ḋ+$¡Ḣ  - Main dyadic link. First input list, second x
       - (implicit) on the previous iteration (starting at input list)
Ḋ      - Dequeue. e.g. [-5,3,-1]
 +     - Add this to
       - (implicit) the previous iteration. e.g. [4+(-5),-5+3,3+(-1),-1+0]
  $¡   - apply this successively x times
    Ḣ  - get the first element from the resultant list
fireflame241
źródło
3

Brachylog , 13 12 bajtów

{,0s₂ᶠ+ᵐ}ⁱ⁾h

Wypróbuj online!

Jak to działa

{,0s₂ᶠ+ᵐ}ⁱ⁾h
{       }ⁱ⁾   iterate the previous predicate
              to the array specified by first element of input
              as many times as the second element of input
           h  and get the first element

              example input to predicate: [4, _5, 3, _1]
 ,0           append 0: [4, _5, 3, _1, 0]
   s₂ᶠ        find all substrings with length 2:
              [[4, _5], [_5, 3], [3, _1], [_1, 0]]
      +ᵐ      "add all the elements" mapped to each subarray:
              [_1, _2, _2, _1]

Poprzednie 13-bajtowe rozwiązanie

{b,0;?z+ᵐ}ⁱ⁾h

Wypróbuj online!

Jak to działa

{b,0;?z+ᵐ}ⁱ⁾h
{        }ⁱ⁾   iterate the previous predicate
               to the array specified by first element of input
               as many times as the second element of input
            h  and get the first element

               example input to predicate: [4, _5, 3, _1]
 b             remove the first element: [_5, 3, _1]
  ,0           append 0: [_5, 3, _1, 0]
    ;?         pair with input: [[_5, 3, _1, 0], [4, _5, 3, _1]]
      z        zip: [[_5, 4], [3, _5], [_1, 3], [0, _1]]
       +ᵐ      "add all the elements" mapped to each subarray:
               [_1, _2, _2, _1]
Leaky Nun
źródło
2

Mathematica, 32 bajty

#&@@Nest[#+Rest@#~Append~0&,##]&
                               &  make a pure function
    Nest[                 &,##]   call inner function as many times as specified
           Rest@#                 drop the first element of the list
                 ~Append~0        and add a 0 to get [b,c,d,0]
         #+                       add original list to get [a+b,b+c,c+d,d]
#&@@                              take the first element after x iterations
Klamka
źródło
2

Python , 80 58 bajtów

Uwielbiam matematykę dla tego wyzwania.

f=lambda a,x:x and f(map(sum,zip(a,a[1:]+[0])),x-1)or a[0]

Jak to działa (działa tylko z Pythonem 2):

f=lambda a,x:                                              - new lambda function
             x and                                         - iterate itself x times
                     map(sum,zip(a,a[1:]+[0]))             - e.g; f(a) = f(a-1) + f'(a-1)
                   f(                         ,x-1)        - iterate new array into itself
                                                   or a[0] - return first element

Wypróbuj online!

100 bajtów na przemian z użyciem trójkąta paskalowego

from math import factorial as F
f=lambda a,x:sum([(a+[0]*x)[i]*F(x)/(F(x-i)*F(i))for i in range(x)])

Jak to działa (działa dla Pythona 2 i 3):

sum([                                                ]) - take the sum of array
     (a+[0]*x)                                        - append x zeros
              [i]*F(x)/(F(x-i)*F(i))                  - multiply each element by x choose i
                                    for i in range(x) - do this for every element

Wzór ten działa poprzez mapowanie współczynniki szeregu xw paskalach trójkąta na tablicy. Każdy element trójkąta paskalnego jest określony przez funkcję wyboru wiersza i indeksu. Suma tej nowej tablicy jest równa wartości wyjściowej w x. Jest również intuicyjny, ponieważ iterowany proces metody newtonów (pokazany w przykładzie) działa dokładnie tak, jak konstrukcja trójkąta paskalowego.

Wypróbuj online!

Ogromne podziękowania dla ovs za zmniejszenie 22 bajtów poprzez przekształcenie pętli w funkcję rekurencyjną

Grawiton
źródło
Oto ulepszona wersja. Przekształciłem pętlę for na funkcję rekurencyjną
ows
Ach, świetny pomysł @ovs
Graviton
jeszcze krótszy Zauważ, że będzie działać tylko z python2
ovs
1

Haskell, 52 45 bajtów

l#n=iterate(zipWith(+)=<<tail.(++[0]))l!!n!!0

Przykład użycia: [-3,3,-3,3,-3,3,-3,3,-3] # 15-> -9009. Wypróbuj online!

Jak to działa

iterate(      )l          -- apply the function again and again starting with l
                          -- and collect the intermediate results in a list
                          -- the function is
          (++[0])         -- append a zero 
  zipWith(+)=<<tail       -- and build list of neighbor sums
                     !!0  -- take the first element from
                  !!n     -- the nth result

Edycja: @xnor zapisał 7 bajtów. Dzięki!

nimi
źródło
Myślę, że iterowaną funkcją może być zipWith(+)=<<tail.(++[0]), tj. Naprawić listę wcześniej niż później.
xnor
@ xnor: tak, to oszczędza wiele bajtów. Dzięki!
nimi
Po prostu nie mogę się =<<
skupić
@flawr: =<<stosuje się w ramach funkcji i jest definiowana jako: (=<<) f g x = f (g x) x. Tutaj używamy =<<infix: (f =<< g) xwith f = zipWith(+)i g = tail, co przekłada się na zipWith(+) (tail x) x.
nimi
Dziękuję za szczegółowe wyjaśnienie, nie wiedziałem o funkcji monada!
flawr
1

CJam , 12 bajtów

q~{_(;.+}*0=

Wypróbuj online!

Wyjaśnienie

Kod bezpośrednio implementuje procedurę opisaną w wyzwaniu.

q~            e# Read input and evaluate. Pushes the array and the number x
  {     }*    e# Do the following x times
   _          e# Duplicate array
    (;        e# Remove first element
      .+      e# Vectorized sum. The last element in the first array, which doesn't 
              e# have a corresponding entry in the second, will be left as is
          0=  e# Get first element. Implicitly display
Luis Mendo
źródło
1

Pyth , 10 bajtów

s.e*b.cQkE

Zestaw testowy.

Jak to działa

s.e*b.cQkE
 .e      E   for (b,k) in enumerated(array):
     .cQk        (input) choose (k)
   *b            * b
s            sum
Leaky Nun
źródło
1

APL (Dyalog) , 29 bajtów

{0=⍺:⊃⍵
(⍺-1)∇(+/¨2,/⍵),¯1↑⍵}

Wypróbuj online!

To jest rekurencyjny dfn, ale okazuje się, że jest zbyt gadatliwy. Gra w golfa w toku ...

user41805
źródło
1

Właściwie 7 bajtów

;lr(♀█*

Wypróbuj online!

Jak to działa

;lr(♀█*  input:
         8, [4, -5, 3, -1]
         top of stack at the right
;        duplicate
         8, [4, -5, 3, -1], [4, -5, 3, -1]
 l       length
         8, [4, -5, 3, -1], 4
  r      range
         8, [4, -5, 3, -1], [0, 1, 2, 3]
   (     rotate stack
         [4, -5, 3, -1], [0, 1, 2, 3], 8
    ♀█   map "n choose r"
         [4, -5, 3, -1], [1, 8, 28, 56]
      *  dot product
         -8
Leaky Nun
źródło
1

Oktawa , 42 bajty

@(a,x)conv(a,diag(flip(pascal(x+1))))(x+1)

Definiuje to anonimową funkcję. Wypróbuj online!

Wyjaśnienie

Rozwiązanie można obliczyć przez wielokrotne zwijanie tablicy wejściowej i wynikowych tablic za pomocą [1, 1]. Ale splot dwukrotnie, trzykrotnie lub ... z [1, 1]odpowiada splotowi raz z [1, 2 ,1], lub [1, 3, 3, 1], lub ...; to znaczy z rzędem trójkąta Pascala. Uzyskuje się to jako anty-przekątną macierzy rzędu Pascala x+1.

Luis Mendo
źródło
0

JavaScript (ES6), 41 bajtów

f=(a,x,[b,...c]=a)=>x--?f(a,x)+f(c,x):b|0

Port of @ xnor doskonałej odpowiedzi Haskell. Poprzednie 47-bajtowe rozwiązanie.

f=(a,x)=>x--?f(a.map((e,i)=>e+~~a[i+1]),x):a[0]
Neil
źródło
0

Python 3 z Numpy , 82 bajty

import numpy
def f(a,x):
 for n in range(x):a=numpy.convolve(a,[1,1])
 return a[x]

Podobna do mojej odpowiedzi MATL , ale przy użyciu splotu pełnowymiarowego, a zatem wynikiem jest x-ty wpis końcowej tablicy.

Wypróbuj online!

Luis Mendo
źródło