Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 49
Текст из файла (страница 49)
Она можетбрать в качестве аргументов два терма и выдавать список, состоящий из списка термов частногои списка термов остатка.Закончите следующее определение div-terms, вставив недостающие выражения. Используйте ее, чтобы реализовать div-poly, которая получает в виде аргументов два экземпляра poly, авыдает список из poly–частного и poly–остатка.(define (div-terms L1 L2)(if (empty-termlist? L1)(list (the-empty-termlist) (the-empty-termlist))(let ((t1 (first-term L1))(t2 (first-term L2)))(if (> (order t2) (order t1))(list (the-empty-termlist) L1)(let ((new-c (div (coeff t1) (coeff t2)))(new-o (- (order t1) (order t2))))(let ((rest-of-resulthрекурсивно вычислить оставшуюся206Глава 2.
Построение абстракций с помощью данныхчасть результатаi))hсформировать окончательный результатi))))))Иерархии типов в символьной алгебреНаша система обработки многочленов показывает, как объекты одного типа (многочлены) могут на самом деле быть составными сущностями, содержащими в качествечастей объекты многих различных типов.
При определении обобщенных операций этоне составляет никакой реальной сложности. Нужно только установить соответствующиеобобщенные операции для выполнения необходимых действий над частями составныхтипов. В сущности, мы видели, что многочлены образуют своего рода «рекурсивнуюабстракцию данных», в том смысле, что части многочленов сами по себе могут бытьмногочленами. Наши обобщенные операции и наш стиль программирования, управляемого данными, могут справиться с такими трудностями без особого труда.С другой стороны, алгебра многочленов представляет собой систему, в которой типыданных нельзя естественным образом выстроить в виде башни.
Например, могут существовать многочлены по x, коэффициенты которых являются многочленами по y. Номогут существовать и многочлены по y, коэффициенты которых являются многочленамипо x. Никакой из этих типов не находится «выше» другого ни в каком естественнымсмысле, и тем не менее элементы этих двух множеств часто требуется складывать. Дляэтого существует несколько способов. Одна из возможностей состоит в том, чтобы преобразовывать один из многочленов к типу другого путем раскрытия и переупорядочениятермов, так, чтобы у обоих многочленов оказалась одна и та же главная переменная.Можно навязать данным башнеподобную структуру путем упорядочения переменных,и, таким образом, всегда преобразовывать любой многочлен к «канонической форме»,где переменная с наибольшим приоритетом всегда доминирует, а переменные с меньшим оказываются зарыты в коэффициенты. Такая стратегия работает довольно хорошо,только преобразование может без особой необходимости «раздуть» многочлен, так чтоего станет неудобно читать и, возможно, менее эффективно обрабатывать.
Для этойобласти структура башни определенно не является естественной, как и для любой другой области, где пользователь может изобретать новые типы динамически, используястарые в различных комбинирующих формах, таких как тригонометрические функции,последовательности степеней или интегралы.Не должно вызывать удивления то, что управление приведением типов представляетсерьезную проблему при разработке крупных систем алгебраических манипуляций. Существенная часть сложности таких систем связана с отношениями между различнымитипами.
В сущности, можно честно признать, что мы до сих пор не до конца понимаемприведение типов. Мы даже не до конца осознаем понятие типа данных. Однако то, чтомы знаем, дает нам солидные принципы структурирования и модуляризации, которыепомогают в разработке больших систем.Упражнение 2.92.Использовав упорядочение переменных, расширьте пакет работы с многочленами так, чтобы сложение и умножение многочленов работало для многочленов с несколькими переменными. (Это непростая задача!)2.5.
Системы с обобщенными операциями207Расширенное упражнение: рациональные функцииМожно расширить обобщенную арифметическую систему и включить в нее рациональные функции (rational functions). Это «дроби», в которых числитель и знаменательявляются многочленами, напримерx+1x3 + 1Система должна уметь складывать, вычитать. умножать и делить рациональные функции, а также осуществлять вычисления вродеxx3 + 2x2 + 3x + 1x+1+=x3 + 1 x2 − 1x4 + x3 − x − 1(здесь сумма упрощена при помощи сокращения общих множителей. Обычное «перекрестное умножение» дало бы многочлен четвертой степени в числителе и пятой в знаменателе.)Если мы изменим пакет арифметики рациональных чисел так, чтобы он использовалобобщенные операции, то он будет делать то, что нам требуется, за исключением задачиприведения к наименьшему знаменателю.Упражнение 2.93.Модифицируйте пакет арифметики рациональных чисел, заставив его пользоваться обобщеннымиоперациями, но при этом измените make-rat, чтобы она не пыталась сокращать дроби.
Проверьтесистему, применив make-rational к двум многочленам, и получив рациональную функцию(define p1 (make-polynomial ’x ’((2 1)(0 1))))(define p2 (make-polynomial ’x ’((3 1)(0 1))))(define rf (make-rational p2 p1))Сложите теперь rf саму с собой, используя add. Вы увидите, что процедура сложения не приводитдроби к наименьшему знаменателю.Приводить дроби многочленов к наименьшему знаменателю мы можем, используяту же самую идею, которой мы воспользовались для целых чисел: изменить makerat, чтобы она делила и числитель, и знаменатель на их наибольший общий делитель.Понятие «наибольшего общего делителя» имеет смысл для многочленов.
Более того,вычислять НОД для многочленов можно с помощью, в сущности, того же алгоритмаЕвклида, который работает на целых числах60 . Вот целочисленная версия:(define (gcd a b)(if (= b 0)a(gcd b (remainder a b))))60 То, что алгоритм Евклида работает для многочленов, в алгебре формализуется утверждением, что многочлены образуют структуру, называемую Евклидовым кольцом (Euclidean ring).
Евклидово кольцо — этоструктура, на которой определены сложение, вычитание и коммутативное умножение, а также некоторыйспособ сопоставить каждому элементу кольца x «меру» — неотрицательное целое число m(x), обладающуюследующими свойствами: m(xy) ≥ m(x) для любых ненулевых x и y, а также для любых x и y существует q,такое, что y = qx + r и либо r = 0, либо m(r) < m(x). С абстрактной точки зрения, это все, что нужно, чтобыдоказать, что алгоритм Евклида работает.
В случае целых чисел, мера m каждого числа есть его модуль. Дляструктуры многочленов мерой служит степень многочлена.208Глава 2. Построение абстракций с помощью данныхВзяв ее за основу, мы можем проделать очевидные изменения и определить операциюизвлечения НОД, которая работает на списках термов:(define (gcd-terms a b)(if (empty-termlist? b)a(gcd-terms b (remainder-terms a b))))где remainder-terms извлекает компоненту списка, соответствующую остатку, изсписка, который возвращает операция деления списков термов divterms, реализованная в упражнении 2.91.Упражнение 2.94.Используя div-terms, напишите процедуру remainder-terms, и с ее помощью определитеgcd-terms, как показано выше.
Напишите теперь процедуру gcd-polys, которая вычисляетНОД двух многочленов. (Процедура должна сообщать об ошибке, если входные объекты являютсямногочленами от разных переменных.) Установите в систему обобщенную операцию greatestcommon-divisor, которая для многочленов сводится к gcd-poly, а для обыкновенных чисел кобыкновенному gcd. В качестве проверки, попробуйте ввести(define p1 (make-polynomial ’x ’((4 1) (3 -1) (2 -2) (1 2))))(define p2 (make-polynomial ’x ’((3 1) (1 -1))))(greatest-common-divisor p1 p2)и проверьте результат вручную.Упражнение 2.95.Пусть P1 , P2 и P3 – многочленыP1 : x2 − 2x + 1P2 : 11x2 + 1P3 : 13x + 5Теперь пусть Q1 будет произведение P1 и P2 , а Q2 произведение P1 и P3 . При помощи greatestcommon-divisor (упражнение 2.94) вычислите НОД Q1 и Q2 .
Обратите внимание, что ответ несовпадает с P1 . Этот пример вводит в вычисление операции с нецелыми числами, и это создаетсложности для алгоритма вычисления НОД61 . Чтобы понять, что здесь происходит, попробуйтевключить трассировку в gcd-terms при вычислении НОД либо проведите деление вручную.Проблему, которую демонстрирует упражнение 2.95, можно решить, если мы используем следующий вариант алгоритма вычисления НОД (который работает только длямногочленов с целыми коэффициентами). Прежде, чем проводить деление многочленовпри вычислении НОД, мы умножаем делимое на целую константу, которая выбираетсятак, чтобы в процессе деления не возникло никаких дробей. Результат вычисления будетотличаться от настоящего НОД на целую константу, но при приведении рациональныхфункций к наименьшему знаменателю это несущественно; будет проведено деление ичислителя, и знаменателя на НОД, так что константный множитель сократится.61 В системах вроде MIT Scheme получится многочлен, который на самом деле является делителем Q и Q ,12но с рациональными коэффициентами.
Во многих других реализациях Scheme, где при делении целых чиселмогут получаться десятичные числа ограниченной точности, может оказаться, что мы не получим правильногоделителя.2.5. Системы с обобщенными операциями209Выражаясь более точно, если P и Q — многочлены, определим O1 как порядок P(то есть порядок его старшего терма), а O2 как порядок Q. Пусть c будет коэффициентстаршего терма Q. В таком случае, можно показать, что если мы домножим P на множитель целости (integerizing factor) c1+O1 −O2 , то получившийся многочлен можно будетподелить на Q алгоритмом div-terms, получив результат, в котором не будет никакихдробей. Операция домножения делимого на такую константу, а затем деления, иногданазывается псевдоделением (pseudodivision) P на Q.
Остаток такого деления называетсяпсевдоостатком (pseudoremainder).Упражнение 2.96.а. Напишите процедуру pseudoremainder-terms, которая работает в точности как remainderterms, но только прежде, чем позвать div-terms, домножает делимое на множитель целости,описанный выше. Модифицируйте gcd-terms так, чтобы она использовала pseudoremainderterms, и убедитесь, что теперь в примере из упражнения 2.95 greatest-common-divisorвыдает ответ с целыми коэффициентами.б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
