Д. Кнут - Искусство программирования том 1 (1119450), страница 94
Текст из файла (страница 94)
Читатели, которые не знакомы с основами вычислительной математики, .могут рассматривать эту задачу как абстрактное упражнение в области алгебраических преобразований, которые определяются гледующими правилами. Р(и / и) = Р(и)/и — (и х Р(и)) /(и 1 2) Р(и 1 и) = Р(и) х (и х (и 1 (и — 1))) + ((1п и) х Р(и)) х (и 1 и) (18) (19) Эти правила позволяют оцэнить производную Р(у) для любой формулы у, состоящей из перечисленных выше операторов. Знак "-" в правиле (14) является унарным оператором, который отличается от бинарного оператора "—" в (16). Далее для обозначения унарного отрицания в узлах деревьев будет использоваться обозначение "пек".
К сожалению, правил (11) — (19) недостаточно, так как, применив их вслепую для очень простой формулы у = 3 1п(х+ 1) — а/х~, получим правильный, но совершенно неудобный для дальнейшей работы результат: Р(у) = О. 1п(х + 1) + 3((1 + 0)/(х+ 1)) — (О/х~ — (а(1(2х~ ') + ((1пх) 0)х~))/(х~) ). (20) Для сокращения количества лишних операций в этом результате нужно предусмо- треть особые случаи сложения с нулем, умножения на нуль, умножения на единицу и возведения в степень "единица". Таким образом можно сократить выражение (20) с приведением его к виду Р(у) = 3(1/(х + 1)) — (( †(а(2х)))/(х ) ). (21) Теперь оно стало более наглядным, но еще не совсем идеътьным.
На самом деле понятие удовлетворительного вида результата математических преобразований не очень хороню определено. поскольку разные математики предпочитают разные способы представления итоговых формул. Однако ясно, что формула (21) не так проста, как могла бы быть. Чтобы представить ее в более приемлемом виде, необходимо разработать специальные программы упрощения алгебраических выражений (см. упр. 17), которые позволят привести формулу (21), например, к виду Р(у) = 3(х + 1) ' + 2ах з. (22) Здесь мы ограничимся описанием программ, с помощью которых можно получить результат в виде формулы (21), а не (22).
При составлении такого алгоритма прежде всего нас будут интересовать подробности реализации этого процесса внутри компьютера. Во многих языках высокого уровня и в специальных программах, которые доступны для большинства типов компьютеров, предусмотрены специальные встроенные средства, позволяющие упростить подобные алгебраические преобразования. Однако назначение этого примера заключается в приобретении опыта работы с основными операциями с деревьями. Основная идея такого алгоритма заключается в обходе дерева в обратном порядке с вычислением производной каждого посещаемого узла до тех пор, пока не будет вычислена производная всего выражения. Использование обратного порядка обхода означает, что узел оператора (например, "+") посещается восле того, как будут продифференцнрованы его операнды.
Правила (11)-(19) подразумевают, что каждая подчиненная формула исходной формулы рано или поздно будет продифференцирована', а потому дифференцирование можно выполнять в обратном порядке обхода дерева. При работе с правопрошитым деревом уже необязательно применять стек во время выполнения этого алгоритма.
С другой стороны, недостаток подобного представления дерева заключается в том, что необходимо делать копии поддеревьев. Например, в правиле для П(и Т и) потребуется трижды копировать и и и, тогда как вместо дерева можно было бы использовать представление в виде Списка из раздела 2.3.5 и избежать такого копирования.
Алгоритм [) (Дифференцирование). Если Т вЂ” адрес заголовка списка, который указывает на формулу, представленную в описанном выше виде, а ОТ вЂ” адрес заголовка списка для пустого дерева, то в результате выполнения этого алгоритма МООЕ(ОТ) будет указывать на дерево, представляющее производную от Т по Х. [)1. [Инициализация.] Установить Р +- Тэ (а именно, первый узел дерева нри обходе в обратном порядке, который является первым узлом соответствующего бинарного дерева в симметричном порядке).
1)2. Дифференцирование.] Установить Р1 < — (Д.1МК(Р) и. если Р1 ф Л, также установить Ц1 +- КьТМК(Р1). Затем выполнить описанную ниже программу 01РР[ТТРЕ(Р)). (Программы 01РР[03 01РР[13 и т. д. вычисляют производную дерева с корнем Р и задают для указательной переменной Ц значение адреса корня этой производной.
Чтобы упростить спецификацию программ 01РР, прежде всего следует установить переменные Р1 и Ц1.) 1)3. [Восстановление связи.] Если ТТРЕ(Р) обозначает бинарный оператор, установить й(,1МК(Р1) +- Р2. (Пояснение дается ниже, при описании следующего шага.) 1)4. [Продвижение к Рэ.] Установить Р2 +- Р, Р +- Рь. Теперь, если КТАО(Р2) = 0 (т. е. если МООЕ(Р2) имеет справа брата или сестру), установить й(.1МК(Р2) +- Ц. (Именно здесь и заключена суть этого алгоритма: структура дерева Т временно разрушается так, чтобы сохранить лля дальнейшего использования связь с производной Р2. Недостающая связь будет восстановлена позднее, па шаге ВЗ. Более подробное описание этой уловки приводится в уцр.
21.) 1)5.[Обход завершен?] Если Р ф Т, вернуться к шагу В2. В противном случае установить 1.1.1МК(ОТ) +- Ц и й(.1МК(Ц) <†ОТ, КТАО(Ц) +- 1. ! Программа. описанная в алгоритме В, является общей программой операций дифференцирования, непосредственно выполняемых программами ОТРК [0), 01РР[ц...., которые вызываются на шаге Р2. Во многом алгоритм Р напоминает программу управлешш интерпретирующей системы (или компилятор), которая рассмотрена в разделе 1.4.3, но совершает обход дерева, а не простой последовательности инструкций. Для завершения алгоритма [) необходимо определить программы, которые непосредственно выполняют дифференцирование.
Далее утверждение "Р указывает на дерево" будет означать, что узел МООЕ(Р) является корнем дерева, которое хранится в памяти компьютера в виде правопрошитого бинарного дерева, хотя оба указателя Ю.1МК(Р) и КТАО(Р) утрачивают смысл при работе с таким деревом. Воспользуемся функцией конструирования деревьев (йве еоиеЬиеЬок)иксйоя). которая позволяет создавать новые деревья за счет объединения деревьев меньшего размера. Пусть х обозначает узезь некоторого типа, содержащий константу, переменную или оператор, а О и Ч обозначают указатели на деревья. В таком случае ТВЕЕ(х, О.
Ч) образует новое дерево с корнем х и поддеревьями О и У этого корня: Ч ч= АУАПь 1НРО(Ч) +- х, (Д.ТНК(Ч) +- О, В(.1МК(О) +- Ч, ВТАО(О) +- О, В(.1МК (У) +- Ч, ВТАС(Ч) +- 1; ТВЕЕ(х,О) аналогично образует новое дерево только с одним поддеревом: Ч ч:= АЧАПв 1МРО(Ч) +- х, ШМК (Ч) +- О, В(.1МК(О) + — Ч, ВТАО(О) < — 1; ТВЕЕ(х) образует новое дерево с корнем х, который является концевым узлом: Ч ь- АУАП., 1МРО(Ч) +- х. 11.1МК(Ч) +- Л.
Кроме того, для ТУРЕ(Ч) задается значение, соответствующее типу узла х. Во всех глучаях значением ТВЕЕ является Ч, т. е. указатель на только что построенное дерево. Читателю следует тщательно изучить эти определения, поскольку они иллюстрируют представление дерева на основе бинарного дерева. Еще одна функция. СОРТ(0), создает копию дерева, на которое указывает О, а ее значением является указатель на только что созданное дерево. Основные функции ТВЕЕ и СОРТ упрощают процесс поэтапного создания дерева, соответствующего производной для заданной формулы.
Нуль-арные операторы (каиспьаьььпм и перемеюьме). Для этих операций узел МОРЕ(Р) является концевым, а значения переменных Р1, Р2, Ц1 и Ц для их выполнения несущественны. Р1РР[0): (МОРЕ(Р) †констан.) Установить Ц +- ТВЕЕ(0). РТРРШ: (МОРЕ(Р) †переменн.) Если 1МРО(Р) = "Х', установить Ц ь— ТВЕЕ(1): в противном случае установить Ц +- ТВЕЕ(0). Унарные операторы (лагарифм и оьтьрицание). Для этих операций НОРЕ(Р) имеет одного ребенка.
К на которого указывает Р1, а Ц указывает на Ю(У). Значения переменных Р2 и Ц1 для выполнения этих операций несущественны. Р1РР [23: (НОРЕ(Р) — ")п".) Если 1МРО ОЦ) ф О, установить Ц +- ТВЕЕ("/", Ц, СОРУ(Р1)). Р1РРИ: (НОРЕ(Р) — "пеК".) Если 1МРО(Ц) ф О, установить Ц +- ТВЕЕ("пей",Ц). Бинарные операторы (сложение, вмчипьаиие, умножение, деление, еогеедсььие е степень). Для этих операций МОРЕ(Р) имеет двух детей, [ь' и 1; на которых указывают Р1 и Р2 соответственно; Ц1 и Ц указывают на Р([ь') и 1)(Ъ') соответственно. Р1РР[4]: (Операция "+".) Если 1МРО(Ц1) = О, установить АЧА11 Ч:= Ц1.
В противном случае, если 1НРО(Ц) = О, установить АУА1Е ь:= Ц и Ц +- Ц1; иначе — установить Ц ь- ТВЕЕ("+",Ц1,Ц). Р1РР [53: (Операция "— ".) Если 1МРООЦ) = О, установить АЧАП. е= Ц и Ц +- Ц1. В противноль случае, если 1МРО(Ц1) = О, установить АЧАП,~Ц1 и Ц+-ТВЕЕ("ььеб",Ц); иначе — установить Ц +- ТВЕЕ("-", Ц1, Ц). РТРР[б): (Операция 'х".) Если 1МРО(Ц1) ф О, установить Ц1 +- МО(.Т(Ц1, СОРУ(Р2)). Затем, если 1НРО(Ц) ф О, установить Ц +- МР(.Т(СОРУ(Р1),Ц). После эьоь о перейти к выполнению программы Р1РР [43.
Здесь ИО|ТЯ, Ч) является новой функцией, которая создает дерево для О х Ч и проверяет, не равны ли О Йли Ч единице: если 1МРО Я) = 1 и ТУРЕ(0) = О, установить АЧАП. ч= О и ИО1Т(О,Ч) +- Ч; если 1ИРО(Ч) = 1 и ТУРЕ(7) = О, установить АЧА1С ~ Ч и МО|Т(О,Ч) <- О; в противном случае установить ВОСТР,Ч) +- ТВЕЕ("х",О,Ч), 01РР [7]: (Операция и/".) Если 1МРОЩ1) ф О, установить Ц1 +- ТВЕЕ(в/",Ц1„СОРТ(Р2)). Затем, если 1МРО(Ц) Р'- О, установить Ц +- ТВЕН(в/",ИЖТ(СОРУ(Р1),Ц),ТВЕН(вТ", СОРТ(Р2),ТВЕЕ(2))), После этого перейти к выполнению программы 01РР[5]. 01РР[8]: (Операция "Т".) Сы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
