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

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

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

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

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

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

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


(define (f n) (A 0 n) )
(define (g n) (A 1 n) )
(define (h n) (A 2 n) )
(define (k n) (* 5 n n) )

Дайте краткие математические определения функций, вычисляемых процедурами f, g и h для положительных целых значений n. Например, (kn) вычисляет 5 n2.

главе 3). Вдохновленные этим, Джеральд Джей Сассман и Гай Льюис Стил мл. (см. Steele 1975) построили интерпретатор Scheme с поддержкой хвостовой рекурсии. Позднее Стил показал, что хвостовая рекурсия является следствием естественного способа компиляции вызовов процедур (Steele 1977). Стандарт Scheme IEEE требует, чтобы все реализации Scheme поддерживали хвостовую рекурсию.

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

53

1.2.2. Древовидная рекурсия

Существует еще одна часто встречающаяся схема вычислений, называемая древовидная рекурсия (tree recursion). В качестве примера рассмотрим вычисление последовательности чисел Фибоначчи, в которой каждое число является суммой двух предыдущих:

Можно немедленно преобразовать это определение в процедуру:

(define (fib n)

(cond ((= n 0) 0)

((= n 1) 1)

(else (+ (fib (- n 1))

(fib (- n 2))))))

Рассмотрим схему этого вычисления. Чтобы вычислить (fib 5) , мы сначала вычисляем (fib 4) и (fib 3). Чтобы вычислить (fib 4), мы вычисляем (fib 3) и (fib 2). В общем, получающийся процесс похож на дерево, как показано на рис. 1.5. Заметьте, что на каждом уровне (кроме дна) ветви разделяются надвое; это отражает тот факт, что процедура fib при каждом вызове обращается к самой себе дважды.

Эта процедура полезна как пример прототипической древовидной рекурсии, но как метод получения чисел Фибоначчи она ужасна, поскольку производит массу излишних вычислений. Обратите внимание на рис. 1.5: все вычисление (fib 3) — почти половина общей работы, — повторяется дважды. В сущности, нетрудно показать, что общее число раз, которые эта процедура вызовет (fib 1) или (fib 0) (в общем, число листьев) в точности равняется Fib(n+1). Чтобы понять, насколько это плохо, отметим, что значение Fibfn) растет экспоненциально при увеличении п. Более точно (см. упражнение 1.13), Fibfn) — это целое число, ближайшее к фп j\J5, где

Таким образом, число шагов нашего процесса растет экспоненциально при увеличении аргумента. С другой стороны, требования к памяти растут при увеличении аргумента всего лишь линейно, поскольку в каждой точке вычисления нам требуется запоминать только те вершины, которые находятся выше нас по дереву. В общем случае число шагов, требуемых древовидно-рекурсивным процессом, будет пропорционально числу вершин дерева, а требуемый объем памяти будет пропорционален максимальной глубине дерева.

Для получения чисел Фибоначчи мы можем сформулировать итеративный процесс. Идея состоит в том, чтобы использовать пару целых а и 6, которым в начале даются

0,1,1, 2, 3, 5, 8,13, 21,...

Общее правило для чисел Фибоначчи можно сформулировать так:

ф= (1 + л/5)/2« 1.6180 то есть золотое сечение (golden ratio), которое удовлетворяет уравнению

ф2 = ф +1

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

Рис. 1.5. Древовидно-рекурсивный процесс, порождаемый при вычислении (fib 5).

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

55

значения Fib(1) = 1 и Fib(O) = 0, и на каждом шаге применять одновременную трансформацию

а ^ а + 6

6 ^ а

Нетрудно показать, что после того, как мы проделаем эту трансформацию n раз, а и 6 будут соответственно равны Fib(n + 1) и Fib(n). Таким образом, мы можем итеративно вычислять числа Фибоначчи при помощи процедуры

(define (fib n)

(fib-iter 1 0 n))

(define (fib-iter a b count)

(if (= count 0) b

(fib-iter (+ab) a (- count 1))))

Второй метод вычисления чисел Фибоначчи представляет собой линейную итерацию. Разница в числе шагов, требуемых двумя этими методами — один пропорционален n, другой растет так же быстро, как и само Fib(n), — огромна, даже для небольших значений аргумента.

Не нужно из этого делать вывод, что древовидно-рекурсивные процессы бесполезны. Когда мы будем рассматривать процессы, работающие не с числами, а с иерархически структурированными данными, мы увидим, что древовидная рекурсия является естественным и мощным инструментом32. Но даже при работе с числами древовиднорекурсивные процессы могут быть полезны — они помогают нам понимать и проектировать программы. Например, хотя первая процедура fib и намного менее эффективна, чем вторая, зато она проще, поскольку это немногим более, чем перевод определения последовательности чисел Фибоначчи на Лисп. Чтобы сформулировать итеративный алгоритм, нам пришлось заметить, что вычисление можно перестроить в виде итерации с тремя переменными состояния.

Размен денег

Чтобы сочинить итеративный алгоритм для чисел Фибоначчи, нужно совсем немного смекалки. Теперь для контраста рассмотрим следующую задачу: сколькими способами можно разменять сумму в 1 доллар, если имеются монеты по 50, 25, 10, 5 и 1 цент? В более общем случае, можно ли написать процедуру подсчета способов размена для произвольной суммы денег?
Предыдущая << 1 .. 17 18 19 20 21 22 < 23 > 24 25 26 27 28 29 .. 269 >> Следующая