Symbolische Differenzierung von Polynomen

20

Symbolische Unterscheidung 1: Coefishin gegangen

Aufgabe

Schreiben Sie ein Programm, das ein Polynom in x von stdin (1 <deg (p) <128) aufnimmt und es differenziert. Das Eingabepolynom ist eine Zeichenfolge der folgenden Form:

"a + bx + cx^2 + dx^3 +" ...

wobei der Koeffizient jedes Terms eine ganze Zahl ist (-128 <a <128). Jeder Term ist durch ein Leerzeichen, ein + und ein anderes Leerzeichen getrennt. lineare und konstante Terme erscheinen wie oben (dh nein x^0oder x^1). Die Terme werden in aufsteigender Reihenfolge angezeigt, und die Potenzen mit dem Koeffizienten Null werden weggelassen. Alle Terme mit dem Koeffizienten 1 oder -1 zeigen diesen Koeffizienten explizit an.

Ihre Ausgabe muss genau die gleiche Form haben. Beachten Sie, dass die Koeffizienten in der Ausgabe möglicherweise 127 * 127 == 16129 betragen.

Beispiele

"3 + 1x + 2x^2" ==> "1 + 4x"
"1 + 2x + -3x^2 + 17x^17 + -1x^107" ==> "2 + -6x + 289x^16 + -107x^106"
"17x + 1x^2" ==> "17 + 2x"

Wertung

Ihre Punktzahl ist die Länge Ihres Programms in Bytes, multipliziert mit drei, wenn Sie eine eingebaute oder eine Bibliothek verwenden, die symbolische Algebra ausführt.

Hypotenuser
quelle
Ich kann nicht glauben, dass wir diese Herausforderung hier noch nicht hatten!
Fehler
5
@flawr Wir haben das irgendwie gemacht. (Obwohl dieses auch andere Funktionen erforderte und keine so strengen Regeln für das Ausgabeformat hatte.)
Martin Ender
@flawr Ich dachte das Gleiche ... und doch habe ich Martins verlinkte Postsuche nicht gefunden. Ah, gut.
Hypotenuser

Antworten:

15

Retina , 53 43 42 41 40 35 Bytes

^[^x]+ |(\^1)?\w(?=1*x.(1+)| |$)
$2

Zu Zählzwecken wird jede Zeile in einer separaten Datei abgelegt. Sie können die obige Datei jedoch als einzelne Datei ausführen, indem Sie Retina mit dem -sFlag aufrufen .

Dies setzt voraus, dass die Zahlen in der Eingabezeichenfolge unär sind und die Ausgabe im gleichen Format erfolgt. Z.B

1 + 11x + -111x^11 + 11x^111 + -1x^11111
-->
11 + -111111x + 111111x^11 + -11111x^1111

anstatt

1 + 2x + -3x^2 + 2x^3 + -1x^5
-->
2 + -6x + 6x^2 + -5x^4

Erläuterung

Der Code beschreibt eine einzelne Regex-Ersetzung, die im Grunde 4 Ersetzungen umfasst, die zu einer komprimiert sind. Beachten Sie, dass nur einer der Zweige die Gruppe füllt. $2Wenn also einer der drei anderen übereinstimmt, wird die Übereinstimmung einfach aus der Zeichenfolge gelöscht. Wir können uns also die vier verschiedenen Fälle getrennt ansehen:

^[^x]+<space>
<empty>

Wenn es möglich ist, ein Leerzeichen vom Anfang der Zeichenfolge aus zu erreichen, ohne auf ein zu stoßen x, bedeutet dies, dass der erste Term der konstante Term ist und wir ihn löschen. Aufgrund der Gier von +wird dies auch mit dem Pluszeichen und dem zweiten Leerzeichen nach dem konstanten Term übereinstimmen. Wenn es keinen konstanten Term gibt, wird dieser Teil einfach niemals übereinstimmen.

x(?= )
<empty>

Dies entspricht einem, auf xdas ein Leerzeichen folgt, dh dem xdes linearen Terms (falls vorhanden), und entfernt es. Wir können sicher sein, dass dahinter ein Leerzeichen steht, da der Grad des Polynoms immer mindestens 2 ist.

1(?=1*x.(1+))
$1

Dies führt die Multiplikation des Koeffizienten mit dem Exponenten durch. Dies stimmt mit einem einzelnen 1Koeffizienten überein und ersetzt ihn durch den gesamten entsprechenden Exponenten über den Lookahead.

(\^1)?1(?= |$)
<empty>

Dies reduziert alle verbleibenden Exponenten durch Anpassung des Trailings 1(durch den Lookahead sichergestellt). Wenn es möglich ist, eine Übereinstimmung ^11(und eine Wortgrenze) zu finden, entfernen wir diese stattdessen, um den linearen Term korrekt anzuzeigen.

Bei der Komprimierung stellen wir fest, dass sich die meisten Bedingungen nicht gegenseitig beeinflussen. (\^1)?passt nicht zusammen, wenn der Lookahead im dritten Fall wahr ist, also können wir diese beiden als zusammenfassen

(\^1)?1(?=1*x.(1+)| |$)
$2

Jetzt haben wir schon den Look - Ahead für den zweiten Fall benötigt und die anderen können nicht wahr sein , wenn passend x, so dass wir einfach das verallgemeinern kann 1auf ein \w:

(\^1)?\w(?=1*x.(1+)| |$)
$2

Der erste Fall hat eigentlich nichts mit den anderen zu tun, also halten wir ihn getrennt.

Martin Ender
quelle
9

CJam, 43 41 Bytes

Qleu'^/';*'+/{~:E[*'x['^E(]]E<}/]1>" + "*

Vielen Dank an @ jimmy23013 für den Hinweis auf einen Fehler und das Abwerfen von zwei Bytes!

Probieren Sie es online im CJam-Interpreter aus .

Wie es funktioniert

Q           e# Leave an empty array on the bottom of the stack.
l           e# Read a line from STDIN.
eu'^/';*    e# Convert to uppercase and replace carets with semicolons.
'+/         e# Split at plus signs.

{           e# For each resulting chunk:
  ~         e#   Evaluate it. "X" pushes 1 and ";" discards.
            e#   For example, "3X" pushes (3 1) and "3X;2" (3 2).
   :E       e#   Save the rightmost integer (usually the exponent) in E.
   [        e#
     *      e#   Multiply both integers.
            e#   For a constant term c, this repeats the empty string (Q) c times.
     'x     e#   Push the character 'x'.
     ['^E(] e#   Push ['^' E-1].
   ]        e#
   E<       e#  Keep at most E elements of this array.
            e#  If E == 1, 'x' and ['^' E-1] are discarded.
            e#  If E == 2, ['^' E-1] is discarded.
            e#  If E >= 3, nothing is discarded.
}/          e#

]           e# Wrap the entire stack in an array.
1>          e# Discard its first element.
            e# If the first term was constant, this discards [""]. ["" 'x']
            e# or ["" 'x' ['^' E-1]], depending on the constant.
            e# In all other cases, it discards the untouched empty array (Q).
" + "*      e# Join all kept array elements, separating by " + ".
Dennis
quelle
5

Perl, 64 63 Bytes

62b Code + 1 Befehlszeile (-p)

Im Moment nicht erstaunlich, aber ich werde weiterhin versuchen, es zu verkürzen.

s/(\d+)x.(\d+)/$1*$2."x^".($2-1)/eg;s/\^1\b|^\d+ . |x(?!\^)//g

Anwendungsbeispiel:

echo "1 + 2x + 3x^2" | perl -pe 's/(\d+)x.(\d+)/$1*$2."x^".($2-1)/eg;s/\^1\b|^\d+ . |x(?!\^)//g'

Danke Denis für -1b

Jarmex
quelle
5

Julia, 220 Bytes

Keine regulären Ausdrücke!

y->(A=Any[];for i=parse(y).args[2:end] T=typeof(i);T<:Int&&continue;T==Symbol?push!(A,1):(a=i.args;c=a[2];typeof(a[3])!=Expr?push!(A,c):(x=a[3].args[3];push!(A,string(c*x,"x",x>2?string("^",ex-1):""))))end;join(A," + "))

Dadurch wird eine Lambda-Funktion erstellt, die eine Zeichenfolge akzeptiert und eine Zeichenfolge zurückgibt. Die Innereien ahmen nach, was passiert, wenn Julia-Code ausgewertet wird: Eine Zeichenfolge wird in Symbole, Ausdrücke und Aufrufe zerlegt. Ich könnte tatsächlich versuchen, eine vollständige symbolische Julia-Differenzierungsfunktion zu schreiben und sie als Teil von Julia einzureichen.

Ungolfed + Erklärung:

function polyderiv{T<:AbstractString}(y::T)

    # Start by parsing the string into an expression
    p = parse(y)

    # Define an output vector to hold each differentiated term
    A = Any[]

    # Loop through the elements of p, skipping the operand
    for i in p.args[2:end]

        T = typeof(i)

        # Each element will be an integer, symbol, or expression.
        # Integers are constants and thus integrate to 0. Symbols
        # represent x alone, i.e. "x" with no coefficient or
        # exponent, so they integrate to 1. The difficulty here
        # stems from parsing out the expressions.

        # Omit zero derivatives
        T <: Int && continue

        if T == Symbol
            # This term will integrate to 1
            push!(A, 1)
        else
            # Get the vector of parsed out expression components.
            # The first will be a symbol indicating the operand,
            # e.g. :+, :*, or :^. The second element is the
            # coefficient.
            a = i.args

            # Coefficient
            c = a[2]

            # If the third element is an expression, we have an
            # exponent, otherwise we simply have cx, where c is
            # the coefficient.
            if typeof(a[3]) != Expr
                push!(A, c)
            else
                # Exponent
                x = a[3].args[3]

                # String representation of the differentiated term
                s = string(c*x, "x", x > 2 ? string("^", x-1) : "")

                push!(A, s)
            end
        end
    end

    # Return the elements of A joined into a string
    join(A, " + ")
end
Alex A.
quelle
3

C, 204 , 162 Bytes

#define g getchar()^10
h,e;main(c){for(;!h&&scanf("%dx%n^%d",&c,&h,&e);h=g?g?e?printf(" + "):0,0:1:1)e=e?e:h?1:0,e?printf(e>2?"%dx^%d":e>1?"%dx":"%d",c*e,e-1):0;}

Analysieren Sie grundsätzlich jeden Begriff und drucken Sie den differenzierten Begriff nacheinander aus. Ziemliech direkt.

Cole Cameron
quelle
2

JavaScript ES6, 108 Bytes

f=s=>s.replace(/([-\d]+)(x)?\^?(\d+)?( \+ )?/g,(m,c,x,e,p)=>x?(c*e||c)+(--e?x+(e>1?'^'+e:''):'')+(p||''):'')

ES5-Snippet:

// ES5 version, the only difference is no use of arrow functions.
function f(s) {
  return s.replace(/([-\d]+)(x)?\^?(\d+)?( \+ )?/g, function(m,c,x,e,p) {
    return x ? (c*e||c) + (--e?x+(e>1?'^'+e:''):'') + (p||'') : '';
  });
}

[
  '3 + 1x + 2x^2',
  '1 + 2x + -3x^2 + 17x^17 + -1x^107',
  '17x + 1x^2'
].forEach(function(preset) {
  var presetOption = new Option(preset, preset);
  presetSelect.appendChild(presetOption);
});

function loadPreset() {
  var value = presetSelect.value;
  polynomialInput.value = value;
  polynomialInput.disabled = !!value;
  showDifferential();
}

function showDifferential() {
  var value = polynomialInput.value;
  output.innerHTML = value ? f(value) : '';
}
code {
  display: block;
  margin: 1em 0;
}
<label for="presetSelect">Preset:</label>
<select id="presetSelect" onChange="loadPreset()">
  <option value="">None</option>
</select>
<input type="text" id="polynomialInput"/>
<button id="go" onclick="showDifferential()">Differentiate!</button>
<hr />
<code id="output">
</code>

George Reith
quelle
2

Python 2, 166 Bytes

Junge, das scheint länger zu dauern, als es sein sollte.

S=str.split
def d(t):e="^"in t and int(S(t,"^")[1])-1;return`int(S(t,"x")[0])*(e+1)`+"x"[:e]+"^%d"%e*(e>1)
print" + ".join(d(t)for t in S(raw_input()," + ")if"x"in t)

Die Funktion dnimmt einen nicht konstanten Term an tund gibt dessen Ableitung zurück. Der Grund, warum ich defdie Funktion anstelle eines Lambdas verwende, ist, dass ich den Exponenten minus 1 zuweisen kanne , der dann noch viermal verwendet wird. Das nervigste ist, zwischen Strings und Ints hin und her zu wechseln, obwohl der Backtick-Operator von Python 2 dabei hilft.

Wir teilen dann den Eingang in Terme auf und rufen djeden auf, der "x"darin ist, wodurch der konstante Term beseitigt wird. Die Ergebnisse werden wieder zusammengefügt und ausgedruckt.

DLosc
quelle
2

CJam, 62 57 55 49 Bytes

Nun, Dennis hat das beschämt, bevor ich überhaupt bemerkte, dass die Seite wieder online war. Aber hier ist trotzdem meine Schöpfung:

lS/{'x/:T,({T~1>:T{~T~*'xT~(:T({'^T}&}&" + "}&}/;

Die neueste Version spart ein paar Bytes mit von @Dennis vorgeschlagenen Verknüpfungen (verwenden Sie Variablen und teilen Sie stattdessen nach Leerzeichen auf) + ).

Probieren Sie es online aus

Reto Koradi
quelle
1
Das Speichern in einer Variablen ist kürzer als das Poppen im else-Block. Beispielsweise _({'^a\}{;}?ist 1 Byte länger als :T({T'^a\}&.
Dennis
1
Wenn Sie anstelle von Pluszeichen in Leerzeichen aufteilen, benötigen Sie den ~Block else nicht und können diesen auch entfernen.
Dennis
@ Tennis Das funktioniert, danke. Eigentlich wollte ich die Pluszeichen entfernen, aber sie fallen trotzdem aus, wenn ich auf das Vorhandensein von teste x. Während ich dabei war, habe ich weitere Verbesserungen gefunden. Da ich die Werte jetzt in Variablen habe, kann ich sie meistens dort abrufen, wo ich sie wirklich brauche, was einige Stapelmanipulationen erspart. Ich hatte auch einen Streuner a, der hätte gelöscht werden müssen, als ich die Ausgabegenerierung früher optimiert hatte.
Reto Koradi
1

Pyth, 62 Bytes

jJ" + "m::j"x^",*Fdted"x.1$"\x"x.0"kftTmvMcd"x^"c:z"x ""x^1 "J

Ziemlich hässliche Lösung mit einigen Regex-Substitutionen.

orlp
quelle
1

Python 3, 176 Bytes

s=input().split(' + ')
y='x'in s[0]
L=map(lambda x:map(int,x.split('x^')),s[2-y:])
print(' + '.join([s[1-y][:-1]]+['x^'.join(map(str,[a*b,b-1])).rstrip('^1')for a,b in L]))

In der Tat ist die Hauptstörung, zwischen Zeichenfolgen und Ints konvertieren zu müssen. Wenn ein konstanter Term erforderlich wäre, wäre der Code nur 153 Byte groß.

El'endia Starman
quelle
Die erste Antwort war das Schießen gegen DLosc.
El'endia Starman
0

Python 2, 229 Bytes

import os
print' + '.join([i,i[:-2]][i[-2:]=='^1'].replace('x^0','')for i in[`a*b`+'x^'+`b-1`for a,b in[map(int,a.split('x^'))for a in[[[i+'x^0',i+'^1'][i[-1]=='x'],i]['^'in i]for i in os.read(0,9**9).split(' + ')]]]if i[0]!='0')
nog642
quelle
0

Python 2, 174 Bytes

print' + '.join(['%d%s%s'%(b[0]*b[1],'x'*(b[1]>1),'^%d'%(b[1]-1)*(b[1]>2))for b in[map(int,a.split('x^')if 'x^'in a else[a[:-1],1])for a in input().split(' + ')if 'x'in a]])

Leider verkürzt DLoscs Trick, die Aufteilungsmethode umzubenennen und die Unterscheidung in einer bestimmten Funktion vorzunehmen, meinen Code nicht ...

pjmv
quelle