Encuentra los máximos y mínimos locales

14

Definición

Los máximos y mínimos de una función dada son los valores más grandes y más pequeños de la función, ya sea dentro de un rango dado o de lo contrario dentro del dominio completo de la función.

Desafío

El desafío es encontrar los máximos y mínimos locales de una función polinómica dada utilizando cualquier método que desee . No se preocupe, haré todo lo posible para explicar el desafío y mantenerlo lo más simple posible.

La entrada contendrá todos los coeficientes del polinomio variable individual en orden decreciente o creciente de potencia (depende de usted). Por ejemplo,

  • [3,-7,1] representará 3x2 - 7x + 1 = 0
  • [4,0,0,-3] representará 4x3-3=0.

¿Cómo resolver (usando derivados)?

Ahora, digamos que nuestra entrada es [1,-12,45,8], que no es más que la función .x3 - 12x2 + 45x + 8

  1. La primera tarea es encontrar la derivada de esa función. Dado que es una función polinómica, es una tarea simple de hacer.

    La derivada de es . Cualquier término constante presente con simplemente se multiplica. Además, si hay términos agregados / restados, entonces sus derivados también se suman o restan respectivamente. Recuerde, la derivada de cualquier valor numérico constante es cero. Aquí están algunos ejemplos:xnn*xn-1xn

    • x3 -> 3x2
    • 9x4 -> 9*4*x3 = 36x3
    • -5x2 -> -5*2*x = - 10x
    • 2x3 - 3x2 + 7x -> 6x2 - 6x + 7
    • 4x2 - 3 -> 8x - 0 = 8x
  2. Ahora resuelva la ecuación equiparando el nuevo polinomio a cero y obtenga solo los valores integrales de x.

  3. Ponga esos valores de x en la función original y devuelva los resultados. Esa debería ser la salida .

Ejemplo

Tomemos el ejemplo mencionamos anteriormente, es decir, [1,-12,45,8].

  • Entrada: [1,-12,45,8]
  • Función: x3 - 12x2 + 45x + 8
  • Derivado -> 3x2 - 24x + 45 + 0 -> [3,-24,45]
  • Resolviendo la ecuación , obtenemos o .3x2 - 24x + 45 = 0x = 3x = 5
  • Ahora poniendo x = 3y x = 5en la función, obtenemos los valores (62,58).
  • Salida -> [62,58]

Supuestos

  1. Suponga que todos los coeficientes de entrada son enteros . Pueden estar en orden creciente o decreciente de poder.

  2. Suponga que la entrada es al menos un polinomio de 2 grados . Si el polinomio no tiene soluciones enteras, puede devolver cualquier cosa.

  3. Suponga que el resultado final serán enteros solamente.

  4. Puede imprimir los resultados en cualquier orden. El grado del polinomio de entrada no debería ser superior a 5, por lo que su código puede manejarlo.

  5. La entrada será válida para que las soluciones de x no sean puntos de silla.

Además, no está obligado a hacerlo por el método derivado. Puede usar cualquier método que desee.

Muestra de entrada y salida

[2,-8,0] -> (-8)
[2,3,-36,10] -> (91,-34)
[1,-8,22,-24,8] -> (-1,0,-1) 
[1,0,0] -> (0)

Puntuación

Este es el por lo que gana el código más corto.

Manish Kundu
fuente
1
Si lo entiendo correctamente: en el ejemplo, el paso " Resolver la ecuación " sería en parte este desafío anterior tuyo . Además, el paso " Ahora poner x = 3 yx = 5 en la función " significa la función original en " Función " y no la función en " Derivada ", ¿verdad?
Kevin Cruijssen
1
Para la muestra I / O 3, obtengo (-1, 0, 1), lo que creo que es la respuesta correcta real ... aunque no estoy seguro. Si no estás de acuerdo conmigo, hazme ping en el chat.
HyperNeutrino
1
The input will be valid so that the solutions of x are not saddle points, el caso [1,0,0,3]parece dar un punto de silla de montar.
JungHwan Min
1
@JungHwanMin ah ese ejemplo se agregó antes de que se estableciera la regla. Eliminado ahora.
Manish Kundu
1
x^3 - 12x^2 + 45x + 8 = 0 , aunque personalmente prefiero que lo escriba f(x)=x^3-12x^2+45x+8sin el =0porque =0no tiene sentido ya que estamos tratando con una función, no resolviendo una ecuación.
Weijun Zhou

Respuestas:

4

Jalea , 20 bytes

ASŒRḅ@Ðḟ
J’U×µṖÇḅ@€³

Pruébalo en línea!

Explicación

ASŒRḅ@Ðḟ     Helper Function; find all integer solutions to a polynomial
             All integer roots are within the symmetric range of the sum of the absolute values of the coefficients
A            Absolute Value (Of Each)
 S           Sum
  ŒR         Symmetric Range; `n -> [-n, n]`
      Ðḟ     Filter; keep elements where the result is falsy for:
    ḅ@       Base conversion, which acts like the application of the polynomial
J’U×µṖÇḅ@€³  Main Link
J                             Range of length
 ’                    Lowered
  U          Reversed
   ×         Multiplied with the original list (last value is 0)
    µ        Begin new monadic chain
     Ṗ       Pop; all but the last element
      Ç      Apply last link (get all integer solutions of the derivative)
       ḅ@€³  Base conversion of the polynomial into each of the solutions; apply polynomial to each solution of the derivative.

La función auxiliar en este programa se tomó de la respuesta del Sr. Xcoder aquí, que se basó en la respuesta de Luis aquí.

Hiperneutrino
fuente
@JungHwanMin lo señalaré a OP. Esa es una violación directa de la afirmación de que no habrá puntos de silla porque la derivada del polinomio en 3es 0. editar oh ya lo hiciste nvm simplemente votó el comentario entonces
HyperNeutrino
3

JavaScript (ES7), 129 120 bytes

Toma los coeficientes en orden creciente de potencia.

a=>(g=x=>x+k?(A=g(x-1),h=e=>a.reduce((s,n,i)=>s+n*(e||i&&i--)*x**i,0))()?A:[h(1),...A]:[])(k=Math.max(...a.map(n=>n*n)))

Casos de prueba

Comentado

a => (                        // given the input array a[]
  g = x =>                    // g = recursive function checking whether x is a solution
    x + k ? (                 //   if x != -k:
      A = g(x - 1),           //     A[] = result of a recursive call with x - 1
      h = e =>                //     h = function evaluating the polynomial:
        a.reduce((s, n, i) => //       for each coefficient n at position i:
          s +                 //         add to s
          n                   //         the coefficient multiplied by
          * (e || i && i--)   //         either 1 (if e = 1) or i (if e is undefined)
          * x**i,             //         multiplied by x**i or x**(i-1)
          0                   //         initial value of s
        )                     //       end of reduce()
      )() ?                   //     if h() is non-zero:
        A                     //       just return A[]
      :                       //     else:
        [h(1), ...A]          //       prepend h(1) to A[]
    :                         //   else:
      []                      //     stop recursion
  )(k = Math.max(             // initial call to g() with x = k = maximum of
    ...a.map(n => n * n)      // the squared coefficients of the polynomial
  ))                          // (Math.abs would be more efficient, but longer)
Arnauld
fuente
1
falla para 0,0,1(x ^ 2 = 0)
betseg
@betseg Gracias por informar esto. Fijo.
Arnauld
3

Julia 0.6 (con Polynomialspaquete), 57 bytes

using Polynomials
x->map(Poly(x),roots(polyder(Poly(x))))

Pruébalo en línea!

Toma los coeficientes en orden creciente, es decir, la primera entrada es el término constante.

Ejemplo de ejecución:

julia> using Polynomials

julia> g = x -> map(Poly(x), roots(polyder(Poly(x))))
(::#1) (generic function with 1 method)

julia> g([8,45,-12,1])
2-element Array{Float64,1}:
 58.0
 62.0
Rɪᴋᴇʀ
fuente
3

Java 8, 364 239 227 226 218 bytes

a->{int l=a.length,A[]=a.clone(),s=0,i,r,f=l,p;for(;f>0;A[--f]*=f);for(int n:A)s+=n<0?-n:n;for(r=~s;r++<s;){for(p=0,i=f=1;i<l;f*=r)p+=A[i++]*f;if(p==0){for(f=i=0;i<l;f+=a[i++]*Math.pow(r,p++));System.out.println(f);}}}

Utiliza la misma funcionalidad de esta respuesta mía.

-8 bytes gracias a @ OlivierGrégoire al tomar la matriz en orden inverso.

Explicación:

Pruébalo en línea.

a->{                  // Method with integer-varargs parameter and integer return-type
  int l=a.length,     //  The length of the input-array
      A[]=a.clone(),  //  Copy of the input-array
      s=0,            //  Sum-integer, starting at 0
      i,              //  Index-integer
      r,              //  Range-integer
      f=l,            //  Factor-integer, starting at `l`
      p;              //  Polynomial-integer
  for(;f>0;           //  Loop over the copy-array
    A[--f]*=f);       //   And multiply each value with it's index
                      //   (i.e. [8,45,-12,1] becomes [0,45,-24,3])
  for(int n:A)        //  Loop over this copy-array:
    s+=n<0?-n:n;      //   And sum their absolute values
  for(r=~s;r++<s;){   //  Loop `r` from `-s` up to `s` (inclusive) (where `s` is the sum)
    for(p=0,          //   Reset `p` to 0
        i=f=1;        //   and `f` to 1
                      //   (`i` is 1 to skip the first item in the copy-array)
        i<l;          //   Inner loop over the input again, this time with index (`i`)
        f*=r)         //     After every iteration: multiply `f` with the current `r`
      p+=             //    Sum the Polynomial-integer `p` with:
         A[i++]       //     The value of the input at index `i`,
               *f;}   //     multiplied with the current factor `f`
    if(p==0){         //   If `p` is now 0:
      for(f=i=0;      //    Use `f` as sum, and reset it to 0
          i<l;        //    Loop over the input-array
        f+=a[i++]*Math.pow(r,p++));
                      //     Fill in `r` in the parts of the input-function
      System.out.println(f);}}}
                      //    And print the sum
Kevin Cruijssen
fuente
2
falla por 1,0,0(x ^ 2 = 0)
betseg
@betseg Gracias! Fijo y golf.
Kevin Cruijssen
1
Debe aceptar la entrada en orden inverso (se permite explícitamente) para reducir el recuento de la siguiente manera: int... ,i, ...; for(;f>0;)A[--f]*=f;. A menos que me equivoque, esto debería ahorrarle al menos 4 bytes. Si hace esto, asegúrese de invertir todos sus accesos a la entrada.
Olivier Grégoire
@ OlivierGrégoire Gracias, ¡8 bytes guardados!
Kevin Cruijssen
2

Haskell , 89 bytes

-3 bytes gracias a Laikoni.

r#l=foldr1((.(r*)).(+))l
r l|_:d<-zipWith(*)[0..]l,t<-sum$abs<$>d=[i#l|i<-[-t..t],i#d==0]

Pruébalo en línea!

Toma los coeficientes invertidos.

totalmente humano
fuente
2
d<-tail$se puede acortar a _:d<-.
Laikoni
1

Python 3 , 156 bytes

def f(p,E=enumerate):a=lambda p,v:sum(e*v**i for i,e in E(p));d=[e*i for i,e in E(p)][1:];r=sum(map(abs,d));return[a(p,x)for x in range(-r,r+1)if a(d,x)==0]

Pruébalo en línea!

-2 bytes gracias a Mr. Xcoder
-22 bytes gracias a ovs

Hiperneutrino
fuente
1

Python + numpy, 91

  • 1 byte guardado gracias a @KevinCruijssen
from numpy import*
p=poly1d(input())
print map(lambda x:int(polyval(p,x)),roots(p.deriv()))

Pruébalo en línea .

Trauma digital
fuente