Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Янин В.Л. "Новгородские акты XII-XV Хронологический комментарий" (История)

Майринк Г. "Белый доминиканец " (Художественная литература)

Хусаинов А. "Голоса вещей. Альманах том 2" (Художественная литература)

Петров Г.И. "Отлучение Льва Толстого " (Художественная литература)

Хусаинов А. "Голоса вещей. Альманах том 1 " (Художественная литература)
Реклама

Структура и интерпритация компьютерных программ - Абельсон Х.

Абельсон Х. Структура и интерпритация компьютерных программ — М.: Добросвет, 2006. — 608 c.
ISBN 978-5-98227-708-4
Скачать (прямая ссылка): strukturaiinterpretacii2006.pdf
Предыдущая << 1 .. 15 16 17 18 19 20 < 21 > 22 23 24 25 26 27 .. 269 >> Следующая


Процедура представляет собой шаблон локальной эволюции (local evolution) вычислительного процесса. Она указывает, как следующая стадия процесса строится из предыдущей. Нам хотелось бы уметь строить утверждения об общем, или глобальном (global) поведении процесса, локальная эволюция которого описана процедурой. В общем случае это сделать очень сложно, но по крайней мере мы можем попытаться описать некоторые типичные схемы эволюции процессов.

В этом разделе мы рассмотрим некоторые часто встречающиеся «формы» процессов, генерируемых простыми процедурами. Кроме того, мы рассмотрим, насколько сильно эти процессы расходуют такие важные вычислительные ресурсы, как время и память. Процедуры, которые мы будем рассматривать, весьма просты. Они будут играть такую же роль, как простые схемы в фотографии: это скорее упрощенные прототипические шаблоны, а не практические примеры сами по себе.

1.2.1. Линейные рекурсия и итерация

Для начала рассмотрим функцию факториал, определяемую уравнением

n! = n ¦ (n — 1) ¦ (n — 2) ¦ ¦ ¦ 3 ¦ 2 ¦ 1

Существует множество способов вычислять факториалы. Один из них состоит в том, чтобы заметить, что n! для любого положительного целого числа n равен n, умноженному на (n — 1)!:

n! = n ¦ [(n — 1) ¦ (n — 2) ¦ ¦ ¦ 3 ¦ 2 ¦ 1] = n ¦ (n — 1)!

Таким образом, мы можем вычислить n!, вычислив сначала (n — 1)!, а затем умножив его на n. После того, как мы добавляем условие, что 1! равен 1, это наблюдение можно непосредственно перевести в процедуру:

1.2. Процедуры и порождаемые ими процессы

49

(factorial 6)

(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial
(* 6 (* 5 (* 4 (* 3 (* 2 (facto
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 0 2 1
720

Рис. 1.3. Линейно рекурсивный процесс для вычисления 6!.

(define (factorial n)

(if (= n 1)

1

(* n (factorial (- n 1)))))

Можно использовать подстановочную модель из раздела 1.1.5 и увидеть эту процедуру в действии при вычислении 6!, как показано на рис. 1.3.

Теперь рассмотрим вычисление факториала с другой точки зрения. Мы можем описать правило вычисления n!, сказав, что мы сначала умножаем 1 на 2, затем результат умножаем на 3, затем на 4, и так пока не достигнем n. Мы можем описать это вычисление, сказав, что счетчик и произведение с каждым шагом одновременно изменяются согласно правилу

произведение = счетчик • произведение счетчик = счетчик + 1

и добавив условие, что n! — это значение произведения в тот момент, когда счетчик становится больше, чем n.

Опять же, мы можем перестроить наше определение в процедуру вычисления факто-

29

риала29:

29B настоящей программе мы, скорее всего, спрятали бы определение fact-iter с помощью блочной структуры, введенной в предыдущем разделе:

(define (factorial n)

(define (iter product counter)

(if (> counter n) product

(iter (* counter product)

(+ counter 1))))

(iter 1 1))

Здесь мы этого не сделали, чтобы как можно меньше думать о разных вещах одновременно.

50

Глава 1. Построение абстракций с помощью процедур

(factorial 6)

(fact-iter 116) (fact-iter 12 6) (fact iter 2 3 6) (fact-iter 6 4 6) (fact-iter 24 5 6)

(fact-iter 120 6 6) (fact-iter 720 7 6) f 720

Рис. 1.4. Линейно итеративный процесс для вычисления 6!.

(define (factorial n)

(fact-iter 1 1 n))

(define (fact-iter product counter max-count)

(if (> counter max-count) product

(fact-iter (* counter product)

(+ counter 1) max-count)))

Как и раньше, мы можем с помощью подстановочной модели изобразить процесс вычисления 6!, как показано на рис. 1.4.

Сравним эти два процесса. С одной стороны, они кажутся почти одинаковыми. Оба они вычисляют одну и ту же математическую функцию с одной и той же областью определения, и каждый из них для вычисления n! требует количества шагов, пропорционального n. Действительно, два этих процесса даже производят одну и ту же последовательность умножений и получают одну и ту же последовательность частичных произведений. С другой стороны, когда мы рассмотрим «формы» этих двух процессов, мы увидим, что они ведут себя совершенно по-разному

Возьмем первый процесс. Подстановочная модель показывает сначала серию расширений, а затем сжатие, как показывает стрелка на рис. 1.3. Расширение происходит по мере того, как процесс строит цепочку отложенных операций (deferred operations), в данном случае цепочку умножений. Сжатие происходит тогда, когда выполняются эти отложенные операции. Такой тип процесса, который характеризуется цепочкой отложенных операций, называется рекурсивным процессом (recursive process). Выполнение этого процесса требует, чтобы интерпретатор запоминал, какие операции ему нужно выполнить впоследствии. При вычислении n! длина цепочки отложенных умножений, а следовательно, и объем информации, который требуется, чтобы ее сохранить, растет линейно с ростом n (пропорционален n), как и число шагов. Такой процесс называется линейно рекурсивным процессом (linear recursive process).
Предыдущая << 1 .. 15 16 17 18 19 20 < 21 > 22 23 24 25 26 27 .. 269 >> Следующая