Установить f равным произведению р и q; Образовать алгебраическое произведение р и q и записать результат под именем f.

Установить f равным частному при делении р на q; Образовать алгебраическое частное р и q и записать результат под именем f. Для выполнения этой операции не нужно привлекать алгоритм деления многочленов, так как рациональная функция может включать один знак деления. Последующие знаки деления могут быть устранены при помощи школьной алгебры.

Установить f равным р в степени с; Рациональная функция р возводится в степень с, и результат записывается под именем f. Показатель степени с должен быть целым числом или именем функции с постоянным значением; если с отрицательно, результатом будет 1/р^|с|.

Установить f равным р с заменой х на q; Заменить каждое вхождение переменной х в р на q и записать полученное значение под именем f. Отметим, что в результате подстановки переменная х может снова возникнуть в f, но ее не следует вновь заменять на q.

Установить f равным производной р по х; Вычислить производную dp/dx и записать полученное значение в f. Конечно, идентификатор х должен быть переменной или именем функции, состоящей из одной переменной.

Напечатать р; Напечатать рациональную функцию р в удобном для чтения виде.

Конец; Завершение последовательности команд.

При реализации команды печати мы сталкиваемся с трудностью, присущей всем программам алгебраических преобразований. При вычислениях функции, как правило, становятся очень сложными. Вместе с тем человек хотел бы получить результаты в достаточно простом виде. Рациональные функции записывают обычно в виде дроби, числитель и знаменатель которой представляют собой сумму членов, включающих только операции умножения и возведения в степень. В каждом таком одночлене все константы перемножены и образуют числовой коэффициент (первый сомножитель), переменные упорядочены (часто по алфавиту) и все степени одной переменной объединены так, чтобы каждая переменная встречалась лишь один раз. Если числовой коэффициент оказывается отрицательным, то такой одночлен должен вычитаться из предыдущих, а не прибавляться к ним. Если коэффициент окажется равным нулю или единице, то весь одночлен или коэффициент должен быть опущен. Если показатель степени отрицателен, то одночлен фактически есть дробь; в этом случае нужно освободиться от знаменателя с помощью стандартных алгебраических правил суммирования дробей. И наконец, следует приводить подобные члены, т. е. объединять одночлены, имеющие одинаковые наборы переменных и степеней, с соответствующим изменением коэффициентов.

Все эти преобразования можно выполнять путем приведения функции к некоторому каноническому внутреннему представлению. В нашем случае можно выбрать такое представление, чтобы рациональные функции были почти готовы для печати; результат каждой операции должен преобразовываться к стандартному виду. Можно и по-другому выбрать внутреннее представление, так, чтобы операция печати преобразовывала представление функции, когда это необходимо. Однако требуемый для такого преобразования объем работы может быть сколь угодно большим. Независимо от выбранного метода для целей упрощения нужно различать целые и вещественные константы, с тем чтобы погрешность машинной арифметики не помешала распознаванию нулевых и единичных значений. Заметьте также, что возведение в первую степень обычно опускают. На рис. 20.1 показаны простая программа и ее результат.

Тема. Напишите программу для работы с рациональными функциями, реализующую описанные выше возможности. Исходными данными должен быть список команд в свободном формате, а результатом — рациональные функции в формате, удобном для чтения. Переменные, константы и слова, входящие в запись команды, не должны переходить с одной строки на другую, но для самих команд и рациональных функций это вполне допустимо. Определение «удобного» формата печати довольно туманно, зато здесь вы можете продемонстрировать свое искусство в удовлетворении тех потребностей пользователей, которые они сами не могут сформулировать. Не забывайте про доказательство правильности результатов, выдаваемых программами. Одна из важных черт программ работы с рациональными функциями — это способность точно выполнять арифметические действия над целыми числами; позаботьтесь об этом в вашей программе.

Рекомендации исполнителю. Чтение программой команд и рациональных функций требует привлечения некоторых простых методов компиляции, в частности лексического анализа для распознавания символов и синтаксического анализа для построения внутреннего представления. Необходимые сведения содержатся в литературе, указанной в других главах. В процессе выполнения программы вам придется поддерживать расширяющуюся таблицу имен и значений; для этого также имеется простой метод. Самая трудная часть реализации — это выбор внутреннего представления для рациональных функций. Они, несомненно, должны представляться с помощью некоторого варианта списочной или древовидной структуры, но какого именно?

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

Инструментовка. Это еще одна задача, требующая списков или деревьев и рекурсивных процедур для их обработки. Для таких задач был создан Лисп, но наравне с ним подойдут и многие другие языки для работы со списками. Снобол несколько слабее по части внутренней обработки данных, но чрезвычайно мощные возможности по анализу вводимой и подготовке выводимой информации делают Снобол конкурентоспособным кандидатом. На самом деле здесь подойдет любой язык типа Паскаля или PL/I, так или иначе приспособленный для работы с текстами, имеющий определяемые структуры данных и рекурсивные процедуры.

Длительность исполнения. Одному исполнителю на 3 недели.

Развитие темы. В настоящее время широко используются многие системы алгебраических преобразований. Как правило, в их основе лежат функции, подобные описанным выше. Дальнейшее развитие происходит по трем направлениям: введение новых типов данных, новых операций и эвристических процедур, предназначенных для выполнения действий с нечетко определенным результатом. Новые типы данных взаимосвязаны с новыми операциями. Можно, например, добавить к рациональным функциям тригонометрические, показательные функции и логарифмы. В таком случае надо будет изменить операцию возведения в степень, чтобы она допускала любой операнд в качестве показателя степени, кроме того, понадобится операция логарифмирования, в которой будет указываться