Interpolasi polinomial

12

Tulis program yang melakukan Interpolasi Polinomial menggunakan bilangan rasional presisi arbitrer sejati. Inputnya terlihat seperti ini:

f (1) = 2/3
f (2) = 4/5
f (3) = 6/7
...

Anda dapat berasumsi bahwa hanya ada satu spasi putih sebelum dan setelah =tanda, semua angka adalah pecahan atau bilangan bulat. Anda juga dapat mengasumsikan, bahwa semua fraksi dalam input sudah dapat direduksi.

Tidak diperlukan pengecekan kesalahan, Anda dapat mengasumsikan, bahwa input tersebut valid dan tidak ada x yang digandakan dalam f (x).

Outputnya harus dalam bentuk yang kompatibel dengan LaTeX, kode LaTeX yang dipancarkan harus menghasilkan representasi grafis yang sama dengan output yang diberikan di sini.

f (x) = 123x ^ 2 + \ frac {45} {2} x + \ frac {7} {4}

Fraksi harus dikurangi sebanyak mungkin, misalnya. sesuatu seperti \frac{2}{4} tidak diizinkan. Jika angka tersebut bilangan bulat, jangan gunakan pecahan.

Aturan khusus:

Program Anda harus ...

  • bekerja untuk polinomial hingga tingkat 12
  • lengkap dalam waktu kurang dari 1 menit untuk input yang masuk akal
  • tidak menggunakan fungsi apa pun yang melakukan seluruh perhitungan untuk Anda
  • output polinomial dari tingkat sekecil mungkin

Testcases:

Testcases yang diberikan hanya untuk klarifikasi. Program Anda harus menghasilkan hasil yang benar untuk semua input yang benar.

Memasukkan

f (1) = 2/3
f (2) = 4/5
f (3) = 6/7

Keluaran

f (x) = - \ frac {4} {105} x ^ 2
       + \ frac {26} {105} x
       + \ frac {16} {35}

Memasukkan

f (-12) = 13/2
f (5/3) = 3/5
f (13) = -6
f (1/5) = -3/4

Keluaran

f (x) = - \ frac {2186133} {239455744} x ^ 3
       + \ frac {2741731} {149659840} x ^ 2
       + \ frac {26720517} {29201920} x
       - \ frac {279464297} {299319680}

Memasukkan

f (4/3) = 617/81
f (2) = 20/3
f (-8/3) = 6749/81
f (-5) = 7367/12
f (0) = 23/3

Keluaran

f (x) = \ frac {1} {2} x ^ 4
     - 2x ^ 3
     + \ frac {7} {4} x ^ 2
     + \ frac {23} {3}

Memasukkan

f (0) = 5
f (1) = 7
f (2) = 9
f (3) = 11
f (4) = 13

Keluaran

f (x) = 2x
     + 5

Memasukkan

f (1/2) = -1/2
f (-25) = -1/2
f (-54/12) = -1/2

Keluaran

f (x) = - \ frac {1} {2}
FUZxxl
sumber
Mengapa Anda berbicara tentang bilangan real jika semua yang pernah Anda gunakan adalah bilangan rasional?
Joey
Maaf. Bahasa Inggris saya tidak bagus. Ya, hanya gunakan angka rasional. Hasilnya harus tepat.
FUZxxl
Di testcase pertama, apakah titik ( ...) benar-benar bagian dari input?
Eelvex
@Eelvex: Tidak. Tetap.
FUZxxl
Output untuk testcase ketiga salah. Jawaban yang benar adalah -\frac{37745}{14592}x^4 - \frac{853249}{43776}x^3 + \frac{57809}{7296}x^2 + \frac{225205}{2736}x + \frac{23}{3}. Saya menduga masukan itu dimaksudkan untuk menjadi sesuatu yang berbeda :)
Timwi

Jawaban:

3

J + sh

Skrip J:

i=:0".(1!:1)3
i=:((-:#i),2)$i
c=:|.(%.(x:((i.#i)^~])"0({."1 i)))(+/ .*)(|:{:"1 i)
(":(-.0=c)#(c,.i.-#c))(1!:2)2

skrip sh:

echo -n 'f(x) = '
tr -d 'f()=' | tr /\\n- r' '_  | ./polyint.ijs | sed -e 's/^/+/;s/_/-/;s/\([0-9]*\)r\([0-9]*\)/\\frac{\1}{\2}/;s/ \([0-9]*$\)/x^\1/;s/\^1//;s/x^0//;s/+\(.*-.*\)/\1/'

Jalankan skrip sh:

./pol-int.sh
f(1/2) = -1/2
f(-25) = -1/2
f(-54/12) = -1/2

f(x) = -\frac{1}{2}

.

./pol-int.sh
f(4/3) = 617/8
f(2) = 20/3
f(-8/3) = 6749/81
f(-5) = 7367/12
f(0) = 23/3

f(x) = -\frac{37745}{14592}x^4
       -\frac{853249}{43776}x^3
     +  \frac{57809}{7296}x^2
     + \frac{225205}{2736}x
     +  \frac{23}{3}
Eelvex
sumber
Anda tidak harus membuat format kode sumber yang sama persis. Dalam output LaTeX. Seharusnya hanya menghasilkan representasi grafis yang sama setelah dijalankan melalui LaTeX. Jangan ragu untuk menyimpan beberapa karakter.
FUZxxl
Saya tidak bisa membaca J, tetapi dari panjang pendek saya menganggap itu berarti J memiliki fungsi bawaan untuk bentuk eselon matriks?
Timwi
@ Timwi: Tidak, tapi saya menggunakan "inverse matrix" bawaan. J sangat singkat: walaupun saya harus mengimplementasikan "invert matrix" itu akan menjadi beberapa karakter.
Eelvex
3

Perl (569 karakter)

use Math'BigInt;sub r{($u,$v)=@_;$v?r($v,$u%$v):$u}sub c{new Math'BigInt$_[0]}$a=@c=<>;for(@c){m!(-?\d+)/?(\d*). = (-?\d+)/?(\d*)!;$j{$_,$i}=$1**c$_,$k{$_,$i|=0}=($2||1)**c$_ for 0..$a;$j{$a,$i}=c$3;$k{$a,$i++}=c$4||1}for$p(0..$a-1){for$y(0..$p-1,$p+1..$a-1){$n=$j{$p,$y}*$k{$p,$p};$o=$k{$p,$y}*$j{$p,$p};$j{$_,$y}=$j{$_,$y}*$k{$_,$p}*$o-$k{$_,$y}*$j{$_,$p}*$n,$k{$_,$y}*=$k{$_,$p}*$o for 0..$a}}print"f(x)=";for(1..$a){$s=r$t=$j{$a,$p=$a-$_}*$k{$p,$p},$w=$k{$a,$p}*$j{$p,$p};$u=abs$t,print$t>0?"$z":'-',($z='+',$w/=$s)-1?"\\frac{$u}{$w}":$u,$p>1?"x^$p":x x$p if$t/=$s}

Penjelasan detail:

use Math'BigInt;

# Subroutine to calculate gcd of two numbers
sub r{($u,$v)=@_;$v?r($v,$u%$v):$u}

# Subroutine to create BigInts
sub c{new Math'BigInt$_[0]}

# Read input
# Throughout, $a is the number of equations.
$a=@c=<>;

# Initialises the $a+1 × $a matrix with all the values.
# $j{$x,$y} contains the numerator, $k{$x,$y} the denominator.
for(@c)
{
    m!(-?\d+)/?(\d*). = (-?\d+)/?(\d*)!;

    # Puzzle for the reader: why is $i|=0 in the second one,
    # not the first one? Answer at the bottom!
    $j{$_,$i}=$1**c$_,$k{$_,$i|=0}=($2||1)**c$_ for 0..$a;
    $j{$a,$i}=c$3;
    $k{$a,$i++}=c$4||1
}

# Generates the matrix echelon form.
# Basically, it works like this:
for$p(0..$a-1)
{
    # For each element along the diagonal {$p,$p}, set all the values above and
    # below it to 0 by adding a multiple of row $p to each of the other rows.
    for$y(0..$p-1,$p+1..$a-1)
    {
        # So we need to multiply the row $p by the value of {$p,$y}/{$p,$p}
        # (stored in $n/$o) and then subtract that from row $y.
        $n=$j{$p,$y}*$k{$p,$p};
        $o=$k{$p,$y}*$j{$p,$p};
            $j{$_,$y}=$j{$_,$y}*$k{$_,$p}*$o-$k{$_,$y}*$j{$_,$p}*$n,
            $k{$_,$y}*=$k{$_,$p}*$o
        for 0..$a
    }
}

# Outputs the result
print"f(x)=";
for(1..$a)
{
    # Note this sets $p = $a-$_. $p is the power of x.
    # We need to divide {$a,$p} by {$p,$p}. Store the result in $t/$w.
    # We also need to put the fraction in lowest terms, so calculate the gcd.
    $s=r$t=$j{$a,$p=$a-$_}*$k{$p,$p},$w=$k{$a,$p}*$j{$p,$p};

    # Output this term only if the numerator ($t) is non-zero.
    # Output a plus sign only if this isn’t the first term.
    # Output a fraction only if the denomator ($w) isn’t 1.
        $u=abs$t,print$t>0?"$z":'-',
        ($z='+',$w/=$s)-1?"\\frac{$u}{$w}":$u,$p>1?"x^$p":x x$p
    if$t/=$s
}

# Answer to the puzzle buried in the code above:
# It’s because the second part is passed as a second argument to c,
# hence it is evaluated before the first part.

Komentar

  • Saya yakin ada modul untuk manipulasi matriks yang menyediakan fungsi untuk bentuk eselon. Saya secara khusus tidak menggunakannya (bahkan tidak mencari) karena saya menganggap ini adalah tujuan dari kontes ini untuk melakukannya sendiri. Lebih menarik juga seperti itu. Tentu saja hal yang sama dapat dikatakan tentang BigInt, tapi kemudian saya curiga tidak ada yang akan mencoba tantangan ini ...

Suntingan

  • (630 → 585) Sadar saya bisa melakukan bentuk eselon dalam satu lingkaran, bukan dua. Tambahkan penjelasan sebagai komentar dalam kode.

  • (585 → 583) Hanya ditemukan sintaks paket yang memungkinkan saya menggunakan 'bukan ::.

  • (583 → 573) Sebagian lagi microgolfing

  • (573 → 569) Ekspresi reguler yang lebih pendek untuk mem-parsing input

Timwi
sumber
Saya terus menerima kesalahan kompilasi: ideone.com/LoB2T
FUZxxl
@ FuZxxl: Terima kasih telah menunjukkan itu. Hanya ada ruang yang hilang. Diperbaiki sekarang
Timwi
3

TI-Basic (83/84): 109 karakter

Secara teknis 109 karakter, TI-Basic menghitung redup (, Untuk (, ->, rref (, [A], dan daftar sebagai "satu karakter").

Input diformat menjadi L1 dan L2, dalam pasangan (x, y) [ex L1 = (1,2,3,4), L2 = (2,3,5,7)].

{1,1}->dim([A]
{dim(L1),dim(L2)+1}->dim([A]
For(A,1,dim(L1)
For(B,dim(L1)-1,0,-1
L1(A)^B->[A](A,dim(L1)-B
End
L2(A->[A](A,dim(L1)+1
End
rref([A]->[A]
{0}->L3
For(A,1,dim(L1)
[A](A,dim(L1)+1->L3(A
End
Disp L3
beary605
sumber
1
Ini tidak menggunakan rasional atau formulir LaTeX.
lirtosiast
1

Metode Lagrange, Python, 199 byte

Sedikit terlambat, tapi ...

def lagrange(dp):
l = lambda i: lambda x: (prod([(x - dp[j][0]) / (dp[i][0] - dp[j][0]) for j in range(len(dp)) if i != j]))
return lambda x: sum([l(i)(x) * dp[i][1] for i in range(len(dp))])
Fred Frey
sumber
1
Anda mungkin tidak membutuhkan semua ruang kosong di sekitar operator, bukan?
0
l=lambda D,i:lambda x:prod((x-Dj[0])/(D[i][0]-Dj[0])for j,Dj in enumerate(D)if i!=j)
L=lambda D:lambda x:sum(l(D,i)(x)*Di[1]for i,Di in enumerate(D))

Hanya versi singkat dari kode Fred Freys. Perhatikan bahwa seseorang mungkin dapat melewati passing D ke l, karena ia hanya dapat menariknya dari lingkup luar. Karena Anda mungkin dapat melakukan hal yang sama dengan saya di sini, kami bahkan dapat mencukur satu lambda. Saya akan mengujinya suatu hari nanti.

Teck-freak
sumber