Нахождение производной

Задача: по заданному дереву построить дерево производную.
Не могу придумать алгоритм. Не могли бы вы подсказать?
Например у меня есть формула ((x+x)*2) т.е. дерево
.......*
...../...\
....+....2
.../..\
..х....х
т.е в узлах лежат знаки (его я уже построил), так же помимо этого я могу выполнять арифметические операции с ним(если в нем только цифры), но не могу посчитать производную...

Добавлено через 3 часа 49 минут
Есть варианты ?

0

Производная зависит от типа узла. Берём формулы для листьев дерева, берём формулы для сложения, умножения, вложенных функций и т.д. и применяем. В чём проблемы-то?

0

Сообщение от Nick Alte Производная зависит от типа узла. Берём формулы для листьев дерева, берём формулы для сложения, умножения, вложенных функций и т.д. и применяем. В чём проблемы-то?

Ну например с умножением траблы, пусть есть (a+a)' = 0, а когда (a+a)*x = 2a, т.е. case для '+', уже не получаеться ...

0

Предлагаю взять формулы из мат. анализа, а не те странные штуки вроде (a + a)'. Формула для сложения (u(x) + v(x))' = u'(x) + v'(x). Если обе функции - константы, то их производные будут 0, получим 0 + 0.
Получившаяся таким образом производная, конечно, не будет иметь тот вид, к которому мы привыкли. 0 + 0 сам по себе не сократится до 0. Но упрощение формул - отдельная задача, с которой можно (если есть такая необходимость) разбираться уже после того, как будет правильно работающий извлекатор производных.

0

Сообщение от Nick Alte Предлагаю взять формулы из мат. анализа, а не те странные штуки вроде (a + a)'. Формула для сложения (u(x) + v(x))' = u'(x) + v'(x).

Вот в этом и задача я не могу написать функцию для правильной оброботки, т.е. как в прошлом примере, если я вызываю функцию для обработки +, то он смотрит констатна это или х, все просто, но эту же функцию я не могу вызвать когда обрабатываю строку (а+а)*х т.к в таком случае он выдаст что это = 0, а это не правильно ...
.......*
...../...\
...+......x
../...\
.0....0
т.к. это константы он сделает так...
......*
..../...\
..0......x

0

Сообщение от Xsenon_rus Есть варианты ?

конечно есть, написать программу на прологе и потом из неё фетчить результаты в программу на с++. кесареву кесарево.

0

Сообщение от Jupiter конечно есть, написать программу на прологе и потом из неё фетчить результаты в программу на с++. кесареву кесарево.

А средствами Си ? =) Так то можно было бы и парсер написать, преворительно обойдя дерево и записав в стринг инфиксную запись, но нет это костыль... Тут что то проще я это чуствую, но не могу подобраться...

0

Xsenon_rus, дифференцирование сложной функции, развитое до метода обратного распространения ошибки (способ быстрого вычисления градиентов в многослойных нейронных сетях) - может помочь отцу русской демократии

0

1. Определяете множество обрабатываемых выражений. У вас они могут быть трёх типов: переменная, число, результат применения функции.
2. Определяете множество функций. Например, обычные арифметические действия (бинарные), возведение в степень (бинарная), отрицание (унарная), взятие производной (бинарная).
3. Определяете правила преобразований: арифметические действия над числами преобразуются в число-результат; взятие производной преобразует выражение в другое выражение.
4. Определяете правило редукции: например, 1) перебирать все правила редукции, пока что-то не сработает, 2) рекурсивно продолжить с потомками, 3) перебрать правила ещё раз для узлов, у которых изменились потомки или они сами.
5. Так как кванторов у вас нет, то такая цепочка редукций конечна и обходится за один раз.

Реализация очевидна:
1. Базовый класс Expression, от него наследуются Number (значение-число), Variable (имя переменной) и Application (функция Function и аргументы Expression).
2. Базовый класс Function, от него варианты для унарных, бинарных, энарных функций. У них нечто вроде Expression* apply(Expression*, Expression*), которая инкапсулирует вычисления.
3. Определяете пачку унарных Function, которые выражают правила преобразований.
4. Пишете функцию reduce, которая принимает исходное выражение, пачку преобразований, и применяет их соответствующим образом.

0