Рис. 2.8: Решение задачи о восьми ферзях.

(define (remove item sequence)

(filter (lambda (x) (not (= x item))) sequence))

Упражнение 2.40.

Определите процедуру unique-pairs, которая, получая целое число n, порождает последовательность пар (i, j), таких, что 1 < j < i < n. С помощью unique-pairs упростите данное выше определение prime-sum-pairs.

Упражнение 2.41.

Напишите процедуру, которая находит все такие упорядоченные тройки различных положительных целых чисел i, j и k, меньших или равных данному целому числу n, сумма которых равна данному числу s.

Упражнение 2.42.

В «задаче о восьми ферзях» спрашивается, как расставить на шахматной доске восемь ферзей так, чтобы ни один из них не бил другого (то есть никакие два ферзя не должны находиться на одной вертикали, горизонтали или диагонали). Одно из возможных решений показано на рисунке 2.8. Один из способов решать эту задачу состоит в том, чтобы идти поперек доски, устанавливая по ферзю в каждой вертикали. После того, как k - 1 ферзя мы уже разместили, нужно разместить k-го в таком месте, где он не бьет ни одного из тех, которые уже находятся на доске. Этот подход можно сформулировать рекурсивно: предположим, что мы уже породили последовательность из всех возможных способов разместить k - 1 ферзей на первых k - 1 вертикалях доски. Для каждого из этих способов мы порождаем расширенный набор позиций, добавляя ферзя на каждую горизонталь k-й вертикали. Затем эти позиции нужно отфильтровать, оставляя только те, где ферзь на k-й вертикали не бьется ни одним из остальных. Продолжая этот процесс, мы породим не просто одно решение, а все решения этой задачи.

Это решение мы реализуем в процедуре queens, которая возвращает последовательность решений задачи размещения п ферзей на доске n х п. В процедуре queens есть внутренняя процедура queen-cols, которая возвращает последовательность всех способов разместить ферзей на первых k вертикалях доски.

(define (queens board-size) (define (queen-cols k) (if (= k 0)

(list empty-board)

(filter

(lambda (positions) (safe? k positions)) (flatmap (lambda (rest-of-queens) (map (lambda (new-row)

(adjoin-position new-row k rest-of-queens)) (enumerate-interval 1 board-size))) (queen-cols (- k 1)))))) (queen-cols board-size))

В этой процедуре rest-of-queens есть способ размещения k - 1 ферзя на первых k - 1 вертикалях, а new-row - это горизонталь, на которую предлагается поместить ферзя с k-й вертикали. Завершите эту программу, реализовав представление множеств позиций ферзей на доске, включая процедуру adjoin-position, которая добавляет нового ферзя на определенных горизонтали и вертикали к заданному множеству позиций, и empty-board, которая представляет пустое множество позиций. Еще нужно написать процедуру safe?, которая для множества позиций определяет, находится ли ферзь с k-й вертикали в безопасности от остальных. (Заметим, что нам требуется проверять только то, находится ли в безопасности новый ферзь - для остальных ферзей безопасность друг от друга уже гарантирована.)

Упражнение 2.43.

У Хьюго Дума ужасные трудности при решении упражнения 2.42. Его процедура queens вроде бы работает, но невероятно медленно. (Хьюго ни разу не удается дождаться, пока она решит хотя бы задачу 6 х 6.) Когда Хьюго просит о помощи Еву Лу Атор, она указывает, что он поменял местами порядок вложенных отображений в вызове процедуры flatmap, записав его в виде

(flatmap

(lambda (new-row)

(map (lambda (rest-of-queens)

(adjoin-position new-row k rest-of-queens)) (queen-cols (- k 1)))) (enumerate-interval 1 board-size))

Объясните, почему из-за такой перестановки программа работает медленно. Оцените, насколько долго программа Хьюго будет решать задачу с восемью ферзями, если предположить, что программа, приведенная в упражнении 2.42, решает ее за время T.

2.2.4 Пример: язык описания изображений

В этой главе мы представляем простой язык для рисования картинок, иллюстрирующий силу абстракции данных и свойства замыкания; кроме того, он существенным образом опирается на процедуры высших порядков. Язык этот спроектирован так, чтобы легко было работать с узорами вроде тех, которые

Рис. 2.9: Узоры, порождаемые языком описания изображений.

показаны на рисунке 2.9, составленными из элементов, которые повторяются в разных положениях и меняют размер.22 В этом языке комбинируемые объекты данных представляются не как списковая структура, а как процедуры. Точно так же, как cons, которая обладает свойством замыкания, позволила нам строить списковые структуры произвольной сложности, операции этого языка, также обладающие свойством замыкания, позволяют нам строить сколь угодно сложные узоры.

Язык описания изображений

Когда в разделе 1.1 мы начинали изучать программирование, мы подчеркивали важность описания языка через рассмотрение его примитивов, методов комбинирования и методов абстракции. Мы будем следовать этой схеме и здесь.

Одно из элегантных свойств языка описания изображений состоит в том, что в нем есть только один тип элементов, называемый рисовалкой (painter). Рисовалка рисует изображение с необходимым смещением и масштабом, чтобы попасть в указанную рамку в форме параллелограмма. Например, существует элементарная рисовалка wave, которая порождает грубую картинку из линий, как показано на рисунке 2.10. Форма изображения зависит от рамки - все четыре изображения на рисунке 2.10 порождены одной и той же рисовалкой wave, но по отношению к четырем различным рамкам. Рисовалки могут быть и более изощренными: элементарная рисовалка по имени rogers рисует портрет основателя MIT Уильяма Бартона Роджерса, как показано на рисунке 2.11.23

22Этот язык описания картинок основан на языке, который создал Питер Хендерсон для построения изображений, подобных гравюре М. К. Эшера «Предел квадрата» (см. Henderson 1982). На гравюре изображен повторяющийся с уменьшением элемент, подобно картинкам, получающимся при помощи процедуры square-limit из этого раздела.

23Уильям Бартон Роджерс (1804-1882) был основателем и первым президентом MIT. Будучи геологом и способным педагогом, он преподавал в Колледже Вильгельма и Марии, а также в университете штата Виргиния. В 1859 году он переехал в Бостон, где у него было больше времени для исследований, разработал план создания «политехнического института» и служил первым Инспектором штата Массачусетс по газовым счетчикам.

Когда в 1861 году был основан MIT, Роджерс был избран его первым президентом. Роджерс исповедовал идеал «полезного обучения», отличного от университетского образования его времени с чрезмерным вниманием к классике, которое, как он писал, «стояло на пути более широкого,