Аналитическое взятие производной

Собственно сабж.

В гугле находил что-то мутное, и как я понял лучше использовать ПОЛИЗ только префиксный (могу не правильно назвать).
Аналитическая запись представляет строку вида "(x+2)^2+3*y" вообще набор операторов "+" "-" "^" (степень, производная от xor тт), еще желательно поддержка "/". Так вот задача вроде не сложная, но все-таки лучше использовать наработанные и проверенные алгоритмы.

Предлагайте!

 

http://www.delphikingdom.com/asp/viewitem.asp?catalogid=1327
Используй слово вычисление вместо взятие и гугл тебе поможет.

 

valterg
честно говоря кроме этого примера, там только учебники по Мат Пакетам, но я гляну что за пример, хотя там и богомерзкий делфи

 

так все просто же, парсишь формулу в дерево, которое есть композиция функций, потом берешь производную по правилам

 

если использовать 3 правила
a + b -> a' + b'
a * b -> a'*b + a*b'
a^n -> n*a^(n-1)

(откуда a/b = a*(b^-1) -> a'/b-a*(b^-2)*b' = (a'*b-a*b')/b^2 )

то и в дереве должны быть операции 3х типов

само собой для этого лучше всего подходит ООП, паттерн интерпретатор (см. GoF)

 

само собой нужны еще правила:
С -> 0
a + 0 -> a
a * 0 -> 0
0 ^ n -> 0

 

GoldFinch
да понятно что просто, просто выбираю оптимальное решение, можно дерево, но я полиз пробовать.

 

а как входные заданы? как массив выборок через промежутки времени? и нужно получить массив выборок производной? тогда тупо дY(X)/дX

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

 

qqwe
Как строка задана, естесно и я прекрасно понимаю как надо решать эту задачу, просто может есть мегоСуперСпособ который я не знаю.

не понял, что имеете в виду? конечно тривиальный полиз можно назвать "любимым компилиром" но я не вкурил )

А про

хм, вроде слово аналитически противоречит "получить массив выборок" и тогда тупо дY(X)/дX не лучший, а точнее не правильный метод, а так методы численного вычисления производной тоже мне известны.


PS ладно, пойду начну писать там видно будет, не если есть мегоСуперСпособ, то сообщите пожалуйста

 

SPA

отвечаете непонятной фразой на непонятную?

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

"аналитически" я понимаю как "численно", а формулы это немного не отсюда. хотя может я и ошибаюсь.

ЗЫ приведите правильный способ. мне иногда сталкиваться с таким приходится. чтобы знать

 

совершенно наоборот, численно != аналитически это скорее противоположности.

все GoldFinch правильно сказал, для составление дерева юзать ПОЛИЗ вот и все, хотя когда задача будет решена, тогда и можно будет говорить о чем-то.

 

http://ru.wikipedia.org/wiki/Обратная_польская_запись
это? а зачем оно? и читать куда как труднее

я имею ввиду. разобрать формулу можно так. (упрощенный вариант. без построения и анализа дерева)

# o - словарь вида {'p': "производная", n: "не производная"}
# компилятор coco - питон форк (есть форки под достаточный спектр лангов)

Код (Text):

1. In<out o>          =                              (. o = '' .)
2.                            AddSub<out o>
3.                        .
4.  
5. AddSub<out o>  = MulDiv<out o1>
6.                           { (  "+"                    (. op = "+" .)
7.                              |
8.                                "-"                     (. op = "-" .)
9.                             ) MulDiv<out o2>    (. (o1p, o1n) = (o['p'], o['n'])
10.                                                           (o2p, o2n) = (o2['p'], o2['n'])
11.                                                           o = { 'p': "( " + o1p + op + o2p + " )",
12.                                                                   'n': "( " + o1n + op + o2n + " )"
13.                                                                }
14.                                                        .)
15.                           }
16.                        .
17.  
18. MulDiv<out o>   = Pow<out o>
19.                          { (  "*"                    (. op = "*" .)
20.                             |
21.                               "/"                     (. op = "/" .)
22.                            ) Pow<out o2>       (. (o1p, o1n) = (o['p'], o['n'])
23.                                                          (o2p, o2n) = (o2['p'], o2['n'])
24.                                                          o = { 'p': "( " + o1p + op + o2n,
25.                                                                  'n': "( " + o1n + op + o2n + " )"
26.                                                               }
27.                                                          if op == "*":
28.                                                             o['p'] += "+" + o1n + "*" + o2p
29.                                                          else:
30.                                                             o['p'] += "-" + o1n + "*" + o2p + "/(" + o2n + "^2)"
31.                                                          o['p'] += " )"
32.                                                       .)
33.                          }
34.                       .
35.  
36. Pow<out o>      = Single<out o>
37.                          [ "^" Number<out o2>  (. (o1p, o1n) = (o['p'], o['n'])
38.                                                             (o2p, o2n) = (o2['p'], o2['n'])
39.                                                             o = { 'p': "( " + o2n + "*" + o1p + "*" + o1n + "^" + (int(o2n) - 1) + " )",
40.                                                                     'n': "( " + o1n + "^" + o2n + " )"
41.                                                                  }
42.                                                          .)
43.                          ]
44.                       .
45.  
46. Single<out o>   =  Number<out o>
47.                        |
48.                          Var<out o>
49.                        |
50.                          "(" In<out o> ")"
51.                        |
52.                          Function<out o>
53.                      .

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

скобки эти таки жуть, но они прообраз дерева

 

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

 

Интересно, а что твоя прога будет делать, если сначала задать полином как x^5+x^4... а потом как (x+5)(x+4)(x+3)... Даже если правильно напишешь дерево или стек чтобы отловить производную сложной функции или длинного произведения то результат даже от простых примеров может получиться хотя и правильным но совершенно неудобоваримым тк нужно еще уметь сокращать, выносить или вносить за скобки, приводить общие члены и тд

 

persicum
пока не парит

 

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

Код (Text):

1. COMPILER P
2.  
3. IGNORECASE    
4.  
5. CHARACTERS
6.   letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".
7.   digit  = "0123456789".
8.   op     = "+-*/^" .
9.   par    = "()" .
10.   eol    = CHR(13) .
11.   lf     = CHR(10) .
12.  
13. TOKENS
14.   number = digit {digit} .
15.   name   = letter {letter | digit} .
16.  
17. COMMENTS
18.   FROM '#' TO eol
19.  
20. IGNORE eol + lf
21.  
22. PRODUCTIONS
23. P = [ In<out o>            (. print o['p'] .)
24.     ]
25.       EOF
26.     .
27.  
28.  
29. //----------------------------------------------------------------------------
30.  
31. In<out o>          =                             (. o = '' .)
32.                            AddSub<out o>
33.                        .
34.  
35. AddSub<out o>  = MulDiv<out o>
36.                           { (  "+"               (. op = "+" .)
37.                              |
38.                                "-"               (. op = "-" .)
39.                             ) MulDiv<out o2>     (. (o1p, o1n) = (o['p'], o['n'])
40.                                                     (o2p, o2n) = (o2['p'], o2['n'])
41.                                                     o = { 'p': o1p + op + o2p,
42.                                                           'n': o1n + op + o2n
43.                                                         }
44.                                                  .)
45.                           }
46.                        .
47.  
48. MulDiv<out o>   = Pow<out o>
49.                          { (  "*"                (. op = "*" .)
50.                             |
51.                               "/"                (. op = "/" .)
52.                            ) Pow<out o2>         (. (o1p, o1n) = (o['p'], o['n'])
53.                                                     (o2p, o2n) = (o2['p'], o2['n'])
54.                                                     o = { 'p': "( " + o1p + op + o2n,
55.                                                           'n': "( " + o1n + op + o2n + " )"
56.                                                         }
57.                                                     if op == "*":
58.                                                        o['p'] += "+" + o1n + "*" + o2p
59.                                                     else:
60.                                                        o['p'] += "-" + o1n + "*" + o2p + "/(" + o2n + "^2)"
61.                                                     o['p'] += " )"
62.                                                  .)
63.                          }
64.                       .
65.  
66. Pow<out o>      = Single<out o>
67.                          [ "^" Number<out o2>    (. (o1p, o1n) = (o['p'], o['n'])
68.                                                     (o2p, o2n) = (o2['p'], o2['n'])
69.                                                     o = { 'p': o2n + "*(" + o1p + ")*" + o1n + "^" + str(int(o2n) - 1),
70.                                                           'n': o1n + "^" + o2n
71.                                                         }
72.                                                  .)
73.                          ]
74.                       .
75.  
76. Single<out o>   = Function<out o>
77.                        |
78.                          Number<out o>
79.                        |
80.                          Var<out o>
81.                        |
82.                          "(" In<out o1> ")"       (. o = { 'p': "( " + o1['p'] + " )",
83.                                                            'n': "( " + o1['n'] + " )"
84.                                                         }
85.                                                 .)
86.                      .
87.  
88. Var<out o>      =  name                          (. o = { 'p': '1',
89.                                                           'n': self.token.val
90.                                                         }
91.                                                  .)
92.                 .
93.  
94. Number<out o>   =  number                        (. o = { 'p': '0',
95.                                                           'n': self.token.val
96.                                                         }
97.                                                  .)
98.                 .
99.  
100. Function<out o> =
101.                    "sin" "(" In<out o1> ")"      (. (o1p, o1n) = (o1['p'], o1['n'])
102.                                                     o = { 'p': " cos(" + o1n + ")*(" + o1p + ")",
103.                                                           'n': "sin(" + o1n + ")"
104.                                                         }
105.                                                  .)
106.                  |
107.                    "cos" "(" In<out o1> ")"      (. (o1p, o1n) = (o1['p'], o1['n'])
108.                                                     o = { 'p': " -sin(" + o1n + ")*(" + o1p + ")",
109.                                                           'n': "cos(" + o1n + ")"
110.                                                         }
111.                                                  .)
112.                 .
113.  
114. END P.

на предложенном выше примере

выдает строку

чтобы поубирать и сократить надо делать хоть примитивное промежуточное дерево и сокращать его.

расширить возможности, можно пользуясь приведенным экзамплом и http://ru.wikipedia.org/wiki/Таблица_производных

если захочется, все же, оптимизации + сокращения, то это не счас. нг на носу однако! выпьем!
YY !

 

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

 

maksim_
чяго чяго? Брат максимка, это ты путаешь дифференцыалы с интегралами, чего делать никак не стоит. Проиизводная всегда легко вычислима и прога для этого нужна не сложнее калькулятора со скобками.

 

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

 

cupuyc

Без разницы. Как говорил наш препод по ТДУ - "дифференцирование - ремесло, интегрирование - искусство!"