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

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

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

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

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

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

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


В качестве примера рассмотрим задачу вычисления квадратного корня. Мы можем определить функцию «квадратный корень» так:

а/ж = такое у, что у > 0 и у2 = х

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

(define (sqrt x)

(the y (and (>= y 0)

(= (square y) x))))

Это только уход от вопроса.

Противопоставление функций и процедур отражает общее различие между описанием свойств объектов и описанием того, как что-то делать, или, как иногда говорят, различие между декларативным знанием и императивным знанием. В математике нас обычно интересуют декларативные описания (что такое), а в информатике императивные описания (как)20.

Как вычисляются квадратные корни? Наиболее часто применяется Ньютонов метод последовательных приближений, который основан на том, что имея некоторое неточное значение у для квадратного корня из числа х, мы можем с помощью простой манипуляции получить более точное значение (более близкое к настоящему квадратному корню), если возьмем среднее между у и х/у21. Например, мы можем вычислить квадратный

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

21 На самом деле алгоритм нахождения квадратного корня представляет собой частный случай метода Ньютона, который является общим методом нахождения корней уравнений. Собственно алгоритм нахождения квадратного корня был разработан Героном Александрийским в первом веке н.э. Мы увидим, как выразить общий метод Ньютона в виде процедуры на Лиспе, в разделе 1.3.4.

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

41

корень из 2 следующим образом: предположим, что начальное приближение равно 1. Приближение Частное x/y Среднее

1

1.5

1.4167 1.4142

Продолжая этот процесс, мы получаем все более точные приближения к квадратному корню.

Теперь формализуем этот процесс в терминах процедур. Начнем с подкоренного числа и какого-то значения приближения. Если приближение достаточно хорошо подходит для наших целей, то процесс закончен; если нет, мы должны повторить его с улучшенным значением приближения. Запишем эту базовую стратегию в виде процедуры:

(define (sqrt-iter guess x)

(if (good-enough? guess x) guess

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

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

(define (improve guess x)

(average guess (/ x guess)))

где

(define (average x y)

(/ (+ x y) 2))

Нам нужно еще сказать, что такое для нас «достаточно хорошее» приближение. Следующий вариант сойдет для иллюстрации, но на самом деле это не очень хороший тест. (См. упражнение 1.7.) Идея состоит в том, чтобы улучшать приближения до тех пор, пока его квадрат не совпадет с подкоренным числом в пределах заранее заданного допуска (здесь 0.001)22:

(define (good-enough? guess x)

(< (abs (- (square guess) x)) 0.001))

22 Обычно мы будем давать предикатам имена, заканчивающиеся знаком вопроса, чтобы было проще запомнить, что это предикаты. Это не более чем стилистическое соглашение. С точки зрения интерпретатора, вопросительный знак — обыкновенный символ.

- = 2 1

— = 1.3333 1.5

2

1.4167

1.4118

а+1 = 1.5

2

1.3333+ 1.5 2

1.4167+1.4118

2

= 1.4167

1.4142

42

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

Наконец, нужно с чего-то начинать. Например, мы можем для начала предполагать, что квадратный корень любого числа равен 123:

(define (sqrt x)

(sqrt-iter 1.0 x))

Если мы введем эти определения в интерпретатор, мы сможем использовать sqrt как любую другую процедуру:

(sqrt 9)

3.00009155413138
Предыдущая << 1 .. 11 12 13 14 15 16 < 17 > 18 19 20 21 22 23 .. 269 >> Следующая