Finden Sie die lokalen Maxima und Minima

14

Definition

Die Maxima und Minima einer gegebenen Funktion sind die größten und kleinsten Werte der Funktion entweder innerhalb eines gegebenen Bereichs oder auf andere Weise innerhalb des gesamten Bereichs der Funktion.

Herausforderung

Die Herausforderung besteht darin , die lokalen Maxima und Minima einer gegebenen Polynomfunktion mit einer beliebigen Methode zu finden . Keine Sorge, ich werde mein Bestes geben, um die Herausforderung zu erklären und sie so einfach wie möglich zu halten.

Die Eingabe enthält alle Koeffizienten des einzelnen variablen Polynoms in abnehmender oder zunehmender Reihenfolge der Potenz (bis zu Ihnen). Beispielsweise,

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

Wie löst man (mit Derivaten)?

Nehmen wir an, unser Input ist [1,-12,45,8], was nichts anderes als die Funktion ist .x3 - 12x2 + 45x + 8

  1. Die erste Aufgabe besteht darin, die Ableitung dieser Funktion zu finden. Da es sich um eine Polynomfunktion handelt, ist dies in der Tat eine einfache Aufgabe.

    Die Ableitung von ist . Alle konstanten Terme, die mit vorhanden sind, werden einfach multipliziert. Wenn Terme addiert / subtrahiert werden, werden auch deren Ableitungen addiert bzw. subtrahiert. Denken Sie daran, dass die Ableitung eines konstanten numerischen Werts Null ist. Hier einige Beispiele: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. Lösen Sie nun die Gleichung, indem Sie das neue Polynom mit Null gleichsetzen und nur die Integralwerte von x erhalten.

  3. Setzen Sie diese Werte von x in die ursprüngliche Funktion und geben Sie die Ergebnisse zurück. Das sollte die Ausgabe sein .

Beispiel

Nehmen wir das zuvor erwähnte Beispiel [1,-12,45,8].

  • Eingang: [1,-12,45,8]
  • Funktion: x3 - 12x2 + 45x + 8
  • Derivat -> 3x2 - 24x + 45 + 0 -> [3,-24,45]
  • Lösen wir die Gleichung , erhalten wir oder .3x2 - 24x + 45 = 0x = 3x = 5
  • Setzen wir nun x = 3und x = 5in die Funktion, erhalten wir die Werte (62,58).
  • Ausgabe -> [62,58]

Annahmen

  1. Angenommen, alle Eingabekoeffizienten sind ganze Zahlen . Sie können in zunehmender oder abnehmender Reihenfolge der Leistung sein.

  2. Angenommen, die Eingabe ist mindestens ein 2-Grad-Polynom . Wenn das Polynom keine ganzzahligen Lösungen hat, können Sie alles zurückgeben.

  3. Angenommen, das Endergebnis ist nur eine ganze Zahl.

  4. Sie können die Ergebnisse in beliebiger Reihenfolge ausdrucken. Der Grad des Eingabepolynoms würde nicht mehr als 5 betragen, damit Ihr Code damit umgehen kann.

  5. Die Eingabe ist gültig, sodass die Lösungen von x keine Sattelpunkte sind.

Auch Sie nicht , es zu tun durch die Ableitung Methode gezwungen. Sie können jede Methode verwenden, die Sie möchten.

Sample Input und Output

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

Wertung

Das ist also gewinnt der kürzeste Code.

Manish Kundu
quelle
1
Wenn ich richtig verstehe: In dem Beispiel wäre der Schritt " Gleichung lösen " teilweise diese vorherige Herausforderung von Ihnen ? Außerdem bedeutet Schritt " Jetzt setze x = 3 und x = 5 in die Funktion " die ursprüngliche Funktion bei " Funktion " und nicht die Funktion bei " Ableitung ", oder?
Kevin Cruijssen
1
Für Beispiel-E / A 3 erhalte ich (-1, 0, 1), was meiner Meinung nach die richtige Antwort ist ... ich bin mir jedoch nicht sicher. Wenn Sie mit mir nicht einverstanden sind, rufen Sie mich im Chat an.
HyperNeutrino
1
The input will be valid so that the solutions of x are not saddle points[1,0,0,3]scheint der Fall einen Sattelpunkt zu geben.
JungHwan Min 31.01.18
1
@JungHwanMin ah, dieses Beispiel wurde hinzugefügt, bevor die Regel erstellt wurde. Jetzt entfernt.
Manish Kundu
1
x^3 - 12x^2 + 45x + 8 = 0 , obwohl ich persönlich lieber schreibe als f(x)=x^3-12x^2+45x+8ohne, =0weil =0es keinen Sinn macht, da es sich um eine Funktion handelt und keine Gleichung gelöst wird.
Weijun Zhou

Antworten:

4

Gelee , 20 Bytes

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

Probieren Sie es online!

Erläuterung

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.

Die Hilfsfunktion in diesem Programm wurde aus der Antwort von Herrn Xcoder hier übernommen, die auf der Antwort von Luis hier basierte

HyperNeutrino
quelle
@JungHwanMin Ich werde OP darauf hinweisen. Das ist eine direkte Verletzung der Aussage, dass es keine Sattelpunkte geben wird, weil die Ableitung des Polynoms bei 3ist 0. edit oh du hast doch schon nvm gerade den kommentar dann
hochgestuft
3

JavaScript (ES7), 129 120 Bytes

Nimmt die Koeffizienten in aufsteigender Reihenfolge der Leistung auf.

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

Testfälle

Kommentiert

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
quelle
1
scheitert für 0,0,1(x ^ 2 = 0)
betseg
Vielen Dank für den Hinweis. Fest.
Arnauld
3

Julia 0.6 (mit PolynomialsPaket), 57 Bytes

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

Probieren Sie es online!

Nimmt Koeffizienten in aufsteigender Reihenfolge auf, dh die erste Eingabe ist der konstante Term.

Beispiellauf:

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ɪᴋᴇʀ
quelle
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);}}}

Verwendet die gleiche Funktionalität aus meiner Antwort.

-8 Bytes dank @ OlivierGrégoire indem das Array in umgekehrter Reihenfolge wird.

Erläuterung:

Probieren Sie es online aus.

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
quelle
2
scheitert für 1,0,0(x ^ 2 = 0)
betseg
@ betseg Danke! Fest und Golf.
Kevin Cruijssen
1
Sie sollten den Eingang in umgekehrter Reihenfolge (es ist ausdrücklich erlaubt) akzeptieren Ihre Zählung so zu reduzieren: int... ,i, ...; for(;f>0;)A[--f]*=f;. Wenn ich mich nicht irre, sollten Sie dadurch mindestens 4 Bytes sparen. Stellen Sie in diesem Fall sicher, dass Sie alle Zugriffe auf die Eingabe invertieren.
Olivier Grégoire
@ OlivierGrégoire Danke, 8 Bytes gespart!
Kevin Cruijssen
2

Haskell , 89 Bytes

-3 Bytes dank Laikoni.

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

Probieren Sie es online!

Nimmt Koeffizienten umgekehrt.

total menschlich
quelle
2
d<-tail$kann auf gekürzt werden _: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]

Probieren Sie es online!

-2 Bytes dank Mr. Xcoder
-22 Bytes dank Ovs

HyperNeutrino
quelle
1

Python + Numpy, 91

  • 1 Byte gespeichert dank @KevinCruijssen
from numpy import*
p=poly1d(input())
print map(lambda x:int(polyval(p,x)),roots(p.deriv()))

Probieren Sie es online aus .

Digitales Trauma
quelle