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

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

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

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

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

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

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


sin X = 3 sin — З

x

3x

4 sm — З

b” = b • b”-1

b0 = 1

60

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

(define (expt b n)

(expt-iter b n 1))

(define (expt-iter b counter product)

(if (= counter 0) product (expt-iter b

(- counter 1)

(* b product))))

Эта версия требует 0(n) шагов и 0(1) памяти.

Можно вычислять степени за меньшее число шагов, если использовать последовательное возведение в квадрат. Например, вместо того, чтобы вычислять b8 в виде

b • (b • (b • (b • (b • (b • (b • b))))))

мы можем вычислить его за три умножения:

b2 = b • b b4 = b2 • b2 b8 = b4 • b4

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

b” = (b”/2)2 если n четно b” = b • b”-1 если n нечетно

Этот метод можно выразить в виде процедуры

(define (fast-expt b n)

(cond ((= n 0) 1)

((even? n) (square (fast-expt b (/ n 2))))

(else (* b (fast-expt b (- n 1))))))

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

(define (even? n)

(= (remainder n 2) 0))

Процесс, вычисляющий fast-expt, растет логарифмически как по используемой памяти, так и по количеству шагов. Чтобы увидеть это, заметим, что вычисление b2” с помощью этого алгоритма требует всего на одно умножение больше, чем вычисление b”. Следовательно, размер степени, которую мы можем вычислять, возрастает примерно вдвое с каждым следующим умножением, которое нам разрешено делать. Таким образом, число умножений, требуемых для вычисления степени n, растет приблизительно так же быстро, как логарифм n по основанию 2. Процесс имеет степень роста 0(log(n))37.

37Точнее, количество требуемых умножений равно логарифму n по основанию 2 минус 1 и плюс количество единиц в двоичном представлении n. Это число всегда меньше, чем удвоенный логарифм n по основанию 2. Произвольные константы k1 и k2 в определении порядка роста означают, что для логарифмического процесса основание, по которому берется логарифм, не имеет значения, так что все такие процессы описываются как ©(log(n)).

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

61

Если n велико, разница между порядком роста 0(log(n)) и 0(n) оказывается очень заметной. Например, fast-expt при n = 1000 требует всего 14 умножений38. С помощью идеи последовательного возведения в квадрат можно построить также итеративный алгоритм, который вычисляет степени за логарифмическое число шагов (см. упражнение 1. 16), хотя, как это часто бывает с итеративными алгоритмами, его нельзя записать

39

так же просто, как рекурсивный алгоритм39.

Упражнение 1.16.

Напишите процедуру, которая развивается в виде итеративного процесса и реализует возведение в степень за логарифмическое число шагов, как fast-expt. (Указание: используя наблюдение, что (bn/2)2 = (b2)n/2, храните, помимо значения степени n и основания b, дополнительную переменную состояния а, и определите переход между состояниями так, чтобы произведение abn от шага к шагу не менялось. Вначале значение а берется равным 1, а ответ получается как значение а в момент окончания процесса. В общем случае метод определения инварианта (invariant quantity), который не изменяется при переходе между шагами, является мощным способом размышления о построении итеративных алгоритмов.)

Упражнение 1.17.

Алгоритмы возведения в степень из этого раздела основаны на повторяющемся умножении. Подобным же образом можно производить умножение с помощью повторяющегося сложения. Следующая процедура умножения (в которой предполагается, что наш язык способен только складывать, но не умножать) аналогична процедуре expt:

(define (* a b)

(if (= b 0)

0

(+ a (* a (- b 1)))))

Этот алгоритм затрачивает количество шагов, линейно пропорциональное b. Предположим теперь, что, наряду со сложением, у нас есть операции double, которая удваивает целое число, и halve, которая делит (четное) число на 2. Используя их, напишите процедуру, аналогичную fast-expt, которая затрачивает логарифмическое число шагов.

Упражнение 1.18.

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

Упражнение 1.19.

Существует хитрый алгоритм получения чисел Фибоначчи за логарифмическое число шагов. Вспомните трансформацию переменных состояния а и b процесса fib-iter из раздела 1.2.2:

38Если Вас интересует, зачем это кому-нибудь может понадобиться возводить числа в 1000-ю степень, смотрите раздел 1.2.6.

39Итеративный алгоритм очень стар. Он встречается в Чанда-сутре Ачарьи Пингалы, написанной до 200 года до н.э. В Knuth 1981, раздел 4.6.3, содержится полное обсуждение и анализ этого и других методов возведения в степень.

40Этот алгоритм, который иногда называют «методом русского крестьянина», очень стар. Примеры его использования найдены в Риндском папирусе, одном из двух самых древних существующих математических документов, который был записан (и при этом скопирован с еще более древнего документа) египетским писцом по имени А’х-мосе около 1700 г. до н.э.
Предыдущая << 1 .. 20 21 22 23 24 25 < 26 > 27 28 29 30 31 32 .. 269 >> Следующая