O objetivo deste desafio é usar o método de Euler para aproximar a solução de uma equação diferencial da forma f ⁽ⁿ⁾ (x) = c. ^†

A entrada será uma lista de números inteiros, em que o n th valor representa o valor de f ⁽ⁿ⁾ (0). O primeiro número inteiro é f (0), o segundo é f '(0) e assim por diante. O último número inteiro nesta lista é a constante e sempre permanecerá o mesmo.

Também fornecido como entrada, será um número inteiro positivo (diferente de zero) x , que representa o valor alvo (você está tentando estimar f (x)). O tamanho da etapa para o método de Euler será sempre 1. Portanto, você precisará executar x etapas no total.

Se você não é familiar com o método de Euler, aqui está um exemplo detalhado com uma explicação para a entrada [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

Essencialmente, cada célula na tabela gerada é a soma da célula acima dela e da célula acima e à direita. Então, f (a) = f (a-1) + f '(a-1); f '(a) = f' (a-1) + f '' (a-1); e f '' (a) = f '' (a-1) + f '' '(a-1). A resposta final é f (8) ≈ -8. ^††

A lista de entrada sempre conterá 2 ou mais elementos, todos com valores absolutos menores que 10. x ≥ 1 também é garantido. A saída é um único inteiro, a aproximação de f (x). A entrada pode ser obtida em qualquer ordem (a lista antes de x ou x antes da lista). x também pode ser o primeiro ou o último elemento da lista, se desejado.

Casos de teste:

[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

^{†: é notável que o uso de um método de aproximação nessa situação seja, de fato, estúpido. no entanto, a função mais simples possível foi escolhida para os propósitos deste desafio.}

^{††: o valor real passa a ser -25⅓, o que qualificaria essa aproximação como "não muito boa".}

Haskell , 38 bytes

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

Experimente online!

Aprimorado de 39 bytes:

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

Expressa recursivamente a saída l%n. Mover para cima corresponde a decrementar ne mover para a direita corresponde a tirar tail lpara deslocar todos os elementos da lista um espaço à esquerda. Portanto, a saída l%né o valor acima l%(n-1), mais o valor acima e à direita(tail l)%(n-1)

O caso base n==0é pegar o primeiro elemento da lista.

Idealmente, a entrada seria preenchida com infinitos zeros à direita, uma vez que as derivadas de um polinômio acabam se tornando zero. Simulamos isso anexando a 0quando pegamos o tail.

Alt 41 estranho:

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

MATL , 9 bytes

:"TTZ+]1)

Experimente online! Ou verifique todos os casos de teste .

Explicação

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

Gelatina , 6 5 bytes

Ḋ+$¡Ḣ

Experimente online!

-1 byte graças a @Doorknob

Explicação

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

Braquilog , 13 12 bytes

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

Experimente online!

Como funciona

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

Solução anterior de 13 bytes

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

Experimente online!

Como funciona

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

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

Ame a matemática para este desafio.

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

Como funciona (funciona apenas com 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

Experimente online!

Alternativa de 100 bytes com o uso do triângulo pascal

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

Como funciona (funciona para python 2 e 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

Essa fórmula funciona mapeando os coeficientes da linha xdo triângulo pascal na matriz. Cada elemento do triângulo pascal é determinado pela função de escolha da linha e do índice. A soma dessa nova matriz é equivalente à saída em x. Também é intuitivo, pois o processo iterado do método newtons (mostrado no exemplo) atua exatamente como a construção do triângulo pascal.

Experimente online!

Muito obrigado aos ovs por reduzir 22 bytes convertendo o loop em uma função recursiva

Haskell, 52 45 bytes

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

Exemplo de uso: [-3,3,-3,3,-3,3,-3,3,-3] # 15-> -9009. Experimente online!

Como funciona

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

Edit: @xnor salvou 7 bytes. Obrigado!

CJam , 12 bytes

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

Experimente online!

Explicação

O código implementa diretamente o procedimento descrito no desafio.

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

Pitão , 10 bytes

s.e*b.cQkE

Suíte de teste.

Como funciona

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

APL (Dyalog) , 29 bytes

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

Experimente online!

Este é um dfn recursivo, mas acaba sendo muito detalhado. Golfe em andamento ...

Na verdade , 7 bytes

;lr(♀█*

Experimente online!

Como funciona

;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

Oitava , 42 bytes

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

Isso define uma função anônima. Experimente online!

Explicação

A solução pode ser calculada através da convocação repetida da matriz de entrada e das matrizes resultantes [1, 1]. Mas convolver duas ou três vezes, ou ... com [1, 1]corresponde a convolver uma vez com [1, 2 ,1], ou [1, 3, 3, 1], ou ...; isto é, com uma linha do triângulo Pascal. Isto é obtido como a anti-diagonal da matriz de ordem Pascal x+1.

JavaScript (ES6), 41 bytes

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

Porto da excelente resposta Haskell do @ xnor. Solução anterior de 47 bytes.

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

Python 3 com Numpy , 82 bytes

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

Semelhante à minha resposta MATL , mas usando convolução em tamanho real, e, portanto, o resultado é a x-a entrada da matriz final.

Experimente online!

Python , 51 bytes

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

Experimente online!

Esta é uma porta da minha resposta Haskell .