Блочная структура

В примере с вычислением квадратного корня использовалось несколько процедур, но все, кроме sqr - вспомогательные.

Недостатки:

§ Глобальная область имён ''засоряется'' именами вспомогательных функций

§ При копировании можно легко ''потерять'' какую-нибудь функцию

§ Связи между функциями не слишком очевидны

§ Связь между функциями приходится осуществлять с полным набором параметров

Существует альтернатива: блочная структура.

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

(define (sqr x) (define (average x y) (/ (+ x y) 2)) (define (good-enough? guess x) (< (abs (- (* guess guess) x)) 0.000000001)) (define (improve guess x) (average guess (/ x guess))) (define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))) (sqrt-iter 1.0 x))

Процедура вычисления факториала может быть представлена в следующем виде:

(define (factorial n) (define (iter product counter) (if (> counter n) product (iter (* counter product) (+ counter 1)))) (iter 1 1))

Форматирование даёт представление о строении тела процедуры: после заголовка factorialследует вложение тела вспомогательной функции iter, а потом следует её вызов с фактическими параметрами 1 и 1.

Аналогично можно реализовать и нахождение числа Фибоначчи:

(define (fib n) (define (fib-iter a b count) (if (= count 0) b (fib-iter (+ a b) a (- count 1)))) (fib-iter 1 0 n))

Вспомогательная функция fib-iter НЕ видна в глобальном пространстве имён и может определяться в любом количестве функций без конфликтов.

Блочная структура может содержать не одну вспомогательную функцию:

(define (fib n) (define (sum a b) (+ a b)) (define (dec a) (- a 1)) (define (fib-iter a b count) (if (= count 0) b (fib-iter (sum a b) a (dec count)))) (fib-iter 1 0 n))

Определения вспомогательных процедур располагаются последовательно.

Пример - шахматное число

Рассмотрим в качестве примера задачу нахождения шахматного числа

\textit{

На первую клетку шахматной доски помещается 1 зерно, на вторую - 2, на третью - 4 и т.д. Сколько зёрен поместится на стандартной шахматной доске 8х8?}

Решение задачи:

(define (chess-number)

(define (iter sum n)

(if (= n 64)

sum

(iter (+ sum (expt 2 n)) (+ n 1))))

(iter 0 0))

Ответ: 18 446 744 073 709 551 615

Пример - ханойские башни

Другая интересная задача связана с головоломкой под названием Ханойские башни

В одном из буддийских монастырей монахи уже тысячу лет занимаются перекладыванием колец. Они располагают тремя пирамидами, на которых надеты кольца разных размеров. В начальном состоянии 64 кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи должны переложить все кольца с первой пирамиды на вторую, выполняя единственное условие - кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света.

Графическое изображение стержней с кольцами (в начале задачи):

Очевидно, что при количестве колец решение элементарное
Решение при N>1

Нужно применить рекурсивно алгоритм, переложив кольцо с первой пирамиды на третью пирамиду. Затем сделать очевидный ход, переложив последнее самое большое кольцо с первой пирамиды на вторую. Затем снова применить рекурсию, переложив кольцо с третьей пирамиды на вторую пирамиду.

Количество операций равно

Реализация на Scheme:

(define (hanoi n first second third)

(if (= n 1)

(print-text first third)

(begin

(hanoi (- n 1) first third second)

(hanoi 1 first second third)

(hanoi (- n 1) second first third))))

(define (print-text first last)

(begin

(display (list first '-> last))

(newline)))

Результат работы программы для

1->3

1->2

3->2

1->3

2->1

2->3

1->3

30) Процедуры высших порядков

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

Процедуры высших порядков могут:

§ принимать другие процедуры в качестве параметров и вызывать их.

§ порождать другие процедуры и возвращать их.

Процедура как аргумент ничем не отличается от обычных данных.