|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[64] Поскольку мы установили процедуры сложения и умножения многочленов add-poly и mul-poly в обобщенной арифметической системе в качестве операций add и mul для типа polynomial, наша система оказывается автоматически способна производить операции над многочленами вроде [(у + 1)x2 + (у2 + 1)x + (у - 1)] • [(у - 2)x + (у3 + 7)] Причина этого в том, что, когда система пытается скомбинировать коэффициенты, она диспетчирует через add и mul. Поскольку коэффициенты сами по себе являются многочленами (по у), они будут скомбинированы при помощи add-poly и mul-poly. В результате получается своего рода «рекурсия, управляемая данными», где, например, вызов mul-poly приводит к рекурсивным вызовам mul-poly для того, чтобы скомбинировать коэффициенты. Если бы коэффициенты коэффициентов сами по себе были бы многочленами (это может потребоваться, если надо представить многочлены от трех переменных), программирование, управляемое данными, позаботится о том, чтобы система прошла еще через один уровень рекурсивных вызовов, и так далее, на столько уровней структуры, сколько требуют данные.57 Представление списков термов Наконец, мы сталкиваемся с задачей реализовать хорошее представление для списков термов. Список термов, в сущности, есть множество коэффициентов, проиндексированное порядком терма. Следовательно, любой из методов представления множеств, описанных в 2.3.3, годится для этой задачи. С другой стороны, наши процедуры add-terms и mul-terms всегда обрабатывают списки термов последовательно от наибольшего порядка к наименьшему, так что мы будем использовать некоторую разновидность упорядоченного представления. Как нам устроить структуру данных, которая представляет список термов? Одно из соображений - «плотность» многочленов, с которыми мы будем работать. Многочлен называется плотным (dense), если в термах с большинством порядков у него ненулевые коэффициенты. Если же в нем много нулевых коэффициентов, он называется разреженным (sparse). Например, A : x5 + 2x4 + 3x2 - 2x - 5 плотный многочлен, а B : x100 + 2x2 + 1 разреженный. Списки термов плотных многочленов эффективнее всего представлять в виде списков коэффициентов. Например, A в приведенном примере удобно представляется в виде (1 2 0 3 -2 -5). Порядок терма в таком представлении 57Чтобы все это работало совершенно гладко, потребуется добавить в нашу систему обобщенной арифметики возможность привести «число» к типу многочлена, рассматривая его как многочлен степени ноль, коэффициентом которого является данное число. Это нужно, если мы хотим осуществлять операции вроде [x2 + (y + 1)x + 5] + [x2 + 2x + 1] где требуется сложить коэффициент y +1 с коэффициентом 2. есть длина списка, начинающегося с этого коэффициента, уменьшенная на 1.58 Для разреженного многочлена вроде 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(the-empty-termlist) ()) (define(first-term term-list) (carterm-list)) (define(rest-terms term-list) (cdrterm-list)) (define(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? для многочленов в обобщенный арифметический пакет. Это позволит adjoin-term работать с многочленами, чьи коэффициенты сами по себе многочлены. Упражнение 2.88. Расширьте систему многочленов так, чтобы она включала вычитание многочленов. (Подсказка: может оказаться полезным определить обобщенную операцию смены знака.) 58В этих примерах многочленов мы предполагаем, что реализовали обобщенную арифметическую систему при помощи механизма типов, предложенного в упражнении 2.78. Таким образом, коэффициенты, которые являются обыкновенными числами, будут представлены самими числами, а не парами с первым элементом - символом scheme-number. 59Хотя мы предполагаем, что списки термов упорядочены, мы реализовали adjoin-term путем простого cons к существующему списку термов. Нам это может сойти с рук, пока мы гарантируем, что процедуры (вроде add-terms), которые используют adjoin-term, всегда вызывают ее с термом большего порядка, чем уже есть в списке. Если бы нам не хотелось давать такую гарантию, мы могли бы реализовать adjoin-term подобно конструктору adjoin-set для представления множеств в виде упорядоченных списков (упражнение 2.61). Упражнение 2.89. Определите процедуры, которые реализуют представление в виде списка термов, описанное выше как подходящее для плотных многочленов. Упражнение 2.90. Допустим, что мы хотим реализовать систему многочленов, которая эффективна как для плотных, так и для разреженных многочленов. Один из способов это сделать заключается в том, чтобы разрешить в системе оба типа представления. Ситуация аналогична примеру с комплексными числами из раздела 2.4, где мы позволили сосуществовать декартову и полярному представлению. Чтобы добиться этого, нам придется различать виды списков термов и сделать операции над списками термов обобщенными. Перепроектируйте систему с многочленами так, чтобы это обобщение было реализовано. Это потребует большого труда, а не только локальных изменений. Упражнение 2.91. Многочлены с одной переменной можно делить друг на друга, получая частное и х5 - 1 остаток. Например, --= х3 + х, остаток х - 1. х2 - 1 Деление можно производить в столбик. А именно, разделим старший член делимого на старший член делителя. В результате получится первый терм частного. Затем умножим результат на делитель, вычтем получившийся многочлен из делимого и, рекурсивно деля разность на делитель, получим оставшуюся часть частного. Останавливаемся, когда порядок делителя превысит порядок делимого, и объявляем остатком то, что тогда будет называться делимым. Кроме того, если когда-нибудь делимое окажется нулем, возвращаем ноль в качестве и частного, и остатка. Процедуру div-poly можно разработать, следуя образцу add-poly и mul-poly. Процедура проверяет, одна ли и та же у многочленов переменная. Если это так, div-poly откусывает переменную и передает задачу в div-terms, которая производит операцию деления над списками термов. Наконец, div-poly прикрепляет переменную к результату, который выдает div-terms. Удобно сделать так, чтобы div-terms выдавала и частное, и остаток при делении. Она может брать в качестве аргументов два терма и выдавать список, состоящий из списка термов частного и списка термов остатка. Закончите следующее определение div-terms, вставив недостающие выражения. Используйте ее, чтобы реализовать div-poly, которая получает в виде аргументов два экземпляра poly, а выдает список из poly-частного и poly-остатка. (define (div-terms Ll L2) (if (empty-termlist? Ll) (list (the-empty-termlist) (the-empty-termlist)) (let ((tl (first-term Ll)) (t2 (first-term L2))) (if (> (order t2) (order tl)) (list (the-empty-termlist) Ll) (let ((new-c (div (coeff tl) (coeff t2))) (new-o (- (order tl) (order t2)))) (let ((rest-of-result (рекурсивно вычислить оставшуюся часть результата) )) (сформировать окончательный результат) )))))) |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||