Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 29
Текст из файла (страница 29)
Мы вычисляем многочленan xn + an−1 xn−1 + . . . + a1 x + a0по известному алгоритму, называемому схема Горнера (Horner’s rule),формулу в виде(. . . (an x + an−1 )x + . . . + a1 )x + a0 )которое переписываетДругими словами, мы начинаем с an , умножаем его на x, и так далее, пока не достигнем a0 16 .Заполните пропуски в следующей заготовке так, чтобы получить процедуру, которая вычисляет15 Ричард Уотерс (Waters 1979) разработал программу, которая анализирует традиционные программы наФортране, представляя их в терминах отображений, фильтров и накоплений.
Он обнаружил, что 90 процентовкода в Пакете Научных Подпрограмм на Фортране хорошо укладывается в эту парадигму. Одна из причинуспеха Лиспа как языка программирования заключается в том, что списки дают стандартное средство представления упорядоченных множеств, с которыми можно работать при помощи процедур высших порядков.Язык программирования APL своей мощности и красоте во многом обязан подобному же выбору. В APLвсе данные выражаются как массивы, и существует универсальный и удобный набор общих операторов длявсевозможных действий над массивами.16 Согласно Кнуту (Knuth 1981), это правило было сформулировано У. Г.
Горнером в начале девятнадцатоговека, но на самом деле его использовал Ньютон более чем на сто лет раньше. По схеме Горнера многочленвычисляется с помощью меньшего количества сложений и умножений, чем при прямолинейном способе: вычислить сначала an xn , затем добавить an−1 xn−1 и так далее. На самом деле можно доказать, что любойалгоритм для вычисления произвольных многочленов будет использовать по крайней мере столько сложенийи умножений, сколько схема Горнера, и, таким образом, схема Горнера является оптимальным алгоритмом длявычисления многочленов.
Это было доказано (для числа сложений) А. М. Островским в статье 1954 года,126Глава 2. Построение абстракций с помощью данныхмногочлены по схеме Горнера. Предполагается, что коэффициенты многочлена представлены ввиде последовательности, от a0 до an .(define (horner-eval x coefficient-sequence)(accumulate (lambda (this-coeff higher-terms) h??i)0coefficient-sequence))Например, чтобы вычислить 1 + 3x + 5x3 + x5 в точке x = 2, нужно ввести(horner-eval 2 (list 1 3 0 5 0 1))Упражнение 2.35.Переопределите count-leaves из раздела 2.2.2 в виде накопления:(define (count-leaves t)(accumulate h??i h??i (map h??ih??i)))Упражнение 2.36.Процедура accumulate-n подобна accumulate, только свой третий аргумент она воспринимает как последовательность последовательностей, причем предполагается, что все они содержатодинаковое количество элементов.
Она применяет указанную процедуру накопления ко всем первым элементам последовательностей, вторым элементам последовательностей и так далее, и возвращает последовательность результатов. Например, если s есть последовательность, состоящаяиз четырех последовательностей, ((1 2 3) (4 5 6) (7 8 9) (10 11 12)), то значением(accumulate-n + 0 s) будет последовательность (22 26 30).
Заполните пробелы в следующем определении accumulate-n:(define (accumulate-n op init seqs)(if (null? (car seqs))nil(cons (accumulate op init h??i)(accumulate-n op init h??i))))Упражнение 2.37.Предположим, что мы представляем векторы v = (vi ) как последовательности чисел, а матрицыm = (mij ) как последовательности векторов (рядов матрицы). Например, матрица321 2 3 44 4 5 6 6 56 7 8 9представляется в виде последовательности ((1 2 3 4) (4 5 6 6) (6 7 8 9)). Имея такоепредставление, мы можем использовать операции над последовательностями, чтобы кратко выразить основные действия над матрицами и векторами. Эти операции (описанные в любой книге поматричной алгебре) следующие:которая по существу заложила основы современной науки об оптимальных алгоритмах.
Аналогичное утверждение для числа умножений доказал В. Я. Пан в 1966 году. Книга Бородина и Мунро (Borodin and Munro1975) дает обзор этих результатов, а также других достижений в области оптимальных алгоритмов.2.2. Иерархические данные и свойство замыканияСкалярное произведение (dot-product v w) возвращает сумму127Pi vi wi ;Произведениематрицы и вектора (matrix-*-vector m v) возвращает вектор t, где ti =Pj mij vi ;ПроизведениеP матриц (matrix-*-matrix m n) возвращаетpij =k mik nkjматрицуp,гдеТранспозиция (transpose m) возвращает матрицу n, где nij = mjiСкалярное произведение мы можем определить так17 :(define (dot-product v w)(accumulate + 0 (map * v w)))Заполните пропуски в следующих процедурах для вычисления остальных матричных операций.(Процедура accumulate-n описана в упражнении 2.36.)(define (matrix-*-vector m v)(map h??i m))(define (transpose mat)(accumulate-n h??i h??i mat))(define (matrix-*-matrix m n)(let ((cols (transpose n)))(map h??i m)))Упражнение 2.38.Процедура accumulate известна также как fold-right (правая свертка), поскольку она комбинирует первый элемент последовательности с результатом комбинирования всех элементов справаот него.
Существует также процедура fold-left (левая свертка), которая подобна fold-right,но комбинирует элементы в противоположном направлении:(define (fold-left op initial sequence)(define (iter result rest)(if (null? rest)result(iter (op result (car rest))(cdr rest))))(iter initial sequence))Каковы значения следующих выражений?(fold-right / 1 (list 1 2 3))(fold-left / 1 (list 1 2 3))(fold-right list nil (list 1 2 3))(fold-left list nil (list 1 2 3))17 Этоопределение использует расширенную версию map, описанную в сноске 12.Глава 2. Построение абстракций с помощью данных128Укажите свойство, которому должна удовлетворять op, чтобы для любой последовательностиfold-right и fold-left давали одинаковые результаты.Упражнение 2.39.Закончите следующие определения reverse (упражнение 2.18) в терминах процедур foldright и fold-left из упражнения 2.38.(define (reverse sequence)(fold-right (lambda (x y) h??i) nil sequence))(define (reverse sequence)(fold-left (lambda (x y) h??i) nil sequence))Вложенные отображенияРасширив парадигму последовательностей, мы можем включить в нее многие вычисления, которые обычно выражаются с помощью вложенных циклов18 .
Рассмотримследующую задачу: пусть дано положительное целое число n; найти все такие упорядоченные пары различных целых чисел i и j, где 1 ≤ j < i ≤ n, что i + j является простым.Например, если n равно 6, то искомые пары следующие:iji+j2133254 41 35 75 62 17 76511Естественный способ организации этого вычисления состоит в том, чтобы породить последовательность всех упорядоченных пар положительных чисел, меньших n, отфильтровать ее, выбирая те пары, где сумма чисел простая, и затем для каждой пары (i, j),которая прошла через фильтр, сгенерировать тройку (i, j, i + j).Вот способ породить последовательность пар: для каждого целого i ≤ n перечислить целые числа j < i, и для каждых таких i и j породить пару (i, j). В терминахопераций над последовательностями, мы производим отображение последовательности(enumerate-interval 1 n). Для каждого i из этой последовательности мы производим отображение последовательности (enumerate-interval 1 (- i 1)).
Длякаждого j в этой последовательности мы порождаем пару (list i j). Это дает нампоследовательность пар для каждого i. Скомбинировав последовательности для всехi (путем накопления через append), получаем необходимую нам последовательностьпар19 .(accumulate appendnil(map (lambda (i)(map (lambda (j) (list i j))(enumerate-interval 1 (- i 1))))(enumerate-interval 1 n)))18 Этот подход к вложенным отображениям нам показал Дэвид Тёрнер, чьи языки KRC и Миранда обладаютизящным формализмом для работы с такими конструкциями. Примеры из этого раздела (см.
также упражнение 2.42) адаптированы из Turner 1981. В разделе 3.5.3 мы увидим, как этот подход можно обобщить набесконечные последовательности.19 Здесь мы представляем пару в виде списка из двух элементов, а не в виде лисповской пары. Иначе говоря,«пара» (i, j) представляется как (list i j), а не как (cons i j).2.2. Иерархические данные и свойство замыкания129Комбинация из отображения и накопления через append в такого рода программахнастолько обычна, что мы ее выразим как отдельную процедуру:(define (flatmap proc seq)(accumulate append nil (map proc seq)))Теперь нужно отфильтровать эту последовательность пар, чтобы найти те из них, гдесумма является простым числом.
Предикат фильтра вызывается для каждой пары впоследовательности; его аргументом является пара и он должен обращаться к элементампары. Таким образом, предикат, который мы применяем к каждому элементу пары, таков:(define (prime-sum? pair)(prime? (+ (car pair) (cadr pair))))Наконец, нужно породить последовательность результатов, отобразив отфильтрованнуюпоследовательность пар при помощи следующей процедуры, которая создает тройку, состоящую из двух элементов пары и их суммы:(define (make-pair-sum pair)(list (car pair) (cadr pair) (+ (car pair) (cadr pair))))Сочетание всех этих шагов дает нам процедуру целиком:(define (prime-sum-pairs n)(map make-pair-sum(filter prime-sum?(flatmap(lambda (i)(map (lambda (j) (list i j))(enumerate-interval 1 (- i 1))))(enumerate-interval 1 n)))))Вложенные отображения полезны не только для таких последовательностей, которыеперечисляют интервалы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
