Рекурсия и процессы, порождаемые процедурами

Реализуйте процедуру, вычисляющую n-ю степень аргумента, где n — неотрицательное целое.

Простой алгоритм, выполняющий n умножений в виде процедуры, порождающей

1. линейно рекурсивный процесс.
2. линейно итеративный процесс.

Эффективный алгоритм с логарифмической степенью роста также в двух вариантах.

Процедуры высшего порядка

Дана абстрактная процедура вычисления суммы (см. SICP [1], глава 1.3.1 «Процедуры в качестве аргументов»):

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

Обратите внимание, что в качестве аргументов term и next принимаются процедуры. Как работает sum? Покажите пример использования.

Упражнение 1.31a из SICP.

Процедура sum — всего лишь простейшая из обширного множества подобных абстракций, которые можно выразить через процедуры высших порядков. Напишите аналогичную процедуру под названием product, которая вычисляет произведение значений функции в точках на указанном интервале. Покажите, как с помощью этой процедуры определить процедуру вычисления факториала.

Упражнение 1.32 из SICP.

а. Покажите, что sum и product являются частными случаями еще более общего понятия, называемого накопление (accumulation), которое комбинирует множество термов с помощью некоторой общей функции накопления

(accumulate combiner null-value term a next b)

Процедура accumulate принимает в качестве аргументов те же описания термов и диапазона, что и sum с product, а еще процедуру combiner (двух аргументов), которая указывает, как нужно присоединить текущий терм к результату накопления предыдущих, и null-value, базовое значение, которое нужно использовать, когда термы закончатся. Напишите accumulate и покажите, как и sum, и product можно определить в виде простых вызовов accumulate.

Если Ваша процедура accumulate порождает рекурсивный процесс, перепишите ее так, чтобы она порождала итеративный. Если она порождает итеративный процесс, перепишите ее так, чтобы она порождала рекурсивный.

Процедуры как возвращаемые значения

Упражнение 1.42 из SICP.

Если f есть численная функция, а n — положительное целое число, то мы можем построить n-кратное применение f, которое определяется как функция, значение которой в точке x равно f(f(…(f(x))…)). Например, если f есть функция x↦x+1, то n-кратным применением f будет функция x↦x+n. Если f есть операция возведения в квадрат, то n-кратное применение f есть функция, которая возводит свой аргумент в 2n-ю степень. Напишите процедуру, которая принимает в качестве ввода процедуру, вычисляющую f, и положительное целое n, и возвращает процедуру, вычисляющую n-кратное применение f. Требуется, чтобы вашу процедуру можно было использовать в таких контекстах:

> ((repeated sqr 2) 5)
625

Подсказка: может оказаться удобно использовать compose.

Работа со списками

Реализуйте рекурсивную процедуру append, которая соединяет два списка:

> (append '(1 2 3) '(4 5 6))
'(1 2 3 4 5 6)

Доработайте append так, чтобы она работала для произвольного количества аргументов-списков:

> (append)
'()

> (append '(1 2 3))
'(1 2 3)

> (append '(1 2) '(3 4) '(5 6))
'(1 2 3 4 5 6)

Определите вариант append для двух и для произвольного числа списков с использованием функции свертки (foldl или foldr).

Задание 5

На основе упражнения 2.32 из SICP.

Множество можно представить как список его различных элементов, а множество его подмножеств как список списков. Например, если множество равно (1 2 3), то множество его подмножеств равно (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)). Разработайте процедуру, которая порождает множество подмножеств. Подсказка: рекурсивно определите множество подмножеств через множество подмножеств исходного множества без одного элемента. Используйте append и map.

Задание 6

В «задаче о восьми ферзях» спрашивается, как расставить на шахматной доске восемь ферзей так, чтобы ни один из них не бил другого (то есть никакие два ферзя не должны находиться на одной вертикали, горизонтали или диагонали). Один из способов решать эту задачу состоит в том, чтобы идти поперек доски, устанавливая по ферзю в каждой вертикали. После того, как 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)
        (list empty-board)
        (filter (λ (positions) (safe? k positions))
                (append-map
                 (λ (rest-of-queens)
                   (map (λ (new-row)
                          (adjoin-position new-row k rest-of-queens))
                        (range 1 (+ board-size 1))))
                 (queen-cols (- k 1))))))
  (queen-cols board-size))

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

Задание 7

Разработайте процедуру для построения графического представления способов размещения ферзей, получаемых в задании 6. Используйте библиотеку 2htdp/image.

Пример визуализации одного из возможных способов размещения для доски 8 × 8 с использованием набора изображений Planet Cute (2htdp/planetcute):

Задание 8

В задаче 6 количество способов размещения ферзей быстро растет с увеличением размера доски. Реализуйте вариант решения этой задачи с использованием потоков, так чтобы можно было получать нужное количество способов размещения, не вычисляя их все.