SICP по-русски

У процедур right-split и up-split есть очень много общего. По сути, они отличаются лишь порядком вызова операций beside и below. Таким образом мы можем ввести обобщенную операцию generic-split, которая будет задавать схему работы, общую для right-split и up-split, и процедуру высшего порядка split, которая с помощью generic-split по заданным операциям (главной и вложенной) будет генерировать конкретную процедуру, реализующую определенный способ рекурсивного комбинирования рисовалок по этой обобщенной схеме.

Сказанное иллюстрирует приведенное ниже определение процедуры split:

(define (split main-operation sub-operation)
  (define (generic-split painter n)
    (if (= n 0)
        painter
        (let ((smaller (generic-split painter (- n 1))))
          (main-operation painter (sub-operation smaller smaller)))))
  generic-split)

Еще раз подчеркну, что split - это операция высшего порядка, принимающая на вход и дающая на выходе операции над рисовалками. Она принимает на вход две комбинирующие операции над рисовалками и возвращает также операцию над рисовалками.

Это дает возможность определять конкретные операции над рисовалкми таким образом:

(define right-split (split beside below))
(define up-split (split below beside))

Процедура up-split очень похожа на приводящуюся в книге right-split. Если right-split оставляет в левой части рамки старую рисовалку (ох и перевод!), а правую делит на две расположенные одна под другой части и вызывает себя для них рекурсивно, то up-split оставляет старую рисовалку в нижней половине рамки, а верхнюю делит на две части, расположенные рядом по горизонтали, и вновь вызывает себя рекурсивно.

Таким образом определение для процедуры up-split записывается таким образом:

(define (up-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (up-split painter (- n 1))))
        (below painter (beside smaller smaller)))))

Сохранена полная аналогия с определением right-split.

Если быть откровенным, мне не совсем очевидно, почему результат операции below по определению рисует изображение первого аргумента под изображением второго, а не над ним (что, на мой взгляд, было бы логичнее). Но это вопрос договоренностей, на котором нет смысла слишком сильно концентрироваться.

Переставив фрагменты программы, Хьюго внес рекурсивный вызов queen-cols внутрь итерации по номерам строк, то есть если ранее при решении задачи для доски NxN решение задачи для доски (N-1)x(N-1) вычислялось один раз, то теперь это происходит N раз. Таким образом здесь пахнет экспоненциальным ухудшением производительности.

Примем упрощенно, что обработка очередной позиции (добавление одного ферзя и проверка на безопасность) на каждом шаге отнимает одинаковое время P (на самом деле это не так, ведь время работы проверки на безопасность зависит от количества ферзей, но это не влияет особенно на результат, так как на каждом шаге число ферзей мало по сравнению с числом позиций). Тогда время T(N) решения задачи для доски NxN складывается из времени решения задачи для доски (N-1)x(N-1) и времени обработки каждой из позиций помноженного на количество позиций для обработки (количества решений L(N-1) для доски (N-1)x(N-1) помноженного на N).

Тогда для исходного решения получаем:

T(N) = P * N * L(N-1) + T(N-1), или, что то же

T(N) = P * N * (L(N-1) + L(N-2) + … + L(1)),

а для решения Хьюго:

T_h(N) = P * N * L(N-1) + N * T(N-1) или

T_h(N) = P * N * (L(N-1) + N * L(N-2) + … + NN-2 * L(1)).

Для задачи с 8 ферзями, то есть доски 8×8
Воспользуемся вычисленными в прошлом упражнении значениями L(N):

L(1)=L(2)=L(3)=0, L(4)=2, L(5)=10, L(6)=4, L(7)=40.

Тогда

T(8) = P * 8 * (L(7) + L(6) + … + L(1)) = P * 8 * 56 = 448*P,

T_h(8) = P * 8 * (L(7) + 8*L(6) + … +86*L(1)) = P * 8 * (40+32+640+1024) = 13888*P.

То есть T_h(8) = 31 * T(8), и программа Хьюго отработает в 31 раз медленнее для задачи с восемью ферзями. Причем разница в эффективности будет расти экспоненциально с ростом размерности задачи.

Меня по-прежнему не покидает чувство, что приведенное решение упражнения не идеально. Думаю, со временем я смогу его улучшить.

Задача о восьми ферзях - это классический пример проблемы, которая решается перебором вариантов. Задача сама по себе, как и задача о Ханойских башнях, весьма интересна, а ее решение показывает несколько важных алгоритмических приемов.

Каркас процедуры решения за нас уже определили заботливые авторы, нам же осталось только задать представление позиций на доске константой empty-board и процедурой adjoin-position, а также реализовать проверку безопасности позиции процедурой-предикатом safe?.

Я предлагаю хранить позиции как списки номеров горизонталей, в которых располагаются ферзи. Список позиций тогда задается списком таких списков. Пустая доска обозначается пустым списком (списком из нуля элементов, так как на доске расставлено 0 ферзей). Для удобства операций при описании позиции ферзи в списке будут перечисляться в обратном порядке (от последнего добавленного к первому). Можно также описать такое задание как движение не слева направо по вертикалям, а справа налево.

Для пояснения рассмотрим доску 4х4, где ферзи расставлены слева направо во второй, четвертой, первой и третьей горизонталях.

Эта позиция будет задаваться списком (3 1 4 2).

Итак, пустая доска задается пустым списком:

(define empty-board (list))

Для того, чтобы добавить к позиции еще одного ферзя, просто добавим номер горизонтали, на которой он расположен, в начало списка, обозначающего позицию:

(define (adjoin-position new-row k rest-of-queens)
  (cons new-row rest-of-queens))

Проверка позиции на безопасность заключается в том, чтобы пройти по всем ферзям с предпоследнего до первого и проверить безопасны ли они для последнего (по построению они гарантированно безопасны друг для друга). Эту задачу выполняет предикат queens-safe?. Проверка того, безопасен ли очередной ферзь для последнего выполняется предикатом queen-safe?, который проверяет два условия:

1. стоят ли эти ферзи на одной горизонтали (равенство горизонталей),
2. стоят ли эти ферзи на одной диагонали (равенство модуля разности между горизонталями и модулю разности между вертикалями).

Проверку того, стоят ли ферзи на одной вертикали делать не нужно, так как по построению все вертикали гарантированно различны.

Таким образом получаем следующее определение процедуры safe?:

(define (safe? k position)
  (define (queens-safe? queen-count rest-rows)
    (define (queen-safe? col row)
      (let ((last-col k) (last-row (car position)))
        (and (not (= last-row row))
             (not (= (abs (- last-row row))
                     (abs (- last-col col)))))))
    (cond ((null? rest-rows) true)
          ((queen-safe? queen-count (car rest-rows))
             (queens-safe? (- queen-count 1) (cdr rest-rows)))
          (else false)))
  (queens-safe? (- k 1) (cdr position)))

Собирая результат воедино, получим для доски 4х4 следующие две безопасные позиции:

> (queens 4)
((3 1 4 2) (2 4 1 3))

Для доски 5х5 существует 10 различных решений. Для доски 6х6 количество решений меньше, всего 4. Для доски 7х7 есть уже 40 решений. Для доски 8х8 ферзей можно расставить 92 способами. Доска 9х9 допускает 352 различных расстановки, а 10х10 - 724.

Одно из решений (первое, которое выдает наша программа) задачи о восьми ферзях (то есть для доски 8х8) изображено ниже:

Правда, интересная задачка?

Отвлечемся немного от решения упражнений (пятница, все же) и решим красивую задачку, которой в упражнениях к SICP нет (по крайней мере, пока не встретилось).

Задача о Ханойских башнях является классической алгоритмической задачей. Формулируется она следующим образом.

На одном из трех алмазных шпилей надето 64 круглых золотых диска. Диски имеют разные радиусы и расположены на шпиле в порядке убывания радиусов от основания к вершине. Требуется перенести диски с первого шпиля на второй, используя при необходимости и третий шпиль. При этом неукоснительно должны соблюдаться следующие правила:

1. за один раз можно перемещать только один диск;
2. больший диск нельзя располагать на меньшем диске;
3. снятый диск необходимо надеть на какой-либо шпиль перед тем, как будет снят другой диск.

Переносом дисков занимаются буддийские монахи и, по легенде, когда они закончат эту работу, наступит конец света (случится это, впрочем, не скоро).

Итак, составим для монахов план, в соответствии с которым им нужно осуществлять перенос дисков. План состоит из последовательности операций по переносу одного диска с одного шпиля на другой. Перенос задается начальным и конечным шпилями.

Обозначим шпили буквами a, b и c. Отметим, что для того, чтобы перенести n дисков со шпиля a на шпиль b, используя шпиль c как вспомогательный, нам достаточно выполнить следующие действия:

1. перенести n-1 диск со шпиля a на шпиль c, используя b как вспомогательный;
2. перенести единственный оставшийся на шпиле a самый большой диск на шпиль b;
3. перенести n-1 диск со шпиля c на шпиль b, используя a как вспомогательный.

Таким образом мы свели решение задачи для n дисков к решению двух задач для n-1 дисков, а значит можем применить древовидную рекурсию.

Обозначая перенос диска со шпиля a на шпиль b как список из двух элементов (a b) и формируя план переноса дисков как список таких двухэлементных списков, можем записать элегантное и простое решение программы на языке Scheme:

(define (hanoi n src dest inter)
  (if (= n 0)
      null
      (append (hanoi (- n 1) src inter dest)
              (list (list src dest))
              (hanoi (- n 1) inter dest src))))

Для того, чтобы получить план переноса 64 дисков, достаточно будет сделать вызов (hanoi 64 1 2 3), где 1,2 и 3 - это просто номера шпилей (вместо номеров можно задавать произвольные идентификаторы шпилей).

Сегодня выяснил, что создателем русского перевода SICP, который носит название “Структура и интерпретация компьютерных программ”, является Юрий Бронников, известный в интернете под ником gogabr.

Хочу выразить ему огромную признательность за очень хороший перевод. Это особенно ценно для такой фундаментальной книги, как творение Абельсона и Сассмана.

Определим сначала процедуру, генерирующую все наборы различных троек. Она строится аналогично процедуре, генерирующей все уникальные пары из прошлого упражнения (можно даже использовать unique-pairs в реализации, но я этого не буду делать:

(define (unique-triples n)
    (flatmap (lambda (i)
          (flatmap (lambda (j)
                (map (lambda (k) (list i j k))
                     (enumerate-interval 1 (- j 1))))
                   (enumerate-interval 1 (- i 1))))
             (enumerate-interval 1 n)))

Теперь применим к набору троек, построенному процедурой unique-triples, фильтр, проверяющий равенство суммы элементов тройки заданному числу s:

(define (triples-with-sum s n)
  (filter (lambda (t) (= (accumulate + 0 t) s))
          (unique-triples n)))

Процедура triples-with-sum является решением этого упражнения.

Это не единственное возможное решение. Как я уже писал выше, можно переиспользовать определенную ранее процедуру unique-pairs. Можно также не разбивать весь процесс на два этапа (генерацию троек и фильтрацию), а сразу строить тройки таким образом, чтобы их сумма была равна s.

Процедура unique-pairs определяется способом, описанным в тексте параграфа:

(define (unique-pairs n)
  (flatmap (lambda (i) (map (lambda (j) (list i j))
                            (enumerate-interval 1 (- i 1))))
           (enumerate-interval 1 (- n 1))))

Теперь процедуру prime-sum-pairs легко определить таким образом, чтобы она генерировала все уникальные пары, фильтровала их, оставляя только пары с простой суммой, а затем строила тройки (слагаемое, слагаемое, сумма) по этим парам:

(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum?
               (unique-pairs n))))

Вот и все.

Использование функциональных языков и, в частности, Scheme в обучении будущих программистов весьма популярно в вузах Европы и Америки. К сожалению, у нас эта практика, так же как и использование учебными заведениями операционных систем семейства Unix, пока не прижилась.

Посмотрите на список вузов, колледжей и средних школ, использующих Scheme в процессе обучения.

Обратите внимание на то, сколько вузов и школ используют Scheme во вводных курсах, то есть как первый язык программирования, с которым знакомятся учащиеся. Мне кажется, эти значения говорят о многом.

Определить reverse через свертки можно таким образом:

(define (reverse sequence)
  (fold-right (lambda (x y) (append y (list x))) nil sequence))

(define (reverse sequence)
  (fold-left (lambda (x y) (cons y x)) nil sequence))

Определения получаются путем анализа процесса вычислений сверток.

Хочу отметить, что использование для реверсирования последовательности левой свертки более видится более эффективным, поскольку задействованные операции более простые, а процесс итеративен.