9

El objetivo de este desafío es utilizar el método de Euler para aproximar la solución de una ecuación diferencial de la forma f ⁽ⁿ⁾ (x) = c. ^†

La entrada será una lista de números enteros en la que el n º valor representa el valor de f ⁽ⁿ⁾ (0). El primer entero es f (0), el segundo es f '(0), y así sucesivamente. El último entero en esta lista es la constante y siempre seguirá siendo el mismo.

También se proporcionará como entrada un número entero positivo (distinto de cero) x , que representa el valor objetivo (está intentando estimar f (x)). El tamaño del paso para el método de Euler siempre será 1. Por lo tanto, deberá realizar un total de x pasos.

Si no está familiarizado con el método de Euler, aquí hay un ejemplo detallado con una explicación para la 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

Esencialmente, cada celda en la tabla generada es la suma de la celda arriba de ella y la celda arriba y a la derecha. Entonces, f (a) = f (a-1) + f '(a-1); f '(a) = f' (a-1) + f '' (a-1); y f '' (a) = f '' (a-1) + f '' '(a-1). La respuesta final es f (8) ≈ -8. ^††

La lista de entrada siempre contendrá 2 o más elementos, todos los cuales tendrán valores absolutos inferiores a 10. x ≥ 1 también está garantizado. La salida es un entero único, la aproximación de f (x). La entrada puede tomarse en cualquier orden (la lista antes de x o x antes de la lista). x también puede ser el primer o el último elemento de la lista, si lo desea.

Casos de prueba:

[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

^{†: es notable que usar un método de aproximación en esta situación es, de hecho, estúpido. sin embargo, se eligió la función más simple posible para los propósitos de este desafío.}

^{††: el valor real es -25⅓, lo que calificaría esta aproximación como "no muy buena".}

code-golf number arithmetic integer Pomo de la puerta
fuente

2

Muy relacionado

Peter Taylor

2

También muy relacionado.

xnor

3

Haskell , 38 bytes

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

Pruébalo en línea!

Mejorado de 39 bytes:

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

Expresa recursivamente la salida l%n. Mover hacia arriba corresponde a disminuir n, y moverse hacia la derecha corresponde a tomar tail lpara cambiar todos los elementos de la lista un espacio a la izquierda. Entonces, la salida l%nes el valor anterior l%(n-1), más el valor anterior y a la derecha(tail l)%(n-1)

El caso base n==0es tomar el primer elemento de la lista.

Idealmente, la entrada se rellenaría con infinitos ceros a la derecha, ya que las derivadas de un polinomio eventualmente se convierten en cero. Simulamos esto agregando un 0cuando tomamos el tail.

Extraño alt 41:

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

xnor
fuente

3

MATL , 9 bytes

:"TTZ+]1)

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

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

3

Jalea , 6 5 bytes

Ḋ+$¡Ḣ

Pruébalo en línea!

-1 byte gracias a @Doorknob

Explicación

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

3

Brachylog , 13 12 bytes

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

Pruébalo en línea!

Cómo 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]

Solución anterior de 13 bytes

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

Pruébalo en línea!

Cómo 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]

Monja permeable
fuente

2

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

Pomo de la puerta
fuente

2

Python , 80 58 bytes

Me encantan las matemáticas para este desafío.

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

Cómo funciona (solo funciona con 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

Pruébalo en línea!

100 bytes alternativos con el uso del 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)])

Cómo funciona (funciona para python 2 y 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

Esta fórmula funciona mapeando los coeficientes de la fila xdel triángulo de pascales en la matriz. Cada elemento del triángulo pascal está determinado por la función elegir de la fila y el índice. La suma de esta nueva matriz es equivalente a la salida en x. También es intuitivo, ya que el proceso iterado del método de newtons (que se muestra en el ejemplo) actúa exactamente como la construcción del triángulo de pascales.

Pruébalo en línea!

Muchas gracias a los ovs por reducir 22 bytes al convertir el bucle en una función recursiva

Graviton
fuente

Aquí hay una versión mejorada.

Convertí

Ah, gran idea @ovs

Graviton

incluso más corto Tenga en cuenta que solo funcionará con python2

ovs

1

Haskell, 52 45 bytes

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

Ejemplo de uso: [-3,3,-3,3,-3,3,-3,3,-3] # 15-> -9009. Pruébalo en línea!

Cómo 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

Editar: @xnor guardó 7 bytes. ¡Gracias!

nimi
fuente

Creo que la función iterada puede ser zipWith(+)=<<tail.(++[0]), es decir, arreglar la lista de antemano en lugar de después.

xnor

@xnor: sí, eso ahorra muchos bytes. ¡Gracias!

nimi

No puedo envolver mi mente alrededor de la utilización de =<<aquí, esto es una locura :)

flawr

@flawr: =<<se utiliza en contexto función y se define como: (=<<) f g x = f (g x) x. Aquí usamos =<<infijo: (f =<< g) xcon f = zipWith(+)y g = tail, que se traduce en zipWith(+) (tail x) x.

nimi

Gracias por la explicación detallada, ¡no estaba al tanto de la función mónada!

flawr

1

CJam , 12 bytes

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

Pruébalo en línea!

Explicación

El código implementa directamente el procedimiento descrito en el desafío.

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
fuente

1

Pyth , 10 bytes

s.e*b.cQkE

Banco de pruebas.

Cómo funciona

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

Monja permeable
fuente

1

APL (Dyalog) , 29 bytes

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

Pruébalo en línea!

Este es un dfn recursivo, pero resulta ser demasiado detallado. Golf en progreso ...

usuario41805
fuente

1

En realidad , 7 bytes

;lr(♀█*

Pruébalo en línea!

Cómo 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

Monja permeable
fuente

1

Octava , 42 bytes

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

Esto define una función anónima. Pruébalo en línea!

Explicación

La solución podría calcularse convolviendo repetidamente la matriz de entrada y las matrices resultantes con [1, 1]. Pero convolucionar dos veces, o tres, o ... con [1, 1]corresponde a convolucionar una vez con [1, 2 ,1], o [1, 3, 3, 1], o ...; es decir, con una fila del triángulo de Pascal. Esto se obtiene como la anti-diagonal de la matriz de orden Pascal x+1.

Luis Mendo
fuente

0

JavaScript (ES6), 41 bytes

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

La excelente respuesta de Haskell de @xnor. Solución previa de 47 bytes.

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

Neil
fuente

0

Python 3 con Numpy , 82 bytes

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

Similar a mi respuesta MATL , pero usando convolución de tamaño completo, y por lo tanto el resultado es elx entrada enésima de la matriz final.

Pruébalo en línea!

Luis Mendo
fuente

0

Python , 51 bytes

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

Pruébalo en línea!

Este es un puerto de mi respuesta de Haskell .

xnor
fuente

Implementar el método de Euler

Respuestas:

Haskell , 38 bytes

MATL , 9 bytes

Explicación

Jalea , 6 5 bytes

Brachylog , 13 12 bytes

Cómo funciona

Solución anterior de 13 bytes

Cómo funciona

Mathematica, 32 bytes

Python , 80 58 bytes

Haskell, 52 45 bytes

CJam , 12 bytes

Explicación

Pyth , 10 bytes

Cómo funciona

APL (Dyalog) , 29 bytes

En realidad , 7 bytes

Cómo funciona

Octava , 42 bytes

Explicación

JavaScript (ES6), 41 bytes

Python 3 con Numpy , 82 bytes

Python , 51 bytes