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

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

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

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

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

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

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


(sqrt (+ 100 37) )

11. 704699917758145

(sqrt (+ (sqrt 2) (sqrt 3)))

1. 7739279023207892

(square (sqrt 1000))

1000.000369924366

Программа sqrt показывает также, что того простого процедурного языка, который мы описали до сих пор, достаточно, чтобы написать любую чисто вычислительную программу, которую можно было бы написать, скажем, на Си или Паскале. Это может показаться удивительным, поскольку в наш язык мы не включили никаких итеративных (циклических) конструкций, указывающих компьютеру, что нужно производить некое действие несколько раз. Sqrt-iter, с другой стороны, показывает, как можно выразить итерацию, не имея никакого специального конструкта, кроме обыкновенной способности вызвать процедуру24.

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

Лиза П. Хакер не понимает, почему if должна быть особой формой. «Почему нельзя просто определить ее как обычную процедуру с помощью cond?» — спрашивает она. Лизина подруга Ева Лу Атор утверждает, что, разумеется, можно, и определяет новую версию if:

(define (new-if predicate then-clause else-clause)

(cond (predicate then-clause)

(else else-clause)))

Ева показывает Лизе новую программу:

23Обратите внимание, что мы записываем начальное приближение как 1.0, а не как 1.Во многих реализациях Лиспа здесь не будет никакой разницы. Однако интерпретатор MIT Scheme отличает точные целые числа от десятичных значений, и при делении двух целых получается не десятичная дробь, а рациональное число. Например, поделив 10/6, получим 5/3, а поделив 10.0/6.0, получим 1.6666666666666667. (Мы увидим, как реализовать арифметические операции над рациональными числами, в разделе 2.1.1.) Если в нашей программе квадратного корня мы начнем с начального приближения 1, а x будет точным целым числом, все последующие значения, получаемые при вычислении квадратного корня, будут не десятичными дробями, а рациональными числами. Поскольку при смешанных операциях над десятичными дробями и рациональными числами всегда получаются десятичные дроби, то начав со значения 1.0, все прочие мы получим в виде десятичных дробей.

24Читателям, которых заботят вопросы эффективности, связанные с использованием вызовов процедур для итерации, следует обратить внимание на замечания о «хвостовой рекурсии» в разделе 1.2.1.

1.1. Элементы программирования

43

(new-if (= 2 3) 0 5)

5

(new-if (=11)0 5)

0

Обрадованная Лиза переписывает через new-if программу вычисления квадратного корня:

(define (sqrt-iter guess x)

(new-if (good-enough? guess x) guess

(sqrt-iter (improve guess x) x) ) )

Что получится, когда Лиза попытается использовать эту процедуру для вычисления квадратных корней? Объясните.

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

Проверка good-enough?, которую мы использовали для вычисления квадратных корней, будет довольно неэффективна для поиска квадратных корней от очень маленьких чисел. Кроме того, в настоящих компьютерах арифметические операции почти всегда вычисляются с ограниченной точностью. Поэтому наш тест оказывается неадекватным и для очень больших чисел. Альтернативный подход к реализации good-enough? состоит в том, чтобы следить, как от одной итерации к другой изменяется guess, и остановиться, когда изменение оказывается небольшой долей значения приближения. Разработайте процедуру вычисления квадратного корня, которая использует такой вариант проверки на завершение. Верно ли, что на больших и маленьких числах она работает лучше?

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

Метод Ньютона для кубических корней основан на том, что если у является приближением к кубическому корню из х, то мы можем получить лучшее приближение по формуле

X/у2 +2 у

3

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

1.1.8. Процедуры как абстракции типа «черный ящик»

Sqrt — наш первый пример процесса, определенного множеством зависимых друг от друга процедур. Заметим, что определение sqrt-iter рекурсивно (recursive); это означает, что процедура определяется в терминах самой себя. Идея, что можно определить процедуру саму через себя, возможно, кажется Вам подозрительной; неясно, как такое «циклическое» определение вообще может иметь смысл, не то что описывать хорошо определенный процесс для исполнения компьютером. Более осторожно мы подойдем к этому в разделе 1.2. Рассмотрим, однако, некоторые другие важные детали, которые иллюстрирует пример с sqrt.

44

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

sqrt

sqrt-iter

good-enough improve

square abs average Рис. 1.2. Процедурная декомпозиция программы sqrt.

Заметим, что задача вычисления квадратных корней естественным образом разбивается на подзадачи: как понять, что очередное приближение нас устраивает, как улучшить очередное приближение, и так далее. Каждая из этих задач решается с помощью отдельной процедуры. Вся программа sqrt может рассматриваться как пучок процедур (показанный на рис. 1.1.8), отражающий декомпозицию задачи на подзадачи.
Предыдущая << 1 .. 12 13 14 15 16 17 < 18 > 19 20 21 22 23 24 .. 269 >> Следующая