Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 30
Текст из файла (страница 30)
Допустим, нам нужно перечислить все перестановки множестваS, то есть все способы упорядочить это множество. Например, перестановки множества{1, 2, 3} — это {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2} и {3, 2, 1}. Вот план того, какможно породить все перестановки S: Для каждого элемента x из S, нужно рекурсивнопородить все множество перестановок S − x20 , затем добавить x к началу каждой из них.Для каждого x из S это дает множество всех перестановок S, которые начинаются с x.Комбинация всех последовательностей для всех x дает нам все перестановки S 21 :(define (permutations s)(if (null? s)(list nil)20 Множество; пустое множество?; последовательность,; содержащая пустое множествоS − x есть множество, состоящее из всех элементов S, кроме x.с запятой в коде на Scheme начинают комментарии (comments).
Весь текст, начиная от точки с запятой и заканчивая концом строки, интерпретатор игнорирует. В этой книге мы мало используем комментарии;мы стараемся, чтобы программы документировали себя сами при помощи описательных имен переменных.21 ТочкиГлава 2. Построение абстракций с помощью данных130(flatmap (lambda (x)(map (lambda (p) (cons x p))(permutations (remove x s))))s)))Заметим, что такая стратегия сводит задачу порождения перестановок S к задаче порождения перестановок для множества, которое меньше, чем S. В граничном случае мыдобираемся до пустого списка, который представляет множество, не содержащее элементов. Для этого множества мы порождаем (list nil), которое является последовательностью из одного члена, а именно множества без элементов.
Процедура remove,которую мы используем внутри permutations, возвращает все элементы исходной последовательности, за исключением данного. Ее можно выразить как простой фильтр:(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 ферзей на доске n × n. В процедуре queens есть внутренняя процедура queen-cols, которая возвращает последовательность всех способов разместить ферзей напервых k вертикалях доски.(define (queens board-size)(define (queen-cols k)(if (= k 0)2.2. Иерархические данные и свойство замыкания131Рис. 2.8.
Решение задачи о восьми ферзях.(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 вродебы работает, но невероятно медленно. (Хьюго ни разу не удается дождаться, пока она решит хотя132Глава 2. Построение абстракций с помощью данныхРис. 2.9. Узоры, порождаемые языком описания изображений.бы задачу 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, составленными из элементов, которые повторяются в разных положениях и меняют размер22 . Вэтом языке комбинируемые объекты данных представляются не как списковая структура, а как процедуры. Точно так же, как cons, которая обладает свойством замыкания,позволила нам строить списковые структуры произвольной сложности, операции этогоязыка, также обладающие свойством замыкания, позволяют нам строить сколь угодносложные узоры.22 Этот язык описания картинок основан на языке, который создал Питер Хендерсон для построения изображений, подобных гравюре М.
К. Эшера «Предел квадрата» (см. Henderson 1982). На гравюре изображенповторяющийся с уменьшением элемент, подобно картинкам, получающимся при помощи процедуры squarelimit из этого раздела.2.2. Иерархические данные и свойство замыкания133Язык описания изображенийКогда в разделе 1.1 мы начинали изучать программирование, мы подчеркивали важность описания языка через рассмотрение его примитивов, методов комбинирования иметодов абстракции. Мы будем следовать этой схеме и здесь.Одно из элегантных свойств языка описания изображений состоит в том, что в неместь только один тип элементов, называемый рисовалкой (painter).
Рисовалка рисуетизображение с необходимым смещением и масштабом, чтобы попасть в указанную рамкув форме параллелограмма. Например, существует элементарная рисовалка wave, котораяпорождает грубую картинку из линий, как показано на рисунке 2.10. Форма изображениязависит от рамки — все четыре изображения на рисунке 2.10 порождены одной и тойже рисовалкой wave, но по отношению к четырем различным рамкам.
Рисовалки могутбыть и более изощренными: элементарная рисовалка по имени rogers рисует портретоснователя MIT Уильяма Бартона Роджерса, как показано на рисунке 2.1123 . Четыреизображения на рисунке 2.11 нарисованы относительно тех же рамок, что и картинкиwave на рисунке 2.10.При комбинировании изображений мы используем различные операции, которыестроят новые рисовалки из рисовалок, полученных в качестве аргументов. Например,операция beside получает две рисовалки и порождает новую составную рисовалку, ко23 Уильям Бартон Роджерс (1804-1882) был основателем и первым президентом MIT.
Будучи геологом и способным педагогом, он преподавал в Колледже Вильгельма и Марии, а также в университете штата Виргиния. В1859 году он переехал в Бостон, где у него было больше времени для исследований, разработал план создания«политехнического института» и служил первым Инспектором штата Массачусетс по газовым счетчикам.Когда в 1861 году был основан MIT, Роджерс был избран его первым президентом. Роджерс исповедовалидеал «полезного обучения», отличного от университетского образования его времени с чрезмерным вниманиемк классике, которое, как он писал, «стояло на пути более широкого, высокого и практического обучения ипреподавания в естественных и общественных науках».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
