Цель этой задачи - использовать метод Эйлера для аппроксимации решения дифференциального уравнения вида f ⁽ⁿ⁾ (x) = c. ^†

Входными данными будет список целых чисел, в которых n- е значение представляет значение f ⁽ⁿ⁾ (0). Первое целое число - это f (0), второе - это f '(0) и так далее. Последнее целое число в этом списке является константой и всегда останется неизменным.

Также в качестве входных данных будет предоставлено положительное (ненулевое) целое число x , которое представляет целевое значение (вы пытаетесь оценить f (x)). Размер шага для метода Эйлера всегда будет равен 1. Таким образом, вам нужно будет сделать х шагов всего.

Если вы не знакомы с методом Эйлера, вот подробный пример с объяснением ввода [4, -5, 3, -1], х = 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

По сути, каждая ячейка в сгенерированной таблице является суммой ячейки над ней и ячейки сверху и справа. Итак, f (a) = f (a-1) + f '(a-1); f '(a) = f' (a-1) + f '' (a-1); и f '' (a) = f '' (a-1) + f '' '(a-1). Окончательный ответ: f (8) ≈ -8. ^††

Входной список всегда будет содержать 2 или более элементов, каждый из которых будет иметь абсолютные значения менее 10. x ≥ 1 также гарантируется. Выходные данные представляют собой одно целое число, приближение f (x). Ввод может быть сделан в любом порядке (список перед x или x перед списком). x также может быть первым или последним элементом списка, если это необходимо.

Тестовые случаи:

[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

^{† Примечательно, что использование метода приближения в этой ситуации, на самом деле, глупо. однако для целей этой задачи была выбрана самая простая возможная функция.}

^{††: фактическое значение составляет -25⅓, что квалифицирует это приближение как «не очень хорошее».}

Haskell , 38 байт

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

Попробуйте онлайн!

Улучшено с 39 байтов:

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

Рекурсивно выражает вывод l%n. Перемещение вверх соответствует уменьшению n, а перемещение вправо соответствует tail lсдвигу всех элементов списка на один пробел влево. Таким образом, выходное l%nзначение является значением выше l%(n-1), плюс значение выше и справа(tail l)%(n-1)

Базовый случай n==0состоит в том, чтобы взять первый элемент списка.

В идеале вход должен дополняться бесконечным числом нулей справа, поскольку производные полинома в конечном итоге становятся равными нулю. Мы моделируем это, добавляя, 0когда мы берем tail.

Странный альт 41:

(iterate(\q l->q l+q(tail l++[0]))head!!)

MATL , 9 байт

:"TTZ+]1)

Попробуйте онлайн! Или проверьте все тестовые случаи .

объяснение

:"      % 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

Желе , 6 5 байт

Ḋ+$¡Ḣ

Попробуйте онлайн!

-1 байт благодаря @ Doorknob

объяснение

Ḋ+$¡Ḣ  - 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

Брахилог , 13 12 байт

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

Попробуйте онлайн!

Как это работает

{,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]

Предыдущее 13-байтовое решение

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

Попробуйте онлайн!

Как это работает

{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]

Mathematica, 32 байта

#&@@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

Python , 80 58 байт

Люблю математику для этого вызова.

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

Как это работает (работает только с Python 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

Попробуйте онлайн!

100 байтов чередуются с использованием треугольника паскалей

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)])

Как это работает (работает для Python 2 и 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

Эта формула работает путем сопоставления коэффициентов строки xиз Треугольника Паскаля на массив. Каждый элемент треугольника Паскаля определяется функцией выбора строки и индекса. Сумма этого нового массива эквивалентна выводу в x. Это также интуитивно понятно, так как повторяющийся процесс метода Ньютона (показанный в примере) действует точно так же, как построение треугольника Паскаля.

Попробуйте онлайн!

Большое спасибо ovs за сокращение 22 байтов путем преобразования цикла в рекурсивную функцию

Haskell, 52 45 байт

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

Пример использования: [-3,3,-3,3,-3,3,-3,3,-3] # 15-> -9009. Попробуйте онлайн!

Как это работает

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

Редактировать: @xnor сохранил 7 байтов. Спасибо!

CJam , 12 байт

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

Попробуйте онлайн!

объяснение

Код непосредственно реализует процедуру, описанную в задании.

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

Pyth , 10 байт

s.e*b.cQkE

Тестирование.

Как это работает

s.e*b.cQkE
 .e      E   for (b,k) in enumerated(array):
     .cQk        (input) choose (k)
   *b            * b
s            sum

APL (Dyalog) , 29 байт

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

Попробуйте онлайн!

Это рекурсивный dfn, но он оказывается слишком многословным. Гольф в прогрессе ...

На самом деле 7 байтов

;lr(♀█*

Попробуйте онлайн!

Как это работает

;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

Октава , 42 байта

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

Это определяет анонимную функцию. Попробуйте онлайн!

объяснение

Решение может быть вычислено путем многократного свертывания входного массива и полученных массивов с [1, 1]. Но сворачивание дважды, или трижды, или ... с [1, 1]соответствует сворачиванию один раз с [1, 2 ,1], или [1, 3, 3, 1], или ...; то есть с рядом треугольника Паскаля. Это получается как антидиагональ матрицы порядка Паскаля x+1.

JavaScript (ES6), 41 байт

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

Порт @ xnor отличный ответ на Haskell. Предыдущее 47-байтовое решение.

f=(a,x)=>x--?f(a.map((e,i)=>e+~~a[i+1]),x):a[0]

Python 3 с Numpy , 82 байта

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

Аналогично моему ответу на MATL , но с использованием полноразмерной свертки, и, следовательно, результатом является x-ая запись окончательного массива.

Попробуйте онлайн!

Python , 51 байт

f=lambda l,n:n and f(l,n-1)+f(l[1:]+[0],n-1)or l[0]

Попробуйте онлайн!

Это порт моего ответа на Haskell .