Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 48
Текст из файла (страница 48)
Кроме того, мыпредположим, что имеется предикат empty-termlist?, который говорит, пуст ли данный список, селектор first-term, который получает из списка термов тот, у которогонаибольший порядок, и селектор rest-terms, который возвращает все термы, крометого, у которого наибольший порядок. Мы предполагаем, что для работы с термами унас есть конструктор make-term, строящий терм с указанными порядком и коэффициентом, и селекторы order и coeff, которые, соответственно, возвращают порядоки коэффициент терма. Эти операции позволяют нам рассматривать и термы, и их списки как абстракции данных, о конкретной реализации которых мы можем позаботитьсяотдельно.Вот процедура, которая строит список термов для суммы двух многочленов56 :(define (add-terms L1 L2)(cond ((empty-termlist? L1) L2)56 Эта операция очень похожа на процедуру объединения множеств union-set, которую мы разработали вупражнении 2.62.
На самом деле, если мы будем рассматривать многочлены как множества, упорядоченные постепени переменной, то программа, которая порождает список термов для суммы, окажется почти идентичнаunion-set.202Глава 2. Построение абстракций с помощью данных((empty-termlist? L2) L1)(else(let ((t1 (first-term L1)) (t2 (first-term L2)))(cond ((> (order t1) (order t2))(adjoin-termt1 (add-terms (rest-terms L1) L2)))((< (order t1) (order t2))(adjoin-termt2 (add-terms L1 (rest-terms L2))))(else(adjoin-term(make-term (order t1)(add (coeff t1) (coeff t2)))(add-terms (rest-terms L1)(rest-terms L2)))))))))Самая важная деталь, которую здесь надо заметить, — это что для сложения коэффициентов комбинируемых термов мы использовали обобщенную процедуру add. Это влечетглубокие последствия, как мы увидим ниже.Чтобы перемножить два списка термов, мы умножаем каждый терм из первого спискана все термы второго, используя в цикле mul-term-by-allterms, которая умножает указанный терм на все термы указанного списка.
Получившиеся списки термов (поодному на каждый терм в первом списке) накапливаются и образуют сумму. Перемножение двух термов дает терм, порядок которого равен сумме порядков множителей, акоэффициент равен произведению коэффициентов множителей:(define (mul-terms L1 L2)(if (empty-termlist? L1)(the-empty-termlist)(add-terms (mul-term-by-all-terms (first-term L1) L2)(mul-terms (rest-terms L1) L2))))(define (mul-term-by-all-terms t1 L)(if (empty-termlist? L)(the-empty-termlist)(let ((t2 (first-term L)))(adjoin-term(make-term (+ (order t1) (order t2))(mul (coeff t1) (coeff t2)))(mul-term-by-all-terms t1 (rest-terms L))))))Вот и все, что нам требуется для сложения и умножения многочленов. Обратитевнимание, что, поскольку мы работаем с термами при помощи обобщенных процедурadd и mul, наш пакет работы с многочленами автоматически оказывается в состоянииобрабатывать любой тип коэффициента, о котором знает обобщенный арифметическийпакет.
Если мы подключим механизм приведения типов, подобный тому, который обсуждался в разделе 2.5.2, то мы автоматически окажемся способны производить операциинад многочленами с коэффициентами различных типов, например2[3x2 + (2 + 3i)x + 7] · [x4 + x2 + (5 + 3i)]32.5. Системы с обобщенными операциями203Поскольку мы установили процедуры сложения и умножения многочленов add-polyи mul-poly в обобщенной арифметической системе в качестве операций add и mulдля типа polynomial, наша система оказывается автоматически способна производитьоперации над многочленами вроде[(y + 1)x2 + (y 2 + 1)x + (y − 1)] · [(y − 2)x + (y 3 + 7)]Причина этого в том, что, когда система пытается скомбинировать коэффициенты, онадиспетчирует через add и mul.
Поскольку коэффициенты сами по себе являются многочленами (по y), они будут скомбинированы при помощи add-poly и mul-poly. Врезультате получается своего рода «рекурсия, управляемая данными», где, например,вызов mul-poly приводит к рекурсивным вызовам mul-poly для того, чтобы скомбинировать коэффициенты. Если бы коэффициенты коэффициентов сами по себе были бымногочленами (это может потребоваться, если надо представить многочлены от трех переменных), программирование, управляемое данными, позаботится о том, чтобы системапрошла еще через один уровень рекурсивных вызовов, и так далее, на столько уровнейструктуры, сколько требуют данные57 .Представление списков термовНаконец, мы сталкиваемся с задачей реализовать хорошее представление для списков термов. Список термов, в сущности, есть множество коэффициентов, проиндексированное порядком терма.
Следовательно, любой из методов представления множеств,описанных в 2.3.3, годится для этой задачи. С другой стороны, наши процедуры addterms и mul-terms всегда обрабатывают списки термов последовательно от наибольшего порядка к наименьшему, так что мы будем использовать некоторую разновидностьупорядоченного представления.Как нам устроить структуру данных, которая представляет список термов? Одно изсоображений — «плотность» многочленов, с которыми мы будем работать. Многочленназывается плотным (dense), если в термах с большинством порядков у него ненулевыекоэффициенты.
Если же в нем много нулевых коэффициентов, он называется разреженным (sparse). Например,A : x5 + 2x4 + 3x2 − 2x − 5плотный многочлен, аB : x100 + 2x2 + 1разреженный.Списки термов плотных многочленов эффективнее всего представлять в виде списковкоэффициентов. Например, A в приведенном примере удобно представляется в виде (157 Чтобы все это работало совершенно гладко, потребуется добавить в нашу систему обобщенной арифметикивозможность привести «число» к типу многочлена, рассматривая его как многочлен степени ноль, коэффициентом которого является данное число.
Это нужно, если мы хотим осуществлять операции вроде[x2 + (y + 1)x + 5] + [x2 + 2x + 1]где требуется сложить коэффициент y + 1 с коэффициентом 2.204Глава 2. Построение абстракций с помощью данных2 0 3 -2 -5). Порядок терма в таком представлении есть длина списка, начинающегося с этого коэффициента, уменьшенная на 158 . Для разреженного многочлена вродеB такое представление будет ужасным: получится громадный список нулей, в которомизредка попадаются одинокие ненулевые термы. Более разумно представление разреженного многочлена в виде списка ненулевых термов, где каждый терм есть список, содержащий порядок терма и коэффициент при этом порядке.
При такой схеме многочлен Bэффективно представляется в виде ((100 1) (2 2) (0 1)). Поскольку большинствоопераций над многочленами применяется к разреженным многочленам, мы используемэто представление. Мы предполагаем, что список термов представляется в виде списка,элементами которого являются термы, упорядоченные от бо́льшего порядка к меньшему.После того, как решение принято, реализация селекторов и конструкторов для термов исписков термов не представляет трудностей59 :(define (adjoin-term term term-list)(if (=zero? (coeff term))term-list(cons term term-list)))(define(define(define(define(the-empty-termlist) ’())(first-term term-list) (car term-list))(rest-terms term-list) (cdr term-list))(empty-termlist? term-list) (null? term-list))(define (make-term order coeff) (list order coeff))(define (order term) (car term))(define (coeff term) (cadr term))где =zero? работает так, как определяется в упражнении 2.80 (см.
также ниже упражнение 2.87).Пользователи многочленного пакета будут создавать (помеченные) многочлены припомощи процедуры:(define (make-polynomial var terms)((get ’make ’polynomial) var terms))Упражнение 2.87.Установите =zero? для многочленов в обобщенный арифметический пакет. Это позволит adjointerm работать с многочленами, чьи коэффициенты сами по себе многочлены.58 В этих примерах многочленов мы предполагаем, что реализовали обобщенную арифметическую системупри помощи механизма типов, предложенного в упражнении 2.78. Таким образом, коэффициенты, которыеявляются обыкновенными числами, будут представлены самими числами, а не парами с первым элементом —символом scheme-number.59 Хотя мы предполагаем, что списки термов упорядочены, мы реализовали adjoin-term путем простогоcons к существующему списку термов.
Нам это может сойти с рук, пока мы гарантируем, что процедуры(вроде add-terms), которые используют adjoin-term, всегда вызывают ее с термом бо́льшего порядка, чемуже есть в списке. Если бы нам не хотелось давать такую гарантию, мы могли бы реализовать adjoin-termподобно конструктору adjoin-set для представления множеств в виде упорядоченных списков (упражнение 2.61).2.5. Системы с обобщенными операциями205Упражнение 2.88.Расширьте систему многочленов так, чтобы она включала вычитание многочленов. (Подсказка:может оказаться полезным определить обобщенную операцию смены знака.)Упражнение 2.89.Определите процедуры, которые реализуют представление в виде списка термов, описанное вышекак подходящее для плотных многочленов.Упражнение 2.90.Допустим, что мы хотим реализовать систему многочленов, которая эффективна как для плотных,так и для разреженных многочленов.
Один из способов это сделать заключается в том, чтобы разрешить в системе оба типа представления. Ситуация аналогична примеру с комплексными числамииз раздела 2.4, где мы позволили сосуществовать декартову и полярному представлению. Чтобыдобиться этого, нам придется различать виды списков термов и сделать операции над спискамитермов обобщенными. Перепроектируйте систему с многочленами так, чтобы это обобщение былореализовано.
Это потребует большого труда, а не только локальных изменений.Упражнение 2.91.Многочлены с одной переменной можно делить друг на друга, получая частное и остаток. Наx5 − 1= x3 + x, остаток x − 1.пример, 2x −1Деление можно производить в столбик. А именно, разделим старший член делимого на старший член делителя. В результате получится первый терм частного. Затем умножим результат наделитель, вычтем получившийся многочлен из делимого и, рекурсивно деля разность на делитель,получим оставшуюся часть частного.
Останавливаемся, когда порядок делителя превысит порядок делимого, и объявляем остатком то, что тогда будет называться делимым. Кроме того, есликогда-нибудь делимое окажется нулем, возвращаем ноль в качестве и частного, и остатка.Процедуру div-poly можно разработать, следуя образцу add-poly и mul-poly. Процедурапроверяет, одна ли и та же у многочленов переменная. Если это так, div-poly откусываетпеременную и передает задачу в div-terms, которая производит операцию деления над спискамитермов. Наконец, div-poly прикрепляет переменную к результату, который выдает div-terms.Удобно сделать так, чтобы div-terms выдавала и частное, и остаток при делении.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
