Polynominterpolation

12

Schreiben Sie ein Programm, das die Polynominterpolation unter Verwendung von rationalen Zahlen mit willkürlicher Genauigkeit durchführt. Die Eingabe sieht folgendermaßen aus:

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

Sie können davon ausgehen, dass vor und nach dem =Vorzeichen genau ein Leerzeichen steht. Alle Zahlen sind entweder Brüche oder ganze Zahlen. Sie können auch davon ausgehen, dass alle Brüche in der Eingabe bereits irreduzibel sind.

Es ist keine Fehlerprüfung erforderlich. Sie können davon ausgehen, dass die Eingabe gültig ist und in f (x) kein x verdoppelt wird.

Die Ausgabe sollte in einer LaTeX-kompatiblen Form vorliegen. Der ausgegebene LaTeX-Code sollte dieselbe grafische Darstellung wie die hier angegebene Ausgabe ergeben.

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

Der Anteil muss so weit wie möglich reduziert werden, z. sowas \frac{2}{4} ist nicht erlaubt. Wenn die Zahl eine Ganzzahl ist, verwenden Sie keinen Bruch.

Sonderregeln:

Ihr Programm sollte ...

  • Arbeit für Polynome bis Grad 12
  • In weniger als 1 Minute erledigt, um eine sinnvolle Eingabe zu erhalten
  • Verwenden Sie keine Funktionen, die die gesamte Berechnung für Sie durchführen
  • Geben Sie das Polynom mit dem kleinstmöglichen Grad aus

Testfälle:

Die angegebenen Testfälle dienen nur zur Verdeutlichung. Ihr Programm sollte für alle korrekten Eingaben ein korrektes Ergebnis liefern.

Eingang

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

Ausgabe

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

Eingang

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

Ausgabe

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

Eingang

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

Ausgabe

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

Eingang

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

Ausgabe

f (x) = 2x
     + 5

Eingang

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

Ausgabe

f (x) = - \ frac {1} {2}
FUZxxl
quelle
Warum redest du über reelle Zahlen, wenn alles, was du jemals benutzt, rationale Zahlen sind?
Joey
Es tut uns leid. Mein Englisch ist schlecht. Ja, verwenden Sie nur rationale Zahlen. Die Ergebnisse müssen genau sein.
FUZxxl
Sind im ersten Testfall Punkte ( ...) wirklich Teil der Eingabe?
Eelvex
@Eelvex: Nein. Fest.
FUZxxl
Die Ausgabe für den dritten Testfall ist falsch. Die richtige Antwort lautet -\frac{37745}{14592}x^4 - \frac{853249}{43776}x^3 + \frac{57809}{7296}x^2 + \frac{225205}{2736}x + \frac{23}{3}. Ich vermute, die Eingabe sollte etwas anderes sein :)
Timwi

Antworten:

3

J + sh

J-Skript:

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

sh script:

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/'

Führen Sie das sh-Skript aus:

./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
quelle
Sie müssen nicht genau die gleiche Quellcode-Formatierung erstellen. In der LaTeX-Ausgabe. Nach dem Ausführen von LaTeX sollte nur die gleiche grafische Darstellung angezeigt werden. Fühlen Sie sich frei, einige Zeichen zu speichern.
FUZxxl
Ich kann J nicht lesen, aber aufgrund der kurzen Länge, die ich nehme, bedeutet das, dass J eine eingebaute Funktion für die Matrixebenenform hat?
Timwi
@ Timwi: Nein, aber ich benutze die eingebaute "inverse Matrix". J ist allerdings sehr knapp: Selbst wenn ich "invert matrix" implementieren würde, wären es ein paar Zeichen.
Eelvex
3

Perl (569 Zeichen)

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}

Ausführliche Erklärung:

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.

Bemerkungen

  • Ich bin sicher, dass es ein Modul für die Matrixmanipulation gibt, das eine Funktion für die Echelonenform bietet. Ich habe das ausdrücklich nicht benutzt (habe nicht einmal nach einem gesucht), weil ich annehme, dass es der Sinn dieses Wettbewerbs ist, es selbst zu tun. Interessanter ist es auch so. Natürlich kann man dasselbe über BigInt sagen, aber dann wird vermutlich niemand diese Herausforderung annehmen ...

Bearbeitungen

  • (630 → 585) Es wurde mir klar, dass ich die Staffelform in einer Schleife anstatt in zwei machen kann. Fügen Sie eine Erklärung als Kommentar in den Code ein.

  • (585 → 583) Ich habe gerade die Paketsyntax entdeckt, mit der ich sie 'anstelle von verwenden kann ::.

  • (583 → 573) Noch etwas Mikrogolf

  • (573 → 569) Kürzere reguläre Ausdrücke zum Analysieren von Eingaben

Timwi
quelle
Ich bekomme
FUZxxl
@FUZxxl: Danke für den Hinweis. Es fehlte nur ein Platz. Jetzt behoben.
Timwi
3

TI-Basic (83/84): 109 Zeichen

Technisch gesehen zählt TI-Basic 109 Zeichen als dim (, For (, ->, rref (, [A] und listet als "ein Zeichen".

Die Eingabe wird in (x, y) Paaren in L1 und L2 formatiert [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
quelle
1
Dies verwendet keine Rationalals oder LaTeX-Form.
Lirtosiast
1

Lagrange-Methode, Python, 199 Bytes

Ein bisschen spät, aber ...

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
quelle
1
Sie brauchen wahrscheinlich nicht all das Leerzeichen um die Operatoren, oder?
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))

Nur eine verkürzte Version von Fred Freys Code. Beachten Sie, dass man wahrscheinlich die Übergabe von D nach l überspringen könnte, da es nur aus dem äußeren Bereich gezogen werden kann. Da Sie hier wahrscheinlich dasselbe mit mir machen können, könnten wir sogar einen Lambda abschneiden. Ich werde es eines Tages testen.

Teck-Freak
quelle