Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.89
Xsenon_rus
8 / 8 / 0
Регистрация: 18.04.2011
Сообщений: 104
#1

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

28.11.2013, 21:26. Просмотров 2512. Ответов 8
Метки нет (Все метки)

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

Добавлено через 3 часа 49 минут
Есть варианты ?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nick Alte
Эксперт С++
1603 / 995 / 118
Регистрация: 27.09.2009
Сообщений: 1,918
Завершенные тесты: 1
28.11.2013, 21:40     Нахождение производной #2
Производная зависит от типа узла. Берём формулы для листьев дерева, берём формулы для сложения, умножения, вложенных функций и т.д. и применяем. В чём проблемы-то?
Xsenon_rus
8 / 8 / 0
Регистрация: 18.04.2011
Сообщений: 104
28.11.2013, 21:46  [ТС]     Нахождение производной #3
Цитата Сообщение от Nick Alte Посмотреть сообщение
Производная зависит от типа узла. Берём формулы для листьев дерева, берём формулы для сложения, умножения, вложенных функций и т.д. и применяем. В чём проблемы-то?
Ну например с умножением траблы, пусть есть (a+a)' = 0, а когда (a+a)*x = 2a, т.е. case для '+', уже не получаеться ...
Nick Alte
Эксперт С++
1603 / 995 / 118
Регистрация: 27.09.2009
Сообщений: 1,918
Завершенные тесты: 1
28.11.2013, 22:14     Нахождение производной #4
Предлагаю взять формулы из мат. анализа, а не те странные штуки вроде (a + a)'. Формула для сложения (u(x) + v(x))' = u'(x) + v'(x). Если обе функции - константы, то их производные будут 0, получим 0 + 0.
Получившаяся таким образом производная, конечно, не будет иметь тот вид, к которому мы привыкли. 0 + 0 сам по себе не сократится до 0. Но упрощение формул - отдельная задача, с которой можно (если есть такая необходимость) разбираться уже после того, как будет правильно работающий извлекатор производных.
Xsenon_rus
8 / 8 / 0
Регистрация: 18.04.2011
Сообщений: 104
28.11.2013, 22:29  [ТС]     Нахождение производной #5
Цитата Сообщение от Nick Alte Посмотреть сообщение
Предлагаю взять формулы из мат. анализа, а не те странные штуки вроде (a + a)'. Формула для сложения (u(x) + v(x))' = u'(x) + v'(x).
Вот в этом и задача я не могу написать функцию для правильной оброботки, т.е. как в прошлом примере, если я вызываю функцию для обработки +, то он смотрит констатна это или х, все просто, но эту же функцию я не могу вызвать когда обрабатываю строку (а+а)*х т.к в таком случае он выдаст что это = 0, а это не правильно ...
.......*
...../...\
...+......x
../...\
.0....0
т.к. это константы он сделает так...
......*
..../...\
..0......x
Jupiter
Каратель
Эксперт C++
6549 / 3969 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
28.11.2013, 22:40     Нахождение производной #6
Цитата Сообщение от Xsenon_rus Посмотреть сообщение
Есть варианты ?
конечно есть, написать программу на прологе и потом из неё фетчить результаты в программу на с++. кесареву кесарево.
Xsenon_rus
8 / 8 / 0
Регистрация: 18.04.2011
Сообщений: 104
28.11.2013, 23:00  [ТС]     Нахождение производной #7
Цитата Сообщение от Jupiter Посмотреть сообщение
конечно есть, написать программу на прологе и потом из неё фетчить результаты в программу на с++. кесареву кесарево.
А средствами Си ? =) Так то можно было бы и парсер написать, преворительно обойдя дерево и записав в стринг инфиксную запись, но нет это костыль... Тут что то проще я это чуствую, но не могу подобраться...
VTsaregorodtsev
315 / 295 / 41
Регистрация: 19.02.2010
Сообщений: 1,270
29.11.2013, 01:02     Нахождение производной #8
Xsenon_rus, дифференцирование сложной функции, развитое до метода обратного распространения ошибки (способ быстрого вычисления градиентов в многослойных нейронных сетях) - может помочь отцу русской демократии
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.11.2013, 01:07     Нахождение производной
Еще ссылки по теме:

C++ Поменять нахождение min среди двумерного массива, на нахождение min в каждой сточке
Алгоритм Рунге-Кутта для производной второго порядка C++
Построить таблицу значений непрерывной функции y=y(x) и её производной C++
C++ Используя таблицу конечных разностей, определить значение 1 и 2-ой производной
Создать програму для вычисления производной в заданной точке C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
29.11.2013, 01:07     Нахождение производной #9
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, которая принимает исходное выражение, пачку преобразований, и применяет их соответствующим образом.
Yandex
Объявления
29.11.2013, 01:07     Нахождение производной
Ответ Создать тему
Опции темы

Текущее время: 03:03. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru