Здравствуйте, Ujniy, Вы писали:
U>Всем доброе время суток! Подскажите пожалуйста, как ПРАВИЛЬНО найти производную функции U>одной переменной, что можно прочитать по этому поводу? На входе строка или массив, например U>"arctg(1/x) — x^2" на выходе, соответственно должно быть "(-1 – 2*x^3 – 2*x )/ (x^2 + 1)".
Всем доброе время суток! Подскажите пожалуйста, как ПРАВИЛЬНО найти производную функции
одной переменной, что можно прочитать по этому поводу? На входе строка или массив, например
"arctg(1/x) — x^2" на выходе, соответственно должно быть "(-1 – 2*x^3 – 2*x )/ (x^2 + 1)".
Здравствуйте, Ujniy, Вы писали:
U>Всем доброе время суток! Подскажите пожалуйста, как ПРАВИЛЬНО найти производную функции U>одной переменной, что можно прочитать по этому поводу? На входе строка или массив, например U>"arctg(1/x) — x^2" на выходе, соответственно должно быть "(-1 – 2*x^3 – 2*x )/ (x^2 + 1)".
Основная идея — парсим выражение в дерево, дальше идем по дереву, применяя правила дифференцирования и строя другое дерево — дерево производной. Полученное дерево выводим.
Здравствуйте, Vintik_69, Вы писали:
V_>Здравствуйте, Ujniy, Вы писали:
U>>Всем доброе время суток! Подскажите пожалуйста, как ПРАВИЛЬНО найти производную функции U>>одной переменной, что можно прочитать по этому поводу? На входе строка или массив, например U>>"arctg(1/x) — x^2" на выходе, соответственно должно быть "(-1 – 2*x^3 – 2*x )/ (x^2 + 1)".
V_>Основная идея — парсим выражение в дерево, дальше идем по дереву, применяя правила дифференцирования и строя другое дерево — дерево производной. Полученное дерево выводим.
Большое спасибо за ваш ответ! Не подскажите книгу или другой источник с примером?
И возможно ли стек использовать вместо дерева? Я, признаюсь, с деревьями не работал пока...
U>Большое спасибо за ваш ответ! Не подскажите книгу или другой источник с примером? U>И возможно ли стек использовать вместо дерева? Я, признаюсь, с деревьями не работал пока...
Здравствуйте, Ujniy, Вы писали:
U>И возможно ли стек использовать вместо дерева? Я, признаюсь, с деревьями не работал пока...
С деревьями будет наиболее очевидно. Но и со стеком можно, правда, на выходе всё равно будет дерево.
Правила дифференцирования таковы, что если идти сверху вниз, то в выражении одновременно появляются и исходные подвыражения, и их производные.
Поэтому, если мы пойдём снизу вверх (от элементарных подвыражений), то придётся запоминать и подвыражение, и его производную.
Грамматика у нас операторная, поэтому элементы стека — это чередующиеся операторы и операнды.
Операнд — это пара (выражение, его производная).
Правила трансформации такие:
(f,f') "+" (g,g') --> (f+g, f'+g')
(f,f') "*" (g,g') --> (f*g, f*g'+f'*g)
откуда они берутся: если исходное выражение было f*g, то, зная f,f', g,g', мы узнаём и результат комбинации f*g, и производную этой комбинации fg'+f'g
Ну и так далее:
"fun" (f,f') --> (fun(f), fun'(f)*f')
(f,f') "^" "const" --> (f^const, const*f^(const-1))
Маленькая выгода: мы можем хранить операнды прямо в виде строк, а не в виде синтаксических деревьев.
Здравствуйте, Ujniy, Вы писали: U>Большое спасибо за ваш ответ! Не подскажите книгу или другой источник с примером? U>И возможно ли стек использовать вместо дерева? Я, признаюсь, с деревьями не работал пока...
У Кнута есть описание этого алгоритма, к сожалению не помну какой том.
Здравствуйте, What, Вы писали:
W>Здравствуйте, Ujniy, Вы писали: U>>Большое спасибо за ваш ответ! Не подскажите книгу или другой источник с примером? U>>И возможно ли стек использовать вместо дерева? Я, признаюсь, с деревьями не работал пока... W>У Кнута есть описание этого алгоритма, к сожалению не помну какой том.
В первом.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, Vintik_69, Вы писали:
V_>Здравствуйте, Ujniy, Вы писали:
U>>Всем доброе время суток! Подскажите пожалуйста, как ПРАВИЛЬНО найти производную функции U>>одной переменной, что можно прочитать по этому поводу? На входе строка или массив, например U>>"arctg(1/x) — x^2" на выходе, соответственно должно быть "(-1 – 2*x^3 – 2*x )/ (x^2 + 1)".
V_>Основная идея — парсим выражение в дерево, дальше идем по дереву, применяя правила дифференцирования и строя другое дерево — дерево производной. Полученное дерево выводим.
Делал я такую штуку таким же методом. Этот этап прост. Над чем парился — это упрощения выражений. Уж очень неудобоваримые эти деревья в текстовом виде. И так и сяк, но до идеала не дошел. И дело не только в том, что человеку плохо видно. Даже если с производной будет иметь делло только машина, иногда хочется трансформировать ее так, чтобы ее выисление было бы максимально быстрым.
Не стыдно попасть в дерьмо, стыдно в нём остаться!
Здравствуйте, Ujniy, Вы писали:
U>Всем доброе время суток! Подскажите пожалуйста, как ПРАВИЛЬНО найти производную функции U>одной переменной, что можно прочитать по этому поводу? На входе строка или массив, например U>"arctg(1/x) — x^2" на выходе, соответственно должно быть "(-1 – 2*x^3 – 2*x )/ (x^2 + 1)".
Перекуём баги на фичи!
