На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (3) [1] 2 3  все  ( Перейти к последнему сообщению )  
> Нахождение производной
    Подскажите пожалуйста алгоритм нахождения производной...
        Переведи свое выражение в польско-инверсную или польско-префиксную запись. А потом в лоб переведи ее в производную.
        А вообще я эту тему переношу в раздел "Алгоритмы". Так как спп я в ней не вижу.
        2leprecon

        ну ты блин даёшь. человек спрашивает, как найти производную, а ты ему что????
        один из шагов одного из многих способов решения одного из вариантов постановки задачи. для него (да и для меня в какой-то степени) это звучит как магическое заклинание или как издевательство. наверняка он и с с++ом-то не знаком! ну при чём сдесь польша???????????

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

        начнём с первой. делаешь так: находишь значение функции в твоей точке, назовём её х, находишь его же в точке, удалённой от х на малое_по_твоему_мнению_расстояние dx, напр 0,001 - точка будет называться x+dx. разность значений функций, поделённое на dx, и будет производной. для вящей пущности следует также найти производную, используя точку x-dx, а потом посчитать среднее арифметическое. ежели тебе дана величина максимально допустимой ошибки, то надо уменьшить dx например в 10 раз и снова посчитать производную, а затем сравнить с предыдущим её значением. если разница превышает твою ошибку, надо снова уменьшить dx, в противном случае удовлетвориться полученным значением.

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

        программы писать лень, к тому же я не очень дружу с с++ом.
          Цитата wormball, 13.03.03, 18:51:55
          2leprecon ну ты блин даёшь. ...........
          наверняка он и с с++ом-то не знаком! ну при чём сдесь польша?

          При чем сдесь C++ ???
          Если бы ты знал что такое польско-инверсная или префиксная запись, то не стал бы спрашивать при чем здесь она.
          Цитата wormball, 13.03.03, 18:51:55
          найти аналитический вид производной функции, заданной в аналитическом же виде (т е в виде строки).

          Так вот, польская запись, получается из аналитического вида функции (т.е. в виде строки). И представляет собой наиболее удобный вид для алгоритмической работы с функцией.
          аналитический вид: a+b*c/d+e  
          польско-инверсный: abc*d/+e+
          польско-префиксный: ++a/*bcde

          Цитата wormball, 13.03.03, 18:51:55
          будет у тебя рекурсивная функция, которая будет последовательно применять к строке правила нахождения производной.

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

          Дифференцируем по b
          Если найти производную в лоб, то получится вот что: 0+((1*c+b*0)*d-(b*c)*0)/d^2+0 => Это тоже самое что c/d

          Если пройтись рекурсией по польско префиксной записи, то как раз получится
          0+((1*c+b*0)*d-(b*c)*0)/d^2+0. Останется только упростить выражение и все - аналитический вид производной в польско-префиксной нотации получен!

          Если делать тоже самое с польско-инверсной записью, то вместо рекурсии будет цикл и стек.

          Т.е. для нахождения аналитического вида производной алгоритм такой:
          1. Дано выражение : a+b*c/d+e  
          2. Переводим в польскую запись, например префиксная: ++a/*bcde
          3. Рекурсивным алгоритмом считаем производную.
             Получается ++0/-*+*1с*b0d*bc*dd0
             Или в нормальной записи 0+((1*c+b*0)*d-(b*c)*0)/d^2+0
          4. Упрощаем выражение. Убираем все умножения на нули и сложения с нулями.
             Получается /cd
          5. Переводим обратно в нормальный вид c/d
          Сообщение отредактировано: Leprecon -
            Попробую объяснить польскую запись:
            Префиксная это когда впереди стоит операция а за ней стоят два параметра.
            Цитата
            т.е. a+b это +ab


            Цитата
            a+b+с это ++abc
            Первый плюс: 1 операнд +ab.
                               2 операнд c
            Второй плюс 1 операнд a
                             2 операнд b


            Инверсная запись наоборот:
            a+b  = ab+
            a+b+c = ab+c+ или abc++
            Например двигаемся по инверсной записи ab+c+ с самого начала:
            1. Толкаем в стек a
            2. Толкаем в стек b
            3. Оператор + => берем из стека два верних значения, складываем и толкаем в стек результат.
            4. Толкаем в стек с
            5. Оператор + => берем из стека c и значение a+b, складываем и заносим в стек.
            6. В конце верхний элемент стек это результат выражения.

            В префиксной записи сложнее, там не цикл со стеком, а рекурсия.
            ++abc
                     +
              +           c
            a    b
              Цитата wormball, 13.03.03, 18:51:55
              2leprecon:
              ну ты блин даёшь. человек спрашивает, как найти производную, а ты ему что????
              ...наверняка он и с с++ом-то не знаком! ну при чём сдесь польша???????????

              Раз с С/С++ не знаком, знач заставляем юзера взять калькулятор и считать самому производную, потому что сами, как ты сказал, С/С++ не знаем и ессно "польско-инверсную" и " польско-префиксную" запись не можем воплотить в код...

              Так что будь любезен не упрекать человека (тем более модера... почему? читай >> этот ФАК <<) в том, чего сам не знаешь...

              ЗЫ
              Ты сначала спроси, что это за записи, а потом строй из себя кого-то!
              Сообщение отредактировано: SUnteXx -
                Нет, вы тут что демагогию решили развести. Устроили тут ромашка прав-неправ, польская - не польская, знает - не знает.... >:(

                2True_Hart:
                Будьте любезны задавайте вопросы более конкретно...
                Какой алгоритм и для какого случаю конкретно... в численном или явном виде надо найти производную... Для численного поиска, кажется проблем вообще нет...
                  Всем большое спасибо.....
                  Производнуй n-ой степени надо найти в числовом виде , следующей функции, (sin x)^n
                  Еще раз большое спасибо....
                    2True_Hart

                    ну вот, я как всегда оказался прав 8).

                    как я понимаю, спасибо мне 8).

                    зы. я где-то слышал версию, что форма называется не польской, а венгерской 8)
                      Венгерская - ЭтоТакойСпособДаватьИменаПеременным.
                      (сорри за оффтоп)
                      Сообщение отредактировано: volatile -
                        Проблемы с численным решением все же есть.
                        df(x) = (f(x+h)-f (x)) / h
                        если уменьшать шаг разность f(x+h)-f (x) будет становиться все меньше и
                        в конце концов получим что угодно, но не производную.
                          Цитата Trurl, 24.03.03, 14:54:46
                          Проблемы с численным решением все же есть.
                          df(x) = (f(x+h)-f (x)) / h
                          если уменьшать шаг разность f(x+h)-f (x) будет становиться все меньше и
                          в конце концов получим что угодно, но не производную.

                          Не понял ???
                          Единственный косяк может иногда получиться только в окрестностях точек, разрыва....
                            >Проблемы с численным решением все же есть.  
                            > df(x) = (f(x+h)-f (x)) / h
                            >если уменьшать шаг разность f(x+h)-f (x) будет становиться все меньше и  
                            >в конце концов получим что угодно, но не производную.
                            2GrAnd:
                            Я думаю, что Trurl здесь имел ввиду следующее:
                             Чем меньше число, тем менее оно точно. Все таки число занимает ограниченное количество памяти.
                             Но я думаю что это не существенно. Все таки 64 бита не так уж мало. Если только мы не возьем dx=0,00000000000...0000001! ;)
                              f(x) всегда вычисляется с некоторой погрешностью.
                              При вычитании близких чисел относительная погрешность увеличивается,
                              а при делении на h увеличивается абсолютная погрешность.
                              Т.е. с уменьшением шага погрешность будет сначала уменьшаться, а затем увеличиваться.
                              Например ищем производную ln(sin(x))  в т. x=0.1
                              Начинаем с h= 0.001 - получаем 1 значащую цифру.
                              Затем последовательно уменьшаем h в 10 раз.
                              Количество значащих цифр: 2,3,4,5,6,7,6,5,4,3,2,2,1.
                                Вычисление производной через разностное отношение - не корректно.
                                Самый распространенный способ - это разбить функцию на отрезке [a,b] сеткой:
                                a = x0 < x1 < .... < xn < xn+1 = b
                                т.е. вычислить ее значения в этой сетке, соответственно f0, f1, ... fn, fn+1.
                                По этим значениям построить многочлен n+1 степени. К примеру Лангранжа:
                                Ln(x) = C0f(x0) + C1f(x1) + ... Cnf(xn)
                                где Ck = w(x)/((x-xk)w'(xk))
                                где w(x) = (x-x0)(x-x1)....(x-xn)
                                а w'(xk) = (x-x0)(x-x1)...(x-xk-1)(x-xk+1)...(x-xn)
                                Раскрыть скобки, найти коэффициенты a0, a1, ... , an+1. По ним найти n-ую производную этого многочлена, все, примерное значение производной готово.
                                Сообщение отредактировано: Leprecon -
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (3) [1] 2 3  все


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0451 ]   [ 15 queries used ]   [ Generated: 4.03.24, 07:10 GMT ]