Temukan Maxima Lokal Dan Minima

14

Definisi

Maksima dan minimum dari fungsi yang diberikan adalah nilai terbesar dan terkecil dari fungsi baik dalam rentang tertentu atau dalam seluruh domain fungsi.

Tantangan

Tantangannya adalah untuk menemukan maksimum lokal dan minimum dari fungsi polinomial tertentu menggunakan metode apa pun yang Anda suka . Jangan khawatir, saya akan mencoba yang terbaik untuk menjelaskan tantangan dan menjaganya sesederhana mungkin.

Input akan berisi semua koefisien polinomial variabel tunggal baik dalam penurunan atau peningkatan urutan daya (terserah Anda). Sebagai contoh,

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

Bagaimana Mengatasi (Menggunakan Derivatif)?

Sekarang, katakanlah input kita adalah [1,-12,45,8], yang tidak lain adalah fungsinya .x3 - 12x2 + 45x + 8

  1. Tugas pertama adalah menemukan turunan dari fungsi itu. Karena ini adalah fungsi polinomial, maka itu memang tugas yang mudah untuk dilakukan.

    Derivatif dari adalah . Setiap istilah yang konstan hadir dengan hanya dikalikan. Juga, jika ada istilah yang ditambahkan / dikurangi, maka turunannya juga ditambahkan atau dikurangi masing-masing. Ingat, turunan dari setiap nilai numerik konstan adalah nol. Berikut ini beberapa contoh: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. Sekarang pecahkan persamaan dengan menyamakan polinomial baru ke nol dan dapatkan hanya nilai integral x.

  3. Masukkan nilai-nilai x dalam fungsi asli dan kembalikan hasilnya. Itu harus menjadi output .

Contoh

Mari kita ambil contoh yang kami sebutkan sebelumnya, yaitu [1,-12,45,8],.

  • Memasukkan: [1,-12,45,8]
  • Fungsi: x3 - 12x2 + 45x + 8
  • Derivatif -> 3x2 - 24x + 45 + 0 -> [3,-24,45]
  • Memecahkan persamaan , kita dapatkan atau .3x2 - 24x + 45 = 0x = 3x = 5
  • Sekarang dengan meletakkan x = 3dan x = 5dalam fungsinya, kita mendapatkan nilainya (62,58).
  • Output -> [62,58]

Asumsi

  1. Asumsikan bahwa semua koefisien input adalah bilangan bulat . Mereka bisa dalam meningkatkan atau mengurangi urutan kekuasaan.

  2. Asumsikan input setidaknya polinomial 2-derajat . Jika polinomial tidak memiliki solusi integer, Anda dapat mengembalikan apa pun.

  3. Asumsikan bahwa hasil akhirnya hanya bilangan bulat.

  4. Anda dapat mencetak hasilnya dalam urutan apa pun. Tingkat input polinomial tidak akan lebih dari 5, sehingga kode Anda dapat mengatasinya.

  5. Input akan valid sehingga solusi x bukanlah titik pelana.

Juga, Anda tidak dipaksa untuk melakukannya dengan metode turunan. Anda dapat menggunakan metode apa pun yang Anda suka.

Input dan Output Sampel

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

Mencetak gol

Ini adalah sehingga kode terpendek menang.

Manish Kundu
sumber
1
Jika saya mengerti dengan benar: pada contoh langkah " Memecahkan persamaan " akan menjadi sebagian tantangan Anda sebelumnya ? Juga, langkah " Sekarang menempatkan x = 3 dan x = 5 di fungsi " berarti fungsi asli di " Function " dan bukan fungsi di " Derivative ", kan?
Kevin Cruijssen
1
Untuk sampel I / O 3, saya mendapatkan (-1, 0, 1), yang saya percaya adalah jawaban yang benar sebenarnya ... meskipun tidak yakin. Jika Anda tidak setuju dengan saya ping saya di chat.
HyperNeutrino
1
The input will be valid so that the solutions of x are not saddle points, case ini [1,0,0,3]sepertinya memberikan poin sadel.
JungHwan Min
1
@JungHwanMin ah contoh itu ditambahkan sebelum aturan dibuat. Dihapus sekarang.
Manish Kundu
1
x^3 - 12x^2 + 45x + 8 = 0 , walaupun secara pribadi saya lebih suka Anda menulisnya f(x)=x^3-12x^2+45x+8tanpa =0karena =0tidak masuk akal karena kita berhadapan dengan suatu fungsi, bukan memecahkan persamaan.
Weijun Zhou

Jawaban:

4

Jelly , 20 byte

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

Cobalah online!

Penjelasan

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.

Fungsi pembantu dalam program ini diambil dari jawaban Tuan Xcoder di sini yang didasarkan pada jawaban Luis di sini

HyperNeutrino
sumber
@JungHwanMin saya akan tunjukkan ke OP. Itu merupakan pelanggaran langsung terhadap pernyataan bahwa tidak akan ada poin pelana karena turunan dari polinomial 3adalah 0. sunting oh Anda sudah melakukan nvm baru saja
meng
3

JavaScript (ES7), 129 120 byte

Mengambil koefisien dalam meningkatkan urutan kekuasaan.

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

Uji kasus

Berkomentar

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
sumber
1
gagal untuk 0,0,1(x ^ 2 = 0)
betseg
@betseg Terima kasih telah melaporkan ini. Tetap.
Arnauld
3

Julia 0,6 (dengan Polynomialspaket), 57 byte

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

Cobalah online!

Mengambil koefisien dalam urutan yang meningkat, yaitu input pertama adalah istilah konstan.

Contoh dijalankan:

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ɪᴋᴇʀ
sumber
3

Java 8, 364 239 227 226 218 byte

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

Menggunakan fungsi yang sama dari jawaban saya ini.

-8 byte terima kasih kepada @ OlivierGrégoire dengan mengambil array dalam urutan terbalik.

Penjelasan:

Cobalah online.

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
sumber
2
gagal untuk 1,0,0(x ^ 2 = 0)
betseg
@betseg Terima kasih! Tetap dan golf.
Kevin Cruijssen
1
Anda harus menerima input dalam urutan terbalik (secara eksplisit diperbolehkan) untuk mengurangi jumlah Anda seperti ini: int... ,i, ...; for(;f>0;)A[--f]*=f;. Kecuali saya salah, ini akan menghemat setidaknya 4 byte. Jika Anda melakukan ini, pastikan untuk membalikkan semua akses Anda ke input.
Olivier Grégoire
@ OlivierGrégoire Terima kasih, 8 byte disimpan!
Kevin Cruijssen
2

Haskell , 89 byte

-3 byte terima kasih kepada Laikoni.

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

Cobalah online!

Membawa koefisien terbalik.

benar-benar manusiawi
sumber
2
d<-tail$dapat disingkat menjadi _:d<-.
Laikoni
1

Python 3 , 156 byte

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]

Cobalah online!

-2 bytes terima kasih kepada Tn. Xcoder
-22 bytes terima kasih kepada ovs

HyperNeutrino
sumber
1

Python + numpy, 91

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

Cobalah online .

Trauma Digital
sumber