Символическое дифференцирование многочленов

20

Символическое дифференцирование 1: ушел Coefishin '

задача

Напишите программу, которая принимает полином от x из стандартного ввода (1 <deg (p) <128) и дифференцирует его. Входной многочлен будет строкой следующей формы:

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

где коэффициент каждого члена является целым числом (-128 <a <128). Каждый член отделяется одним пробелом, + и другим пробелом; линейные и постоянные члены выглядят, как указано выше (то есть, нет x^0или x^1). Термины будут появляться в порядке возрастания степени, а те степени с нулевым коэффициентом опущены. Все термины с коэффициентом 1 или -1 отображают этот коэффициент явно.

Ваш вывод должен иметь точно такую ​​же форму. Обратите внимание, что коэффициенты на выходе могут быть такими большими, как 127 * 127 == 16129.

Примеры

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

счет

Ваша оценка - это длина вашей программы в байтах, умноженная на три, если вы используете встроенную или библиотеку, которая выполняет символическую алгебру.

hYPotenuser
источник
Я не могу поверить, что у нас еще не было этого вызова здесь!
flawr
5
@flawr Мы вроде как сделали. (Хотя для этого требовались и другие функции, и не было строгих правил для формата вывода.)
Мартин Эндер,
@flawr Я думал то же самое ... и все же я не нашел поиск по ссылкам Мартина. Ах хорошо.
hYPotenuser

Ответы:

15

Retina , 53 43 42 41 40 35 байт

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

В целях подсчета каждая строка идет в отдельном файле, но вы можете запустить вышеуказанное как один файл, вызвав Retina с -sфлагом.

Это предполагает, что числа во входной строке будут даны в унарном формате и будут давать выходные данные в том же формате. Например

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

вместо того

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

объяснение

Код описывает одну подстановку регулярных выражений, которая в основном состоит из 4 подстановок, сжатых в одну. Обратите внимание, что только одна из ветвей заполнит группу, $2поэтому, если какие-либо другие три совпадения, совпадение будет просто удалено из строки. Итак, мы можем взглянуть на четыре разных случая отдельно:

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

Если можно найти пробел в начале строки, не встречая, это xозначает, что первый член является постоянным, и мы его удаляем. Из-за жадности +, это также будет соответствовать плюс и второй пробел после постоянного члена. Если нет постоянного члена, эта часть просто никогда не будет совпадать.

x(?= )
<empty>

Это соответствует символу, xза которым следует пробел, т. Е. xЛинейного члена (если он существует), и удаляет его. Мы можем быть уверены, что после него есть пробел, потому что степень многочлена всегда равна как минимум 2.

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

Это выполняет умножение коэффициента на показатель степени. Это соответствует единичному 1коэффициенту и заменяет его на весь соответствующий показатель степени с помощью предварительного просмотра.

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

Это уменьшает все оставшиеся экспоненты путем сопоставления конечного значения 1(обеспечивается предварительным просмотром). Если это возможно, чтобы соответствовать ^11(и граница слова), мы удаляем это вместо этого, который заботится о правильном отображении линейного термина.

Что касается сжатия, мы замечаем, что большинство условий не влияют друг на друга. (\^1)?не будет совпадать, если предположение в третьем случае истинно, поэтому мы можем сложить эти два как

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

Теперь у нас уже есть предпросмотр , необходимое для второго случая , а другие никогда не могут быть истинными при совпадении x, так что мы можем просто обобщить 1к \w:

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

Первый случай на самом деле не имеет ничего общего с другими, поэтому мы держим его отдельно.

Мартин Эндер
источник
9

CJam, 43 41 байт

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

Спасибо @ jimmy23013 за указание на одну ошибку и отыгрывание двух байтов!

Попробуйте онлайн в интерпретаторе CJam .

Как это устроено

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 " + ".
Деннис
источник
5

Perl, 64 63 байта

62b код + 1 командная строка (-p)

Не удивительно на данный момент, но я буду продолжать пытаться сократить его.

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

Пример использования:

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

Спасибо Денис за -1б

Jarmex
источник
5

Юлия, 220 байт

Нет регулярных выражений!

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," + "))

Это создает лямбда-функцию, которая принимает строку и возвращает строку. Внутренние символы имитируют то, что происходит, когда вычисляется код Джулии: строка разбирается на символы, выражения и вызовы. Я мог бы на самом деле попытаться написать полную функцию символического дифференцирования Юлии и представить ее как часть Юлии.

Ungolfed + объяснение:

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
Алекс А.
источник
3

C 204 162 байта

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

В основном разберите каждый термин и распечатайте дифференцированный термин в последовательности. Довольно просто.

Коул Камерон
источник
2

JavaScript ES6, 108 байт

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

Фрагмент ES5:

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

Джордж Райт
источник
2

Python 2, 166 байт

Мальчик, это кажется дольше, чем должно быть.

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)

Функция dпринимает непостоянный член tи возвращает свою производную. Причина, по которой я defиспользую функцию вместо использования лямбды, заключается в том, что я могу присвоить показатель минус 1 e, который затем используется еще четыре раза. Основная раздражающая вещь заключается в том, что нужно переходить туда-сюда между строками и целыми числами, хотя в этом помогает оператор backtick в Python 2.

Затем мы разбиваем входные данные на термины и вызываем dкаждый из "x"них, тем самым устраняя постоянный член. Результаты объединяются и печатаются.

DLosc
источник
2

CJam, 62 57 55 49 байт

Ну, Деннис опозорил это еще до того, как я заметил, что сайт вернулся. Но вот мое творение в любом случае:

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

Последняя версия сохраняет несколько байтов с ярлыками, предложенными @Dennis (используйте переменные и разделяйте их пробелами вместо +).

Попробуйте онлайн

Рето Коради
источник
1
Сохранение в переменной короче, чем выталкивание в блоке else. Например, _({'^a\}{;}?на 1 байт длиннее :T({T'^a\}&.
Деннис
1
Если вы разделяете пробелы вместо знаков плюс, вам не нужен ~оставшийся блок else, и вы можете также удалить его.
Деннис
@ Денис Это работает, спасибо. Изначально я хотел устранить знаки плюс, но они все равно выпадают, когда я проверяю наличие x. Я нашел еще несколько улучшений, пока я был на этом. Главным образом, поскольку у меня теперь есть значения в переменных, я могу вспомнить их там, где они мне действительно нужны, сохранив некоторые манипуляции со стеком. У меня также был шальной, aкоторый должен был быть удален, когда я оптимизировал генерацию вывода ранее.
Рето Коради
1

Pyth, 62 байта

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

Довольно уродливое решение, использующее некоторые подстановки регулярных выражений.

orlp
источник
1

Python 3, 176 байт

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

Действительно, главное раздражение в том, что нужно конвертировать строки в строки. Кроме того, если требуется постоянный термин, код будет только 153 байта.

Эльендия Старман
источник
Первый ответ, стрельба за избиение DLosc, не совсем получилось.
El'endia Starman
0

Python 2, 229 байт

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
источник
0

Python 2, 174 байта

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

К сожалению, трюк DLosc переименовать метод split и выполнить дифференцирование в определенной функции не сокращает мой код ...

pjmv
источник